프로그래민👨‍💻

이 문제는 BFS를 응용하는 문제이다. 문제에서 a~f까지 키가 주어지는데 이것을 가지고 있는 상태에서 움직여야한다. 그래서 비트연산을 통하여 각 Pos클래스에 가지도록 변수 alp를 선언해주었고, 열쇠를 가진상태에서 방문또한 변화가있으므로 visit배열도 3차원으로 visit[R][C][1

비트연산을 이용하는 문제이다. 비트연산 | 을 이용하고 2진수로 바꿔주는 간단한 문제이다. 이문제에선 주의할점은 n의 크기만큼 문자열을 맞추기 위해 공백을 추가하는 작업이 필요한데 이작업이 없다면 테스트케이스에서 틀리는 부분이 존재한다. 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 programmers; public class Solution_2018카카오_비밀지도 { public static void main(String[] ..

이 문제는 위상정렬(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..