- 목표 - codekodo.tistory.com/42 [코독하구만 팀] 2021.01.27(수) - 6주차 개인 목표 - 목표 - 다이나믹 프로그래밍의 개념을 실습 문제를 통해 학습하고, 이를 응용하여 백준 문제에 적용해본다. 1. 피보나치 피보나치 수열의 N번째 항을 출력하시오. [입력 값] 0 [출력 값] 0 [입력 codekodo.tistory.com 1. 피보나치 재귀로 풀어도 되지만 dp를 활용하면 더욱 빠르게 정답에 접근이 가능하다. 2. 가방 점화식을 유도해야한다. 행은 가방의 최대 무게이고, 열은 주어진 물건의 무게이다. 이를 이용하여 최대한의 값어치를 구하고 표를 채우면 다음과 같이 채울 수 있다. 0 1 2 3 4 5 0 0 0 0 0 0 0 2 0 0 3 3 3 3 3 0 0 3 4..
- 목표 - 다이나믹 프로그래밍의 개념을 실습 문제를 통해 학습하고, 이를 응용하여 백준 문제에 적용해본다. 1. 피보나치 피보나치 수열의 N번째 항을 출력하시오. [입력 값] 0 [출력 값] 0 [입력 값] 5 [출력 값] 5 [입력 값] 20 [출력 값] 6765 2. 가방 가방에 물건을 넣어 옮기려한다. 배낭에는 넣을 수 있는 물건 크기에 한계가 있으며, 각 물건은 크기와 가치가 부여되어있다. 배낭에 넣을 수 있는 물건들의 최대 가치를 구하시오. [입력 값] 5 # 배낭 크기 4 # 물건 개수 2 3 4 5 # 물건 크기 3 4 5 6 # 물건 가치 [출력 값] 7 3. 제재소 재목을 만드는 제재소에는 재료로 들어온 나무를 정확히 K미터로 자르는 기계가 있다. 재료로 들어온 나무 관리를 위하여, 나..
- 목표 - codekodo.tistory.com/33 [코독하구만 팀] 2021.01.20(수) - 5주차 개인 목표 - 목표 - 네트워크 유량을 계산하는 포드 풀커슨 알고리즘의 개념을 학습하고, 이를 정리한다. 위상정렬과 A* 알고리즘의 개념도 추가적으로 학습한다. 이후 실습 문제와 백준 문제를 통해 이를 codekodo.tistory.com 1. 위상 정렬 선행 과목이 있는 경우 선행 과목을 출력하고 이후에 연계된 과목을 출력하는 문제였다. 과목명이 처음에 주어지므로 이 과목명을 dict형으로 저장한다. M개의 입력 값에서 선행 과목, 후행 과목이 입력되는데 선행 과목이 있는 경우 이를 count 해준다. count가 0이면 이는 선행 과목이 없는 경우이다. 이후 BFS를 통해 과목 이수 순서를 탐..
- 목표 - 네트워크 유량을 계산하는 포드 풀커슨 알고리즘의 개념을 학습하고, 이를 정리한다. 위상정렬과 A* 알고리즘의 개념도 추가적으로 학습한다. 이후 실습 문제와 백준 문제를 통해 이를 응용한다. 1. 위상 정렬 2. 정글의 법칙 3. 기름이 간당간당 4. 백준 2188번 - 축사배정 백준 2188번 - 축사배정 (www.acmicpc.net/problem/2188) 2188번: 축사 배정 농부 존은 소 축사를 완성하였다. 축사 환경을 쾌적하게 유지하기 위해서, 존은 축사를 M개의 칸으로 구분하고, 한 칸에는 최대 한 마리의 소만 들어가게 계획했다. 첫 주에는 소를 임의 배정해 www.acmicpc.net
- 목표 - codekodo.tistory.com/26 [코독하구만 팀] 2021.01.13(수) - 4주차 개인 목표 목표 : 최단 경로를 탐색하는 알고리즘인 다익스트라 알고리즘의 개념을 정리하고 관련된 실습 문제 3문제를 풀어본다. 이후 백준에서 관련된 문제를 풀어봄으로써 이를 응용하는 법까지 학습 codekodo.tistory.com 다익스트라란? 최단 경로를 탐색하는 알고리즘의 한 종류로 정점들 사이의 가중치를 비교하는 과정을 통해 최단 경로를 탐색한다. 해당 그림에서 정점과 간선의 가중치를 표로 나타내면 다음과 같다. 특정 행에서 특정 열로 이동할 때 발생하는 가중치를 나타낸 표이다. 인접하지 않은 경우 INF, 방향성에 의해 도달할 수 없을 때는 X로 나타내었다. A(여기로) B C D E F..
- 목표 - 최단 경로를 탐색하는 알고리즘인 다익스트라 알고리즘의 개념을 정리하고 관련된 실습 문제 3문제를 풀어본다. 이후 백준에서 관련된 문제를 풀어봄으로써 이를 응용하는 법까지 학습한다. 1. 다익스트라 방향 가중치 그래프의 노드와 엣지가 주어졌을 때 방향 가중치 그래프를 그리고, 질의 노드 사이의 최단 거리 엣지 경로를 출력하시오. [입력 값] 6 7 A B C D E F A B 10 A C 15 B D 12 B F 15 C E 10 D F 1 F E 5 A E [출력 값] A C 15 C E 10 2. 벨만 포드 음의 가중치가 있는 방향 가중치 그래프의 노드와 엣지가 주어졌을 때 방향 가중치 그래프를 그리고, 질의 노드 사이의 최단 거리 엣지 경로를 출력하시오. 만약, 무한 루프가 발생할 경우 ..
- 목표 - codekodo.tistory.com/12 [코독하구만 팀] 2021.01.05(화) - 3주차 개인 목표 목표 : LCA(Lowest Common Ancestor) 알고리즘 개념 및 실습 문제를 복습하고 백준 문제를 통해 실제 문제에 적용해본다. 실습은 총 4문제로 알고리즘 수업 시간이 진행되었던 실습 문제이다. 1. root 찾기 codekodo.tistory.com LCA(Lowest Common Ancestor) 알고리즘 개념 및 실습 문제를 복습하고 백준 문제를 통해 실제 문제에 적용해봄으로써 알고리즘 동작방식에 대해 알게 되었다. 실습에서 배운 방식으로 백준 문제를 접근하였지만 아직 풀지 못하였다. 다른 방식으로 LCA를 접근해보려고 한다. 1. root 찾기 def main():..
목표 : LCA(Lowest Common Ancestor) 알고리즘 개념 및 실습 문제를 복습하고 백준 문제를 통해 실제 문제에 적용해본다. 실습은 총 4문제로 알고리즘 수업 시간이 진행되었던 실습 문제이다. 1. root 찾기 이진 트리의 노드의 개수가 주어지고, 노드의 key와 자식들이 주어졌을 때 해당 트리의 root를 찾으시오. [입력 값] 6 # N D . . # 간선의 정보 N개 E . . F . . C F . B D E A B C [예상 출력] A 2. 트리 순회 이진 트리의 노드의 개수가 주어지고, 노드의 key와 자식들이 주어졌을 때 해당 트리의 Preorder/ Inorder / Postorder 순으로 순회하고 출력하시오. [입력 값] 6 # N D . . # 간선의 정보 N개 E ...
prim와 kruskal를 개념과 실습 문제를 복습하고 백준 문제를 통해 실제 문제에 적용해봄으로써 둘의 차이와 알고리즘 동작방식에 대해 확실하게 아는 계기가 되었다. - 목표 - codekodo.tistory.com/8 [코독하구만 팀] 2020.12.30(수) - 2주차 개인 목표 목표 : prim 알고리즘과 kruskal 알고리즘 개념 및 실습 문제를 복습하고 백준 문제를 통해 실제 문제에 적용해본다. 실습은 총 3문제로 알고리즘 수업 시간이 진행되었던 실습 문제이다. 1. prim 알고 codekodo.tistory.com 1. prim 알고리즘 import heapq def prim(edges, vertices, n): queue = [] heapq.heappush(queue, [0, verti..
목표 : prim 알고리즘과 kruskal 알고리즘 개념 및 실습 문제를 복습하고 백준 문제를 통해 실제 문제에 적용해본다. 실습은 총 3문제로 알고리즘 수업 시간이 진행되었던 실습 문제이다. 1. prim 알고리즘 무방향 가중치 그래프가 주어졌을 때 prim 알고리즘을 이용하여 MST를 구하고 그 에지의 합을 출력. (모든 노드가 연결되지 않아, MST가 없을 경우 0을 출력) 입력 값은 다음과 같이 주어진다. 7 12 # N, M A B C D E F G # 노드의 개수 N 개 A B 7 # 간선의 정보 M 개 C B 8 A D 5 C E 5 D B 9 E B 7 D E 15 E G 9 F G 11 E F 8 F D 6 E D 15 2. kruskal 알고리즘 무방향 가중치 그래프가 주어졌을 때 kr..
