개발자로 살아남기

펠린드롬 문제는 DP 로 풀이할 수 있다. 해결방법은 다음과 같다. https://www.acmicpc.net/problem/10942

이 문제는 DAG 문제의 응용이다. 들어오는 간선의 개수가 0일 때 큐에 추가하여 다음 문제를 해결해 가면 된다. 쉬운 문제를 먼저 풀어야 하기 때문에 우선순위 큐(PriorityQueue)를 이용하여 처리하는 것이 더 좋다. https://www.acmicpc.net/problem/1766/

파일합치기는 다이나믹 프로그래밍을 이용하여 해결할 수 있다. https://www.acmicpc.net/problem/11066

경로 찾기는 배열과 BFS를 이용하여 간단하게 해결 할 수 있다. https://www.acmicpc.net/problem/11403

트리를 순회하는 방법을 전위 순회, 루트 -> 왼쪽 -> 오른쪽중위 순회, 왼쪽 -> 루트 -> 오른쪽후위 순회, 왼쪽 -> 오른쪽 -> 루트 https://www.acmicpc.net/problem/1991

https://www.acmicpc.net/problem/1149 이 문제는 다이나믹 프로그래밍으로 해결할 수 있다. 이웃을 같은 색으로 칠할 수 없으므로집을 이동해 가면서 이전에 칠 할 수 있었던 색 중 최소값을 현재의 색의 비용으로 선택하여 다이나믹 테이블에 저장하면 된다 .

https://www.acmicpc.net/problem/5721 DP를 이용하여 해결이 가능하다. 한행만 선택이 가능하므로 행마다 따로 선택할 수 있는 최대값을 계산하여 그 값을 이용하여 따로 최대값을 계산해 준다. 하나를 선택하면 다음을 걸러서 선택할 수 있으므로 점화식은 다음과 같다. dp[i] = Math.max(dp[i - 2] + dp[i], dp[i - 1])

https://www.acmicpc.net/problem/1504 이 문제는 다익스트라 알고리즘을 이용한다. 두 지점 사이의 경로를 구하기 위해서 다익스트라 알고리즘을 3번 호출하면 된다. * 주어지는 중간 지점이 어느쪽이 더 가까운지 알 수 없기 때문에 2번 호출하여야 한다.

https://www.acmicpc.net/problem/1463 이 문제는 다이나믹 프로그래밍을 이용하여 해결할 수 있다. i번째 값을 만들 수 있는 경우는i-1 번째에서 1을 더하는 경우i%2 == 0인 경우에서 1을 더하는 경우i%3 == 0인 경우에서 1을 더하는 경우이다. 이 세가지 경우를 for 문을 이용하여 반복하여 해결한다.

https://www.acmicpc.net/problem/1275 이 문제는 기본적인 세그먼트 트리문제이다. 구간합을 이용하여 해결하면 된다. 변경되는 값을 잘 기록해 두면 해결 가능한다.

다익스트라 알고리즘은 음수를 갖지 않는 유향 그래프에서 출발점과 도착점 사이의 최단거리를 구하는 알고리즘이다.

플로이드 알고리즘은 그래프의 모든 꼭지점 사이의 최단거리를 구하는 알고리즘이다. - 음수 가중치를 갖는 간선도 순환만 없다면 처리할 수 있다. - 3개의 for문을 이용하여 처리한다. - 바깥 for 문은 중간지점, 가운데 for 문은 시작지점, 안쪽 for 문은 종료지점이다. 플로이드 알고리즘 설명 백준 11404 플로이드 - https://www.acmicpc.net/problem/11404

다이나믹을 이용하여 해결할 수 있다. 자신이 얼리어답터일 때와 아닐때를 구분하여, 관계를 더하여 가면 해결할 수 있다.

히스토그램에서 가장 큰 사각형문제는 세그먼트 트리를 이용하여 해결합니다.

1학년 문제는 DP를 이용해서 해결할 수 있습니다. 20까지의 숫자만 이용할 수 있고,+, - 연산만 할 수 있기 때문에 memo[20][연산횟수]로 메모이제이션을 하면 됩니다.

점프 가능한 곳으로 이동가능 한 최소값을 이용하여 다이나미그 프로그래밍으로 문제를 해결한다. https://www.acmicpc.net/problem/11060

이 문제는 "위상정렬"과 메모이제이션을 이용하여 해결할 수 있다. 인입 간선이 0인 노드를 시작점으로 하여, 건물을 지을 때 걸리는 시간을 메모하여 최종 목적하는 건물을 지을 때 걸리는 시간을 확인하면 된다. https://www.acmicpc.net/problem/1005

유니온 파인드 상호 배타적 집합이라고도 한다. 2가지 연산으로 이루어져 있다. 1. Find: x가 어떤 집합에 포함되어 있는지 찾는 연산2. Union: x와 y가 퐇마되어 있는 집합을 합치는 연산- 구현은 트리를 이용해서 한다. - parent[i] = i 의 parent 가 저장되어 있음 * parent[] 배열을 각자 자기 번호로 초기화 하는 것에 주의** find 연산에서 결과를 가지고 있다가 저장하고 반환하는 것에 주의 *** 이 union, find 연산은 MST의 크루스칼 알고리즘에 사용된다. https://www.acmicpc.net/problem/1717

가수의 순서에 따라 인입간선의 개수를 설정하고, 하나씩 제거하면서 DAG로 문제를 해결한다. https://www.acmicpc.net/problem/2623

이 문제도 DAG 형태로 풀 수 있다. 1. 선행관계 처리를 위해 노드별로 인입되는 간선의 개수를 기록한다. 2. 인입 간선이 0인 노드를 큐에 넣어서, 선행 처리가 끝난 노드에서 방문가능 한 노드 들을 차례로 방문하면서 시간을 더해준다. 3. 최종적으로 시간이 가장 많이 걸리는 작업을 출력한다. https://www.acmicpc.net/problem/2056

다이나믹 프로그래밍을 이용하여 풀이가 가능하다. 현재위치까지 이동가능한 경우의 수(dp[x][y])를 다음 이동가능한 위치(dp[x+move][y], dp[x][y+move])에 더하여 이동가능한 경우를 모두 더하여 준다. 2 3 3 1 1 2 1 3 1 2 3 1 3 1 1 0 1 0 1 0 0 0 0 0 1 1 0 1 1 0 1 3 3 https://www.acmicpc.net/problem/1890

이 문제는 DP로 해결 가능하다. 아래와 같이 해결이 가능하다. https://www.acmicpc.net/problem/11048

LCA 문제는 우선 트리형태를 구성해서BFS를 이용하여 현재 노드의 부모노드, 깊이를 구한다. 그다음 깊이를 동일하게 설정하고, 한단계씩 올라오면서 부모가 같아지면 그때 부모를 출력하면 해결할 수 있다. https://www.acmicpc.net/problem/11437

이 문제는 다익스트라 알고리즘을 이용하여 해결할 수 있다. * 주의 사항은 nXn 배열을 이용하여 간선의 정보를 입력 받는데 동일한 경로로 다른 비용의 데이터가 입력되는 경우에 대한 회피만 잘 해주면 된다. https://www.acmicpc.net/problem/1916

최단경로 문제는 다익스트라 알고리즘을 이용하여 최단경로를 확인한다. 현재 최소값을 가지는 경로를 선택하여 해당 경로 부터의 거리를 확인하면 된다. https://www.acmicpc.net/problem/1753

시작지점 부터의 최단거리 확인을 위한 알고리즘을 사용하여 처리한다. 음수를 입력받을 수 있기 때문에 벨만포드 알고리즘을 이용한다. https://www.acmicpc.net/problem/11657

쉬운 계단수는 앞에서 선택된 숫자 다음에 올 수 있는 숫자는 앞숫자-1, 앞숫자+1 이라는 것을 생각하여 해결 할 수 있다. 자리수가 1일때는 1~9까지 9개가 존재한다. 자리수가 2일때부터 다음숫자에 0이 나올 수가 있다. 앞자리가 0, 9일때는 뒤에 1, 8만 올 수 있으므로 하나만 선택가능하다. 하지만 1~8은 -1 또는 +1 인 숫자가 올 수 있다. 이를 이용하여 다음과 같이 해결하면 된다. memo[length][number] = memo[length-1][number - 1] + memo[length-1][number + 1 이 결과를 MOD 로 나눈 나머지를 저장하면 된다. https://www.acmicpc.net/problem/10844

줄세우기 문제는 DAG로 표현할 수 있다. 메모리 절약을 위해 간선의 연결 상태는 리스트로 표현한다. 노드에 입력이 들어는 것을 따로 배열로 표현하여 더이상 연결이 되지 않는 노드는 제거하면 된다. https://www.acmicpc.net/problem/2252

내리막길은 DFS와 DP를 혼합하여 해결할 수 있는 문제이다. DFS를 이용하여 종점을 찾아서 다시 돌아오면서 DP로 현재 경로에서 종점으로 갈 수 있는 경우를 메모한다. 이미 메모한 곳을 찾으면 해당 값을 반환하면 된다. * -1로 초기화 하여, 방문한 곳을 0으로 표시하면 다시 방문하지 않아도 된다. 최종 위치에서 되돌아 가면서 경로를 표시하고, 새로운 경로로 가면서 최종 위치로 도달할 수 있는 경로를 만나면 그값을 더하여 처리한다. 10 1020 19 18 17 16 15 14 13 12 11 19 18 17 16 15 14 13 12 11 10 18 17 16 15 14 13 12 11 10 9 17 16 15 14 13 12 11 10 9 8 16 15 14 13 12 11 10 9 8 7 15..

N개의 동전의 가치를 합하여, K원을 만드는 경우를 구한다. 1, 2, 5 원의 동전을 이용하여 10원을 만드는 경우는 다음과 같다. 사용동전1 2 5 개수 1 1 1 2 1+1 2 2 3 1+1+1 1+2 2 4 1+1+1+1 1+1+2, 2+2 3 5 1+1+1+1+1 1+1+1+2, 1+2+2 5 4 5원을 만드는 경우는 위와 같다. 1원동전 사용: 1원을 5개 사용2원동전 사용: 3원을 만드는 경우에 2원을 더하여 생성5원동전 사용: 0원을 만드는 경우에 5원을 더하여 생성 https://www.acmicpc.net/problem/2293