본문 바로가기

Programming

BOJ 14501 · 퇴사 알고리즘 분류 : 브루트 포스재귀 함수를 이용하여 최대 수익을 구할 수 있는 문제다. 이 문제는 다이나믹 프로그래밍 방식으로도 해결할 수 있다.수익 계산 종료 조건 : 날짜가 N+1 일이 된 경우 (day == N+1)재귀 함수 종료 조건 : 날짜가 N+1 일을 넘은 경우 (day > N+1)day 번째 일에 상담을 하는 경우 : solve(day+t[day], profit+p[day])day 번째 일에 상담을 하지 ..
BOJ 1182 · 부분집합의 합 알고리즘 분류 : 브루트 포스재귀 함수를 이용하여 구현할 수 있는 문제다.집합의 원소가 N 개 있을 때, 모든 부분집합의 개수는 2^N 개이다. N의 제한이 최대 20이므로, 가능한 경우의 수는 2^20 (약 100만)이다. 따라서 모든 부분 집합을 구한 후, 그 집합의 합이 S 인지 판별해보면 된다.재귀 함수 종료 조건 : 인덱스가 범위를 벗어난 경우 (index >= N)정답을 찾은 경우 : 부분집합의 총합이 S인 경우 (..
BOJ 5427 · 불 알고리즘 분류 : BFSBFS를 통해 최소 이동거리를 구하는 문제이다. BOJ 3055번 '탈출'과 유사한 문제이다.사람(상근)은 건물 밖으로 탈출해야 하고, 불은 인접한 상하좌우로 번진다. 사람은 불이 번진 곳과 불이 다음에 번질 곳으로 이동할 수 없으므로, 불의 위치를 먼저 Queue에 넣고, 이후에 사람의 위치를 Queue에 넣어야 한다.Queue에 불의 위치와 사람의 위치가 모두 들어가므로, 불과 사람을 구분할 flag를 둔다.빌딩 ..
BOJ 2146 · 다리 만들기 알고리즘 분류 : BFSBFS(또는 DFS)를 통해 맵 전체를 탐색하면서 최단 거리를 구하는 문제이다. BOJ 1261번 '알고스팟'과 비슷한 문제이다.Queue를 2개 이용하거나, Deque을 이용하여 해결할 수 있다.Deque을 선언하고, 시작점을 육지(1)로 하여 한 군데의 위치를 Deque에 넣어둔다.BFS 탐색을 하면서 섬과 섬 사이의 거리가 가장 짧은 곳을 정답으로 낸다.현재 위치가 육지(1)이고, 다음 위치도 육지(1)라면, 이동 거리를..
BOJ 1759 · 암호 만들기 알고리즘 분류 : 브루트 포스BOJ 6603번 '로또'와 유사한 문제다. L개의 문자 중, C개의 문자를 뽑아서 암호를 만들면 된다. 조합(Combination)을 이용한 방법으로 구현할 수 있고, 재귀 함수를 이용한 방법으로도 구현할 수도 있다.C++은 재귀 함수를 이용했고, Python은 조합을 이용했다.모음 1개 이상, 자음 2개 이상으로 이루어진 암호인지 확인해야 한다.C++ 소스코드#include..
BOJ 6603 · 로또 알고리즘 분류 : 브루트 포스K개의 숫자 중에서 6개를 뽑아서 나열하는 문제다. 재귀 함수를 이용하여 간단히 구현할 수 있지만, 조합(Combination)을 이용한 방법으로도 구현할 수 있다.C++의 STL에 조합(combination)이 없으므로, 순열(permutation)을 이용해야 한다. Python은 itertools에 있는 combinations를 이용하면 간단하다.순열을 응용하여 조합을 만들 수 있다..
BOJ 10819 · 차이를 최대로 알고리즘 분류 : 브루트 포스|A[i]-A[i-1]|를 0부터 N-1까지 모두 더했을 때, 가장 큰 값을 찾는 문제다. A 리스트의 값은 순서가 바뀔 수 있으므로, 순열로 하나씩 순서대로 구해보면 된다. 절댓값은 abs 함수를 이용하면 된다.A 값을 입력받은 후, 정렬한다.A 값을 next_permutation(C++ STL) / permutations(Python itertools)을 통해 순열을 돌린다.합을 구해서 최댓값이면 저장한다.C..
BOJ 1325 · 효율적인 해킹 알고리즘 분류 : BFSBFS(또는 DFS)를 통해 모든 노드를 탐색하고, 탐색 가능한 최댓값을 구하는 문제다.A가 B를 신뢰할 경우, B를 해킹하면 A도 해킹이 가능하다. A가 B를 신뢰한다는 것을 다르게 말하면, B → A 로 연결된 방향 그래프라고 말할 수 있다.입력받으면서 A와 B의 신뢰 관계를 연결 리스트로 저장한다.컴퓨터 개수가 N개일 때, 1부터 N까지 BFS를 N번 호출하여 해킹 가능한 최대 컴퓨터 개수를 저장한다.이때 가장 많이 해킹..
BOJ 2680 · QR 알고리즘 분류 : 시뮬레이션, 문자열 처리이 문제는 최소 사이즈(21*21)의 QR 코드를 디코딩하는 문제다. 구현보다 문제 이해가 어려운 문제다. 인코딩된 16진수 코드를 원래 정보로 복원해야 한다. 문자열로 처리하여 다소 무식하게 구현했다.헥스 코드를 바이너리 코드로 변환한다.바이너리 코드를 앞에서부터 순서대로 읽으면서, 모드 비트(Mode Bits)와 카운트 비트(Count Bits)를 먼저 처리한다.숫자(N..
BOJ 2589 · 보물섬 알고리즘 분류 : BFSBFS를 통해 맵을 탐색하면서 최단 거리를 구한다. 최단 거리 중에서 가장 긴 거리가 정답이다.보물섬에서 이동할 때, 땅(L)에서 땅(L)으로만 이동할 수 있다. 물(W)로는 이동할 수 없다.BFS 탐색을 하면서 매번 이동 거리를 저장하고, 가장 큰 이동거리를 별도로 저장한다.전체 맵에 있는 땅(L)의 개수만큼 BFS 탐색을 반복한다.BFS 탐색 결과로 나오는 이동 거리 중, 가장 큰 값을 정답으로 낸다.C++ 소스코드#inc..
BOJ 10026 · 적록색약 알고리즘 분류 : BFS적록색약인과 비색약인이 구별하는 색의 영역 개수를 구하는 문제다. BFS(또는 DFS)를 통해 구현할 수 있다.BFS를 이용하여 맵을 탐색한다.먼저 비색약인으로 모든 영역을 탐색하면서, 영역의 개수를 카운트한다.다음으로 적록색약인으로 모든 영역을 탐색한다.적록색약인의 경우, 적색(R)과 녹색(G)을 같은 색으로 취급한다.C++ 소스코드#include <cstdio> #include <cstri..
BOJ 2644 · 촌수계산 알고리즘 분류 : BFSBFS를 통해 촌수를 계산하는 문제다.촌수는 거리로 바꿔서 생각하면 된다.부모와 자식 간의 관계를 인접리스트로 변환하여 저장한다.사람(X) 부터 BFS로 탐색하면서 사람(Y)를 만나면 종료한다.BFS 탐색이 끝날 때 까지 사람(Y)를 만나지 못하면, 촌수 계산이 불가능하므로 -1을 출력한다.C++ 소스코드#include <cstdio> #include <queue> #include <vector>..