프로그래밍/알고리즘
BOJ 16506 · CPU
알고리즘 분류 : 시뮬레이션, 문자열 처리 어셈블리어 코드를 기계어로 코드로 번역하여 출력하는 문제다. 문제를 천천히 정독하여 그대로 구현하면 된다. 문자열 처리는 파이썬이 간결하고 구현하기 쉽다. C++ 소스코드 #include #include using namespace std; const string reg[] = {"000", "001", "010", "011", "100", "101", "110", "111"}; const string con[] = {"0000", "0001", "0010", "0011", "0100", "0101", "0110", "0111", "1000", "1001", "1010", "1011", "1100", "1101", "1110", "1111"}; bool opco..
BOJ 10678 · Meeting Time
알고리즘 분류 : 브루트 포스, DFS N이 최대 16이므로, DFS를 통해 모든 경로를 만들어서 해결할 수 있다. path 에 경로를 입력받고, 인접 리스트로 활용한다. 인접 행렬로 구현해도 무방하다.DFS를 통해 모든 경로를 탐색하고 N에 도착하면 이동 거리의 합을 dist 에 추가한다.Bessie의 이동 경로와, Elsie의 이동 경로를 모두 구한다.2개의 dist 리스트에서 서로 값을 비교한다. 값이 겹치면서 가장 작은 값을 정답으로 낸다. C++ 소스코드 #include #include #include using namespace std; struct field { int x, d; }; int n, m; void dfs(vector path[], vector &dist, int now, int..
BOJ 16755 · Magnus
알고리즘 분류 : 문자열 처리 문자열에서 HONI의 개수를 출력하는 문제다. 인덱스 0부터 시작해서 문자열의 길이까지 순서대로 이동하면서 다 찾아보면 된다. C++ 소스코드 #include #include using namespace std; string s; char honi[] = "HONI"; void solve() { int k = 0, ans = 0; for (int i=0; i
BOJ 11965 · Bessie's Dream
알고리즘 분류 : 다익스트라 빨간색(0), 분홍색(1), 주황색(2), 파란색(3), 보라색(4) 등 총 5가지 색의 타일이 있는 미로를 이동하면서 탈출해야 한다. 이미 방문했던 타일을 다시 방문할 수 있으므로, 일반적인 BFS로 최단 거리를 구하기는 까다롭다. 구현할 때, 보라색(4) 타일을 유의해야 한다. 빨간색(0) 타일로는 이동할 수 없다. 다음 이동에서 0번 타일을 보면 무시한다.분홍색(1) 타일로는 이동할 수 있다. 평범한 이동을 하면 된다.주황색(2) 타일로는 이동할 수 있으며, 이 타일을 밟으면 오렌지 냄새를 풍긴다. 냄새 상태를 True로 만든다.파란색(3) 타일로는 냄새 상태가 True일 때에만 이동할 수 있다. 냄새 상태가 False라면 이동할 수 없다.보라색(4) 타일에서는 보라색 ..
BOJ 5558 · チーズ
알고리즘 분류 : BFS 쥐가 먹을 수 있는 치즈를 순서대로 먹으면서 이동하는 최단 거리를 구하는 문제다. 다음 치즈를 먹으러 이동할 때, 방문했던 곳을 다시 방문할 수 있다.치즈를 낮은 숫자부터 순서대로 먹어야 하고, 현재 먹을 수 없는 높은 숫자의 치즈는 무시하고 이동할 수 있다.위 두 가지를 잘 고려하여, BFS 탐색을 해야 한다. 우선 BFS를 통해 먹을 수 있는 치즈를 찾고, 먹은 위치와 이동 거리를 저장한 후 BFS를 종료한다.방문 여부를 확인하는 check 배열을 초기화하고, 위에서 먹은 위치부터 다음 치즈까지 BFS 탐색을 다시 시작한다.즉, 시작점 → 1번 치즈, 1번 치즈 → 2번 치즈, ···, N-1번 치즈 → N번 치즈 순으로 BFS를 돌리면 된다. C++ 소스코드 #include..
BOJ 16769 · Mixing Milk
알고리즘 분류 : 시뮬레이션 1 → 2, 2 → 3, 3 → 1 (X → Y)을 순서대로 100번 해서 각 양동이에 우유가 얼마나 남았는지 확인하는 문제다. 순서대로 100번만 반복하면 된다. 우선 옮기기 전에, X번 양동이에 남아있는 우유의 양과 Y번 양동이에 남아있는 우유의 양을 더해서 temp에 저장해둔다.Y번 양동이의 최대치(C)와 temp와 비교한다.temp가 C보다 크거나 같을 경우 (temp - C)를 X번 양동이에 저장하고, 아니라면 0을 X번 양동이에 저장한다.Y번 양동이의 최대치(C)와 temp를 다시 비교한다.temp가 C보다 크거나 같을 경우 C를 Y번 양동이에 저장하고, 아니라면 temp를 Y번 양동이에 저장한다.위 과정을 100번 반복한다. C++ 소스코드 #include int..
BOJ 6593 · 상범 빌딩
알고리즘 분류 : BFS BFS를 통해 최단 탈출 시간을 구하는 문제다. 상범 빌딩에 갇힌 사람을 빌딩 밖으로 탈출시켜야 한다. 시작점은 'S'로 주어지고, 탈출구는 'E'로 주어진다. 3차원 배열을 선언하여 빌딩의 정보를 입력받고, 이동 거리를 저장할 dist 배열을 3차원으로 선언하고 방문 체크 용도로 사용한다. 입력받을 때 시작점의 위치와 도착점의 위치를 저장해두어야 한다.이동은 인접한 '동서남북상하'로 한 칸씩만 이동할 수 있다.이동할 때 빌딩의 범위를 벗어나는지 확인해야 한다.벽(#)으로 이동할 수 없다.탈출구에 도착하면 "Escaped in x minute(s)."를 출력한다. 탈출구에 도달하지 못하면 "Trapped!"를 출력한다.여러 개의 테스트케이스가 주어지므로, 변수 초기화에 유의한다...
BOJ 4485 · 녹색 옷 입은 애가 젤다지?
알고리즘 분류 : 다익스트라 링크가 검은 루피를 먹으면서 루피를 잃으면서 이동할 때, 가장 적게 잃는 경로를 구하는 문제다. 각 칸마다 잃을 수 있는 루피는 0~9 이므로, 다익스트라 알고리즘을 통해 구현하면 된다. N X N 의 맵을 입력받고, 이를 dist 배열을 업데이트할 때 이용한다.정답은 dist[n-1][n-1]에 있으며, 이 값에 처음부터 잃는 루피인 a[0][0]을 더해주어야 한다.테스트케이스가 여러 개 주어지므로, 테스트케이스마다 dist 배열을 초기화해주어야 한다. C++ 소스코드 #include #include #include using namespace std; struct zelda { // The person wearing green clothes is Zelda, right? ..