문제 https://www.acmicpc.net/problem/2263 2263번: 트리의 순회 첫째 줄에 n(1≤n≤100,000)이 주어진다. 다음 줄에는 인오더를 나타내는 n개의 자연수가 주어지고, 그 다음 줄에는 같은 식으로 포스트오더가 주어진다. www.acmicpc.net 풀이 solved.ac 난이도: Gold 3 이진트리의 순회 순서를 공부하기 좋은 문제이다. 이진트리의 순회 순서에는 3가지가 존재한다. 3가지 순회의 이름은 루트 노드를 언제 방문하는지에 따라 지어졌다. 모든 순회는 항상 오른쪽 노드보다 왼쪽 노드를 먼저 방문한다. 1. 전위 순회(preorder traverse): 루트 -> 왼쪽 -> 오른쪽 2. 중위 순회(inorder traverse): 왼쪽 -> 루트 -> 오른쪽 ..

문제 https://algospot.com/judge/problem/read/FORTRESS algospot.com :: FORTRESS 요새 문제 정보 문제 중세의 성과 요새들은 보안을 튼튼히 하면서도 더 넓은 영역을 보호하기 위해 여러 개의 성벽을 갖고 있었다고 하지요. 전세계에서 가장 편집증이 심한 영주가 지은 스트로 algospot.com 풀이 종만북 난이도: 중 기하적인 문제 같아서 어려워 보이지만 성벽들은 서로 겹치거나 닿지 않기 때문에 모든 성벽들은 서로의 포함관계로 즉, 계층구조인 트리로 나타낼 수 있다. 성벽을 트리로 나타내면 문제의 답은 간단히 보인다. 바로 서로 가장 먼 두 노드 사이의 간선 수(경로)가 두 지점을 이동하기 위해 가장 많이 넘어야하는 성벽 수이다. 성벽을 가장 많이 넘..

문제 https://www.acmicpc.net/problem/3015 3015번: 오아시스 재결합 첫째 줄에 줄에서 기다리고 있는 사람의 수 N이 주어진다. (1 ≤ N ≤ 500,000) 둘째 줄부터 N개의 줄에는 각 사람의 키가 나노미터 단위로 주어진다. 모든 사람의 키는 231 나노미터 보다 작다. 사람 www.acmicpc.net 풀이 solved.ac 난이도: Gold 1 스택을 활용해서 푸는 문제. 해당 문제가 까다로운 이유는 아래와 같다. 문제에서는 A와 B의 사이에 키가 큰 사람이 없다면 서로 볼 수 있다. 즉, 사이에 키가 같은 사람이 껴있어도 서로를 문제없이 볼 수 있다. 현실적으로 눈의 위치가 얼굴의 중간쯤(?)에 있기 때문에 중간에 키가 비슷한 사람이 있다면 앞의 사람을 볼 수 없..

문제 https://www.acmicpc.net/problem/3190 3190번: 뱀 'Dummy' 라는 도스게임이 있다. 이 게임에는 뱀이 나와서 기어다니는데, 사과를 먹으면 뱀 길이가 늘어난다. 뱀이 이리저리 기어다니다가 벽 또는 자기자신의 몸과 부딪히면 게임이 끝난다. 게임 www.acmicpc.net 풀이 solved.ac 난이도: Gold 5 큐를 이용하면 더 쉽게 구현할 수 있는 문제. 큐에 머리가 이동한 위치를 저장하고, 만약 이동한 곳에 사과가 없다면 큐의 앞에서 pop해준다. (꼬리가 줄어듬) 단, 머리가 움직인 곳에 꼬리가 있더라도 결국 꼬리는 다음 칸으로 이동해야하므로 게임 오버가 아님을 주의하자. 뱀의 이동방향의 경우 아래와 같이 mod연산으로 구현하였다. (오른쪽(0) 부터 시계..

문제 https://www.acmicpc.net/problem/17298 17298번: 오큰수 첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000,000)이 주어진다. 둘째에 수열 A의 원소 A1, A2, ..., AN (1 ≤ Ai ≤ 1,000,000)이 주어진다. www.acmicpc.net 풀이 solved.ac 난이도: Gold 4 스택 자료구조로 해결 가능한 문제. 수열의 뒤에서부터 차례대로 진행하면 해결할 수 있다. 수열의 크기가 arr_size라 할 때 수열(arr)의 가장 마지막 수는 오큰수를 가질 수 없으므로 nge(arr_size-1)= -1을 저장하고 스택에 해당 수, arr[arr_size-1]를 넣고 시작하자. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15..

문제 https://www.acmicpc.net/problem/2304 2304번: 창고 다각형 첫 줄에는 기둥의 개수를 나타내는 정수 N이 주어진다. N은 1 이상 1,000 이하이다. 그 다음 N 개의 줄에는 각 줄에 각 기둥의 왼쪽 면의 위치를 나타내는 정수 L과 높이를 나타내는 정수 H가 한 개의 www.acmicpc.net 풀이 solved.ac 난이도: Silver 2 굳이 스택으로 풀지 않아도 되지만 스택으로 분류되어 있어 스택으로만 해결하려 하다 보니 코드가 복잡해진 것 같다. 일단 가장 높은 기둥(8번 기둥)의 왼쪽 부분만 생각해보자. 만약 기둥의 높이마다 지붕을 맞춘다면 5번 기둥에서 지붕이 낮아지고 8번 기둥에서 다시 높아진다면 오목한 부분이 생겨 비가 고이게 된다. 따라서 최장 기둥..

문제 https://algospot.com/judge/problem/read/ITES algospot.com :: ITES 외계 신호 분석 문제 정보 문제 수환이는 외계에서 날아오는 전파를 연구하는 범세계 대규모 프로젝트, ITES@home에 참가하고 있습니다. 외계에서 날아오는 전파는 전처리를 거쳐 각 숫자가 [1,10000 algospot.com 풀이 종만북 난이도: 중 큐를 사용하여 해결하는 문제. 신호의 기록은 입력값으로 주어지는 것이 아니라 직접 생성하는 문제이다. 특이 신호의 개수 N은 최대 50,000,000이므로 생성하여 저장하기보단 각 테스트 케이스마다 다시 생성하여 사용하는 것이 메모리를 절약할 수 있다. 우리는 신호의 수열에서 부분 연속 수열의 원소합이 K인 부분 수열의 개수를 찾아야..

문제 https://www.acmicpc.net/problem/10999 10999번: 구간 합 구하기 2 첫째 줄에 수의 개수 N(1 ≤ N ≤ 1,000,000)과 M(1 ≤ M ≤ 10,000), K(1 ≤ K ≤ 10,000) 가 주어진다. M은 수의 변경이 일어나는 횟수이고, K는 구간의 합을 구하는 횟수이다. 그리고 둘째 줄부터 N+1번째 줄 www.acmicpc.net 풀이 solved.ac 난이도: Paltium 4 백준- 수열과 쿼리 21(16975)와 동일한 문제. 수열과 쿼리 문제는 펜윅 트리로 풀었지만 위의 문제와 같이 느리게 갱신되는 세그먼트 트리(lazy propagation)로 해결 가능하다. 프로그래밍 분야에서 lazy라는 의미는 계산이 필요할 때까지 최대한 처리를 늦추는 방..

문제 https://www.acmicpc.net/problem/16975 16975번: 수열과 쿼리 21 길이가 N인 수열 A1, A2, ..., AN이 주어진다. 이때, 다음 쿼리를 수행하는 프로그램을 작성하시오. 1 i j k: Ai, Ai+1, ..., Aj에 k를 더한다. 2 x: Ax 를 출력한다. www.acmicpc.net 풀이 solved.ac 난이도: Platium 4 느리게 갱신되는 세그먼트 트리로 해결할 수 있는 문제이지만 A를 아래와 같이 B에 대하여 나타낸다면 일반적인 세그먼트 트리나 펜윅 트리로도 해결이 가능하다. 동일한 구성의 문제를 느리게 갱신되는 세그먼트 트리로 해결하는 풀이는 아래를 참조하자. 백준 - 구간 합 구하기2(10999) 펜윅 트리 모른다면 대해서는 깔끔하게 설..

*문제들의 난이도 분류는 종만북 혹은 solved.ac 출처임을 밝힙니다.* ★ 문제는 작성자가 다시 풀어보고 싶은 문제 혹은 어려웠던 문제입니다. +가 붙은 문제는 해당 문제에서 중요하게 생각하는 부분입니다. 기본 누적합 문제 백준 - 개똥벌래(3020) - Gold 5 세그먼트 트리 문제 백준 - 구간 합 구하기(11658) + 세그먼트 트리 - Gold 1 백준 - 최솟값과 최댓값(2357) + 세그먼트 트리 - Gold 1 백준 - 구간 곱 구하기(11505) + 세그먼트 트리 - Gold 1 백준 - 공장(7578)★ + 세그먼트 트리, Inversion Counting - Platium 5 알고스팟 - 족보 탐험(FAMILYTREE)★+ LCA + 세그먼트 트리 - 상 느리게 갱신되는 세그먼트..