본문 바로가기

Programming/BOJ

BOJ 2573 · 빙산 알고리즘 분류 : DFS, BFS1년마다 빙산이 녹는데, 빙산이 두 덩어리 이상으로 나눠지는 최초 연도를 구하는 문제다. 0은 바다고, 1 이상의 숫자는 빙산의 높이다. 빙산은 인접한 바다의 수(상하좌우)만큼 녹는다. 예를 들어 빙산의 위쪽과 왼쪽이 바다라면, 1년에 2만큼 녹는다.입력받을 때 바다를 0대신 -1로 저장하고, 빙산의 위치는 Queue에 집어넣는다.빙산이 녹는 것은 BFS와 비슷한 방법으로, 빙산에 인접한 상하좌우를 ..
BOJ 10974 · 모든 순열 알고리즘 분류 : 브루트 포스C++ STL의 algorithm에 구현되어 있는 next_permutation 함수를 사용하면 된다.next_permutation 구현은 다음 글을 참조.C++ 소스코드#include <cstdio> #include <algorithm> using namespace std; int main() { int n; scanf("%d", &n); int a[n]; for..
BOJ 10973 · 이전 순열 알고리즘 분류 : 브루트 포스C++ STL의 algorithm에 있는 prev_permutation 함수를 사용하면 된다.prev_permutation 구현 방법은 next_permutation과 똑같이 구현할 수 있으며, 순서만 바꾸면 된다.next_permutation 구현 방법은 다음 글을 참조.C++ 소스코드#include <cstdio> #include <algorithm> using namespace std; int..
BOJ 10972 · 다음 순열 알고리즘 분류 : 브루트 포스순열 알고리즘은 C++ STL에 구현되어 있다. algorithm 라이브러리에 있는 next_permutation 함수를 이용하면 된다. next_permutation은 배열(또는 벡터)의 범위를 인자로 받고, 다음 순열이 존재하면 true를 없으면 false를 반환한다.next_permutation을 구현하는 방법은 아래와 같다. 배열 또는 벡터의 이름이 a라고 가정하자.인덱스 i가 0보다 크고, a[i-1] ..
BOJ 1476 · 날짜 계산 알고리즘 분류 : 브루트 포스나머지를 이용하여 연도를 구할 수 있다.C++ 소스코드#include <cstdio> int main() { int e, s, m; scanf("%d %d %d", &e, &s, &m); int year = 0; while (true) { int x = year%15, y = year%28, z = year%19; if (x == ..
BOJ 1966 · 프린터 큐 알고리즘 분류 : 브루트 포스큐 자료구조를 이용하는 알고리즘 문제다. 큐(Queue)는 선입선출(FIFO; First In First Out)의 선형 자료구조이다. 먼저 들어간 데이터가 먼저 나온다는 뜻이다. 이 문제는 우선순위가 있는 큐를 이용해야 한다. N개의 문서에서 우선순위가 높은 문서부터 먼저 출력되고, 이때 M번 문서는 몇 번째에 인쇄되는지 출력해야 한다.입력받은 데이터를 큐에 집어넣는다.데이터와 함께 데이터의 인덱스를 별도의 큐..
BOJ 1065 · 한수 알고리즘 분류 : 브루트 포스정수 N이 주어질 때, 1부터 N 사이에 존재하는 한수의 수를 구하는 알고리즘을 짜는 문제다. 한수란 각 자릿수가 등차수열을 이루는 수를 말한다. 예를 들면 123은 1, 2, 3 순으로 1씩 증가하는 한수이며, 642는 6, 4, 2 순으로 2씩 감소하는 한수이다. 한 자릿수, 두 자릿수는 모두 한수이며, 세 자릿수 이상은 각 자릿수가 일정한 공차를 이루고 있어야만 한다.N이 100 미만일 경우, N이..
BOJ 2309 · 일곱 난쟁이 알고리즘 분류 : 브루트 포스난쟁이 9명 중 7명 키의 합이 100이 되는 것을 찾는 간단한 문제다. 9명 중 2명을 빼서 100을 찾는다고 생각하면 더 쉽다.9명의 키를 입력받으면서 모두 더한다. 입력이 끝나면 정렬한다.모두 더한 값에서 2명을 빼서 100이 되는 값을 찾는다.2명을 제외하고 순서대로 출력한다.C++ 소스코드#include <cstdio> #include <algorithm> const in..
BOJ 3055 · 탈출 알고리즘 분류 : BFSBFS를 통해 고슴도치가 동굴까지 이동하는 최단 거리를 구하는 문제다. 1분마다 물은 상하좌우로 1칸씩 번지고, 고슴도치도 1칸씩 움직인다. 고슴도치는 물로 이동할 수 없고, 다음 시간에 물이 차는 곳으로도 갈 수 없다. 때문에 물을 먼저 Queue에 넣고, 그다음 고슴도치를 Queue에 넣어 BFS를 돌리면 된다.Queue에 고슴도치의 위치와 물의 위치가 들어가므로, 물과 고슴도치를 구별할 flag를 만든다.map struc..
BOJ 9328 · 열쇠 알고리즘 분류 : BFSBFS를 통해 맵을 탐색하면서 문서를 얻는 문제다. 이동 가능한 위치까지 최대한 이동해서 문서를 얻어야 한다. 빌딩 밖을 나갔다가 다시 들어와서 문을 열 수 있으므로, 주어진 맵을 확장할 필요가 있다. 예를 들면 아래 그림처럼 확장한다.맵을 입력받을 때, 가장자리를 빈 공간(.)으로 만든다. 맵의 범위가 가로(1~W), 세로(1~H)라면, 가로(0, W+1), 세로(0, H+1)를 빈 공간으로 설정하면 된다. C++ ..
BOJ 14442 · 벽 부수고 이동하기 2 알고리즘 분류 : BFS2206번 '벽 부수고 이동하기'를 변형한 문제다. 이전 문제는 벽을 최대 1개까지만 부술 수 있었으나, 이번 문제는 최대 10개까지 가능하다. 1개에서 10개로 늘어난 것이므로, 풀이는 비슷하게 접근할 수 있다. 이전 문제는 이곳에서 참조.C++ 소스코드#include <cstdio> #include <queue> using namespace std; struct map { int x, y, w..
BOJ 2206 · 벽 부수고 이동하기 알고리즘 분류 : BFSBFS를 통해 최단 거리를 구할 수 있는 문제다. 미로 탐색에서 약간 변형된 문제이며, 벽을 최대 1개만 부셔서 이동할 수 있다.벽을 부수지 않거나(0), 벽을 1개 부시는(1) 경우로 나뉜다.위의 경우를 확인하기 위해 flag를 만들고, 이를 Queue에 집어 넣는다.다음 이동에서 벽을 만난 경우, flag가 0이면 벽을 부수고 flag를 1로 바꾼다.방문 여부는 dist 값에 있으며, 값이 0이 아니면 방문한 곳이다.정답은..