[SWEA] - 서로소 집합 / 3289번 (Java)

[SWEA] - 서로소 집합 / 3289번 (Java) [SWEA] - 서로소 집합 / 3289번 (Java) 1. 문제 접근 총 n개의 단일 원소를 갖는 집합에 대해 `0`(두 집합을 합치기), `1`(두 집합이 거로 같은 집합에 속하는지) 연산을 실행하고 `1`번 연산에 대해 결과를 출력하면 된다. 기본적인 Union Find 알고리즘이다. Union Find에는 총 3개의 연산이 존재한다 `makeSet()`: 초기 집합 상태를 만드는 연산 `union()`: 두 집합을 하나의 집합으로 합치는 연산 `getRoot()`: 특정 노드의 집합을 식별하는 연산 따라서 `0`번 입력이 들어오면 `union()`을, `1`번 연산이 들어오면 `getRoot()`연산을 통해 결과를 얻으면 된다. switch ..

• 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

[BOJ] - 치즈 / 2636 (Java)

[BOJ] - 치즈 / 2636 (Java) 1. 문제 접근 치즈가 모두 녹아서 없어지는 데 걸리는 시간과 모두 녹기 한 시간 전에 남아있는 치즈조각이 놓여 있는 칸의 개수를 구하면 된다. 해당 문제에서 고려할 점은 외부 공기에 노출되어있지 않은 치즈를 외부 공기에 노출되기 전까지 녹이면 안된다는 것이다. 따라서, "판의 가장자리에는 치즈가 놓여있지 않다"는 조건을 이용하여 1시간 단위로 [0, 0]부터 탐색을 시작, 외부 공기에 노출 된 치즈를 구한다. // 공기라면 그냥 큐에 추가 if (map[tempRow][tempCol] == 0) { q.offer(new Pos(tempRow, tempCol)); } else { // 치즈일 경우, 치즈 저장해두는 큐에 삽입 saveCheese.offer(ne..

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

[BOJ] - 줄세우기 / 2252번 (Java)

[BOJ] - 줄세우기 / 2252번 (Java) 1. 문제 접근 일부 학생들의 키를 비교한 결과가 주어졌을 때, 줄을 세우는 프로그램을 구현하면 된다. 일부 학생들의 키를 비교한 결과가 주어진다는 말은, 노드(학생)들 간의 간선에서 방향성이 있다는 의미이다. 1 3 2 3 위와 같이 입력이 주어질 경우, 간선의 방향은 1번 학생에서 3번 학생, 2번 학생에서 3번 학생으로 향한다. 따라서, 위상 정렬(topological sorting)을 사용해 Queue에서 노드를 poll할 때 마다 출력해주면 된다. 위상 정렬(topological sorting)은 유향 그래프의 꼭짓점들(vertex)을 변의 방향을 거스르지 않도록 나열하는 것을 의미한다. 2. 코드 package boj; import java.i..

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