본문 바로가기

Programming

BOJ 6087 · 레이저 통신 알고리즘 분류 : BFS'C'와 'C' 사이를 레이저로 연결하기 위해 필요한 거울의 개수를 세는 문제다. 최소의 거울을 설치해야 하므로, BFS 탐색을 통해 해결하는 것이 좋다. 레이저는 직선으로 움직이며, 레이저가 방향을 꺾기 위해서 거울이 필요하다.기본적으로 BFS 탐색을 하되, 한 번 이동할 때 갈 수 있는 데까지 이동한다."갈 수 있는 데까지"란, 벽('*')을 만나기 전까지 또는 범위를 벗어나기 전까지이다.같은 방향으로 한 칸씩 이..
BOJ 1445 · 일요일 아침의 데이트 알고리즘 분류 : 다익스트라S부터 출발해서 F에 도착할 때까지, 쓰레기를 최소로 지나면서, 쓰레기의 옆을 최소로 지나는 방법을 찾는 문제다. 두 가지의 우선순위 조건 때문에, 다익스트라 알고리즘을 사용하는 것이 좋다. 다익스트라를 이용하기 위해, 입력으로 주어지는 문자열 맵에 상응하는 인접 행렬을 만든다.쓰레기가 있는 칸 'g'는 2500으로 두고, g에 인접한 4칸은 1로 둔다. 나머지 칸은 0으로 둔다.맵이 최대 50*..
BOJ 2665 · 미로만들기 알고리즘 분류 : BFS미로를 이동하면서 검은 방을 흰 방으로 만드는 최소 횟수를 구해야 하는 문제다. 덱(Deque)과 BFS를 이용하여 해결할 수 있다. 이 문제는 BOJ 1261 '알고스팟' 문제와 유사하다.흰 방을 이동할 때는 덱의 뒤에 넣고, 이동 거리는 이전과 같게 한다.검은 방을 이동할 때는 덱의 앞에 넣고, 이동 거리를 +1 업데이트한다.덱에서 이동 좌표를 꺼낼 때, 덱의 뒤에서부터 꺼낸다.C++ 소스코드#includ..
BOJ 2529 · 부등호 알고리즘 분류 : 백트래킹기본적으로 재귀 함수를 이용하여 브루트 포스로 구현할 수 있다. 재귀 함수를 호출하기 전에 부등호 체크를 하는 방식으로 백트래킹을 하여 시간을 단축할 수 있다.하나의 숫자를 구하기 위해서 입력으로 주어진 길이(N)+1 만큼 재귀 함수를 호출해야 한다. 올바른 부등식은 숫자 개수가 부등호 개수보다 1개 더 많다.재귀 함수 종료 조건 : 숫자 개수(길이) == N+1수를 중복하여 사용..
BOJ 14889 · 스타트와 링크 알고리즘 분류 : 브루트 포스두 팀으로 나눠서 두 팀의 능력치 차에 대한 최솟값을 구하는 문제다. 재귀 함수를 이용하여 구현할 수 있다.재귀 함수는 두 팀으로 나누는 과정에 이용한다.팀을 구분하는 체크 배열 c를 둔다. 팀의 구분은 true와 false로 한다.재귀 함수 종료 조건은 인덱스가 N을 벗어났을 때이거나 팀 인원이 N/2 명이 되었을 때이다.팀 능력치의 총합은 N^2 for 문으로 구한다.Aij 는 i와 j가 같은 팀일 ..
BOJ 1748 · 수 이어 쓰기 1 알고리즘 분류 : 구현입력으로 N이 주어질 때, 1부터 N까지 수를 이어 붙여서 나온 수의 길이를 구하는 문제다.자릿수로 나눠서 생각하면 구현이 쉽다.N이 주어졌을 때, 1의 자리가 있는 수는 1부터 N까지이다. 따라서 1의 자리가 있는 수는 (N-1+1)이다.10의 자리가 있는 수는 10부터 N까지이다. 이를 구하면, (N-10+1) 이다.100의 자리가 있는 수는 100부터 N까지이다. 이를 구하면, (N-100+1) 이다.위의 과정을 N의 자릿..
BOJ 13913 · 숨바꼭질 4 알고리즘 분류 : BFSN부터 K까지 이동하기 위해 걸리는 최소 시간을 구하는 문제다. BOJ 1697번 '숨바꼭질' 문제를 변형한 문제다. 최소 시간과 이동한 방법을 출력해야 한다. 이동한 방법은 이동 경로를 역순으로 추적하면 된다.최소 시간은 이전 문제를 참고.이동 경로를 저장할 path 배열을 만든다.path[다음 좌표] = (현재 좌표) 방식으로 path 배열을 저장한다.K에 도착하면, path 배열을 K부터 시작해서 N까지 역순으로..
BOJ 13549 · 숨바꼭질 3 알고리즘 분류 : BFSN부터 K까지 이동하기 위해 걸리는 최소 시간을 구하는 문제다. BOJ 1697 '숨바꼭질' 문제를 변형한 문제다. 최소 시간을 구해야 하는데, 이동 시간에 차이가 있다. 순간 이동(2*X)은 0초 걸리고, X+1, X-1 이동은 1초 걸린다.0초와 1초 케이스로 나뉘므로, 덱(deque)을 이용하면 좋다.순간 이동(2*X)이 더 빠른 시간(0초)으로 이동할 수 있으므로, X+1, X-1 이동보다 우선순위를 ..
BOJ 12851 · 숨바꼭질 2 알고리즘 분류 : BFSN부터 K까지 이동하기 위해 걸리는 최소 시간을 구하는 문제다. BOJ 1697번 '숨바꼭질'에서 변형된 문제다. 최소 시간과 그 경우의 수를 구해야 한다.최소 시간은 이전 문제를 참고한다.x에서 nx에 도착하는 경우의 수는 여러 가지 일 수 있으므로, dist[x]에 아직 방문하지 않은 상태(dist[x]==0)이거나, 이미 방문했더라도 이동 거리가 같다면(dist[nx] == dist[x]+1) ..
BOJ 14226 · 이모티콘 알고리즘 분류 : BFSS개의 이모티콘을 화면에 만드는 데 걸리는 최소 시간을 구하는 문제다. 3개의 동작이 있고, 각 동작은 1초가 걸리며, 이 동작의 최소 횟수를 구하는 문제이므로, BFS 풀이로 접근할 수 있다.방문(상태) 체크를 하기 위해서, 2차원 배열이 필요하다.2차원 배열의 인덱스는 [화면에 있는 이모티콘] [클립보드에 있는 이모티콘] 이다.화면에 있는 이모티콘을 x, 클립보드에 있는 이모티콘을 y라 했을 때, 현재 상태를 (x, y)라..
BOJ 15666 · N과 M (12) 알고리즘 분류 : 브루트 포스입력받은 N개의 숫자 중에서 M개를 뽑아서 출력하는 문제다. N과 M (8) 문제와 비슷하나, N개의 숫자 중 중복된 숫자가 주어질 수 있다. N과 M (11) 문제에서 for문의 시작 지점만 바꾸면 된다.C++ 소스코드#include <cstdio> #include <vector> #include <algorithm> using namespace std; int n, m; vector&..
BOJ 15665 · N과 M (11) 알고리즘 분류 : 브루트 포스입력받은 N개의 숫자 중에서 M개를 뽑아서 출력하는 문제다. N과 M (7) 문제와 비슷하나, N개의 숫자 중 중복된 숫자가 주어질 수 있다. 중복된 수를 제거하고 (7) 문제와 비슷하게 그대로 돌리면 된다.C++ 소스코드#include <cstdio> #include <vector> #include <algorithm> using namespace std; int n, m; vector..