Pearlii-Log

문제 풀이 날짜: 2023.10.13 포스트 작성일: 2023.10.16 * 학습 목적으로 작성하는 글입니다. 풀이가 정석적이지 못할 수도 있습니다. 문제 출처 백준 온라인 저지 2473번: 세 용액 (골드3) 키워드 이분 탐색 풀이 접근법 주어진 수의 범위가 크므로 범위에 주의하자. 배열이나 변수를 Long으로 선언해야 한다. 세 가지 용액을 혼합하여 답을 도출해야 하므로, 서로 다른 세 용액을 가리키는 변수(ansL, ansR, ansM)를 선언하였다. 하나의 mid를 기준점으로 잡고, 양 끝에서부터 left와 right를 좁혀가며 이분탐색을 한다. 이분 탐색 포인터가 범위를 넘어갔다면 mid의 위치를 조정하여 다시 양 끝부터 탐색한다. 현재까지 발견한 0에 가장 가까운 특성값 key를 갱신하며 탐색..

문제 풀이 날짜: 2023.10.13 포스트 작성일: 2023.10.16 * 학습 목적으로 작성하는 글입니다. 풀이가 정석적이지 못할 수도 있습니다. 문제 출처 백준 온라인 저지 1939번: 중량제한 (골드3) 키워드 다익스트라 풀이 접근법 서로 다른 두 공장 A, B가 있다고 할 때, A → B로 이동하는 모든 경로(직+간접) 중에서 ‘최대 하중’을 구하는 문제이다. 따라서 다익스트라로 풀이하였다. 단, 전체 경로 중에서 건너게 되는 다리마다의 최대 하중은 각기 다르며, 그 다리 중 가장 버틸 수 있는 무게가 적은 쪽을 기준으로 맞추어야 한다. 따라서 경로 중 경유하는 간선 중 가장 가중치가 작은 간선을 ‘하중’으로 택한다. 가중치 큰 간선을 우선 선택한다. pq에는 무게가 큰 순서대로 Node를 넣어..

문제 풀이 날짜: 2023.10.13 포스트 작성일: 2023.10.16 * 학습 목적으로 작성하는 글입니다. 풀이가 정석적이지 못할 수도 있습니다. 문제 출처 백준 온라인 저지 1019번: 책 페이지 (골드1) 키워드 수학, 나머지 연산(모듈러) 풀이 접근법 SWEA 5604번: [Professional] 구간 합 문제와 거의 유사한 문제이다. 구하는 배열은 같고 구간 합만 계산하지 않는다는 차이가 있다. N이 10^9이하의 자연수이기 때문에 O(N)보다도 더 빠른 알고리즘이 필요하다. N자리의 수가 있다고 할 때, 각 자리마다 떼어서 0~9가 몇 개 나왔는지를 살핀다. 예를 들어 4자리 수의 0~9 출현 횟수를 구하고 싶다면, 일의 자리를 0~9로 변형시켜서 개수를 센다. 이 과정을 일의 자리부터 천..

문제 풀이 날짜: 2023.10.13 포스트 작성일: 2023.10.16 * 학습 목적으로 작성하는 글입니다. 풀이가 정석적이지 못할 수도 있습니다. 문제 출처 백준 온라인 저지 24230번: 트리 색칠하기 (골드5) 키워드 트리의 특징, BFS 풀이 접근법 단순 DFS로 탐색하면 시간 초과가 난다. 또, 트리를 양방향 그래프로 생성하지 않으면 반례가 생기므로 주의한다. 그래프로 구현한 트리를 루트부터 탐색하면서, 답안으로 주어진 색과 동일하다면 넘어가고, 동일하지 않다면 부모노드의 색깔로 색칠하며 리프 노드까지 탐색한다. 자식 노드를 칠할 때는, 부모 노드의 색깔을 가져다가 쓴다.(colors[child] = prevColors[parent]) 이때, 각 노드마다 부모노드의 색을 기억해야 하므로 별도의..

문제 풀이 날짜: 2023.10.11 포스트 작성일: 2023.10.16 * 학습 목적으로 작성하는 글입니다. 풀이가 정석적이지 못할 수도 있습니다. 문제 출처 SWEA 14510번: 나무 높이 (D2) 키워드 그리디, 수학, 나머지 연산(모듈러) 풀이 접근법 모든 나무가 성장해야 하는 높이 (remains[i]) 를 2로 나눈 몫은 필요한 짝수 날짜의 수이고, 2로 나눈 나머지는 필요한 홀수 날짜의 수이다. 이때 홀수 날짜와 짝수 날짜의 수는 항상 쌍을 이루어야 한다. (예: 홀수 날짜에 3회 물을 주었다면 짝수 날짜에도 3회 물을 주어야 한다. 쌍을 이루지 않는 날짜는 하루를 쉬고 건너서 물을 준 것이다. (편의상 건너뛴 날을 ∅로 표현한다.) 그런데, 짝수 날짜(∅ + 2m)는 '연달아서 물을 준 ..

문제 풀이 날짜: 2023.10.11 포스트 작성일: 2023.10.16 * 학습 목적으로 작성하는 글입니다. 풀이가 정석적이지 못할 수도 있습니다. 문제 출처 백준 온라인 저지 17182번: 우주 탐사선 (골드3) 키워드 플로이드-워샬, DFS 풀이 접근법 입력 그래프가 인접 행렬로 주어지며, 모든 행성을 탐사하기 위한 최소 시간이 필요하므로 플로이드-워샬로 풀이한다. 그런데 여기서 플로이드 워샬로 구해진 결과물은 단순히 각 점으로 가는 최소 시간(최단 경로)일 뿐이다. 우리가 구하고 싶은 것은 시작점부터 모든 정점을 지나는 최소 시간이다. 따라서 0부터 모든 정점을 지나는 경로는 DFS(그래프 탐색)로 구해준다. (N은 최대 10) 시작점 K는 문제에서 주어진다. 중복 경우를 제거하기 위해 시작점을 ..

문제 풀이 날짜: 2023.10.10 포스트 작성일: 2023.10.16 * 학습 목적으로 작성하는 글입니다. 풀이가 정석적이지 못할 수도 있습니다. 문제 출처 구현, 시뮬레이션 키워드 백준 온라인 저지 17144번: 미세먼지 안녕! (골드4) 풀이 접근법 행렬의 모든 점을 중에서 미세먼지의 위치(Point)를 List로 취합하여 해당 부분을 중심으로 인접한 네 방향으로 확산시킨다. 단, List를 사용하면 메모리를 더 많이 차지하므로 행렬의 모든 점(R * C)을 탐색하는 것보다 효율적일 수도, 비효율적일 수도 있다. 미세먼지를 4방 확산시키면서, 미세먼지가 위치한 곳을 다시 List에 취합한다. 기존 미세먼지가 사라졌을 수도 있고, 기존에는 없었던 위치에 새 미세먼지가 생겼을 수도 있기 때문이다. 단..

문제 풀이 날짜: 2023.10.05 포스트 작성일: 2023.10.16 * 학습 목적으로 작성하는 글입니다. 풀이가 정석적이지 못할 수도 있습니다. 문제 출처 SWEA 5656번: [모의 SW 역량테스트] 벽돌 깨기 키워드 구현, 시뮬레이션 풀이 접근법 기본 절차 W개의 벽돌 중 깨트릴 것을 고른다. 해당 벽돌을 깨트리고 newMatrix에 기록한다. 벽돌을 바닥으로 내린다. 다음 depth에 복사된 newMatrix를 인자로 넘겨준다. 리턴받는다면 원본 matrix를 이용하여 새 결과를 계산한다. 기저조건 더이상 깰 벽돌이 없다면 minCount를 0으로 갱신하고 true(최적해를 찾음)를 리턴한다. 모든 구슬을 다 던졌다면 잔여 벽돌 수도 minCount를 갱신하고 false(더 탐색해야 함)를 리..

문제 풀이 날짜: 2023.08.02 포스트 작성일: 2023.10.12 * 학습 목적으로 작성하는 글입니다. 풀이가 정석적이지 못할 수도 있습니다. 문제 출처 백준 온라인 저지 2042번 : 구간 합 구하기 (골드1) 키워드 세그먼트 트리, 부분 합 풀이 접근법 단순 배열로 풀이하려고 하면 시간 초과가 발생한다. 배열은 선형 탐색을 진행하기 때문에 O(N) 시간을 소모하기 때문이다. 따라서 더욱 빠른 자료 구조인 세그먼트 트리를 이용하여 풀이한다. 세그먼트 트리란, 트리의 특징을 이용하여 구간 합의 계산이나 값의 수정을 O(logN) 시간만에 해결할 수 있는 자료구조이다. 트리의 특성 상 값 초기화나 검색은 재귀로 구현한다. 트리의 리프노드에 초기값들을 저장하고, 위로 올라갈 수록 더 큰 부분합이 저장..

문제 풀이 날짜: 2023.10.05 포스트 작성일: 2023.10.05 * 학습 목적으로 작성하는 글입니다. 풀이가 정석적이지 못할 수도 있습니다. 문제 출처 SWEA 5658번: [모의 SW 역량테스트] 보물상자 비밀번호 키워드 시뮬레이션, 배열 풀이 접근법 보물 상자에 적힌 숫자로 만들 수 있는 모든 수 중, K번째로 큰 수를 구하기 각 변에 있는 세 자리 문자를 조합하면 16진수 수가 하나 나온다. (예: B3B) 그런데 상자의 변이 총 4개이므로 한 회전당 4가지 16진수가 나온다. (1B3, B3B, 81F, 75E) 그리고 이것을 0, 1, 2, ..., N / 4 - 1 회전시킬 수 있으므로 최대 ( N / 4 - 1) * 4 = N - 4가지 16진수를 얻을 수 있다. 이 중 K번째로 큰..