단한의 개발 탐사기

C번 - 카카오뷰 큐레이팅 효용성 분석 (브론즈 2) (1AC 0WA) A번 문제를 읽고 있었는데 스코어보드에 C번에 풀리는 것을 보고 바로 C번으로 넘어왔다. 단순하게 입력을 배열에 저장하고 합을 구하는 문제였다. 첫 번째 줄 입력 받으면서 배열에 흥미도를 저장하고 전체 흥미도의 합을 구했다. 두 번째 줄 입력을 받으면서 0을 입력받은 경우 동일한 index의 흥미도를 앞서 저장한 배열에서 찾아 변수에 더했다. 알고리즘은 문제를 읽으면서 바로 파악했는데 A번 풀다가 넘어오는 시간과 C++로 구현하는 시간이 더해져 11min만에 풀었다. 더 빨리 풀 수 있었는데 늦게 제출해 조금 아쉬운 문제이다. C번 코드 #include #include using namespace std; int n; // 콘텐츠의 ..

문제 [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로 바꿔 그림에서 둘의 차이를 없앴다. 그림을 바꿨기 때문에 구역의 수를 구하는 과정은 적록색약이 아닌 사람이 봤을 때의 구역의 수를 구하는 방법과 같다. 구역의 수를..