반응형 알고리즘 PS/백준 알고리즘31 [백준] 1182번 - 부분수열의 합 (Java) https://www.acmicpc.net/problem/1182 1182번: 부분수열의 합 첫째 줄에 정수의 개수를 나타내는 N과 정수 S가 주어진다. (1 ≤ N ≤ 20, |S| ≤ 1,000,000) 둘째 줄에 N개의 정수가 빈 칸을 사이에 두고 주어진다. 주어지는 정수의 절댓값은 100,000을 넘지 않는다. www.acmicpc.net 1. 종료조건은 tree level이 N까지 진행될 때이다. 2. 합이 S가 되면 count +1을 한다. - 합이 S가 되더라도 탐색은 계속 진행한다. 3. 모든 탐색이 끝나면 count를 출력한다. 4. 부분집합을 구하는 것이기 때문에 지금 수(A[i])를 더하거나 더하지 않는 수, 2가지 경우의 수로 나뉜다. - 현재 수(A[level])를 더하고 다음 l.. 2022. 12. 11. [백준] 2665번 - 미로만들기 (Java) https://www.acmicpc.net/problem/2665 2665번: 미로만들기 첫 줄에는 한 줄에 들어가는 방의 수 n(1 ≤ n ≤ 50)이 주어지고, 다음 n개의 줄의 각 줄마다 0과 1이 이루어진 길이가 n인 수열이 주어진다. 0은 검은 방, 1은 흰 방을 나타낸다. www.acmicpc.net 검은 방을 변경하는 로직을 어떻게 가져 가야할 지 고민이 되었다. 처음엔 백준 14502 연구소 문제와 비슷한 유형으로 생각하고 아이디어를 생각해보았다. 랜덤하게 검은방 하나씩 변경하고 BFS탐색을 하는 식으로 진행해 봤는데 14502와는 차이점이 그 문제는 문 3개가 되면 탐색을 시작한다는 명확한 재귀탈출 조건이 있었고, 이 문제는 조건 세우기가 애매했다. 검은방의 위치, 갯수... 랜덤하게 진.. 2022. 10. 27. [백준] 2293번 - 동전 1 (Java) https://www.acmicpc.net/problem/2293 2293번: 동전 1 첫째 줄에 n, k가 주어진다. (1 ≤ n ≤ 100, 1 ≤ k ≤ 10,000) 다음 n개의 줄에는 각각의 동전의 가치가 주어진다. 동전의 가치는 100,000보다 작거나 같은 자연수이다. www.acmicpc.net 동전의 종류가 n개 있다. k원이 되도록 하는 경우의 수를 구해야 한다. 동전의 수는 제한이 없다. 시간제한이 0.5초 이므로 이분탐색 혹은 DP일 가능성이 높다. 배열을 사용해서 동전의 가치를 저장한다. dp[i]는 i원까지 동전의 경우의 수이다. 10원을 표현하기 위해 동전 1, 2, 5를 갖고 있을 때 경우의 수는 점화식 dp[n] = dp[n-1] + dp[n-2] + dp[n-5] impo.. 2022. 10. 14. [백준] 14713번 - 앵무새 (Java) N마리의 앵무새가 한 문장씩 이야기 한다. 다른 앵무새가 문장을 이야기 하는 중간에 다른 앵무새가 치고 들어올 수 있다. 예제 문장이 조합이 가능하면 possible, 불가능하면 Impossible을 출력한다. 큐를 배열로 N개만큼 만들어서 앵무새의 문장을 단어로 잘라서 저장한다. 테스트 문장은 배열, 리스트 혹은 큐로 저장하자. 테스트 문장을 루프를 돌리면서 첫 단어를 앵무새 문장의 첫 단어에 있는지 루프를 돌리며 탐색하자. 있으면 그 단어는 삭제하고 다음으로 넘어가자. 없으면 바로 Impossible 출력한다. 테스트 문장 끝까지 무사히 탐색했으면 Possible을 출력한다. 받아적은 문장의 단어의 수와 N개의 앵무새가 말한 단어의 수가 같아야 한다. 받아적은 문장의 단어검색이 끝났는데 앵무새의 단어.. 2022. 10. 12. [백준] 2304번 - 창고 다각형 (Java) https://www.acmicpc.net/problem/2304 2304번: 창고 다각형 첫 줄에는 기둥의 개수를 나타내는 정수 N이 주어진다. N은 1 이상 1,000 이하이다. 그 다음 N 개의 줄에는 각 줄에 각 기둥의 왼쪽 면의 위치를 나타내는 정수 L과 높이를 나타내는 정수 H가 한 개의 www.acmicpc.net 1. N개의 막대기둥이 늘어서있다. 폭은 모두 1m이다. 2. 막대기둥을 다 덮을 지붕을 만들어야 한다. - 지붕은 각 기둥의 윗면과 닿아야 한다. - 지붕은 어떤 기둥의 옆면과 닿아야 한다. 1. class point { int x, int y } 선언한다. 2. 배열로 입력받은 기둥을 삽입한다. 3. stack으로 비교 함수를 만든다. - 첫 기둥을 스택에 넣는다. - stac.. 2022. 10. 11. [백준] 1926번 - 그림 (Java) https://www.acmicpc.net/problem/1926 1926번: 그림 어떤 큰 도화지에 그림이 그려져 있을 때, 그 그림의 개수와, 그 그림 중 넓이가 가장 넓은 것의 넓이를 출력하여라. 단, 그림이라는 것은 1로 연결된 것을 한 그림이라고 정의하자. 가로나 세로 www.acmicpc.net map : 1과 0으로 구성. 그림 : 상하좌우가 1로 연결된 것 그림의 갯수와 가장 큰 그림의 넓이를 출력한다. 그림이 하나도 없는 경우에는 가장 큰 그림의 넓이는 0을 출력한다. 입력정보 세로축 N : 2022. 10. 10. [백준] 14496번 - 그대, 그머가 되어 (Java) https://www.acmicpc.net/problem/14496 14496번: 그대, 그머가 되어 첫째 줄에 머호가 바꾸려 하는 문자 a와 b가 주어진다. 둘째 줄에 전체 문자의 수 N과 치환 가능한 문자쌍의 수 M이 주어진다. (1 ≤ N ≤ 1,000, 1 ≤ M ≤ 10,000) 이후 M개의 줄에 걸쳐 치환 가능한 문 www.acmicpc.net 문자열 a를 b로 바꾸는 최소 치환 횟수를 구하는 문제이다. 문자열 관련 문제처럼 보이나 실상은 문자열 a에서 b로 가는 최단경로를 구하는 문제이다. 우선순위 큐와 다익스트라 알고리즘을 사용해서 풀면된다. 인접리스트 방식 둘로 나눠서 풀어보자. 1. class Node를 구성하자. cost로 오름차순으로 PQ를 구성한다. 2. 방문배열(boolean v.. 2022. 10. 8. [백준] 17179번 - 케이크 자르기 (Java) https://www.acmicpc.net/problem/17179 17179번: 케이크 자르기 첫 번째 줄에 자르는 횟수가 담긴 목록의 길이 N과 자를 수 있는 지점의 개수 M, 그리고 롤 케이크의 길이인 정수 L이 주어진다. (1 ≤ N ≤ M ≤ 1,000, 1 < L ≤ 4,000,000) 다음 M줄에 걸쳐 자를 수 있는 www.acmicpc.net N : 자르는 횟수 ( 2022. 10. 7. [백준] 3055번 - 탈출 (Java) https://www.acmicpc.net/problem/3055 3055번: 탈출 사악한 암흑의 군주 이민혁은 드디어 마법 구슬을 손에 넣었고, 그 능력을 실험해보기 위해 근처의 티떱숲에 홍수를 일으키려고 한다. 이 숲에는 고슴도치가 한 마리 살고 있다. 고슴도치는 제 www.acmicpc.net 지도는 R행 C열로 이루어짐. 비어있는 곳 '.' 물이 차있는 곳 '*' 돌은 'X' 비버의 굴은 'D' 고슴도치의 위치는 'S' 고슴도치는 매분마다 인접한 상/하/좌/우의 칸 하나로 이동할 수 있다. 물도 매분마다 인접한 비어있는 칸으로 확장한다. (이것도 상/하/좌/우?) 물과 고슴도치는 돌을 통과할 수 없다. 고슴도치는 물로 차있는 지역으로 이동할 수 없다. 물도 비버의 굴로 이동할 수 없다. 고슴도치는.. 2022. 10. 5. 이전 1 2 3 4 다음 반응형
