본문 바로가기

공부/알고리즘

(39)
[알고리즘 자습]그래프(Graph) - 5. 최소 신장 트리 - 프림(Prim) 알고리즘, 파이썬 전 게시물들에서, 그래프 자료구조 그래프 순회 알고리즘 중 BFS 그래프 순회 알고리즘 중 DFS 위상 정렬 에 대해 알아보았다. 이번 시간에는 최소 신장트리를 만드는 알고리즘인 프림 알고리즘에 대해 알아보자. 신장 트리 신장 트리란, 주어진 그래프의 정점의 집합과 간선의 집합을 원소로 가지는 부분집합, 즉 sub-graph 중에서, 다음 조건을 만족하는 sub-graph(트리)를 말한다. 그래프 내의 모든 정점을 포함한다. 사이클이 존재해선 안된다. (사이클이란, 이동 가능한 경로 중, 출발점과 도착점이 같은 경로를 말한다.) N개의 정점을 가진 신장 트리는 N-1개의 정점을 가진다. 이러한 신장 트리는, 최소의 링크를 사용하는 네트워크를 구축하는데에 쓰인다. 신장 트리는 한 그래프 내에 여러 개가 존..
[알고리즘 자습]그래프(Graph) - 3. 위상 정렬, 파이썬(Python3) 앞선 게시물들에서, 0. 그래프 자료구조 1. BFS, 너비우선 탐색 2. DFS, 깊이우선 탐색 이 3가지에 대한 정의와 활용을 예제를 통해 알아보면서 정리했다. 이 정도 수준의 알고리즘을 알았다면, 우리는 그래프에 관해서는 어느정도 잘 이해하고 있다고 봐도 좋다. 그렇기 때문에, 그래프 알고리즘 중 하나인 위상 정렬에 대해 아주 쉽게 알아볼 수 있다. 알아서 나쁠거 하나도 없고, 위상 정렬을 이용해 문제를 풀면 BFS, DFS보다 쉽게 풀리는 문제도 있다. 따라서, 우리는 충분히 위상 정렬에 대해 알아볼 필요가 있다. 위상 정렬 위상 정렬에 대해 설명하기 전에, 단어를 먼저 이해하고 시작하는 것이 좋을 것 같다. 우리는 살면서 알게 모르게 위상이라는 단어를 많이 써왔다. 누구누구의 사회적 위상이 어떻..
[알고리즘 자습]그래프(Graph) - 2. DFS(깊이 우선 탐색)의 정의와 활용, 예제, 파이썬(Python3) 2020/03/04 - [공부/알고리즘] - [알고리즘 자습]그래프(Graph) - 1. BFS(너비우선탐색)의 정의와 활용, 예제, 파이썬(Python3) [알고리즘 자습]그래프(Graph) - 1. BFS(너비우선탐색)의 정의와 활용, 예제, 파이썬(Python3) 코딩테스트를 준비하는 사람이든 아니든, 프로그래밍에 발을 들여본 적이 있는 사람들은 무조건 들어봤을 것이다. 너비 우선 탐색, BFS이다. 코딩테스트 단골 문제이기도 하고, 백준 및 프로그래머스에서도 굉장히.. sexy-developer.tistory.com 위의 링크를 걸어놓은 이전 게시물에서, 그래프 순회 알고리즘을 배워야 하는 이유, 그리고 최단 경로 등의 문제에 주로 쓰이는 BFS에 대해 알아보고, 예제를 풀어봄으로써 그 원리를 익..
[알고리즘 자습]그래프(Graph) - 1. BFS(너비우선탐색)의 정의와 활용, 예제, 파이썬(Python3) 코딩테스트를 준비하는 사람이든 아니든, 프로그래밍에 발을 들여본 적이 있는 사람들은 무조건 들어봤을 것이다. 너비 우선 탐색, BFS이다. 코딩테스트 단골 문제이기도 하고, 백준 및 프로그래머스에서도 굉장히 많은 문제가 준비되어 있다. 문제가 많다는 것인 즉슨 연습할 기회가 충분히 주어져 있다는 뜻이다. 근데 나는 옛날에 배웠던 BFS가 정확히 기억이 나지를 않아서, 쉬운 문제도 풀지 못했다. 그래서, 한번 정리를 하고자 한다. 혹시, 이 글을 읽는 사람이 BFS가 뭔지는 들어는 봤고, 너비우선 탐색이라 한 노드에 연결되어있는 다른 노드들을 방문한 다음에 이러쿵저러쿵... 이렇게까지 설명은 할 수 있지만, 당장 구현을 못하겠다라는 생각이 든다면 나와 같이 이글을 쭉 읽어보자. 그래프 순회 알고리즘 전 게..
[알고리즘 자습]그래프(Graph) - 0. 자료 구조 컴공 전공이든 복수전공이든 부전공이든 모두들 그래프 자료구조에 대해서 들어봤을 것이다. 그리고 뭘 뜻하는지도 알고 있을 것이다. 나도 그랬다. 나는 내가 그래프 이론을 충분히 이해하고 있고 DFS, BFS, 최단경로 문제등이 나오면 정말 쉽게 풀 수 있을 줄 알았다. 그러나 막상 문제를 마주하고 구현을 해보려니까 뭐 기억도 잘 안나고 어떻게 응용할지도 감이 안오더라. 그래서 공부를 하고, 예제를 풀어본 뒤 정리해서 글을 올린다. 그래프 자료구조 DFS, BFS는 그래프를 순회하는 알고리즘이다. 따라서 그래프 자료구조부터 알 필요가 있다. 그래프란, 수학시간에 봤던 X축있고 Y축있는 그래프도 있지만, 여기서 말하는 그래프는 정점(vertex or node)과 간선(edge or link)로 이루어진 자료구..
[프로그래머스 탐욕법]저울 - Python3 문제 https://programmers.co.kr/learn/courses/30/lessons/42886 코딩테스트 연습 - 저울 | 프로그래머스 하나의 양팔 저울을 이용하여 물건의 무게를 측정하려고 합니다. 이 저울의 양팔의 끝에는 물건이나 추를 올려놓는 접시가 달려 있고, 양팔의 길이는 같습니다. 또한, 저울의 한쪽에는 저울추들만 놓을 수 있고, 다른 쪽에는 무게를 측정하려는 물건만 올려놓을 수 있습니다. 저울추가 담긴 배열 weight가 매개변수로 주어질 때, 이 추들로 측정할 수 없는 양의 정수 무게 중 최솟값을 return 하도록 solution 함수를 작성해주세요. 예를 들어, 무게가 각 programmers.co.kr 하나의 양팔 저울을 이용하여 물건의 무게를 측정하려고 합니다. 이 저울의..
[프로그래머스 연습]124나라의 숫자 - Python3 문제 https://programmers.co.kr/learn/courses/30/lessons/12899 코딩테스트 연습 - 124 나라의 숫자 | 프로그래머스 124 나라가 있습니다. 124 나라에서는 10진법이 아닌 다음과 같은 자신들만의 규칙으로 수를 표현합니다. 124 나라에는 자연수만 존재합니다. 124 나라에는 모든 수를 표현할 때 1, 2, 4만 사용합니다. 예를 들어서 124 나라에서 사용하는 숫자는 다음과 같이 변환됩니다. 10진법 124 나라 10진법 124 나라 1 1 6 14 2 2 7 21 3 4 8 22 4 11 9 24 5 12 10 41 자연수 n이 매개변수로 주어질 때, n을 124 programmers.co.kr 124 나라가 있습니다. 124 나라에서는 10진법이 아닌..
[프로그래머스 연습]2 X N 타일링 - Python3 문제 https://programmers.co.kr/learn/courses/30/lessons/12900 코딩테스트 연습 - 2 x n 타일링 | 프로그래머스 가로 길이가 2이고 세로의 길이가 1인 직사각형모양의 타일이 있습니다. 이 직사각형 타일을 이용하여 세로의 길이가 2이고 가로의 길이가 n인 바닥을 가득 채우려고 합니다. 타일을 채울 때는 다음과 같이 2가지 방법이 있습니다. 타일을 가로로 배치 하는 경우 타일을 세로로 배치 하는 경우 예를들어서 n이 7인 직사각형은 다음과 같이 채울 수 있습니다. 직사각형의 가로의 길이 n이 매개변수로 주어질 때, 이 직사각형을 채우는 방법의 수를 return 하는 s programmers.co.kr 가로 길이가 2이고 세로의 길이가 1인 직사각형모양의 타일이..