BOJ
BOJ 16236 · 아기 상어
알고리즘 분류 : BFS 아기 상어가 물고기를 먹으면서 움직이는 최단 거리를 구하는 문제다. 여러 가지 조건이 까다로운 문제다. 첫 번째, 아기 상어는 자신보다 크거나 같은 크기의 물고기를 먹을 수 없다. 두 번째, 상어에게 가장 가까운 위치에 있는 물고기를 우선순위로 먹어야 한다. 세 번째, 여러 마리가 가까이에 있다면, 가장 위쪽에 있는 물고기, 그다음 순서로 가장 왼쪽에 있는 물고기를 우선순위로 먹어야 한다. 이 세 가지 조건을 모두 만족하면서 BFS 탐색을 하기 위해서는, 최소 힙(Min Heap)이 구현된 우선순위 큐(Priority Queue)를 사용하면 된다. 상어의 크기(body), 물고기를 먹은 횟수(eat)를 별도로 저장하는 변수를 둔다.BFS에 사용할 큐를 우선순위 큐로 대체한다. C..
BOJ 16235 · 나무 재테크
알고리즘 분류 : 시뮬레이션 봄, 여름, 가을, 겨울에 따라 나무가 개수가 변할 때, K년이 지난 후 남아있는 나무의 개수를 구하는 문제다. 문제 자체가 복잡하기 때문에 제대로 정독하고 계절 순서대로 구현하는 것이 좋다. 봄에는 나무가 자신의 나이만큼 땅에 있는 양분을 먹고, 나이가 1 증가한다. 한 구역의 땅에 나무가 여러 그루 존재할 수 있다. 나이가 어린 나무부터 양분을 먹는다. 땅에 남아있는 양분이 부족하여 양분을 먹지 못한 나무는 죽는다.나이 순서대로 먹는다는 내용 때문에, 단순히 나이를 오름차순 정렬하면 비효율적이다.효율적인 방법은 '덱' 자료구조를 사용하는 것이다. 나무를 새로 심을 때는 Front push하고, 나무가 죽을 때는 Back pop을 해주는 것이다. 또는 '힙' 자료구조를 사용..
BOJ 12001 · Load Balancing (Bronze)
알고리즘 분류 : 브루트 포스 농장을 4군데로 분할하여, 가장 균형 있게 나누는 방법을 푸는 문제다. 균형 있게 나눈다는 것은 4군데 중 어느 한곳에 너무 많은 소가 배치되지 않도록 나누는 것을 말한다. N이 최대 100이므로, 모든 경우의 수를 만들어도 해결할 수 있다. X축 기준을 정하고 위아래로 나눈다.Y축 기준을 정하고 양옆으로 나눈다.각 지역에 존재하는 소가 몇 마리인지 센다.위에서 센 소의 수 중, 가장 큰 값을 cow라고 하자.N*N 번 반복하면서 얻을 수 있는 cow 중, 가장 작은 값이 정답이다. C++ 소스코드 #include #include #include using namespace std; int n, m; vector x, y; void solve() { int ans = 1e9..
BOJ 3568 · iSharp
알고리즘 분류 : 문자열 처리 입력받은 한 줄의 변수 선언을 여러 줄의 변수 선언으로 바꾸는 문제다. 변수는 띄어쓰기로 구분되고, 여러 개의 변수가 주어질 수 있다. 또한 변수 이름이 여러 글자일 수 있기 때문에, 문자열을 뒤집을 때 유의해야 한다. C++은 String Stream을 이용하여 띄어쓰기로 분리된 문자열을 각각 처리하면 편하다.Python은 split으로 각각 처리하면 된다.문자열을 뒤쪽부터 탐색하면서, 특수 문자가 나타나면 자료형 앞으로 붙인다.알파벳이 나온다면, 변수명이다. 뒤쪽부터 탐색했으므로, 거꾸로 뒤집어서 출력한다. C++ 소스코드 #include #include #include using namespace std; void solve(string s) { for (int i=(..
BOJ 16196 · 중국 신분증 번호
알고리즘 분류 : 시뮬레이션, 문자열 처리 문제를 천천히 정독하여 그대로 구현하면 된다. 날짜는 윤년도 고려해야 하므로, 윤달인 경우 29일이 될 수 있다.문자열을 끊어서 읽은 후, 정수로 변환하여 유효성을 검사하면 된다. C++ 소스코드 #include #include #include #include #define leapyear(y) (((y)%4==0)-((y)%100==0)+((y)%400==0)) using namespace std; string id; int n; int days[] = {0, 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31}; vector zone; void solve() { int area = stoi(id.substr(0, 6)); if..
BOJ 16197 · 두 동전
알고리즘 분류 : BFS BFS 탐색을 통해 두 동전을 보드에서 떨어뜨리는 최단 거리를 구하면 된다. 동전 두 개가 동시에 움직이므로, 방문 여부를 확인할 배열을 4차원으로 설정하는 것이 좋다. '구슬 탈출'과 비슷한 문제다. 방문 여부를 확인하고 거리를 저장할 배열 dist를 4차원으로 선언한다. (동전1 X좌표, 동전1 Y좌표, 동전2 X좌표, 동전2 Y좌표)보드를 입력받을 때 가장자리를 0으로 비워두고, 입력받는다. 즉, N*M 사이즈를 (N+2)*(M+2) 사이즈로 확장한다.동전 두 개 중 하나가, 가장자리(인덱스 0, N+1 또는 0, M+1)인 경우 BFS 탐색을 중지하고 거리를 출력한다.동전이 둘 다 가장자리로 갔다면, 둘 다 떨어뜨릴 수 없으므로 무시한다.동전이 벽(#)에 부딪혔을 경우, ..
BOJ 16198 · 에너지 모으기
알고리즘 분류 : 브루트 포스 재귀 함수를 이용하여 모든 경우의 수를 구하고, 그중에서 최댓값을 구하면 된다. 에너지 구슬을 사용하면 그 에너지 구슬은 더 이상 사용하지 않기 때문에, 사용 여부를 확인할 check 배열을 만든다.에너지 구슬을 고를 때, 첫 번째 구슬과 마지막 구슬은 사용하지 않으므로 인덱스의 범위를 앞뒤로 1씩 줄인다.양옆의 구슬을 이용하여 에너지를 모을 때, 이전에 사용된 구슬인지 확인해야 한다.왼쪽이 사용된 구슬이라면 사용하지 않은 구슬이 나올 때까지 왼쪽으로 간다. 오른쪽은 반대로 확인한다.사용한 구슬의 개수가 N-2개라면 에너지의 양이 최댓값인지 확인한다. C++ 소스코드 #include int n, ans; int w[10]; bool check[10]; void solve(i..
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..