단한의 개발 탐사기

문제 [BOJ][C++] 백준 6604번: Matrix Chain Multiplication 문제는 링크를 클릭해서 볼 수 있다. 풀이 입력 및 저장 행렬의 개수 n을 입력 받고 이어서 n개의 행렬의 정보를 입력 받는다. 행렬의 정보는 행렬의 이름, 행의 개수, 열의 개수로 이루어져있다. 행과 열을 동시에 저장하기 위해 pair 자료형을 사용했고, 행렬의 이름으로 행렬의 정보를 접근하기 위해 unordered_map을 사용했다. unordered_map은 key의 hash 값으로 value에 접근할 수 있고 탐색 속도는 O(1)이다. 다음으로 예제 입력이 끝날 때까지 입력을 받기 위해 while (cin >> formula) 를 사용했다. string formula; while (cin >> formul..

문제 [BOJ][C++] 백준 1920번: 수 찾기 문제는 링크를 클릭해서 볼 수 있다. 풀이 stl sort 함수에 compare 함수를 직접 정의해 시리얼 번호를 정렬했다. compare 함수에서 시리얼 번호를 정렬하는 기준은 크게 둘로 나누었다. a와 b의 길이가 다른 경우와 같은 경우. 첫 번째 a와 b의 길이가 다른 경우, a와 b의 길이를 .length()로 구한 뒤 두 길이의 비교값을 반환했다. 두 번째 a와 b의 길이가 같은 경우, get_integer_sum 함수로 a와 b의 자리수 합을 구했다. get_integer_sum 함수는 문자열에서 숫자만 골라내어 그 합을 구하는 함수이다. 구한 두 자리수의 합이 서로 다르다면 두 자리수의 합 비교값을 반환하고, 같다면 a, b 자체 비교값을 ..

문제 [BOJ][C++] 백준 1920번: 수 찾기 문제는 링크를 클릭해서 볼 수 있다. 풀이 문제 조건에서 n과 m의 크기는 최대 100,000이다. 시간 제한 1초를 맞추기 위해 시간 복잡도를 고려해야한다. 선형 탐색을 선택할 경우 시간 복잡도는 O(n m)으로 1초의 시간 제한을 넘기게 된다. 따라서 O(log N)의 시간복잡도를 가지는 이분 탐색을 선택했다. 이분 탐색을 선택할 경우 시간 복잡도는 O(n log m)이 되어 시간 제한을 맞출 수 있다. 정수 a들을 a_array에 입력받은 뒤 이분 탐색 알고리즘을 사용하기 위해 a_array를 오름차순으로 정렬했다. left, mid, right는 a_array의 인덱스를 저장한 변수이다. left와 right의 초기값은 각각 0과 n - 1이다...

문제 [BOJ][C++] 백준 10026번: 적록색약 문제는 https://www.acmicpc.net/problem/10026를 클릭해서 볼 수 있다. 풀이 먼저 적록색약이 아닌 사람이 봤을 때의 구역의 수부터 구했다. 구역을 구하는 과정은 그림을 돌면서 처음 방문하는 노드를 찾아 dfs를 진행했다. 현재 방문한 노드에서 인접 노드 중 방문한 적이 없고, 현재 노드와 색이 같은 인접 노드로 이동했다. 적록색약인 사람이 봤을 때의 구역의 수를 구하기 전에 2가지를 바꿨다. 첫 번째는 적록색약인 사람은 R과 G가 구분되지 않기 때문에 R을 G로 바꿔 그림에서 둘의 차이를 없앴다. 그림을 바꿨기 때문에 구역의 수를 구하는 과정은 적록색약이 아닌 사람이 봤을 때의 구역의 수를 구하는 방법과 같다. 구역의 수를..