기억보다는 기록을 해볼까

문제 https://www.acmicpc.net/problem/1991 1991번: 트리 순회 첫째 줄에는 이진 트리의 노드의 개수 N(1 ≤ N ≤ 26)이 주어진다. 둘째 줄부터 N개의 줄에 걸쳐 각 노드와 그의 왼쪽 자식 노드, 오른쪽 자식 노드가 주어진다. 노드의 이름은 A부터 차례대로 알파 www.acmicpc.net 생각 트리 구조에 대해 공부할 수 있는 기회 전위 순회(preorder traversal), 중위 순회(inorder traversal), 후위 순회(postorder traversal) 전위 순회한 결과 : ABDCEFG // (루트) (왼쪽 자식) (오른쪽 자식) 중위 순회한 결과 : DBAECFG // (왼쪽 자식) (루트) (오른쪽 자식) 후위 순회한 결과 : DBEGFCA..

문제 1932번: 정수 삼각형 첫째 줄에 삼각형의 크기 n(1 ≤ n ≤ 500)이 주어지고, 둘째 줄부터 n+1번째 줄까지 정수 삼각형이 주어진다. www.acmicpc.net 생각 어제 푼 RGB 거리 1149와 비슷하게 이번에는 최대값을 구하는 것이다. 코드 #include using namespace std; const int MAXN = 501; int main() { int n; cin >> n; int map[MAXN][MAXN]; for(int i = 1; i map[i][j]; } } int M = 0; int dp[MAXN][MAXN] ={0, }; for(int i = 1; i

문제 1149번: RGB거리 첫째 줄에 집의 수 N(2 ≤ N ≤ 1,000)이 주어진다. 둘째 줄부터 N개의 줄에는 각 집을 빨강, 초록, 파랑으로 칠하는 비용이 1번 집부터 한 줄에 하나씩 주어진다. 집을 칠하는 비용은 1,000보다 작거나 www.acmicpc.net 생각 DP 이전에 구한 것을 토대로 다음 값을 구한다. 코드 #include #include using namespace std; int arr[1001][3]; int main() { int N; int cost[3]; arr[0][0] = 0; arr[0][1] = 0; arr[0][2] = 0; cin >> N; for(int i = 1; i > cost[0] >> cost[1] >> cost[2]; arr[i][0] = min(..

문제 https://www.acmicpc.net/problem/16236 16236번: 아기 상어 N×N 크기의 공간에 물고기 M마리와 아기 상어 1마리가 있다. 공간은 1×1 크기의 정사각형 칸으로 나누어져 있다. 한 칸에는 물고기가 최대 1마리 존재한다. 아기 상어와 물고기는 모두 크기를 가 www.acmicpc.net 생각 문제의 조건이 많아 천천히 읽으며 정리해야 한다. 안 그러면 이상한 풀이로 계속 풀다가 꼬인다. 1주일 정도 고민을 했지만 계속 답이 나올락 말락 안 나왔다. 그래서 다른 사람의 코드를 참고했다. https://yulme.tistory.com/92 이 사람은 우선순위 큐로 우선순위를 연산자로 정했다. 우선순위는 거리 > 가장 위 > 가장 왼쪽 순이다. 이동하는 거리를 저장하는데 ..

문제 https://www.acmicpc.net/problem/11725 11725번: 트리의 부모 찾기 루트 없는 트리가 주어진다. 이때, 트리의 루트를 1이라고 정했을 때, 각 노드의 부모를 구하는 프로그램을 작성하시오. www.acmicpc.net 생각 트리의 루트와 노드의 기본에 대해 이해하기 좋은 문제이다. 코드 #include #include #include using namespace std; int main() { int n; cin >> n; vector v[100001]; bool vst[100001]; int arr[100001]; for(int i = 0; i > a >> b; v[a].push_back(b); v[b].push..

문제 11053번: 가장 긴 증가하는 부분 수열 수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이 www.acmicpc.net 생각 코드 #include #include using namespace std; int main() { int n; int dp[1000]; int arr[1000]; int sum = 0; cin >> n; for (int i = 0; i > arr[i]; for (int i = 0; i < n; i++) { //현재 위치 //자기 자신만으로도 1 dp..

문제 1931번: 회의실 배정 (1,4), (5,7), (8,11), (12,14) 를 이용할 수 있다. www.acmicpc.net 생각 처음 봤을 때 어떻게 해야 할지 막막했다. 다른 사람의 코드도 읽어 봤는데 이게 어떻게 잘 굴러가는 건지 잘 모르겠어서 그것을 참고만 하고 나의 새로운 코드를 작성했다. 먼저 배열을 다 받은 다음에 정렬을 시킨다 전의 끝나는 시간보다 현재의 시작하는 시간이 더 작고 현재의 끝나는 시간이 전의 끝나는 시간보다 작거나 같으면 끝나는 시각을 현재의 끝나는 시각으로 최신화해준다. 전의 끝나는 시간보다 현재의 시작하는 시간이 크거나 같으면 회의가 새로 생기는 것이기 때문에 카운트를 하나 늘려준다. 코드 #include #include #include using namespac..

오늘은 당직을 가야 하니 간단한 1 문제만 풀고 가야겠다. 재귀를 통한 순열 구현문제이다 이제부터는 순열 관련 문제들이 꽤 포스팅될 것 같다. #include using namespace std; int n; int arr[9]; bool visited[9]; int m; void dfs(int num, int cnt) { if(cnt == m) { for(int i = 0; i < m; i++) cout m; dfs(1, 0); }

처음에 브루트포스로 안풀었더니 시간초과가 나와서 검색을 동원해 결국 브루트포스로 풀었다. 아래는 브루트포스로 푼게 아닌 답이다. #include #include using namespace std; int main() { int n; cin >> n; int m; cin >> m; bool arr[10]; for(int i = 0; i > a; arr[a] = true; } if(n == 100) { cout