프로그래민👨‍💻

MST 문제이다. 이 문제를 풀기 위해선 Kruskal 이나 Prim을 사용해야한다. 참고 이 문제를 두가지방법 모두 사용하여 풀어보았다. 첫번째로 Kruskal 알고리즘을 사용하였는데 , 정렬을 함에 있어 PriorityQueue를 사용하였고, 같은 팀임을 보기 위해 UnionFind를 같이 사용하였다. 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 7..

최소신장트리 즉, MST를 구하는 문제이다. 최소신장트리란 , 그래프에서 V개의 접점과 E개의 간선이 있을 때, V-1개의 간선으로 이루어진 트리로 싸이클이 생겨나지 않고, 방향이 없으며 간선들의 합이 최소일 때를 말한다. 구하는 대표적인 알고리즘으로는 Kruskal, Prim이 있다. ※그래프 정점V 와 간선E로 이루어진 연결관계를 모아 놓은 자료. 프로그래밍상 표현법은 다음과 같다. - 간선의 배열 : 정점과 정점의 연결정보인 간선을 모아놓음 - 인접 리스트 : 각 정점별로 연결된 정점의 정보를 모아놓음(ex. List[]) - 인접행렬 : 2차원 행렬에 각 정점과 정점간의 연결정보를 표시(ex. arr[][]) ※Kruskal 알고리즘 그래프에서 간선을 기준으로 MST를 찾고 싶을 때 사용하는 알고..

TSP문제 이다. N의 범위가 10이하이므로 순열을 사용하여 풀었다. perm라는 순열을 구하는 함수를 작성하였다. 여기서 arr라는 배열을 준비하여 각 인덱스 마다 도시의 번호로 지정하고, result라는 배열을 이용하여 도시들을 방문하는 경우의 수를 구하였다. result 배열이 전부 준비되었을 때 서로 도시끼리 갈 수 있는지 여부를 체크하면서 최종적으로 돌아오는 경우까지 계산하여 최종 답을 구하였다. 이 문제는 생각을 달리한다면 시간복잡도를 줄일 수 있는데, 그 경우는 시작 지점을 고정시키는 개념이다. 즉 0 1 2 3 4 0 과 1 2 3 4 0 1 은 동일한 연산이므로 첫번째 시작지점을 고정시켜서 동일한 계산을 반복안하게 하는 방법으로 시간복잡도를 줄일 수 있다. 1 2 3 4 5 6 7 8 9..

nextPermutation()을 구현하는 문제이다. 순열문제이다. 재귀적으로도 순열을 구현할 수 있으나, N의 범위를 고려하였을 때, 좋지 않은 방법이다. 이 문제는 c++에 존재하는 nextPermutation()을 구현하는 문제이다. c++은 구현되어 있기에 그냥 사용하면 몇줄로 끝나는 문제지만 java는 직접 구현해야 하기에 개념을 모른다면 까다로운 문제이다. nextPermutation()은 다음과 같은 로직을 따른다. 1. 배열의 뒤쪽부터 탐색하며 꼭대기(i)를 찾는다. 즉, 뒤에서 부터 탐색하며 부등호가 > 에서 < 되는 지점을 찾는다. 2. 꼭대기(i)기준으로 교환인덱스를 i-1로 잡고, 뒤에서부터 탐색하며 arr[i-1]

스택을 이용하여 비교하는 문제이다. 탑의 첫번째 부터 확인하며 스택이 비어있다면 0(벽), 만일 스택이 안비어있다면 스택의 top이 현재보다 크다면 top의 인덱스 출력 그렇지 않다면 top을 pop해주는 것을 반복해주며 최종적으로는 push를 계속 해주는 과정을 반복해주었다. 로직을 천천히 생각해봐야할 필요가 있는 문제였다. 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 package selfStudy.chap04; import java.io.BufferedReader; import java.io.Inpu..

이 문제는 BFS를 계속 반복하면서 문제에 주어진 조건대로 구현하는 시뮬레이션 문제이다. 문제를 다소 어렵게 생각했었지만, 꼼꼼히 읽어보니 있는 그대로 구현하면 되는 문제였다. 4개이상 똑같은 알파벳이 연결된 것이 있나 BFS를 이용하여 찾고, 폭파시킨다음 맵을 아래로 내리면서 계속 반복하는 문제이다. 맵을 끌어 내리는 함수는 mapDown() 이라는 함수를 이용하였는데, 맨 아래 행부터 시작해 '.'을 찾으면 위의 있는 문자와 바꾸어 주는 형식으로 구현하였다. 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..

소수를 구하는 방법은 크게 두가지가 있다. 1. 어떤수 N이 소수인지 판별하는 방법 특정수 N이 소수인지 확인하기 위해 i=2부터 i*i

간단해보이는 문제지만 다양한 개념들이 사용된 문제이다. 다음과 같은 개념들이 사용되었다. 모듈러연산의 특징 모듈려는 /을 제외한 +, -, * 에 대해서 다음과 같은 특징을 가진다. (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^..

여러가지 기법이 혼합되어 있는 문제이다. 우선 전체 25개의 알파벳중 7개를 뽑는 경우의 수를 생각하였다. 백트래킹을 이용한 조합을 사용할 계획으로 7개의 알파벳을 고르는 것을 구현한 후 1차적으로 S가 4개 이상인지를 확인하였다. 그 다음 S가 4개이상임이 확인이 된다면 BFS를 이용하여 7개의 알파벳이 하나의 그룹으로 이루어져있는지 확인하였다. 만일 하나의 그룹이면 최종답을 하나추가 시켰다. 수의 범위가 구현이 가능한 범위임으로 문제에 주어진 대로 구현하는게 중요한 문제였다. 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 4..

문제에 주어진 대로 하면 되는 시뮬레이션이다. 단순 구현 문제이기 때문에 문제에 주어진 조건그대로를 수행하게 된다면 풀 수 있는 문제이다. 하나의 톱니바퀴가 돈다면 양쪽으로 끝지점 까지 영향을 끼칠 수 있으므로 left함수와 right함수를 만들어서 양 끝 인덱스 까지 재귀를 하는 방식으로 구현하였다. 구현함에 있어 고려할 부분이 상당히 많아서 풀이하는 시간을 상당히 많이 소요하였다. 꼼꼼함이 필요한 문제같다. 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 5..