코드코도

Bellman Ford (벨만 포드) 최단 경로 탐색 - 2 오늘은 지난번 다익스트라에 이어 최단 경로를 탐색하는 알고리즘을 정리하려고 한다. 지난번 다익스트라 포스팅에서 다익스트라는 음의 사이클이 있는 그래프에서는 사용이 불가능하다고 하였다. 그 이유는 무엇일까? 우선, 다음과 같은 그래프의 시작 정점이 A라고 했을 때의 최단 경로를 구해보자. [예상 결과] A : 0 B : -4 C : 3 D : -7 E : 1 F : -3 [실제 결과] 시작 정점에서 이상한 값이 출력되는 것을 볼 수 있다. 다른 예시를 보자. [예상 결과] A : 0 B : 2 ( 재방문을 하지 않는다고 가정) C : 5 D : 1 E : 3 [실제 결과] 역시, E 정점에서 이상한 값이 출력되는 것을 볼 수 있다. 이유가 뭘까?..

Dijsktra (다익스트라) 최단 경로 탐색 - 1 정말 오랜만에 포스팅이다. 원래 목표대로 진행했으면 개강을 하기 전에 DP까지 포스팅을 했어야하는데 요새 조금 바빴다...(사실 의욕이 없던걸 수도...) 아무튼 이번 3-1 과목에 알고리즘 응용이라는 과목을 수강하는데 작년에는 딥러닝과 관련하여 수업했다고해서 신청했는데 이번에 교수님이 바뀌면서 정말 알고리즘에 대해 학습하는 수업이 되어버렸다. 살짝 아쉬웠지만 강의계획서를 보니 2-2 알고리즘 수업과 거의 비슷해서? 학기 초에 미리미리 정리해두려고 한다. 서론이 길었다. 다익스트라는 최단 경로를 탐색하는 알고리즘이다. 다음과 같은 그래프의 최단 경로를 탐색해보자. graph 변수에 연결된 정점과 가중치가 저장되어 있다고 본다. graph[1] = [2..

www.acmicpc.net/problem/2565 2565번: 전깃줄 첫째 줄에는 두 전봇대 사이의 전깃줄의 개수가 주어진다. 전깃줄의 개수는 100 이하의 자연수이다. 둘째 줄부터 한 줄에 하나씩 전깃줄이 A전봇대와 연결되는 위치의 번호와 B전봇대와 연결되는 www.acmicpc.net 입력 첫째 줄에는 두 전봇대 사이의 전깃줄의 개수가 주어진다. 전깃줄의 개수는 100 이하의 자연수이다. 둘째 줄부터 한 줄에 하나씩 전깃줄이 A전봇대와 연결되는 위치의 번호와 B전봇대와 연결되는 위치의 번호가 차례로 주어진다. 위치의 번호는 500 이하의 자연수이고, 같은 위치에 두 개 이상의 전깃줄이 연결될 수 없다. 출력 첫째 줄에 남아있는 모든 전깃줄이 서로 교차하지 않게 하기 위해 없애야 하는 전깃줄의 최소 ..

www.acmicpc.net/problem/11054 11054번: 가장 긴 바이토닉 부분 수열 첫째 줄에 수열 A의 크기 N이 주어지고, 둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ N ≤ 1,000, 1 ≤ Ai ≤ 1,000) www.acmicpc.net 입력 첫째 줄에 수열 A의 크기 N이 주어지고, 둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ N ≤ 1,000, 1 ≤ Ai ≤ 1,000) 출력 첫째 줄에 수열 A의 부분 수열 중에서 가장 긴 바이토닉 수열의 길이를 출력한다. 해결 방법 이전 문제인 가장 긴 증가하는 부분 수열의 변형 문제이다. (아직 풀지 않았다면 아래 문제를 먼저 풀어보도록 하자.) www.acmicpc.net/problem/11053 11..

2020년 겨울방학 모각코 결산 - 일정 - 2020.12.23(수) ~ 2021.01.27(수) (총 6주) - 계획 - codekodo.tistory.com/2 2020년 겨울방학 모각코 계획 < 2020년 겨울방학 모각코(모여서 각자 코딩) 계획 > - 목표 - 2020-2학기 수강과목 알고리즘의 복습 및 백준 문제 풀이 - 설명 - 총 6주에 걸친 기간 동안 2020년 2학기에 수강한 알고리즘(이영석 교수 codekodo.tistory.com - 주간 목표 - codekodo.tistory.com/6 [코독하구만 팀] 2020.12.23(수) - 1주차 모임 목표 [코독하구만 팀] 2020.12.23(수) - 1주차 모임 목표 고도현 - DFS와 BFS를 개념과 실습 문제를 복습하고 백준 문제를 ..

[코독하구만 팀] 2020.01.27(수) - 6주차 모임 결과 고도현 - 다이나믹 프로그래밍의 개념과 메모이제이션에 대해 학습하였고 이를 실제 문제에 응용하면서 dp를 이용하면 효율적으로 코드를 짜는 방법에 대해 좀 더 생각할 수 있었다. 신희승 - 그리디 알고리즘 이용하면 dp방식보다 시간적으로 효율적이게 프로그래밍을 할 수 있다는 것을 알 수 있었다. 이동헌 - 이를 바탕으로 재귀적으로 해결해야 하는 문제가 생긴다면 직접 재귀로 푸는 방식을 적용하기 이전에 Dynamic Programming 방식을 적용하여 시간복잡도와 공간복잡도를 최소화하도록 하자. 최현석 - 평소에 자주 사용한 음원사이트의 차트 정보를 직접 뽑아보니 재미있었고, 앞으로도 다양한 웹사이트에서 정보를 뽑아야 할 때 필요한 스킬을 배..

- 목표 - 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..

[코독하구만 팀] 2020.01.27(수) - 6주차 모임 목표 고도현 - 다이나믹 프로그래밍의 개념을 실습 문제를 통해 학습하고, 이를 응용하여 백준 문제에 적용해본다. 신희승 - 5회차에 공부했던 Greedy Algoalgorithm을 이용하여 백준 알고리즘 문제를 풀어보며 개념을 확립시킨다. 이동헌 - DP(Dynamic Programming)을 사용하여 피보나치 수열의 문제를 풀어보고 재귀적으로 값을 구할 때와 비교해본다. 최현석 - 정점이 주어졌을 때 최단 거리를 구하는 알고리즘( 다익스트라 )을 다시 공부해보며 익힌다. 지난 5주 간 독학해온 웹 크롤링법으로 멜론 차트의 음원의 제목, 가수를 출력해본다. 고도현 - codekodo.tistory.com/42 신희승 - ciwekdo.tistor..

- 목표 - 다이나믹 프로그래밍의 개념을 실습 문제를 통해 학습하고, 이를 응용하여 백준 문제에 적용해본다. 1. 피보나치 피보나치 수열의 N번째 항을 출력하시오. [입력 값] 0 [출력 값] 0 [입력 값] 5 [출력 값] 5 [입력 값] 20 [출력 값] 6765 2. 가방 가방에 물건을 넣어 옮기려한다. 배낭에는 넣을 수 있는 물건 크기에 한계가 있으며, 각 물건은 크기와 가치가 부여되어있다. 배낭에 넣을 수 있는 물건들의 최대 가치를 구하시오. [입력 값] 5 # 배낭 크기 4 # 물건 개수 2 3 4 5 # 물건 크기 3 4 5 6 # 물건 가치 [출력 값] 7 3. 제재소 재목을 만드는 제재소에는 재료로 들어온 나무를 정확히 K미터로 자르는 기계가 있다. 재료로 들어온 나무 관리를 위하여, 나..

www.acmicpc.net/problem/11053 11053번: 가장 긴 증가하는 부분 수열 수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이 www.acmicpc.net 입력 첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000)이 주어진다. 둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ Ai ≤ 1,000) 출력 첫째 줄에 수열 A의 가장 긴 증가하는 부분 수열의 길이를 출력한다. 해결 방법 a[i]를 입력된 수열, dp[i]를 i번째까지 가장 긴 증가하는 부분 수열의 길이라고 ..

www.acmicpc.net/problem/2156 2156번: 포도주 시식 효주는 포도주 시식회에 갔다. 그 곳에 갔더니, 테이블 위에 다양한 포도주가 들어있는 포도주 잔이 일렬로 놓여 있었다. 효주는 포도주 시식을 하려고 하는데, 여기에는 다음과 같은 두 가지 규 www.acmicpc.net 입력 첫째 줄에 포도주 잔의 개수 n이 주어진다. (1≤n≤10,000) 둘째 줄부터 n+1번째 줄까지 포도주 잔에 들어있는 포도주의 양이 순서대로 주어진다. 포도주의 양은 1,000 이하의 음이 아닌 정수이다. 출력 첫째 줄에 최대로 마실 수 있는 포도주의 양을 출력한다. 해결 방법 포도주를 마실 수 있는 방법은 어떻게 될까? dp를 n번째 잔까지 마실 때 가장 많은 양의 포도주, grape를 n번째 잔의 포도..

www.acmicpc.net/problem/10844 10844번: 쉬운 계단 수 첫째 줄에 정답을 1,000,000,000으로 나눈 나머지를 출력한다. www.acmicpc.net 입력 첫째 줄에 N이 주어진다. N은 1보다 크거나 같고, 100보다 작거나 같은 자연수이다. 출력 첫째 줄에 정답을 1,000,000,000으로 나눈 나머지를 출력한다. 해결 방법 우선 규칙을 찾을 필요가 있다. 길이가 1인 계단의 수는 몇 개가 있을까? 1 2 3 4 5 6 7 8 9 답은 9개 그럼 길이가 2인 계단의 수는? 10 12 21 23 32 34 43 45 54 56 65 67 76 78 87 89 98 답은 17개 규칙이 보이는가? 보이지 않아도 된다. (본인도 푸는데 오래걸렸으니... 이 문제 많이 어려웠..

[코독하구만 팀] 2020.01.20(수) - 5주차 모임 결과 고도현 - 이번 주차는 어려웠다. 개념적으로 학습이 덜 된 것 같다. 특히 A* 알고리즘에 대한 추가적인 정리가 필요하다. 알고리즘 개념 정리를 하면서 다시 볼 생각이다. 신희승 - 그리디 알고리즘은 동적 계획법과는 다르게 전체에서의 최적이 아니라 각 순간순간에서의 최적해를 이용하여 값을 구한다. 따라서 구한 값이 항상 최적은 아닐수도 있지만 dp보다 빠르게 결과를 만들어 낼 수 있다는 것을 알 수 있었다. 이동헌 - 복잡한 문제를 비교적 간단하고 반복적인 문제로 바꾸어서 효율적으로 문제를 풀수 있었다. 최현석 - Floyd-Warshall은 학기 수업 때 시험 비중이 낮아서 중요하게 보지 않았다. 그래서 이번 모각코에서 복습을 하며 전보다..

- 목표 - codekodo.tistory.com/33 [코독하구만 팀] 2021.01.20(수) - 5주차 개인 목표 - 목표 - 네트워크 유량을 계산하는 포드 풀커슨 알고리즘의 개념을 학습하고, 이를 정리한다. 위상정렬과 A* 알고리즘의 개념도 추가적으로 학습한다. 이후 실습 문제와 백준 문제를 통해 이를 codekodo.tistory.com 1. 위상 정렬 선행 과목이 있는 경우 선행 과목을 출력하고 이후에 연계된 과목을 출력하는 문제였다. 과목명이 처음에 주어지므로 이 과목명을 dict형으로 저장한다. M개의 입력 값에서 선행 과목, 후행 과목이 입력되는데 선행 과목이 있는 경우 이를 count 해준다. count가 0이면 이는 선행 과목이 없는 경우이다. 이후 BFS를 통해 과목 이수 순서를 탐..

DFS(Depth-Find-Search) 깊이 우선 탐색 지난 시간 BFS에 이어 오늘은 DFS에 대해 알아보려고 한다. DFS는 Depth-Find-Search로 깊이 우선 탐색이다. BFS와 다르게 DFS는 깊이를 우선적으로 탐색한다. 즉 최대 깊이까지 재귀적으로 이동한 후 최대 깊이에 도달한 경우 옆으로 이동한다. 또한 BFS에서는 Queue를 사용했다면 DFS에서는 Stack을 사용한다. 이 Stack에 저장된 값이 우리가 원하는 DFS의 탐색 순서이다. 알고리즘 동작 방식 다음과 같다. 1. 특정 정점이 아직 방문하지 않은 정점인 경우 이를 방문처리 해준다. 2. 해당 정점과 연결된 다른 정점에 대해 위 과정을 반복한다. 다음과 같은 그래프가 주어졌을 때 DFS를 적용해보자. ① 시작 정점을 8..