1. 문제 2. 풀이 방법문제를 이해하기 위해 예제로 주어진 트리를 그려봤다. 루트가 주어지기에 자연스럽게 계층 구조가 형성된다. 서브트리의 개수는 곧 자기와 자식들의 정점 수를 모두 합친 수였다. 시간복잡도를 따져봤을 때 정점의 개수는 십만이고, 쿼리의 개수도 십만이기에 O(N)이나 O(logN)으로 풀어야할 것 같았다.어떻게하면 한 번의 쿼리 때 logN의 시간복잡도를 가질 수 있을까 고민해보다가 그냥 한 번 전체탐색을 돌려서 모든 정점의 서브트리의 개수를 구한 후 쿼리에 맞춰 답을 출력해주면 될 것 같았다. 서브트리를 구하는 방법은 재귀적으로 자식 노드들을 방문하면서 개수를 구하면 될 것 같아서 바로 코드로 옮겨봤다.우선 트리를 형성하기 위해 ArrayList 배열을 이용하였다. 아래와 같이 주어..
1. 문제https://www.acmicpc.net/problem/15990 2. 접근문제가 너무 DP스러워서 바로 경우의 수들을 차례차례 써봤다. 처음에는 잘 안보였는데 연속해서 사용하면 안된다 조건에 집중해서 계속 생각해봤다. 1이 마지막에 나오면 그 후엔 2와 3만 올 수 있고 그러면 n-2와 n-3에서 정보를 가져와야 할텐데.. 또 마지막에 나오는 수를 저장하기 위해 2차원 배열을 사용해볼까! 하다가 점화식이 떠올랐다 나온 점화식은 아래와 같다dp[i][1] = (dp[i-1][2] + dp[i-1][3]) % MODdp[i][2] = (dp[i-2][1] + dp[i-2][3]) % MODdp[i][3] = (dp[i-3][1] + dp[i-3][2]) % MOD-> result : dp[i][..
1. 문제 2. 접근고려해야 하는 조건은 다음과 같다1번에서 시작해서 N으로 끝내야 한다선택할 수 있는 도시는 최대 M개이다.a도시에서 b도시로 갈 때 경로가 여러개 주어질 수 있다. 최대값만 얻어야 한다 처음 접근은 다익스트라 알고리즘을 사용하는 것이었다. 최대 비용으로 노드를 선택했을 때를 구현하면 될 것 같았다. 하지만 중간에 구현하다가 기내식의 비용이 같을 때는 어떻게 처리하지? 의문이 들었고 그리디적 알고리즘으로 최적의 상황이 해가되는 다익스트라로는 풀 수 없는 것을 깨달았다. 어떻게 풀나 찾아봤더니 DP를 이용하는 문제였다. DP를 2차원 배열 DP[N][M] 선언하고 도시 N을 M번째로 선택했을 떄의 값을 구해준다.점화식은 다음과 같다` DP[b][M] = Math.max(DP[b][M..
1. 문제 2. 접근 입력값이 최대 10만이고 그래이드는 5개이므로 O(5n)으로 풀면 되지 않을까 생각했다. 처음 접근은 이전의 그레이드와 현재 그레이드를 비교해서 연속하면 누적 카운트를 더해주고, 연속이 끊기면 누적 카운트를 맥스값과 비교해서 갱신한 후 누적값을 초기화 시키는 것이었다. 하지만 틀렸다! 더 좋은 방법은 2차원 배열로 student[6][N]를 만들어서 진행하는 것이다. 처음 student 배열을 0으로 모두 초기화한 후, 차례대로 N번 루프를 돈다. 이때 n은 책상의 수로 입력으로 주어지는 n책상에 대한 그레이드 정보를 이용한다. grage1, grade2를 알아낸 후 이전의 값에 1을 더한다. 누적값을 알아야 하므로 이렇게 하면 변수 하나로 누적값을 관리할 수 있다. 그리고 연결이 ..
문제 링크 21278번: 호석이 두 마리 치킨 위의 그림과 같이 1번과 2번 건물에 치킨집을 짓게 되면 1번부터 5번 건물에 대해 치킨집까지의 왕복 시간이 0, 0, 2, 2, 2 로 최소가 된다. 2번과 3번 건물에 지어도 동일한 왕복 시간이 나오지만 더 www.acmicpc.net 분류 브루트포스 알고리즘, 플로이드–워셜, 그래프 이론, 그래프 탐색, 최단 경로 문제 설명 컴공 출신은 치킨집을 하게 되어있다. 현실을 부정하지 말고 받아들이면 마음이 편하다. 결국 호석이도 2050년에는 치킨집을 하고 있다. 치킨집 이름은 "호석이 두마리 치킨"이다. 이번에 키친 도시로 분점을 확보하게 된 호석이 두마리 치킨은 도시 안에 2개의 매장을 지으려고 한다. 도시는 N 개의 건물과 M 개의 도로로 이루어져 있다..
1. 문제 11048번: 이동하기 준규는 N×M 크기의 미로에 갇혀있다. 미로는 1×1크기의 방으로 나누어져 있고, 각 방에는 사탕이 놓여져 있다. 미로의 가장 왼쪽 윗 방은 (1, 1)이고, 가장 오른쪽 아랫 방은 (N, M)이다. 준규는 www.acmicpc.net 문제 설명 준규는 N×M 크기의 미로에 갇혀있다. 미로는 1×1크기의 방으로 나누어져 있고, 각 방에는 사탕이 놓여져 있다. 미로의 가장 왼쪽 윗 방은 (1, 1)이고, 가장 오른쪽 아랫 방은 (N, M)이다. 준규는 현재 (1, 1)에 있고, (N, M)으로 이동하려고 한다. 준규가 (r, c)에 있으면, (r+1, c), (r, c+1), (r+1, c+1)로 이동할 수 있고, 각 방을 방문할 때마다 방에 놓여져있는 사탕을 모두 가져갈..
1. 🐳 문제 [Gold III] 파티 - 1238 1238번: 파티 첫째 줄에 N(1 ≤ N ≤ 1,000), M(1 ≤ M ≤ 10,000), X가 공백으로 구분되어 입력된다. 두 번째 줄부터 M+1번째 줄까지 i번째 도로의 시작점, 끝점, 그리고 이 도로를 지나는데 필요한 소요시간 Ti가 들어 www.acmicpc.net 문제 설명 N개의 숫자로 구분된 각각의 마을에 한 명의 학생이 살고 있다. 어느 날 이 N명의 학생이 X (1 ≤ X ≤ N)번 마을에 모여서 파티를 벌이기로 했다. 이 마을 사이에는 총 M개의 단방향 도로들이 있고 i번째 길을 지나는데 Ti(1 ≤ Ti ≤ 100)의 시간을 소비한다. 각각의 학생들은 파티에 참석하기 위해 걸어가서 다시 그들의 마을로 돌아와야 한다. 하지만 이 학..
[Gold V] 자두나무 - 2240 2240번: 자두나무 자두는 자두를 좋아한다. 그래서 집에 자두나무를 심어두고, 여기서 열리는 자두를 먹고는 한다. 하지만 자두는 키가 작아서 자두를 따먹지는 못하고, 자두가 떨어질 때까지 기다린 다음에 떨어 www.acmicpc.net 문제 설명 자두는 자두를 좋아한다. 그래서 집에 자두나무를 심어두고, 여기서 열리는 자두를 먹고는 한다. 하지만 자두는 키가 작아서 자두를 따먹지는 못하고, 자두가 떨어질 때까지 기다린 다음에 떨어지는 자두를 받아서 먹고는 한다. 자두를 잡을 때에는 자두가 허공에 있을 때 잡아야 하는데, 이는 자두가 말랑말랑하여 바닥에 떨어지면 못 먹을 정도로 뭉개지기 때문이다. 매 초마다, 두 개의 나무 중 하나의 나무에서 열매가 떨어지게 된다. ..
1. 즐겨찾기가 가장 많은 식당 정보 출력하기 문제 `REST_INFO` 테이블에서 음식종류별로 즐겨찾기수가 가장 많은 식당의 음식 종류, ID, 식당 이름, 즐겨찾기수를 조회하는 SQL문을 작성해주세요. 이때 결과는 음식 종류를 기준으로 내림차순 정렬해주세요. SELECT FOOD_TYPE, REST_ID, REST_NAME,FAVORITES FROM REST_INFO WHERE (FOOD_TYPE, FAVORITES) in (SELECT FOOD_TYPE, MAX(FAVORITES) FROM REST_INFO GROUP BY FOOD_TYPE) ORDER BY FOOD_TYPE DESC; 어떻게 그룹별로 가장 큰 값을 뽑아 출력할 수 있을지 꽤 고민했다. 정처기 책도 다시 한 번 보고 상관 없지만 정..
1. 문제 [Gold V] 탑 - 2493 2493번: 탑 첫째 줄에 탑의 수를 나타내는 정수 N이 주어진다. N은 1 이상 500,000 이하이다. 둘째 줄에는 N개의 탑들의 높이가 직선상에 놓인 순서대로 하나의 빈칸을 사이에 두고 주어진다. 탑들의 높이는 1 www.acmicpc.net 성능 요약 메모리: 100220 KB, 시간: 792 ms 분류 자료 구조, 스택 문제 설명 KOI 통신연구소는 레이저를 이용한 새로운 비밀 통신 시스템 개발을 위한 실험을 하고 있다. 실험을 위하여 일직선 위에 N개의 높이가 서로 다른 탑을 수평 직선의 왼쪽부터 오른쪽 방향으로 차례로 세우고, 각 탑의 꼭대기에 레이저 송신기를 설치하였다. 모든 탑의 레이저 송신기는 레이저 신호를 지표면과 평행하게 수평 직선의 왼쪽 ..