프로그래민👨‍💻

순열 재귀를 이용하여 푸는 문제이다. 주어진 추를 왼쪽에 놓을때, 오른쪽에 놓을때의 경우를 재귀로 호출하며 풀수있는 문제이다. 다만 여기서 주의할점이 있다. 저울이 양쪽이기에 N개의 추가 있다면 2^N * N!을 총가지수로 가지기 때문에 가지치기가 상당히 중요한 문제이다. 따라서 다음과 같은 가지치기를 하였다. 우선 오른쪽저울에 추가해도 왼쪽저울을 안넘을때 오른쪽 저울에 추가하는 가지치기와 만일 현재왼쪽의 총합*2가 sum을 넘는다면 뒤쪽은 다안보고 한번에 모든 경우를 더해주는 방식으로 가지치기를 하여 시간초과를 통과하였다. 단순한 재귀 문제이지만 가지치기를 하는 방식을 곰곰히 생각해봐야하는 문제이다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 ..

이문제는 순열을 사용하여 접근하는 문제이다. 처음엔 간단히 단순 순열로 접근하여 푸는 문제 인지 알았다. 하지만 최악의 경우 21P10을 가지게 되므로 가지치가 상당히 중요한 문제로 생각하였다. 일단 문제를 쉽게 접근하기 위해 -,+,0으로 주어진 문자열을 2차원 배열의 형태로 만들어주었다. 행을 0부터 N까지로 잡고, 열을 현재행부터 N까지로 주어서 삼각형모양의 2차원배열을 만들었다. 그 후 순열로 접근하였다. 일단 순열을 0부터 N-1까지 정해줄때 해당 index는 2차원배열의 행과열이 같을때의 index의 부호와 같기때문에 크게 경우의 수를 줄일 수 있었고, 그 후 check라는 함수를 만들어 2차원배열의 해당 열의 원소들을 체크해주는 식으로 가지치기를 하였다. 푸는데 상당히 오랜시간이 걸렸고, c..

해밀턴 순환회로, 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..

구현이 중요한 문제다. 문제에 주어진 그대로 구현을 하는 문제이다. 구현은 까다롭지 않지만 다만 여기서 주의할점은 타자의 순서인데, 이 문제에선 1번선수가 4번타자를 맡게 되므로 나머지 8명의 선수를 이용하여 순열을 하고 그때 그때마다 게임을 진행하는 식으로 하였다. 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..

N의 범위를 확인해본 결과 11이므로 nextPermutation()또는 백트래킹을 이용한 순열을 사용하는 문제이다. 하지만 이문제에서 주의할점은 순열을 구해하는 수,기호 에는 중복이 되는 것이 있으므로 무조건 nextPermutation()을 직접 구현해야 풀 수 있는 문제이다. 연산자들을 모아놓은 op배열을 생성후 모든 number에 대하여 연산을 해주면 쉽게 풀어지는 문제이다. 관건은 nextPermutation()의 직접 구현이다. 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 ..

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]

주어진 구슬 N의 최대 크기가 4, 너비 W가 12이므로 모든 경우의 수를 구할 때 순열을 사용하여도 복잡도가 넘어 갈 것 같지 않아서 바로 순열을 사용하였다. 순열을 선택한 후 다음과 같은 과정을 계획하였다. 1. W에서 N개를 선택하는 모든 수열을 구한다. 2-1. 구한 순열의 경우의 수마다 위에서 부터 폭파하는 과정을 BFS를 통하여 계산한다. 2-2. 폭파된 후 중간에 공백을 아래로 당겨준다. 그 후 2-1 반복한다. 3. 모든 폭파가 종료된 후 살아있는 블럭을 카운팅해준다. 또한, 중간에 최적화를 시키기 위해, 만일 2-1 과정에서 선택한 열의 블록이 하나도 없는 경우, 그 순열의 경우는 바로 종료 시키게 해주었다. 문제를 읽고 있는 그대로 차분하게 구현하여서 답을 얻을 수 있었다. 1 2 3 ..