프로그래민👨‍💻

이 문제는 위상정렬(Topoologicl Sort)를 이용하는 문제이다. 위상정렬을 이용하기 위해선 DAG(Directed Acyclic Graph, 유향 싸이클없는 그래프)를 만족해야지 사용할 수 있다. 위상정렬이란 DAG의 정점들을 쭉 나열하였을 때 왼쪽에서 오른쪽(한바향)으로만 모든 간선이 이동하는 모양을 가지도록 정렬되게 하는 알고리즘이다. 즉 다음과 같은 모양으로 모든 정점이 정렬되는 것이다. 이러한 위상정렬을 하기위해선 우선적으로 싸이클이 없는 DAG임을 확인하고, 그다음 indegree배열을 사용하여 자신으로 들어오게 되는 간선의 수를 저장한다. 그 후 queue를 이용하여 indegree[index]=0이 되면 queue에 offer해주고 인접리스트를 돌면서 indegree들을 하나씩 줄여..

조합과 BFS를 이용하여 반복하는 문제이다. 이 문제는 조합을 이용하여 궁수의 위치 3가지를 뽑고, 그 위치에서 BFS를 이용하여 거리 D안에 있는 적들을 PriorityQueue에 집어 넣어 계속 쳐치해가며 map상에 모든 적이 사라질때의 count 값의 최대값을 출력해주는 방식으로 해결하였다. 구현이 어렵지는 않으나 조건이 많으므로 천천히 하나하나 구현하는 것이 필요한 문제이다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64..

소수를 찾아 구간합을 구하는 문제이다. 소수를 찾는 알고리즘은 에라토스테네스의 체를 사용하였고, 구간합에 있어선 투포인터를 사용하여 쉽게 풀 수 있던 문제이다. 이 문제에서 소수의 갯수를 모르기때문에 list를 사용하여 구하였다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 package boj2; import java.io.BufferedReader; import java.io.InputStreamReader; import java.util..

이 문제는 두개의 포인터를 움직이며 구간을 구하는 투포인터를 사용하는 문제이다. 투포인터는 low, high 두지점을 0 부터 시작하여 특정조건에 따라 움직이는 알고리즘이다. 이 문제에선 구간합이기에 sum이라는 변수를 이용하여 low, high를 움직여준다. 다음과 같은 조건 While루프를 움직인다. 1-1. 구간합 sum이 목표 M보다 크거나 같다면 sum-=arr[low], low++ 1-2. high가 맨끝인 N과 같다면 break 1-3. 구간합 sum이 목표 M보다 작다면 sum+=arr[high], high++ 2. 구간합이 sum이 목표 M과 같다면 구간 [low, high)에서 정답을 가짐 상당히 자주 쓰이는 알고리즘이고 활용 N^2을 N으로 줄이는 알고리즘이기에 숙달이 필요할것 같다...

BFS를 이용한 문제이다. 이 문제에선 다음에 갈 점들의 우선순의가 거리>위쪽>왼쪽 으로 주어져있으므로 다음에 갈점을 위해 PriorityQueue를 사용하였다. BFS를 한번 돌때마다 pq에 갈점들을 쭉저장하고 pq가 없다면 멈추는 형식으로 구현하였다. 문제를 이해하는데 오래걸렸다. 문제를 꼼꼼히 읽는 습관이 필요할 것 같다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 ..

구현하는데 있어 상당히 복잡하게 구현을 이룬 문제였다. 이문제는 최소성과 유일성을 만족시키는 후보키를 구하는 문제이다. 맨처음 컬럼의 수를 확인했는데 최대 8이기 때문에 조합으로 풀생각을 하였다. 전체 N개에서 1개부터 N개까지 선택하는 모든 경우를 다따져보았다. 그리고 그 상황에서 hashSet을 이용하여 유일성을 확인하였고, 또다른 hashSet을 이용하여 최소성을 만족하는지 확인하였다. hashSet이 상당히 여러개가 쓰였기에 구현하는데 있어서 많이 복잡하였다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48..

캐시를 직접 구현하는 문제였다. 여기선 캐시에 있어 LRU를 사용하는데 LRU는 queue자료구조와 상당히 유사한 구조를 취하고 있다. 그래서 queue를 이용하여 hit & miss 경우를 나누어 구현하였다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 package programmers; import java.util.LinkedList; import java.util.Queue; public class Solution_2018카카오_캐시 { public static void main(String[] args) { i..

해밀턴 순환회로, A정점에서 시작하여 모든 정점을 최소비용으로 돌아 A정점으로 돌아오는 문제이다. 다른 말로는 TSP, 외판원 순환 문제라고 한다. 이 문제는 다양한 풀이 방법으로 접근 할 수 있지만 N의 값이 12 이하로 주어졌으므로 백트래킹을 이용한 완탐을 사용해보았다. 단, 순열의 완탐을 돌때 첫번째 점(0)을 제외한 N-1개의 순열을 구하고 이때 마지막에 해당하는 점에서 첫번째점(0)으로의 경로가 존재하는 경우 최종답을 확인해주는 방식으로 구해준다. 또한 방문시에 최저값을 갱신할수 있을때만 방문하는 조건을 사용하여 시간을 줄였다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 3..

이 문제는 유니온파인드를 사용하는 문제이다. 유니온파인드를 사용하고 같은 그룹안에 몇개의 원소가 있는지 구하는 문제이다. 이 문제는 주의할점이 있다. 바로 입력의 형태가 문자열의 형태로 들어오기때문에 HashMap을 이용하여 이름을 인덱싱해주는 작업이 필요하다. 인덱싱을 해준후 count라는 배열을 이용하여 union할때마다 원소를 합쳐주는 과정을 거쳐 최종 결과를 출력해주면 된다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64..

이 문제는 여지껏 배운 다양한 알고리즘을 거의다 사용해야 풀 수 있다. 다음과 같은 로직으로 구현하였다. 1. BFS 또는 DFS 를 이용하여 섬을 찾고, 1부터 차례대로 섬에 대해 인덱싱을 해주기 2. 섬의수C2 인 조합을 이용하여 두개의 섬을 고르고, 가장 자리에 대해서 DFS를 이용하여 직선경로 찾기 3. 찾은 직선 경로에 대해 그래프의 형태를 만들기 4. 만든 그래프에 대해 모든 정점을 포함하며 정점보다 하나 적은 간선을 선택하게 되는 MST를 만들기 4-1. UnionFind를 이용한 간선 기준 Kruskal알고리즘 사용 4-2. PriorityQueue를 이용한 정점 기준 Prim 알고리즘 사용 다양한 알고리즘을 한번에 적용 시켜야 했던 문제이고, 여러가지를 다시 복습할 수 있어던 기회여서 좋..