프로그래민👨‍💻

조합과 그래프탐색을 하는 시뮬레이션 문제이다. 이 문제를 접근할때 단순하게 생각하여 접근하였다. 일단 모든 도시들의 연결관계를 그래프를 이용하여 나타내주었고, 그후 도시들을 조합으로 1개부터 N/2개를 만큼 선택을 하였다. 그 후 같은 팀이된 도시들끼리 DFS로 이어져있는지 확인하였고 만일 같은팀이 전부 이어져있는 형태를 그린다면 그때의 인구수 차이를 체크해주었다. 다양한 것을 구현해야하고 구현하는 서순이 복잡하지만 천천히 하나씩 구현해보았다. 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 ..

knapsack 유형의 문제이다. 이 문제는 조합을 통하여 풀수 있는데 조합을 구현하는데 두가지 방법을 사용해보았다. 1번은 선택-비선택 재귀호출으로 구현하였고, 2번은 visit배열은 이용한 백트래킹 조합을 사용하여 구현하였다. 또한 두가지 방법모두 가지치기가 상당히 중요한 요소이므로 잘생각할 필요가 있다. 방법1 : 선택,비선택 재귀 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 package swea; import java.io.BufferedReader; import jav..

이문제는 조합을 이용하여 선택을 한다음 BFS를 사용하는 문제이다. 조합을 사용하여 바이러스의 위치를 뽑아주고, 그 다음 map에서 그위치를 활성화 시켜준 다음 BFS를 돌았다. 그 후 다시 map을 비활성화 시켜주는 작업을 하였다. 이 문제에서 현재 빈칸이 있는지 check를 할 때 맨처음에는 전체를 다보는 식으로 하였는데 시간초과의 결과를 얻었었다. 그래서 맨처음 입력받을때 빈칸의 갯수를 세어놓고 BFS를 돈다음 그 BFS를 도는 칸이 전체 빈칸의 갯수랑 같다면 true라고 생각해주고 답을 찾아주었다. 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 4..

조합과 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..

구현하는데 있어 상당히 복잡하게 구현을 이룬 문제였다. 이문제는 최소성과 유일성을 만족시키는 후보키를 구하는 문제이다. 맨처음 컬럼의 수를 확인했는데 최대 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..

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

조합과 BFS가 합쳐진 문제이다. 이 문제는 바둑판에서 0이 되는 곳의 위치 2개를 뽑는 조합을 사용한다음, 1로 둘러쌓인 2의 최대 갯수를 구하는 BFS문제이다. 이 문제에 주의할점은 2가 테두리 혹은 1로 만 둘러쌓여야 하는데 이과정에서 나는 flag변수 possible을 하나 선언하여 0이랑 인접해있으면 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 65 66 67 68 69 70 71 ..

구현할 것이 상당히 많은 문제였다. 기본적으로 벽이 갈수 있는 위치 3군대를 찾는 과정을 거치고 벽을 셋팅후 BFS하여 모든 0의 갯수를 세어주는 과정을 찾는 문제였다. 조합과 BFS를 연속하여 구현하기 때문에 빼먹을수 있는 부분이 많은 문제이므로 꼼꼼하게 함수로 나누어 코딩하는게 중요한 문제였다. 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 75 76 77 78 79 80..

이 문제는 조합을 사용하여 간단히 풀수있는 문제이다. (전체치킨집수)C(제한된치킨집수) 와 같은 조합식을 세우고 이대로 접근하여 풀고 그 상황에서의 치킨거리의 최솟값을 구하면 쉽게 풀 수 있는 문제이다. 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 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 package boj; impo..

간단해보이는 문제지만 다양한 개념들이 사용된 문제이다. 다음과 같은 개념들이 사용되었다. 모듈러연산의 특징 모듈려는 /을 제외한 +, -, * 에 대해서 다음과 같은 특징을 가진다. (a mod n + b mod n) mod n = (a + b) mod n (a mod n - b mod n) mod n = (a - b) mod n (a mod n * b mod n) mod n = (a * b) mod n 합동관계 두 a, b숫자가 n을 mod한 결과 값이 같다면 모듈러 합동관계라 한다. 즉, a mod n = b mod n의 관계를 a ≡ b (mod n)으로 표현할 수 있다. 페르마의 소정리 p가 소수이고 a가 p로 나누어지지 않는 정수이면 다음과 같은 특징을 가진다. a^p ≡ a (mod p) a^..