[BOJ] - 게리맨더링 / 17471번 (Java)

[BOJ] - 게리맨더링 / 17471번 (Java) [BOJ] - 게리맨더링 / 17471번 (Java) 1. 문제 접근 총 N개의 구역(노드)이 주어지고, 주어진 구역에 대해 인구수 차이가 최소가 되도록 2개의 영역으로 분할하였을 때 인구수의 차이를 구하면 된다. 조건은 다음과 같다. 각 구역은 두 선거구 중 하나에 포함되어야 한다. 선거구는 구역을 적어도 하나 포함해야 하고, 한 선거구에 포함되어 있는 구역은 모두 연결되어 있어야 한다. 떠올린 방법은 조합(Combination)을 통한 완전 탐색이다. 입력값의 제한을 보게 되면, "2 ≤ N ≤ 10" 라고 명시되어있다. 따라서 최대 값인 N = 10일 때를 보면, 구역을 2개로 나누어야하고, 하나의 영역에는 한 개 이상의 구역이 포함 되어야하므로..

• format_list_bulleted 알고리즘
• · 2024. 2. 22.
• textsms

[BOJ] - 암호 만들기 / 1759번 (Java)

[BOJ] - 암호 만들기 / 1759번 (Java) [BOJ] - 암호 만들기 / 1759번 (Java) 1. 문제 접근 C개의 문자들이 주어질 때, L개의 문자로 이루어진 암호 문자열을 만들면 된다. 이 때, 1개 이상의 모음, 2개 이상의 자음이 포함되어야하며, 암호문은 반드시 증가하는 순서로 배열되어있다는 것이다. 일반적인 조합(Combination)문제에 대해 약간의 추가적인 조건들이 추가된 문제라고 생각한다. `암호문은 반드시 증가하는 순서로 배열`라는 조건을 이용하여 조합을 구성하기 전에 주어진 문자 배열을 오름차순으로 정렬해야한다. 또한 기저조건(`selectIdx == L`)을 만족할 경우, 추가적으로 L개의 문자열을 조회하며 모음, 자음의 개수가 조건을 만족하는지 여부를 확인해야한다. ..

• format_list_bulleted 알고리즘
• · 2024. 2. 21.
• textsms

[BOJ] - ABCDE / 13023번 (Java)

[BOJ] - ABCDE / 13023번 (Java) [BOJ] - ABCDE / 13023번 (Java) 1. 문제 접근 A-B-C-D-E와 같은 친구 관계가 있는지 확인하는 문제다. DFS를 이용하여 해결할 수 있다. 0번 노드부터 N-1번 노드까지 순차적으로 DFS의 시작점으로 하여 탐색을 진행한다. `isCorrectConnection()`메소드를 호출할 때 탐색을 시작할 노드(`nodeNum`)과 현재 연결된 친구 수(`0`)을 함께 전달한다. // 0번 정점부터 N-1번 정점까지 DFS 순회 for (int nodeNum = 0; nodeNum < N; ++nodeNum) { isVisited = new boolean[N]; isCorrectConnection(nodeNum, 0); // 이미..

• format_list_bulleted 알고리즘
• · 2024. 2. 21.
• textsms

[BOJ] - 회전 초밥 / 15961 (Java)

[BOJ] - 회전 초밥 / 15961 (Java) [BOJ] - 회전 초밥 / 15961 (Java) 1. 문제 접근 주어진 회전 초밥 벨트에서 먹을 수 있는 초밥의 가짓수의 최댓값을 구하면 된다. 입력값을 살펴보면 2 ≤ N ≤ 3,000,000, 2 ≤ d ≤ 3,000, 2 ≤ k ≤ 3,000 (k ≤ N), 1 ≤ c ≤ d이다. 초밥 벨트 위에 놓여질 수 있는 초밥의 최대값은 300만, 선택할 수 있는 초밥 개수의 최대값은 3000으로 모든 구간에 대해 초밥의 가지 수를 계산하게 되면 대략 90억 번의 연산이 발생할 수 있다. 따라서 한 번의 순회만에 초밥 가지 수의 최대값을 구해야 한다. 한 번의 순회만에 구하기 위해 슬라이딩 윈도우와 `Map`을 사용해서 풀었다. `front`, `rea..

• format_list_bulleted 알고리즘
• · 2024. 2. 20.
• textsms

[BOJ] - ⚾(야구) / 17281번 (Java)

[BOJ] - ⚾(야구) / 17281번 (Java) [BOJ] - ⚾(야구) / 17281번 (Java) 1. 문제 접근 각 선수가 각 이닝에서 어떤 결과를 얻는지 미리 알고 있으며, 가장 많은 득점을 하는 타순을 찾고, 그 때의 득점을 구하면 된다. 총 9명의 선수가 존재하고, 이 때 1번 선수는 4번 타자로 고정이다. 4번 타자가 고정이므로 총 8명의 선수를 줄세우는 경우의 수(8! = 40,320)가 존재한다. 따라서 제한 시간 내에 실행할 수 있으므로, permutation(순열)을 이용해 모든 타자의 순번을 결정하면 된다. 모든 타순을 결정했다면, 이는 기저조건이 되고 모든 이닝을 순회하며 점수 계산을 진행하면 된다. 예시로 2루타의 경우 점수 계산 방법은 아래와 같다. case ANTA_2:..

• format_list_bulleted 알고리즘
• · 2024. 2. 20.
• textsms

[BOJ] - 적록색약 / 10026번 (Java)

[BOJ] - 적록색약 / 10026번 (Java) [BOJ] - 적록색약 / 10026번 (Java) 1. 문제 접근 적록색약인 사람이 봤을 때와 아닌 사람이 봤을 때 구역의 수를 구하면 된다. 적록색약인 사람의 경우, `R`, `G`의 영역에 대해 동일한 영역으로 판별하는 로직만 추가하면 기본적인 BFS를 이용한 Flood Fill 알고리즘과 동일하다. 플러드 필(영어: flood fill) 혹은 시드 필(영어: seed fill)은 다차원 배열의 어떤 칸과 연결된 영역을 찾는 알고리즘이다. 출처 - [위키백과: 플러드 필] // 색 검증 if (color == 'R' || color == 'G') { // 적록 색약의 경우, B만 다른 색으로 인식 if (picture[tempRow][tempCol..

• format_list_bulleted 알고리즘
• · 2024. 2. 20.
• textsms