'알고리즘, 자료구조' 카테고리의 글 목록 (4 Page)

[백준] 9012. 괄호 (Kotlin)

문제 https://www.acmicpc.net/problem/9012 9012번: 괄호 괄호 문자열(Parenthesis String, PS)은 두 개의 괄호 기호인 ‘(’ 와 ‘)’ 만으로 구성되어 있는 문자열이다. 그 중에서 괄호의 모양이 바르게 구성된 문자열을 올바른 괄호 문자열(Valid PS, VPS)이라고 www.acmicpc.net 풀이 0. 문제 해석 괄호는 짝이 맞아야 하므로 스택을 활용해야 한다. 여는 괄호면 스택에 추가한다. 닫는 괄호일 때, 스택이 비어있거나 스택에서 pop 하여 그 값이 닫는 괄호면 NO 리턴 전체 괄호 검사 후 스택에 남아있는 문자가 있을 경우 NO 리턴 2,3번에서 리턴되지 않았을 경우 YES 리턴 1. 전체 코드 // [백준] 9012. 괄호 (Kotlin)..

알고리즘, 자료구조/백준 2022. 3. 4. 11:22

[백준] 3078. 좋은 친구 (Kotlin)

문제 https://www.acmicpc.net/problem/3078 3078번: 좋은 친구 첫째 줄에 N과 K가 주어진다. (3 ≤ N ≤ 300,000, 1 ≤ K ≤ N) 다음 N개 줄에는 상근이네 반 학생의 이름이 성적순으로 주어진다. 이름은 알파벳 대문자로 이루어져 있고, 2글자 ~ 20글자이다. www.acmicpc.net 0. 문제 해석 인덱스 0부터 시작점으로 하여 최대 k 만큼의 학생들과 이름의 길이를 비교해가며 길이가 같을경우를 세준다. 시작점을 하나씩 늘려가며 마지막 인덱스가 시작점이 될 때 까지 반복한다. 위와 같이 완전탐색으로 진행한다면, 구현 자체는 어렵지 않다. 하지만 학생 수가 최대 300000 이므로 일반적인 반복으로 탐색하면 시간초과가 발생한다. 풀이 1 (오답) imp..

알고리즘, 자료구조/백준 2022. 3. 3. 13:05

[백준] 4485. 녹색 옷 입은 애가 젤다지? (Java)

문제 https://www.acmicpc.net/problem/4485 4485번: 녹색 옷 입은 애가 젤다지? 젤다의 전설 게임에서 화폐의 단위는 루피(rupee)다. 그런데 간혹 '도둑루피'라 불리는 검정색 루피도 존재하는데, 이걸 획득하면 오히려 소지한 루피가 감소하게 된다! 젤다의 전설 시리즈의 주 www.acmicpc.net 풀이 0. 문제 해석 일반적인 다익스트라 문제로, bfs를 상하좌우로 진행하면서 그 경로의 최소 금액을 갱신해준다. 1. 초기화 동굴정보, 최소 금액을 저장할 배열과 상하좌우 탐색을 위한 델타를 정의해주고 동굴정보, dist 정보를 초기화해준다. 2. BFS 상하좌우 BFS를 진행하면서 dist에 저장된 값보다 작을 경우 갱신해준다. 3. 전체 코드 // [백준] 4485...

알고리즘, 자료구조/백준 2022. 3. 1. 20:01

[백준] 10816. 숫자 카드 2 (Java)

문제 https://www.acmicpc.net/problem/10816 10816번: 숫자 카드 2 첫째 줄에 상근이가 가지고 있는 숫자 카드의 개수 N(1 ≤ N ≤ 500,000)이 주어진다. 둘째 줄에는 숫자 카드에 적혀있는 정수가 주어진다. 숫자 카드에 적혀있는 수는 -10,000,000보다 크거나 같고, 10, www.acmicpc.net 풀이 0. 문제 해석 숫자 카드의 범위가 -10,000,000 ~ 10,000,000 이므로 일반적인 카운팅 정렬 방식으로 숫자를 카운팅 할 수 없다. 따라서 해시맵 또는 이진 탐색으로 해결해야한다. 1. 전체 코드 // [백준] 10816. 숫자 카드 2 import java.io.BufferedReader; import java.io.IOException..

알고리즘, 자료구조/백준 2022. 2. 28. 22:57

[알고리즘] 자바 최소 신장 트리(MST) 구하기 - 크루스칼, 프림 알고리즘 (백준 1197)

최소 신장 트리란? ▶ 그래프의 모든 정점을 사이클 없이 잇는(신장 트리)트리에서 간선의 가중치의 합이 최소가 되는 트리 크루스칼 알고리즘이란? ▶ 간선 중심으로 최소 신장 트리를 구하는 알고리즘 (간선이 적을 때 프림 알고리즘보다 유리) 간선들을 가중치의 오름차순 정렬하여 가장 작은 간선 선택 그 간선이 지금까지 만들어진 MST와 사이클을 형성한다면 제외, 아니면 MST에 추가 모든 간선에 대해 반복 1197번: 최소 스패닝 트리 첫째 줄에 정점의 개수 V(1 ≤ V ≤ 10,000)와 간선의 개수 E(1 ≤ E ≤ 100,000)가 주어진다. 다음 E개의 줄에는 각 간선에 대한 정보를 나타내는 세 정수 A, B, C가 주어진다. 이는 A번 정점과 B번 정점이 www.acmicpc.net 예시 코드 (..

알고리즘, 자료구조/기본 2022. 2. 23. 16:27

[백준] 14502. 연구소 (Java)

문제 : https://www.acmicpc.net/problem/14502 14502번: 연구소 인체에 치명적인 바이러스를 연구하던 연구소에서 바이러스가 유출되었다. 다행히 바이러스는 아직 퍼지지 않았고, 바이러스의 확산을 막기 위해서 연구소에 벽을 세우려고 한다. 연구소는 크 www.acmicpc.net 풀이 0. 문제 해석 바이러스가 퍼지는 범위를 DFS나 BFS로 구현하여, 최종적으로 변하지 않은 안전 영역을 체크해야 하는 문제이다. 단, 벽이 존재하면 그 벽으로는 퍼져나갈 수 없으며, 벽을 무조건 빈칸에 3개 세워야 한다. 전체 탐색을 통해 임의의 빈칸에 벽을 3개 세우는 모든 경우의 수를 구한다. 벽이 3개 세워 졌을 때, 복사본 배열을 하나 생성하여 그 배열에서 DFS를 진행한다. 모든 경우..

알고리즘, 자료구조/백준 2022. 2. 20. 21:18

[백준] 10163. 색종이 (Java)

문제 https://www.acmicpc.net/problem/10163 10163번: 색종이 평면에 색깔이 서로 다른 직사각형 모양의 색종이 N장이 하나씩 차례로 놓여진다. 이때 색종이가 비스듬하게 놓이는 경우는 없다. 즉, 모든 색종이의 변은 서로 평행하거나, 서로 수직이거나 둘 www.acmicpc.net 풀이 0. 문제 해석 일반적인 구현문제로 색종이가 번호 순으로 위로 쌓이므로 평면 배열 (1001 * 1001) 을 정의해주고 1번 색종이의 포함 범위를 다 1로, 2번 색종이의 포함 범위를 다 2로 변경하는 작업을 반복하면서 아래 번호 색종이를 덮어가면 차지하는 면적을 구할 수 있다. 1. 전체 코드 // [백준] 10163. 색종이 (Java) import java.io.BufferedRead..

알고리즘, 자료구조/백준 2022. 2. 17. 20:41

[백준] 14889. 스타트와 링크 (Java)

문제 https://www.acmicpc.net/problem/14889 14889번: 스타트와 링크 예제 2의 경우에 (1, 3, 6), (2, 4, 5)로 팀을 나누면 되고, 예제 3의 경우에는 (1, 2, 4, 5), (3, 6, 7, 8)로 팀을 나누면 된다. www.acmicpc.net 풀이 1 0. 문제 해석 두 팀으로 나눠야 하므로 인원이 4명일 경우 4C2 , 나머지 2명 로 나뉠 것이고 6명이면 6C3, 나머지 3명 으로 나뉠것이다. 이제 나뉜 팀들의 능력치의 합의 차이가 최소가 되는 값을 찾는다. 즉, 위와 같은 알고리즘을 코드로 구현하면 되는데, 조합의 수가 계속 늘어날수록 반복해야 하기 때문에 재귀 방식으로 조합을 사용한다. 1. 능력치 입력 2. 조합 생성 재귀방식으로 조합을 구현..

알고리즘, 자료구조/백준 2022. 2. 14. 22:52

[알고리즘] 자바 순열, 중복순열, 조합, 중복조합 재귀로 구현하기

1️⃣ 순열 서로 다른 n개중에 r개를 선택하는 경우의 수 순서 O 경우의 수 : n! / (n-r)! // 순열 public static void permutation(ArrayList list, int count) { // 다 뽑았을 때 if (count == 0) { System.out.println(list); perCount++; return; } for(int i = 0; i < n; i++) { if(list.contains(arr[i])) { continue; } list.add(arr[i]); permutation(list, count - 1); // 뽑을 때 마다 count - 1 list.remove(list.size() - 1); // 재귀 위해 마지막에 넣은 원소 제거 } } ar..

알고리즘, 자료구조/기본 2022. 2. 14. 21:11

[백준] 13305. 주유소 (Java)

문제 https://www.acmicpc.net/problem/13305 13305번: 주유소 표준 입력으로 다음 정보가 주어진다. 첫 번째 줄에는 도시의 개수를 나타내는 정수 N(2 ≤ N ≤ 100,000)이 주어진다. 다음 줄에는 인접한 두 도시를 연결하는 도로의 길이가 제일 왼쪽 도로부터 N-1 www.acmicpc.net 풀이 0. 문제 해석 처음 위치에선 주유를 무조건 해야하므로 처음 위치의 가격을 기준으로 놓고, 이후의 도시들의 가격을 순서대로 비교하여 기준점보다 싼 도시가 있을 때, 그 도시까지의 거리만큼만 주유하고 그 도시에 간다음, 그 도시를 기준점으로 정하고 다시 이 작업을 반복하면 최솟값을 구할 수 있다. 위 그림에서는 시작점의 기름값이 5, 그 다음 도시의 기름값이 2 이므로 그 ..

알고리즘, 자료구조/백준 2022. 2. 13. 23:52

경험의 기록