www.acmicpc.net/problem/1991 1991번: 트리 순회 첫째 줄에는 이진 트리의 노드의 개수 N(1≤N≤26)이 주어진다. 둘째 줄부터 N개의 줄에 걸쳐 각 노드와 그의 왼쪽 자식 노드, 오른쪽 자식 노드가 주어진다. 노드의 이름은 A부터 차례대로 영문자 www.acmicpc.net 기초적인 트리 순회 문제. 처음에는 노드로 트리를 구현하여 순회시키려 했지만 생각보다 난이도가 있어서 배열로 구현했다. 이런 식으로 서브 노드가 더 이상 존재하지 않으면 '.'을 넣어 끝임을 표시한다. for (int i = 0; i > a >> b >> c; tree[a - 'A'][0] = b; tree[a - 'A'][1] = c; } [0]은 왼쪽, [1]은 오른쪽으로..

www.acmicpc.net/problem/19699 19699번: 소-난다! 지난 번 헛간 청약의 당첨우(牛)가 발표됐다. 청약에 당첨된 소들은 날아갈 듯이 기뻐하다가 진짜로 하늘을 날았다. 하지만 이후로 소들은 날 수 없었다. 그러던 어느 날, 꿀벌에게 쏘이면 잠깐 � www.acmicpc.net 최근에 추가된 문제 중 하나이다. 처음엔 백트래킹으로 풀었는데 안 풀려서 그냥 next_permutation으로 풀었다. 입력받은 수를 정렬시키고 m번만큼 sum변수에 더해줘서 그 sum이 소수이면 ans에 추가해준다. #include #include #include using namespace std; bool vis[10001]; void era() { fill(vis, vis + 10001, true)..

www.acmicpc.net/problem/2146 2146번: 다리 만들기 여러 섬으로 이루어진 나라가 있다. 이 나라의 대통령은 섬을 잇는 다리를 만들겠다는 공약으로 인기몰이를 해 당선될 수 있었다. 하지만 막상 대통령에 취임하자, 다리를 놓는다는 것이 아깝다 www.acmicpc.net 처음엔 완전 탐색으로 다리를 전부 놓으면서 최적의 수를 찾는 줄 알았다. 알고리즘 분류를 보니 BFS, DFS여서 어떻게 해야 할지 감이 잘 안 잡혔다. 1. 1차 BFS를 통해 대륙의 번호를 지정해준다. 2. 큐에 땅의 위치를 전부 삽입해준다 3. BFS를 한번 더 돌려서 이동 범위가 바다라면 큐에 삽입해준다 4. 이동 범위가 땅인데 대륙 번호가 같지 않다면 거기까지의 거리를 리턴해준다. #include #incl..

www.acmicpc.net/problem/9466 9466번: 텀 프로젝트 이번 가을학기에 '문제 해결' 강의를 신청한 학생들은 텀 프로젝트를 수행해야 한다. 프로젝트 팀원 수에는 제한이 없다. 심지어 모든 학생들이 동일한 팀의 팀원인 경우와 같이 한 팀만 있을 www.acmicpc.net 기본적인 정해는 사이클을 찾아서 각 사이클이 돈다면 그룹으로 나눠주고, 돌지 않는다면 카운팅 해주는 식이다. 그러나 낮은 정답률에서 보면 알 수 있듯 생각 없이 대충 풀다 보면 O(N^2) 풀이로는 시간 초과가 나게 된다. 1, 2, 3, 4, 5, , , , , , , 99999, 100000 이런식으로 나온다면 1부터 10만까지 2부터 10만까지,, 쭉 돌다 보면 TLE이다. 나 또한 시간초과에서 벗어날 수 없어..

www.acmicpc.net/problem/4963 4963번: 섬의 개수 입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스의 첫째 줄에는 지도의 너비 w와 높이 h가 주어진다. w와 h는 50보다 작거나 같은 양의 정수이다. 둘째 줄부터 h개 줄에는 지도� www.acmicpc.net BFS와 DFS를 연습하기에 좋은 간단한 문제였다. 주의해야 할 점이 있다면 상하좌우뿐만 아니라 대각선에도 땅이 있다면 섬으로 연결시켜줘야 한다. #include #include using namespace std; int ar[51][51]; bool vis[51][51]; int dx[8] = { 0,0,1,-1,-1,1,-1,1 }; int dy[8] = { 1,-1,0,0,-1,-1,1,1 }; ..

www.acmicpc.net/problem/2331 2331번: 반복수열 첫째 줄에 반복되는 부분을 제외했을 때, 수열에 남게 되는 수들의 개수를 출력한다. www.acmicpc.net 배열하나 잡고 dfs돌리면서 방문처리 해주면 되는 쉬운 문제인줄 알았으나 5연속 연타임 에러를 맞고 다시 꼼꼼히 살펴봤다. 일단 배열의 크기는 아무리 커도 9^5 * 5 이니 30만을 넘지 않는다. #include #include using namespace std; int vis[300000]; int a, p, ans; int cal(int n) { int ret = 0; while (n > 0) { ret += (int)pow(n % 10, p); n /= 10; } return ret; } void dfs(int ..