Algorithm/BOJ

[백준 2250] 트리의 높이와 너비 (C++)

2250번: 트리의 높이와 너비 첫째 줄에 노드의 개수를 나타내는 정수 N(1 ≤ N ≤ 10,000)이 주어진다. 다음 N개의 줄에는 각 줄마다 노드 번호와 해당 노드의 왼쪽 자식 노드와 오른쪽 자식 노드의 번호가 순서대로 주어진다. www.acmicpc.net 이진 트리의 특성을 활용하는 문제 *주의 사항* 1. 트리의 루트 노드의 번호는 1이 아닐 수 있다. 2. 노드의 열의 위치는 이진 트리의 특성을 통해 결정된다. dfs를 통해 트리를 탐색하며 각 노드별 왼쪽 자식 노드 수의 합, 오른쪽 자식 노드 수의 합을 구한다. (1)과정을 통해서 각 노드별 자식 노드의 수를 알 수 있다. 자식 노드의 개수 + 1(현재 노드) 값이 N과 같으면 루트 노드임을 알 수 있다. 각 노드별 좌, 우 노드 수를 구..

[백준 17135] 캐슬 디펜스 (C++)

17135번: 캐슬 디펜스 첫째 줄에 격자판 행의 수 N, 열의 수 M, 궁수의 공격 거리 제한 D가 주어진다. 둘째 줄부터 N개의 줄에는 격자판의 상태가 주어진다. 0은 빈 칸, 1은 적이 있는 칸이다. www.acmicpc.net 오랜만에 풀어본 백준! 백트래킹을 사용한 완전탐색 문제였다. 주의해야할 궁수의 공격 특징은 다음과 같다. 모든 궁수는 동시에 공격하며 같은 대상을 공격할 수 있다. (같은 적이 여러 궁수에게 공격당할 수 있다.) 적과의 거리가 D이하이면 공격한다. 가장 가까운 적을 공격한다. (가장 가까운 적이 어렷일 시 가장 왼쪽의 적을 공격한다.) 1번과 3번 특징 때문에 궁수의 위치에 따라서 잡을 수 있는 적의 수가 달라질 수 있다는 것을 눈치채야 한다. 궁수가 적절히 배치되어 적을 ..

[백준 16637] 괄호 추가하기 (C++)

16637번: 괄호 추가하기 길이가 N인 수식이 있다. 수식은 0보다 크거나 같고, 9보다 작거나 같은 정수와 연산자(+, -, ×)로 이루어져 있다. 연산자 우선순위는 모두 동일하기 때문에, 수식을 계산할 때는 왼쪽에서부터 순 www.acmicpc.net 꿀 조건 1. 괄호 안에는 연산자 하나만 들어갈 수 있다. 꿀 조건 2. 중첩된 괄호는 사용할 수 없고, 항상 올바른 수식만 주어진다. 모든 괄호 안에는 정직하게 정수1, 연산자, 정수2 의 형태로 구성되어있다. 이 점을 활용해서 백트래킹을 사용한 브루트 포스로 현재 연산자를 둘러싸는 괄호를 추가하는 경우, 그냥 넘어가는 경우 모두에 대해서 수식의 값을 확인하면 답을 구할 수 있다. 현재 연산자가 괄호로 둘러싸일 경우, 바로 다음 연산자(현재인덱스+2..

[백준 14867] 물통 (C++)

14867번: 물통 표준 입력으로 물통 A의 용량을 나타내는 정수 a(1 ≤ a B로 물 이동 B->A로 물이동 현재 상태로부터 총 6가지의 상태로 변화할 수 있다. 하지만 bfs의 특성상 다음 상태가 이미 나온적..

[백준 5547] 일루미네이션 (C++)

5547번: 일루미네이션 첫째 줄에 두 개의 정수 W와 H가 주어진다. (1 ≤ W, H ≤ 100) 다음 H줄에는 상근이네 집의 건물 배치가 주어진다. i+1줄에는 W개의 정수가 공백으로 구분되어 있다. j번째 (1 ≤ j ≤ w) 정수의 좌표는 www.acmicpc.net BFS 구현 문제이다 위 그림에서 2,3 좌표는 비어있는데 건물에 둘러싸인 '내부 공간'이다. 건물이 좌표 바깥이나 외부 공간과 맞닿아 있다면 답을 +1 해주면 되는데, 내부 공간이라는 변수 때문에 단순한 bfs로는 풀리지 않는다. 따라서 빈 공간이 내부 공간인지, 외부 공간인지를 미리 판단 해 놓아야 한다. 그걸 어떻게 판단하는가? 하나 이상으로 이어진 외부 공간은 좌표 바깥 부분과 맞닿아있다. 따라서 좌표의 경계선에 위치한 빈 ..

[백준 2836] 수상 택시 (C++)

2836번: 수상 택시 상근이가 살고 있는 도시에는 큰 강이 흐르고 있고, 모든 사람의 집은 이 강 근처에 있다. 집은 0번부터 M번까지 강을 따라서 번호가 매겨져 있고, 인접한 집 사이의 거리는 모두 1 킬로미터이다. www.acmicpc.net 그리디인줄 알고 삽질을 오래 했다. 스위핑 문제였다. 시간이 녹았다 하지만 스위핑을 제대로 되새길 수 있었다! 역방향 이동거리 * 2 == 초록색으로 표시된 거리 * 2 -> 되돌아 가서 승객을 내려주기 + 되돌아 가기 전 위치로 복귀 ANSWER : M + 위 값들의 합 스위핑 문제임을 파악하고 좌표의 left, right 값을 잘 설정해주자. #include #include #include #include #include #define fasti ios_b..

[백준 4095] 최대 정사각형 (C++)

4095번: 최대 정사각형 입력은 여러 테스트 케이스로 이루어져 있다. 각 테스트 케이스의 첫째 줄에는 N과 M이 주어진다. (1 ≤ N,M ≤ 1,000) 다음 N개의 줄에는 공백으로 구분된 M개의 수가 주어진다. 마지막 줄에는 0이 두 www.acmicpc.net 반례: 1 1 0 answer : 0 1 2 0 answer : 0 2 1 1 2 answer : 1 dp[r][c] : r,c를 오른쪽 아래 꼭짓점으로 가지는 정방 행렬의 크기. 현재 위치의 왼쪽, 위, 왼쪽 위 대각선의 dp값 중에서 가장 작은 값을 +1 한게 현재 위치의 dp값이 된다. dp[r][c] = min(dp[r-1][c-1], min(dp[r][c-1], dp[r-1][c])) + 1; ❗️주의사항 : answer를 반드시 ..

[백준 1280] 나무심기 (C++)

1280번: 나무 심기 첫째 줄에 나무의 개수 N (2 ≤ N ≤ 200,000)이 주어진다. 둘째 줄부터 N개의 줄에 1번 나무의 좌표부터 차례대로 주어진다. 각각의 좌표는 200,000보다 작은 자연수 또는 0이다. www.acmicpc.net 세그먼트 트리를 응용하는 문제 tree 배열은 나무를 심을 수 있는 좌표의 구간(0 ~ 200000)을 node번호로 하는 세그먼트 트리이다. 0 ~ 200000 : 1번 노드, 0 ~ 100000 : 2번 노드, 100001 ~ 200000 : 3번노드 ...... 각 구간에 속하는 나무의 개수가 tree[node].first에 저장된다. 각 구간의 나무 위치의 합이 tree[node].second에 저장된다. 이 정보들이 왜 필요한가?? 새로운 나무를 심을..

[백준 3020] 개똥벌레 (C++)

3020번: 개똥벌레 개똥벌레 한 마리가 장애물(석순과 종유석)로 가득찬 동굴에 들어갔다. 동굴의 길이는 N미터이고, 높이는 H미터이다. (N은 짝수) 첫 번째 장애물은 항상 석순이고, 그 다음에는 종유석과 석순이 www.acmicpc.net 풀이를 떠올리기 어려운 문제였다. top 배열과 bottom 배열의 의미 처음 input함수에서 종유석과 석순의 높이를 입력 받으며, 해당 구간에서 길이가 끝나는 종유석, 석순의 개수를 카운팅해준다. 높이가 7일 때, ex) 석순 3이 입력되면 3번 구간의 장애물이 하나 생겼음을 알 수 있다. ex) 종유석 5가 입력되면 3번 구간의 장애물이 하나 생겼음을 알 수 있다. (7 - 5 + 1) 입력이 끝나면 모든 구간에 있는 장애물의 개수를 누적합으로 계산해 준다. ..

[백준 1649] 택시 (C++)

1649번: 택시 첫 번째 줄에 교차로의 개수인 N(1 ≤ N ≤ 1,000)과 도로의 개수 M이 주어진다. 그 다음 M개에 줄에는 도로의 정보를 알려주는 시작점과 끝점이 주어진다. 다음 줄에는 시작점 A와 끝점 B, 그리고 방 www.acmicpc.net 조건 N개의 노드가 존재하고 노드들은 서로 단방향으로 연결되어 있다. A라는 노드에서 출발해 다시 A노드로 돌아올 수 없다. U -> V 연결이 있다면 V -> U 연결은 있을 수 없다. A에서 B로 가야 한다. 가는 도중에 C1, C2 ... Cn 노드를 거쳐가야 한다. 이때 중간 노드의 방문 순서는 중요하지 않다. 요구사항 A에서 B로 가기 위한 경로의 수를 출력하라. A에서 B로 가는 모든 경로를 탐색해보는 top-down DP로 풀려다가 도저히..