분류 전체보기 (26) 썸네일형 리스트형 강한 결합 요소(Strongly Connected Component) 위상정렬(Topology Sort) 위상 정렬 위상 정렬은 순서가 정해져있는 작업을 차례로 수행해야 할 때 그 순서를 정해주는 알고리즘이다. 이때, 위상 정렬은 DAG(Directed Acyclic Graph/사이클이 발생하지 않는 방향 그래프)에만 적용 가능하다. DAG에 대한 예를 들어보면 아래 그림과 같다. 위상 정렬을 수행하는 알고리즘에는 스택을 이용한 방식과 큐를 이용한 방식이 있는데, 큐를 이용하는 방법에 대해 알아보자. 1. 진입차수가 0인 정점을 큐에 삽입한다 2. 큐에서 원소를 꺼내 연결된 모든 간선을 제거한다(기존진입차수-1) 3. 간선 제거 후에 진입차수가 0이 된 정점을 큐에 삽입한다 4. 큐가 빌 때까지 2~3을 반복한다 (이때, 모든 원소를 방문하기 전에 큐가 빈다면 사이클이 존재하는 것이고 모든 원소를 방문했다면.. [DP] 다이나믹 프로그래밍 타일링 문제 (11726, 11727, 2133) 11726 위 문제를 그림으로 나타내면 아래와 같다. 이와 같이 2*n의 타일을 2*1과 1*2 타일로 채워넣으면 되는 것이다. 처음 다이나믹 프로그래밍을 배우고 푸는 문제라 직접 경우의 수를 다 따져가며.. ㅎㅎ.. 풀려고 했었다.. (삽질) 이는 너무 복잡하게 생각할 필요없이 아래와 같이 풀면 된다. 말로 설명해보면, 2*n의 타일을 채우는 것은 결국 2*n-1의 타일에 2*1을 하나 붙인 것과 2*n-2 타일에 1*2 타일을 두개 붙인 것과 같기 때문에, 이를 점화식으로 쓰면 D[n] = D[n-1] + D[n-2] 과 같게 된다. 이를 코드로 작성하면 아래와 같다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 #define _CRT_S.. 아자아자 이거는 청포도 어쩌고 티인데 걍 청포도 향 나는 홍차였다 ㅎ.. 써.. 아무튼 화이팅하자! 남과 비교하지말고 천천히 느리더라도 내가 할 수 있는 걸 하자 2022-03-03 개강한지 하루 무의식이 비대면이라고 나를 깨워주려던 어머니에게 거짓말을 해서 지각을 할뻔 했지만.. 다행히 오늘 첫날이고, 9시 반 수업이라 택시를 타니 알맞았다 ^^ 오늘 알바 첫날인데 늦을 거 같아 택시를 탔다 택시기사님 감사합니다 달려주신 덕에 제가 시간 맞춰 왔다고 칭찬 들었습니다 히히 오늘 알바하며 중고등생에게 튜터링?을 해보니 낮에 나에게 코드를 설명하던 박사 선배가 이런 기분이었을까 싶다.. 더 알려주고 싶고 괜히 뿌듯하다 선배 죄송합니다 제가 멍청하여 ㅠ 하지만 그만큼 감사합니다!! 정말로 ㅠㅠ 그리고 안돌아가는 코드 어쩌고는.. 그냥 내가 삽질한 거 였다.. 보고서도 쓰고 해야하니까 밤이라도 새면서 모델 돌려보고 보고서도 쓰고 그래야겠다.. 미리 물어보거나 구글링을 잘 했어야했는데.. 아.. 2022-02-27 먼가 되는게 없는 듯한 교수님이 주신 코드는 실행이 안되고 ㅠ 선배가 준 코드도 실행이 안됨 ㅠ 그래서 2d u-net 도 내가 직접 구현해봐야 할 거 같음 ㅠ 어제도 늦게 잤는데(한 5시?) 오늘도 그러겠다 ㅠ 밤샐수도 있을듯한.. 내일 미팅이니까 오늘 좀 더 힘내봐야겠다.. U-net 건드리면서 보고서도 써야겠다.. ㅠ 플로이드 와샬(Floyd Warshall) 알고리즘 플로이드 와샬 플로이드 와샬 알고리즘은 모든 정점에서 모든 정점으로의 최단 경로를 구할 때 사용하는 알고리즘이다. 플로이드 와샬은 가장 적은 비용을 하나씩 선택하는 다익스트라 알고리즘과 달리 거쳐가는 정점을 기준으로 알고리즘을 수행한다. 또한, 플로이드 와샬 알고리즘은 기본적으로 다이나믹 프로그래밍 기술에 의거하는데, 그 이유는 그럼 플로이드 와샬 알고리즘에 대해 알아보자. 플로이드 와샬 알고리즘은 표의 형태로 저장한 그래프에 거쳐갈 정점을 정해 바로 가는 비용과 정점을 거쳐서 가는 비용을 비교해 더 적은 비용으로 갱신하는 것을 반복하는 것이다. 이해를 돕기 위해 그림으로 살펴보면 다음과 같다. 이를 구현한 코드는 아래와 같다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 .. 최단경로탐색 - 다익스트라(Dijkstra) 알고리즘 다익스트라 알고리즘 다익스트라 알고리즘은 대표적인 최단 경로 탐색 알고리즘이다. 다익스트라 알고리즘의 작동 방식은 다음과 같다 1. 출발 노드를 설정 2. 출발 노드를 기준으로 각 노드의 최소 비용을 저장 3. 방문하지 않은 노드 중에서 가장 비용이 적은 노드를 선택 4. 해당 노드를 거쳐서 특정한 노드로 가는 경우를 고려해 최소 비용을 갱신 5. 3~4 반복 좀 더 이해를 돕기 위해 그림으로 예를 들어보자. 이를 구현한 코드는 아래와 같다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 #inc.. 이전 1 2 3 4 다음
