프로그래밍
BOJ 15650 · N과 M (2)
알고리즘 분류 : 브루트 포스 N개의 숫자 중에서 M개를 뽑아서 출력하는 문제다. 단, 중복된 수열이 없어야 하고, 오름차 순으로 출력해야 한다. N과 M (1)의 코드에서 for문의 시작 지점을 수정하면 된다. 시작 지점은 이전에 뽑은 숫자+1 이다. 숫자+1을 다음 재귀 함수 호출에 전달하면 된다. C++ 소스코드 #include #include using namespace std; int n, m, x; vector a; void solve(int index, int cnt) { if (cnt == m) { for (auto i : a) printf("%d ", i+1); printf("\n"); return; } for (int i=index; i
BOJ 15649 · N과 M (1)
알고리즘 분류 : 브루트 포스 N개의 숫자 중에서, M개만 뽑아서 출력하는 문제다. 재귀 함수를 이용하여 구현할 수 있다. 사용 여부를 확인할 배열 check를 N 사이즈로 만들어둔다.1부터 N까지 재귀 함수를 호출한다. 숫자 X를 사용했으면, check[X]를 true로 한다.check가 true라면 재귀 함수를 호출하지 않고 넘어간다.사용한 숫자를 리스트에 담아두고, 리스트의 길이가 M이 되면 리스트를 출력한다. C++ 소스코드 #include #include using namespace std; int n, m; bool check[8]; vector a; void solve(int cnt) { if (cnt == m) { for (auto i : a) printf("%d ", i+1); print..
BOJ 16234 · 인구 이동
알고리즘 분류 : DFS 인접한 국가 간의 연합을 통해 인구 이동을 하는 문제다. 연합은 인접한 두 국가 간의 인구 차이가 L 이상, R 이하일 때만 가능하다. 인구 차이가 이 범위를 벗어난다면 연합을 할 수 없고, 인구 이동을 할 수 없다. 이 문제는 그래프에서 연결 요소 개수를 찾는 문제와 비슷하다. DFS를 통해 연합 가능한 국가가 몇 개인지 찾는다. (1, 1)부터 (N, N)까지 전체 국가를 탐색하면서 방문하지 않은 국가라면 DFS를 호출한다.DFS 탐색을 진행하면서 연합 가능한 국가가 있다면, 연합 국가 개수를 카운트하고, 인구 수의 합을 저장한다.또한 DFS 탐색을 하면서 별도로 연합 국가의 경로를 기록해둔다. 아래 소스코드에서는 moving 이라는 이름의 배열을 사용했다.한 번의 DFS 탐..
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..