알고리즘 (160) 썸네일형 리스트형 [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를 해주었다. 그러니까 정답이 나왔다. 크루스칼 알고리즘 (Kruskal's Algorithm) 크루스칼 알고리즘을 공부하기 전에, 스패닝 트리에 대해서 먼저 알아야 한다.span 은 '완전히 덮다' 라는 느낌의 뜻을 가지고 있는 단어이고, 트리는 사이클이 없는 그래프이다.그래서 스패닝 트리는 그래프의 모든 노드를 포함하는 트리이다. 위의 경우에도 스패닝 트리이고, 밑의 경우에도 스패닝 트리이다.하나의 그래프에서 스패닝트리는 여러개 존재할 수 있다.스패닝 트리의 가중치를 합하면 weight를 알 수 있는데, 그래프에서 weight의 값이 최소인 스패닝 트리를최소 스패닝 트리 (Minimum Spanning Tree) 이라고 한다. 위의 그래프에서 표시된 트리가 최소 스패닝 트리이다.크루스칼 알고리즘을 알기 위해서 또 알아야할 개념중에 하나가 Cut Property 라는 것이다.T1과 T2는 서로 다.. 다익스트라 알고리즘 (Dijkstra's Algorithm) 최단경로를 구하는 알고리즘인 다익스트라 알고리즘을 공부하고자 한다.다익스트라 알고리즘은 한 점에서 모든 점까지 최단거리를 구하는 알고리즘인데, 가중치가 양수일 때만 사용하는 알고리즘이다.예시에서는 1에서 7까지 도달하는 최단경로를 구한다고 해보자. 먼저 시작정점 1까지는 최단경로 0으로 왔기 때문에 최단경로 0으로 도착했다고 표시한다.그리고 다음 경로로 2와 6으로 갈 수 있는데, 1에서 6으로 가는 방법은1 --> 6 과 1 --> 2 --> 6 두가지가 있다. 1에서 2로 가는 방법은 1 --> 6 --> 2 와 1 --> 2 가 있다. 1 --> 2 --> 6 과 1 --> 6 --> 2 를 구하려면2 --> 6 과 6 --> 2 를 알아야 하는데, 아직 1 --> 6 로 갈지 1 --> 2 로 갈.. 이전 1 ··· 14 15 16 17 18 19 20 다음
