BOJ 1005 - ACM Craft
문제 정점 n(\(2 \le n \le 1000\)), 간선 k(\(1 \le k \le 100000\))개와 목표 정점 w가 주어진다. 아래 조건을 만족하며 w를 건설하기 위한 최소 시간을 구해야 한다. 각 정점을 건설할 때의 시간은 d[n]로 주어진다. 간선은 s ...
PS
BOJ 1477 - 휴게소 세우기
문제 기존 정점 n(\(0 \le n \le 50\)), 추가하는 정점 m(\(1 \le m \le 100\)), 선분의 길이 l(\(100 \le l \le 1000\))이 주어질 때, 아래 조건에 맞춰 정점 간의 거리의 최댓값의 하한을 구해야 한다. \(n+m \lt l...
구름LEVEL - 금은보화
문제 원소의 크기가 [1, 2000]에 속하는 정수이고, 길이가 \(N(1 \le N \le 250)\)인 수열 A가 주어진다. 위 수열을 두 개의 부분 수열 C, D로 나눌 때, 아래의 조건을 만족하는 C의 원소의 합 - D의 원소의 합의 차이의 최솟값과, 그 경우의 수를 구...
프로그래머스 - 마법의 엘리베이터
문제 현재 층수 \(L(1 \le L \le 100,000,000)\)과 절댓값이 \(10^{c}(c\ge 0, c \in \mathbb{N})\)인 엘리베이터 버튼이 주어질 때, 0층으로 갈 수 있는 경우의 수 중 버튼을 가장 적게 누르는 경우를 찾아야 한다. 음수 층으로는 갈...
엘리스 코드 챌린지 - 수열 복원
문제 양의 정수로 이루어진 수열 \(a_n\)에 대해, \(n(1\le n \le 15)\), 모든 부분 수열의 합인 \(2^n\)개의 정수가 \(s_1, \cdots s_{2^n}\)으로 주어질 때, 원래 수열의 원소를 구해야 한다. 풀이 \(s_i\)에서 0을 제외한 ...
엘리스 코드 챌린지 - 트리 위의 게임
문제 정점이 \(N(1\le N \le 100000)\)개인 트리의 간선 정보 \(N-1\)개가 주어진다. 루트 노드는 1번이다. 이때 각 정점에서 시작했을 때 아래 조건에 맞춰 게임을 진행한 후, 결과를 출력해야 한다. 선공, 후공 모두 자신의 차례에 아래 동작을 수행한...
BOJ 16236 - 아기 상어
문제 공간 \(N \times N(2\le N \le 20)\)의 정보가 주어질 때 아래 조건에 맞춰 아기 상어가 도움을 요청하지 않고 물고기를 잡아먹을 수 있는 최대 시간을 구해야 한다. 공간의 정보 0 : 빈 칸 [1, 6] : 물고기 크...
BOJ 1918 - 후위 표기식
문제 아래와 같은 조건을 만족하는 중위 표기식이 주어질 때 후위 표기식으로 변환하는 문제이다. 알파벳 대문자로 이루어진 피연산자는 한 번씩만 등장 -가 가장 앞에 오거나 AB와 같이 *가 생략되는 수식은 주어지지 않음 표기식은 알파벳 대문자, +, -, *, /, (...
BOJ 1865 - 웜홀
문제 \(N\)개의 정점에 대한 \(M\)개의 가중치가 양수인 양방향 간선과, \(W\)개의 가중치가 음수인 단방향 간선이 주어진다. 이때 음수 사이클이 존재하는지 판별하는 문제이다. \(1\le N \le 500,\; 1\le M \le 2500,\; 1\le W \le 20...
BOJ 1238 - 파티
문제 \(N\)개의 정점에 대한 \(M\)개의 단방향 간선이 주어진다. 이때 모든 정점에 대해서, 한 정점 \(X\)로 향하는 최단 경로, \(X\)에서부터 도착하는 최단 경로의 합의 최댓값을 구하는 문제이다. \(1\le N \le 1000,\; 1\le M \le 10000...
C++에서 permutation 구하기
Implementation, Simulation 문제를 풀 때는 순열을 사용해야 하는 경우가 종종 있다. <algorithm> 헤더에 있는 next_permutation()을 사용해서 아래와 같이 편리하게 구할 수 있다. 1 2 3 4 5 6 7 8 9 10 11 12...
BOJ 9663 - N-Queen
문제 \(N \times N\) 크기의 타일에 \(N\)개의 퀸을 서로 공격하지 않게 배치할 수 있는 경우의 수를 구하는 문제이다. \(1 \le N \le 15\)이다. 풀이 서로 공격하지 않으려면 각 행/열에 정확히 하나의 퀸만 존재해야 한다. 각 열마다 퀸의 존재유무를...
BOJ 2038 - 골롱 수열
문제 Golomb 수열의 임의의 항을 구하는 문제이다. Golomb 수열은 임의의 \(k\)에 대해 \(k\)가 수열상에서 \(f(k)\)번 등장하는 단조증가 수열이다. \(1\le n \le 2,000,000,000\)일 때 \(f(n)\)을 구해야 한다. 풀이 수열의 정...
BOJ 1720 - 타일 코드
문제 2 X N 사각형을 2 X 1, 2 X 2 타일으로 채우는 경우의 수를 구해야 한다. 이때 좌우 대칭인 두 가지 결과가 존재할 경우 둘을 하나로 처리한다. 풀이 전체 타일의 경우의 수에 대한 점화식은 아래와 같다. dp(n)=2*dp(n-2)+dp(n-1) 이때 팰린드...
BOJ 1341 - 사이좋은 형제
문제 \(0\le{a}\le{b}\le{2^{63}-1}\), \(\text{gcd}(a, b)=1\)인 정수 a, b가 주어진다. 점화식이 \(a_n=\frac{1}{2}\cdot{(\frac{1}{2})}^{n-1}\) 인 무한 등비 수열에 대해 특정한 패턴에 따라서 A, B...
BOJ 1101 - 카드 정리 1
문제 N개의 박스에 M개의 색상([1, M])으로 구분되는 카드들을 넣어야 한다. 이때 아래와 같은 조건을 만족해야 한다. 최대 1개의 박스를 조커 박스로 지정할 수 있고, 조커 박스는 색이 다른 카드들을 보관해도 된다. 조커 박스를 제외한 모든 박스는 비어있거나, 같...
BOJ 1513 - 경로 찾기
문제 N x M 크기인 지도에 1부터 C까지 번호가 매겨진 오락실 C개가 존재한다. 직전에 방문한 오락실의 번호가 이번에 방문할 오락실의 번호보다 작은 경우 방문할 수 있다. 이때 (1, 1)에서 출발하여 (N, M)으로 가는 경로들 중 오락실을 [1, C]개 지나는 경로의 개수...
BOJ 20047 - 동전 옮기기
문제 문자열의 길이 n, 문자 o, x로 이루어진 문자열 S, T, 이동시킬 문자의 위치 i, j가 주어진다. 문자열 S에서 i, j 위치에 있는 문자 두 개의 위상을 유지하면서 이동시켜 T로 변환할 수 있는지 판별하는 문제이다. 이때 i, j는 [0, n)의 범위로 주어진다. ...
BOJ 22871 - 징검다리 건너기 (large)
문제 수열 \(A_N=A_1A_2\dots{A_i}\dots{A_N}\)에 대해 항 사이를 이동할 수 있다. 항상 오른쪽으로만 이동 가능하고, \(i\) 번째 항에서 \(j\) 번째 항으로 이동할 때 드는 비용은 \((j-i)\times{(1+|A_i-A_j|)},\quad i&...
BOJ 21606 - 아침 산책
문제 모든 점이 1(실내), 0(실외)로 구분되는 트리가 주어졌을 때, 산책할 수 있는 경로의 개수를 구하는 문제이다. 경로의 조건은 처음과 끝 지점이 1(실내)이어야 하며, 이외의 점들은 모두 0(실외)여야 한다는 것 뿐이다. 따라서 경로 \(P\)를 뒤집은 경로도 $$P$와 ...
BOJ 17270 - 연예인은 힘들어
문제 그래프 상의 두 점 \(v_j, v_s\)가 주어지면, 임의의 점 \(v\)에 대해 두 점과의 최단 경로의 합이 최소가 되는 점들을 찾고, 나머지 쿼리들을 적용시키는 문제이다. 조건 1. 지헌이의 출발 위치와 성하의 출발 위치는 새로운 약속 장소가 될 수 없다. 조건 2....
BOJ 1135 - 뉴스 전하기
문제 임의의 트리가 주어지고 한 노드는 1분에 하나의 자식에게 전화할 수 있을 때, 루트에서 시작해 모든 노드가 전화를 받기까지 몇 분이 걸리는지 계산하는 문제이다. 풀이 한 노드에 대해, 자식 노드 각각을 루트로하는 서브 트리의 소요 시간이 많은 자식부터 전화를 해야 하기 ...
BOJ 1285 - 동전 뒤집기
문제 n x n으로 표현되는 \(N^2\)개의 동전들의 상태가 주어진다. (\(N\le 20\)) 한 행이나 한 열의 동전들을 모두 뒤집는 작업들을 수행해서 나올 수 있는, 뒷면이 위를 향하는 동전이 최소일 때 그 개수를 구하는 문제이다. 풀이 크기 n인 벡터 안에 각각 n비트...
BOJ 15902 - Split and Merge
문제 1x1, 1x2 조각으로 이루어진 1xL 격자에 대해, 초기 상태와 목표 상태가 각 상태를 이루는 조각의 수, 각 조각들의 너비로 주어진다. e.g. 조각의 수가 4이면 1 2 2 1 1x1 두 개를 1x2로 만드는 연산과, 1x2를 1x1 두 개로 나누는 연산만 가능할 때...
BOJ 2612 - 선분 그룹
문제 x1 y1 x2 y2로 표현되는 선분 N 개가 주어진다. 두 선분이 한 점에서라도 만나면 같은 그룹이라 정의할 때, N 개의 선분이 구성하는 그룹의 개수, 그룹들 중 가장 많은 선분이 속한 그룹의 선분 수를 출력해야 한다. 풀이 점 A(x1, y1), B(x2, y2), ...
BOJ 2261 - 가장 가까운 두 점
x, y 좌표의 절댓값이 10000 이하인 점 N개가 주어진다.(여러 점이 같은 좌표를 가질 수도 있다) 이때 가장 가까운 두 점의 거리의 제곱을 출력하면 된다.(이 이후부터 거리의 제곱을 거리라 하겠다.) 문제 풀이 점들의 배열 ps에 대해서 int clo...
BOJ 1697 - 숨바꼭질
0<=N, K<=100000일 때 +1, -1, *2 세 가지 연산을 사용해서 N에서 K로 가는 최소 연산 횟수를 구하는 문제이다. 문제 풀이 +1, -1, *2 세 가지 연산을 할 수 있는데 N에서 시작해서 이 세 연산들을 하면서 Dijkstra...
BOJ 7453 - 합이 0인 네 정수
N(1<=N<=4000)개의 정수로 이루어진 배열 A, B, C, D가 주어질 때 A[a]+B[b]+C[c]+D[d]=0인 (a, b, c, d)의 개수를 구하는 문제이다. 문제 풀이 (a, b, c, d)를 Brute-force로 구하려면 O(4...
BOJ 1261 - 알고스팟
N X M(1<=N,M<=100) 크기의 미로에서 (1, 1)에서 (N, M)으로 갈 때 부숴야 하는 최소한의 벽의 개수를 구하는 문제이다.(1인 칸이 벽으로 채워졌다고 생각하면 된다. 처음 들어갈 때만 벽을 부수는 느낌) 문제 풀이 벽을 가중치라 정하고 ...
BOJ 1208 - 부분수열의 합 2
수열 A[N](1<=N<=40, A[i]는 정수)에 대해 크기가 양수인 부분수열 중에서 그 수열의 원소를 다 더한 값이 S(|S|<=1000000)가 되는 경우의 수를 찾는 문제이다. 문제 풀이 최대 40개의 원소에 대해 brute-forc...
BOJ 2580 - 스도쿠
9X9 크기의 스도쿠를 푸는 문제이다. 문제 풀이 풀어야 하는 곳들을 저장해놓고 그 순서를 따라서 dfs를 돌리면 된다. 소스코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 ...
BOJ 1107 - 리모컨
보고 싶은 채널 N(0<=N<=500000), 0-9 중 고장난 버튼이 주어질 때 리모컨을 몇 번 조작해야 원하는 채널을 틀 수 있는지 구하는 문제이다. 숫자 버튼 이외에 +, -버튼이 있어 숫자 버튼 10개가 고장날 경우도 주어지고, 원래 틀어져 있던 채널은 10...
BOJ 1517 - 버블 소트
길이 N의 수열이 주어지면 버블소트 하는 과정에서 swap이 몇 번 일어나는지 구하는 문제이다. 문제 풀이 Segment tree를 이용한 풀이 수열을 인덱스와 함께 pair로 저장한 후 값을 기준으로 오름차순 정렬한다. 첫 번째 원소부터 순서대로 seg...
BOJ 2447 - 별 찍기 - 10
n이 주어지면 n x n 크기의 문제에서 주어지는 패턴으로 출력하는 문제이다. 문제 풀이 edge case를 1x1로 잡고 정수배열에 먼저 값을 저장해놓은 후 string으로 옮겨서 한 줄씩 출력했었다. ' '과 '*' 중 ' '가 훨씬 적기 때문에 배열을 모두 '*...
BOJ 1780 - 종이의 개수
3^n x 3^n으로 이루어진 행렬이 주어지는데, 이 행렬을 9분할하면서 분할된 조각의 모든 원소같으면 그 조각은 분할을 멈춘다. 분할이 모두 종료된 후 원소의 종류별(-1/0/1) 조각의 개수를 구하는 문제이다. 문제 풀이 Merge sort와 마찬가지로 1x1까...
BOJ 1654 - 랜선 자르기
현재 선의 수 k, 목표로 하는 선의 수 n, 현재 선들의 길이가 주어질 때 선들을 일정 길이로 잘라야 하는데, n보다 크거나 같은 개수를 만들어야 하고, 일정 길이가 최대가 되도록 길이를 정해야 한다.(자르고 남는 나머지 선들은 버린다) 문제 풀이 bin...
DFS의 구현(Recursive/Iterative)
두 구현 방법의 차이 DFS는 자식 노드 중 방문하지 않은 노드가 있으면 현재 노드에서의 탐색을 멈추고 자식 노드로 옮겨가서 DFS를 완료한 후에 다시 돌아오는 구조이다. 이것을 보기 좋게 함수로 구현한 것이 recursive하게 구현하는 방법이고, stack을 이용...
BOJ 11725 - 트리의 부모 찾기
간선 정보와 루트의 번호만 주어질 때 각 노드들의 부모를 출력하는 문제이다. 문제 풀이 루트노드에서부터 자식들을 bfs로 탐색하면서 부모를 찾아내었다. 아래 코드에서 주석들은 풀고나서 다른 사람들의 코드를 보면서 공부한 것으로, 밑에서 설명...
BOJ 9466 - 텀 프로젝트
모든 노드의 out degree가 1인 그래프에서 cycle에 속하지 않은 노드의 개수를 구하는 문제이다. 문제 풀이 component를 생각하여 방문하지 않은 정점마다 dfs를 돌리면서 cycle을 체크하면 된다. cycle체크는 visited벡터를 0/1/-1(...
BOJ 2178 - 미로 탐색
붙어있는 숫자로 입력이 주어진다. 입력을 받고 BFS를 돌리면 된다. 문제 풀이 소스코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 ...
BOJ 1676 - 팩토리얼 0의 개수
N!을 구해서 오른쪽에서부터 consecutive한 0의 개수를 구하는 문제이다. 문제 풀이 0<=N<=500이기 때문에 팩토리얼을 직접 구해서 푸는 것은 overflow가 나기 때문에 \(N\)까지 수를 곱해가면서 0이 나오자마자 없애고 계산을 이어나가거...
다시 풀어볼 문제들(20.08.26)
목록 Codeforces Round #665 Div.2 D Codeforces Round #665 Div.2 E Codeforces Round #665 Div.2 F BOJ 1324 BOJ 15902 BOJ 16140 지금 안풀리는 문제들이다. 2달 후에(20.10.26...
BOJ 1168 - 요세푸스 문제 2
저번 문제에서 n, k의 범위가 10^5로 넓어진 문제이다. (풀고 걱정했던 내용이 바로 나왔다.) 문제 풀이 segment tree의 leaf노드를 n명의 사람이라 하고 제거되지 않으면 1, 제거된 상태를 0이라 정의했다. 이후 저번 문제와 똑같은 방법으로...
BOJ 1158 - 요세푸스 문제
n, k(n, k<=5000)이 주어질 때 (n, k)-Josephus permutation을 구하는 문제이다. 문제 풀이 n이 작아서 vector로 구현만해도 풀린다. 소스코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16...
BOJ 1406 - 에디터
10^5 이하의 길이인 초기 문자열이 주어지고 쿼리의 개수 N(N<=5*10^5)가 주어졌을 때 모든 쿼리를 마친 후 문자열을 출력하는 문제이다. 문제 풀이 처음에 그냥 vector를 이용해 처리하면 될거라 생각했는데 vector의 경우 insert, ...
BOJ 10989 - 수 정렬하기 3
10000 이하의 자연수가 N(N<=10^7)개 주어질 때 3sec, 8MB 안에 정렬한 결과를 출력하는 문제이다. 문제 풀이 시간만 보고 STL sort를 썼다가 메모리초과를 받아서 당황했다. 들어오는 수의 범위를 이용해서 count...
BOJ 10825 - 국영수
<tuple>이 있다는 것을 알게 되었다. pair<int, pair<string, int>>와 같은 선언과 s.first.second.second와 같은 귀찮고 보기 힘든 내용을 싹 정리해준다. 소...
BOJ 10814 - 나이순 정렬
<algorithm> 헤더에 sort()이외에도 stable_sort()가 있다는 것을 알게 되었다. 종종 쓰일 것 같다. 소스코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 ...
test1
This theme supports link posts, made famous by John Gruber. To use, just add link: http://url-you-want-linked to the post’s YAML front matter and you’re done...