본문 바로가기

Programming

BOJ 15649 · N과 M (1) 알고리즘 분류 : 브루트 포스N개의 숫자 중에서, M개만 뽑아서 출력하는 문제다. 재귀 함수를 이용하여 구현할 수 있다.사용 여부를 확인할 배열 check를 N 사이즈로 만들어둔다.1부터 N까지 재귀 함수를 호출한다. 숫자 X를 사용했으면, check[X]를 true로 한다.check가 true라면 재귀 함수를 호출하지 않고 넘어간다.사용한 숫자를 리스트에 담아두고, 리스트의 길이가 M이 되면 리스트를 출력한다.C++ 소스코드from sys..
BOJ 16234 · 인구 이동 알고리즘 분류 : DFS인접한 국가 간의 연합을 통해 인구 이동을 하는 문제다. 연합은 인접한 두 국가 간의 인구 차이가 L 이상, R 이하일 때만 가능하다. 인구 차이가 이 범위를 벗어난다면 연합을 할 수 없고, 인구 이동을 할 수 없다. 이 문제는 그래프에서 연결 요소 개수를 찾는 문제와 비슷하다.DFS (또는 BFS)를 통해 연합 가능한 국가가 몇 개인지 찾는다. (1, 1)부터 (N, N)까지 전체 국가를 탐색하면서 방문하지 않은 국..
BOJ 16236 · 아기 상어 알고리즘 분류 : BFS아기 상어가 물고기를 먹으면서 움직이는 최단 거리를 구하는 문제다. 여러 가지 조건이 까다로운 문제다. 첫 번째, 아기 상어는 자신보다 크거나 같은 크기의 물고기를 먹을 수 없다. 두 번째, 상어에게 가장 가까운 위치에 있는 물고기를 우선순위로 먹어야 한다. 세 번째, 여러 마리가 가까이에 있다면, 가장 위쪽에 있는 물고기, 그다음 순서로 가장 왼쪽에 있는 물고기를 우선순위로 먹어야 한다. 이 세 가..
BOJ 16235 · 나무 재테크 알고리즘 분류 : 시뮬레이션봄, 여름, 가을, 겨울에 따라 나무가 개수가 변할 때, K년이 지난 후 남아있는 나무의 개수를 구하는 문제다. 문제 자체가 복잡하기 때문에 제대로 정독하고 계절 순서대로 구현하는 것이 좋다.봄에는 나무가 자신의 나이만큼 땅에 있는 양분을 먹고, 나이가 1 증가한다. 한 구역의 땅에 나무가 여러 그루 존재할 수 있다. 나이가 어린 나무부터 양분을 먹는다. 땅에 남아있는 양분이 부족하여 양분을 먹지 못한 나무는 죽는..
BOJ 12001 · Load Balancing (Bronze) 알고리즘 분류 : 브루트 포스농장을 4군데로 분할하여, 가장 균형 있게 나누는 방법을 푸는 문제다. 균형 있게 나눈다는 것은 4군데 중 어느 한곳에 너무 많은 소가 배치되지 않도록 나누는 것을 말한다. N이 최대 100이므로, 모든 경우의 수를 만들어도 해결할 수 있다.X축 기준을 정하고 위아래로 나눈다.Y축 기준을 정하고 양옆으로 나눈다.각 지역에 존재하는 소가 몇 마리인지 센다.위에서 센 소의 수 중, 가장 큰..
BOJ 3568 · iSharp 알고리즘 분류 : 문자열 처리입력받은 한 줄의 변수 선언을 여러 줄의 변수 선언으로 바꾸는 문제다. 변수는 띄어쓰기로 구분되고, 여러 개의 변수가 주어질 수 있다. 또한 변수 이름이 여러 글자일 수 있기 때문에, 문자열을 뒤집을 때 유의해야 한다.C++은 String Stream을 이용하여 띄어쓰기로 분리된 문자열을 각각 처리하면 편하다.Python은 split으로 각각 처리하면 된다.문자열을 뒤쪽부터 탐색하면서, 특수 문자가 나타..
BOJ 16196 · 중국 신분증 번호 알고리즘 분류 : 시뮬레이션, 문자열 처리문제를 천천히 정독하여 그대로 구현하면 된다. 날짜는 윤년도 고려해야 하므로, 윤달인 경우 29일이 될 수 있다.문자열을 끊어서 읽은 후, 정수로 변환하여 유효성을 검사하면 된다.C++ 소스코드#include <iostream> #include <string> #include <algorithm> #include <vector> #define leapyear(y) (..
BOJ 16197 · 두 동전 알고리즘 분류 : BFSBFS 탐색을 통해 두 동전을 보드에서 떨어뜨리는 최단 거리를 구하면 된다. 동전 두 개가 동시에 움직이므로, 방문 여부를 확인할 배열을 4차원으로 설정하는 것이 좋다. '구슬 탈출'과 비슷한 문제다.방문 여부를 확인하고 거리를 저장할 배열 dist를 4차원으로 선언한다. (동전1 X좌표, 동전1 Y좌표, 동전2 X좌표, 동전2 Y좌표)보드를 입력받을 때 가장자리를 0으로 비워두고, 입력받는다. 즉, N*M 사이즈를 ..
BOJ 16198 · 에너지 모으기 알고리즘 분류 : 브루트 포스재귀 함수를 이용하여 모든 경우의 수를 구하고, 그중에서 최댓값을 구하면 된다.에너지 구슬을 사용하면 그 에너지 구슬은 더 이상 사용하지 않기 때문에, 사용 여부를 확인할 check 배열을 만든다.에너지 구슬을 고를 때, 첫 번째 구슬과 마지막 구슬은 사용하지 않으므로 인덱스의 범위를 앞뒤로 1씩 줄인다.양옆의 구슬을 이용하여 에너지를 모을 때, 이전에 사용된 구슬인지 확인해야 한다.왼쪽이 사용된 구슬이라면 사용하지 않은..
BOJ 16506 · CPU 알고리즘 분류 : 시뮬레이션, 문자열 처리어셈블리어 코드를 기계어로 코드로 번역하여 출력하는 문제다. 문제를 천천히 정독하여 그대로 구현하면 된다. 문자열 처리는 파이썬이 간결하고 구현하기 쉽다.C++ 소스코드#include <iostream> #include <string> using namespace std; const string reg[] = {"000", "001", "010", "011", "100", "101", ..
BOJ 10678 · Meeting Time 알고리즘 분류 : 브루트 포스, DFSN이 최대 16이므로, DFS를 통해 모든 경로를 만들어서 해결할 수 있다.path 에 경로를 입력받고, 인접 리스트로 활용한다. 인접 행렬로 구현해도 무방하다.DFS를 통해 모든 경로를 탐색하고 N에 도착하면 이동 거리의 합을 dist 에 추가한다.Bessie의 이동 경로와, Elsie의 이동 경로를 모두 구한다.2개의 dist 리스트에서 서로 값을 비교한다. 값이 겹치면서 가장 작은 값을 정답으로 낸..
BOJ 16755 · Magnus 알고리즘 분류 : 문자열 처리문자열에서 HONI의 개수를 출력하는 문제다. 인덱스 0부터 시작해서 문자열의 길이까지 순서대로 이동하면서 다 찾아보면 된다.C++ 소스코드#include <iostream> #include <string> using namespace std; string s; char honi[] = "HONI"; void solve() { int k = 0, ans = 0; for (int i=..