프로그래밍/알고리즘
BOJ 5427 · 불
알고리즘 분류 : BFS BFS를 통해 최소 이동거리를 구하는 문제이다. BOJ 3055번 '탈출'과 유사한 문제이다.사람(상근)은 건물 밖으로 탈출해야 하고, 불은 인접한 상하좌우로 번진다. 사람은 불이 번진 곳과 불이 다음에 번질 곳으로 이동할 수 없으므로, 불의 위치를 먼저 Queue에 넣고, 이후에 사람의 위치를 Queue에 넣어야 한다. Queue에 불의 위치와 사람의 위치가 모두 들어가므로, 불과 사람을 구분할 flag를 둔다.빌딩 밖으로 탈출하는 것은, 다음 위치가 주어진 맵의 범위를 벗어나는지 아닌지로 판별하면 된다.다음 위치가 맵의 범위를 벗어나는지 확인하고, 벗어나면 현재까지 이동한 거리를 답으로 낸다.다음 위치가 맵의 범위를 벗어나지만, 불이 벗어난 것이라면 무시한다.이동 거리를 통해..
BOJ 2146 · 다리 만들기
알고리즘 분류 : DFS, BFS 섬과 섬 사이에 다리를 놓고, 가장 짧은 다리의 길이를 구하는 문제다. 땅을 DFS를 통해 하나의 섬으로 묶고, 각 섬과 섬 사이의 거리를 BFS를 통해 구하면 된다. 먼저 입력받은 맵에서 붙어있는 육지(1)를 찾아서 섬으로 묶어야 한다.육지를 섬으로 그룹화하는 과정은 DFS를 통해 진행한다. 인접한 육지를 이동하면서 방문 체크를 하고, 카운트를 매긴다. 예를 들어, 첫 번째 섬은 1, 두 번째 섬은 2, ‥, N 번째 섬은 N으로 맵에 마킹한다.섬을 체크했다면, 섬과 섬 사이를 BFS를 통해 이동한다.바다(0)를 이동하다가, 출발한 섬과 다른 섬을 만나면, 이동거리를 최솟값으로 업데이트한다. C++ 소스코드 #include #include #include using n..
BOJ 1759 · 암호 만들기
알고리즘 분류 : 브루트 포스 BOJ 6603번 '로또'와 유사한 문제다. L개의 문자 중, C개의 문자를 뽑아서 암호를 만들면 된다. 조합(Combination)을 이용한 방법으로 구현할 수 있고, 재귀 함수를 이용한 방법으로도 구현할 수도 있다. C++은 재귀 함수를 이용했고, Python은 조합을 이용했다.모음 1개 이상, 자음 2개 이상으로 이루어진 암호인지 확인해야 한다. C++ 소스코드 #include #include #include using namespace std; int L, C; char a[15]; bool possible(string passwd) { int vowel = 0, consonant = 0; for (char c : passwd) { if (c == 'a' || c =..
BOJ 6603 · 로또
알고리즘 분류 : 브루트 포스 K개의 숫자 중에서 6개를 뽑아서 나열하는 문제다. 재귀 함수를 이용하여 간단히 구현할 수 있지만, 조합(Combination)을 이용한 방법으로도 구현할 수 있다.C++의 STL에 조합(combination)이 없으므로, 순열(permutation)을 이용해야 한다. Python은 itertools에 있는 combinations를 이용하면 간단하다. 순열을 응용하여 조합을 만들 수 있다.N 개의 숫자가 있는 리스트 A에서 K 개의 숫자를 뽑는다면, nCk 라고 표기한다.1이 K 개, 0이 N-K 개로 구성된 N 사이즈의 리스트 B를 생성한다. 예를 들어 8C6이라고 했을 때, 11111100 처럼 만든다.리스트 B를 prev_permutation을 통해 순열로 돌리면서 루..
BOJ 10819 · 차이를 최대로
알고리즘 분류 : 브루트 포스 |A[i]-A[i-1]|를 0부터 N-1까지 모두 더했을 때, 가장 큰 값을 찾는 문제다. A 리스트의 값은 순서가 바뀔 수 있으므로, 순열로 하나씩 순서대로 구해보면 된다. 절댓값은 abs 함수를 이용하면 된다. A 값을 입력받은 후, 정렬한다.A 값을 next_permutation(C++ STL) / permutations(Python itertools)을 통해 순열을 돌린다.합을 구해서 최댓값이면 저장한다. C++ 소스코드 #include #include using namespace std; int solve(int n) { int a[n]; int ans = 0; for (int i=0; i
BOJ 1325 · 효율적인 해킹
알고리즘 분류 : BFS BFS를 통해 모든 노드를 탐색하고, 탐색 가능한 최댓값을 구하는 문제다.A가 B를 신뢰할 경우, B를 해킹하면 A도 해킹이 가능하다. A가 B를 신뢰한다는 것을 다르게 말하면, B → A 로 연결된 방향 그래프라고 말할 수 있다. 입력받으면서 A와 B의 신뢰 관계를 연결 리스트로 저장한다.컴퓨터 개수가 N개일 때, 1부터 N까지 BFS를 N번 호출하여 해킹 가능한 최대 컴퓨터 개수를 저장한다.이때 가장 많이 해킹할 수 있는 컴퓨터의 번호를 답으로 출력한다.답이 여러 개일 수 있으므로, 컴퓨터 번호를 별도의 리스트에 저장한다. C++ 소스코드 #include #include #include #include #include using namespace std; int n, m; v..
BOJ 2680 · QR
알고리즘 분류 : 시뮬레이션, 문자열 처리 이 문제는 최소 사이즈(21*21)의 QR 코드를 디코딩하는 문제다. 구현보다 문제 이해가 어려운 문제다. 인코딩된 16진수 코드를 원래 정보로 복원해야 한다. 문자열로 처리하여 다소 무식하게 구현했다. 헥스 코드를 바이너리 코드로 변환한다.바이너리 코드를 앞에서부터 순서대로 읽으면서, 모드 비트(Mode Bits)와 카운트 비트(Count Bits)를 먼저 처리한다.숫자(Numeric)인 경우, 2진수를 10진수로 변환한다.숫자/문자(Alphanumeric)인 경우, 별도의 알파뉴메릭 배열을 만들어서 변환한다.8비트 문자(8 bit Byte) 또는 한자(Kanji)인 경우, 아스키 문자로 변환하거나 아스키 범위를 벗어나면 숫자로 출력한다.종료(Terminati..
BOJ 2589 · 보물섬
알고리즘 분류 : BFS BFS를 통해 맵을 탐색하면서 최단 거리를 구한다. 최단 거리 중에서 가장 긴 거리가 정답이다. 보물섬에서 이동할 때, 땅(L)에서 땅(L)으로만 이동할 수 있다. 물(W)로는 이동할 수 없다.BFS 탐색을 하면서 매번 이동 거리를 저장하고, 가장 큰 이동거리를 별도로 저장한다.전체 맵에 있는 땅(L)의 개수만큼 BFS 탐색을 반복한다.BFS 탐색 결과로 나오는 이동 거리 중, 가장 큰 값을 정답으로 낸다. C++ 소스코드 #include #include #include using namespace std; struct treasure { int x, y, d; }; int n, m; char a[51][51]; bool check[51][51]; const int dx[] = ..