알고리즘/문제풀이 (78) 썸네일형 리스트형 [1932] 정수 삼각형 동적 계획법으로 해결하는 문제다. 맨 위층 부터 시작해서 대각선 왼쪽과 오른쪽 둘 중 하나를 선택해서 가장 밑으로 내려가는데가장 밑에까지 갔을 때 최대값을 출력하는 문제이다. 처음에 나는 1차원 배열로 입력받아서 가장 첫번째 수부터 자식 2개중 큰거를 더하면답이 구해질줄 알았는데, 그렇게 풀면 마지막줄에 엄청 큰값이 있을 때 예외가 생기게 된다. 그러므로 트리 형식으로 풀면 안되는 문제였다.그래서 내가 문제를 해결한 방식은 2차원 배열 DP[][]를 정하여제일 위층은 DP[1][1] 이라고 좌표를 설정하고 두번째 줄부터 DP[2][1] DP[2][2], 세번째 줄은 DP[3][1] DP[3][2] DP[3][3] 으로좌표를 설정하여 .. [2156] 포도주 시식 동적 계획법으로 해결하는 문제이다. 이 문제의 중요한 점은 연속으로 놓여 있는 3잔을 모두 마실 수 없다는 것이다.그래서 2잔을 마시고 건너뛰고 마셔야 한다. 위의 예제처럼 입력이 6 10 13 9 8 1 순으로 들어 왔을 때,DP[] 배열을 만들 때 2잔 단위로 마실 수 있기 때문에 DP[1] = 6, DP[2] = 6 + 10 = 16 이 된다.이제 3번째 부터 어떻게 점화식을 세울지 고민해야 하는데, 2잔씩 마시고 건너뛸 수 있기 때문에 3가지를 비교하여 그 중가장 큰 값을 DP[i] 로 정하여야 한다. DP[i]는 i번째 포도주까지 최대로 마실수 있는 포도주의 양으로 정의한다.① 현재 i와 i-1 번째 포도주를 마실 수 있는 .. [2178] 미로 탐색 BFS를 이용해서 최단경로를 구하는 기초 문제라고 할 수 있다.하지만 아직 BFS를 공부하는 나의 입장에서는 어려워서 고민이 많았다. 내가 고민했던 부분은 BFS를 이용해서 모든 경로를 탐색하는 것은 쉽지만 "어떻게 최단 거리를 구하냐 ?" 이다.위의 예제에서 내가 헷갈렸던 부분을 한번 정리 해보자.4 61 0 1 1 1 11 0 1 0 1 01 0 1 0 1 11 1 1 0 1 1내가 고민했던 부분은 위의 예제에서 (0,4)까지는 길이 1개이기 때문에 탐색을 쉽게했지만 어떻게 오른쪽으로 갈지 밑으로 갈지판단하는 것이 고민되었다. 오른쪽으로 갔다가 다시 왼쪽으로 돌아와서 밑으로 가야하나 아니면 애초에 더짧은 밑에 길을선택해서 가게 코드를 짜야하나 고민했다. 하지만 그런 방법은 내 머리에서는 도저히 찾을 .. [1463] 1로 만들기 동적계획법으로 해결한 문제다. 먼저 Table[i] -> i를 1로 만드는데 주어진 3가지 연산을 사용하는 횟수의 최솟값 이라고 정의한다.1부터 차례대로 예를 들어가면서 문제를 파악해보자. Table[1] = 0이다.2 -> 1 이므로 Table[2] = 13 -> 1 이므로 Table[3] = 14 -> 2 -> 1 과 4 -> 3 -> 1 두가지 경우가 있는데, 둘다 2번 연산하므로 Table[4] = 2 이다. 근데 자세히 보면 Table[4] = Table[2] + 1 이나 Table[3] + 1로 표현할 수 있다.5 -> 4 -> 2 -> 1 과 5 -> 4 -> 3 -> 1 두가지 경우가 있는데 3번 연산을 하므로 Table[5] = 3 이다.Table[5] = Table[4] + 1 로 표현.. [4963] 섬의 개수 2667번 단지번호붙이기 와 똑같은 문제이다. 다른점은 섬의 개수는 대각선으로도 탐색을하여 같은섬인지 아닌지 판단하여야 한다.그래서 나는 단지번호붙이기는 temp[][] 배열을 4개로 상하좌우만 탐색했지만,섬의 개수는 대각선까지 탐색해야하므로 8개로 정해서 문제를 해결했다. [2667] 단지번호붙이기 그래프 형태가 아닌 2차원 배열형태의 DFS BFS 문제이다. 나는 DFS로 문제를 해결 했다.먼저 2차원 배열 map[][] 에 예제를 입력받는다. 그리고나서 0,0 부터 차례대로 탐색하면서 1이 나타나면 그자리에서 DFS를 한다.visited[][] 배열을 따로 만들어서, 방문된 자리는 방문했다고 표시해준다. 그러면 차례대로 탐색할 때, 1을 발견하여도 탐색했기 때문에 그냥넘어갈 수 있다. cnt 변수와 count 변수를 추가해서 cnt에는 반복문이 돌면서 1을 만날 때 DFS를 시작하면서 1씩 증가시켜 단지내 집수를 출력하고,count에는 DFS가 한번씩 끝날 때마다 1씩 증가시켜 총 단지수를 출력하는 방법으로 문제를 풀었다.DFS할 때 중요한 점은 2차원 배열을 DFS하기 때문에 상하좌우로 탐색해.. [11724] 연결 요소의 개수 이 문제는 Connected Component의 개수를 구하는 문제이다. Connected Component는 그래프에서 연결된 정점의 그룹이라고 할 수 있다. 그래서 그래프가 몇개의 그룹으로 나누어져있는가를 구하면된다.나는 DFS를 써서 1부터 정점의 개수 N까지 반복문을 돌면서 방문했는지 안했는지 체크를 하여 Connected Component의 개수를 구했다. [1260] DFS와 BFS 이론에서 배운 DFS와 BFS을 이용해서 문제를 풀었는데, 자꾸 정답이 틀렸다고 나왔다.문제는 입력이 크기 순서대로 들어오지 않기 때문에, 정점이 여러 개인 경우에는 정점 번호가 작은 것을 먼저 방문한다는 점을 놓쳤다.ArrayList에 입력을 받고, 각 정점과 이어진 점들을 Sort를 해주었다. 그러니까 정답이 나왔다. 이전 1 ··· 5 6 7 8 9 10 다음
