'알고리즘, 자료구조/백준' 카테고리의 글 목록 (2 Page)

[백준] 1504. 특정한 최단 경로 (Kotlin)

문제 https://www.acmicpc.net/problem/1504 1504번: 특정한 최단 경로 첫째 줄에 정점의 개수 N과 간선의 개수 E가 주어진다. (2 ≤ N ≤ 800, 0 ≤ E ≤ 200,000) 둘째 줄부터 E개의 줄에 걸쳐서 세 개의 정수 a, b, c가 주어지는데, a번 정점에서 b번 정점까지 양방향 길이 존 www.acmicpc.net 풀이 0. 문제 해석 다익스트라 응용 문제이다. 두 정점을 반드시 지나는 최단경로는 시작점 -> v1 -> v2 -> n 시작점 -> v2 -> v1 -> n 두가지가 존재한다. 따라서 첫번째 경우엔 시작점 -> v1 / v1 -> v2 / v2 -> n 이런식으로 구간을 끊어서 다익스트라를 통해 최단거리를 구한 후 합산한다. 두번째도 동일하고, ..

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

[백준] 2581. 소수 (Kotlin)

문제 https://www.acmicpc.net/problem/2581 2581번: 소수 M이상 N이하의 자연수 중 소수인 것을 모두 찾아 첫째 줄에 그 합을, 둘째 줄에 그 중 최솟값을 출력한다. 단, M이상 N이하의 자연수 중 소수가 없을 경우는 첫째 줄에 -1을 출력한다. www.acmicpc.net 풀이 0. 문제 해석 2021.03.21 - [알고리즘, 자료구조/기본] - [알고리즘] 소수 구하기 알고리즘 (에라토스테네스의 체) [알고리즘] 소수 구하기 알고리즘 (에라토스테네스의 체) 소수는 약수로 1과 자기자신만을 가지는 수이다. 즉, 소수의 배수들은 전부 소수를 약수로 가지기 때문에, 소수가 아니다. 그러므로, 소수를 찾고 싶다면 범위내의 소수의 배수들을 전부 제거하 hanyeop.tisto..

알고리즘, 자료구조/백준 2022. 3. 21. 23:24

[백준] 3273. 두 수의 합 (Kotlin)

문제 https://www.acmicpc.net/problem/3273 3273번: 두 수의 합 n개의 서로 다른 양의 정수 a1, a2, ..., an으로 이루어진 수열이 있다. ai의 값은 1보다 크거나 같고, 1000000보다 작거나 같은 자연수이다. 자연수 x가 주어졌을 때, ai + aj = x (1 ≤ i < j ≤ n)을 만족하는 www.acmicpc.net 풀이 0. 문제 해석 주어지는 정수들은 서로 다르므로 HashSet을 이용하는 방법과 정렬 후 투 포인터 알고리즘을 이용하는 방법 두가지로 풀 수 있다. 1. 전체 코드 (HashSet) // [백준] 3273. 두 수의 합 (Kotlin) import java.io.BufferedReader import java.io.InputStre..

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

[백준] 17298. 오큰수 (Kotlin)

문제 https://www.acmicpc.net/problem/17298 17298번: 오큰수 첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄에 수열 A의 원소 A1, A2, ..., AN (1 ≤ Ai ≤ 1,000,000)이 주어진다. www.acmicpc.net 풀이 0. 문제 해석 스택을 활용해야 하는 것은 알겠는데 어떻게 사용해야 할지 몰라 헤맨 문제이다. 수열을 리스트에 저장한다. 리스트의 첫번째 원소의 인덱스부터 하나하나씩 스택에 인덱스 값을 push한다. 2번 과정에서 push하기 전에, 그 값이 오큰수라면 pop하고 그 pop한 인덱스 값에 해당하는 리스트의 값을 오큰수로 변경해준다. 반복이 종료된 후 스택에 남아있는 인덱스는 오큰수를 찾지 못한 위..

알고리즘, 자료구조/백준 2022. 3. 15. 23:02

[백준] 1655. 가운데를 말해요 (Kotlin)

문제 https://www.acmicpc.net/problem/1655 1655번: 가운데를 말해요 첫째 줄에는 백준이가 외치는 정수의 개수 N이 주어진다. N은 1보다 크거나 같고, 100,000보다 작거나 같은 자연수이다. 그 다음 N줄에 걸쳐서 백준이가 외치는 정수가 차례대로 주어진다. 정수는 -1 www.acmicpc.net 풀이 0. 문제 해석 하나의 우선순위큐를 활용하여 그 큐의 가운데만큼 pop하고 offer 하는 과정을 반복하면 결과를 구할 수 있지만, 이 과정은 매우 비효율적으로 시간초과가 발생한다. 해결방법을 모색해보다가 https://dragon-h.tistory.com/6 님의 글을 참고하였다. 내림차순 우선순위 큐(MaxHeap) , 오름차순 우선순위 큐(MinHeap) 2개 선언..

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

[백준] 10026. 적록색약 (Kotlin)

문제 https://www.acmicpc.net/problem/10026 10026번: 적록색약 적록색약은 빨간색과 초록색의 차이를 거의 느끼지 못한다. 따라서, 적록색약인 사람이 보는 그림은 아닌 사람이 보는 그림과는 좀 다를 수 있다. 크기가 N×N인 그리드의 각 칸에 R(빨강), G(초록) www.acmicpc.net 풀이 0. 문제 해석 색약인 경우와 아닌 경우를 각각 DFS 를 통해 탐색한다. 색약은 R,G를 구분하지 못하므로 R = 1, G = 2, B = 4로 입력받고 그 차이가 1 이하일때만 탐색하도록 하였다. 1. 전체 코드 // [백준] 10026. 적록색약 (Kotlin) import java.io.BufferedReader import java.io.InputStreamReader ..

알고리즘, 자료구조/백준 2022. 3. 9. 19:56

[백준] 1062. 가르침 (Kotlin)

문제 https://www.acmicpc.net/problem/1062 1062번: 가르침 첫째 줄에 단어의 개수 N과 K가 주어진다. N은 50보다 작거나 같은 자연수이고, K는 26보다 작거나 같은 자연수 또는 0이다. 둘째 줄부터 N개의 줄에 남극 언어의 단어가 주어진다. 단어는 영어 소문 www.acmicpc.net 풀이 0. 문제 해석 모든 단어는 "anta" 로 시작하여 "tica" 로 끝나므로 최소 5글자(a,n,t,i,c) 이상은 알고 있어야 한다. 위 5글자를 포함하여 k개의 글자를 포함하는 조합을 생성한다. 그 조합들로 만들 수 있는 단어가 몇가지인지 탐색하여 최대값을 찾는다. 1. 전체 코드 // [백준] 1062. 가르침 (Kotlin) import java.io.BufferedRe..

알고리즘, 자료구조/백준 2022. 3. 6. 23:31

[백준] 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

경험의 기록