프로그래민👨‍💻

조합과 그래프탐색을 하는 시뮬레이션 문제이다. 이 문제를 접근할때 단순하게 생각하여 접근하였다. 일단 모든 도시들의 연결관계를 그래프를 이용하여 나타내주었고, 그후 도시들을 조합으로 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 ..

이 문제는 DP로 해결하였다. 맨 처음 문제를 봤을때 재귀적인 그래프의 탐색형태로 접근하려고 했다. 하지만 N의 크기가 재귀를 사용하기에 너무 큰 경우의 수를 가지기에 재귀말고 DP로 접근하게 되었다. 일단 모든 맵의 칸에서 3가지의 경우의수를 가지고 했다. 파이프가 각각 가로,세로,대각선으로 깔리게 되는 3가지로 두었다. 그리고 만일 i,j에서 가로로깔리게 되는 경우의 수를 생각해보면 i-1,j 에서의 가로와 대각선의 경우의 수를 가질수 있게 된다. 이러한 방식으로 다음과 같이 생각하게 되었다. 1) i,j에서 가로의 파이프를 가지는 경우 : (i-1,j에서 가로) + (i-1,j에서 대각선) 2) i,j에서 세로의 파이프를 가지는 경우 : (i,j-1에서 세로) + (i,j-1에서 대각선) 3) i,..

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..

순열 재귀를 이용하여 푸는 문제이다. 주어진 추를 왼쪽에 놓을때, 오른쪽에 놓을때의 경우를 재귀로 호출하며 풀수있는 문제이다. 다만 여기서 주의할점이 있다. 저울이 양쪽이기에 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 ..

이문제는 조합을 이용하여 선택을 한다음 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..

백트래킹을 이용하여 경로를 찾는 문제이다. 백트래킹 DFS 경로문제는 일반 재귀를 사용하는 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 53 54 55 56 57 58 59 60 61 package online.practice; import java.io.BufferedReader; import java.io.InputStream..

백트래킹을 이용하여 빈칸의 숫자를 확인해가는 문제이다. 문제를 맨처음엔 행의 개념으로 접근하여 행마다 0의 갯수를 세어주고 다 채우면 다음행으로 가고를 반복하는 방식으로 접근하였는데 시간초과를 해결할수 없었다. 그래서 두가지 방법을 생각해냈다. 0의 위치만 List로 저장하는 방법과 행의 개념이 아니라 칸의 개념으로 depth를 81까지 확인하는 방법을 생각해냈다. 생각해낸 두번째 방법으로 구현을 직접 구현을 해보았고, check라는 함수를 만들어 행,열, 사각형 반경을 체크해주었다. 옛날에 풀었던 문제지만 다시 풀어보았다. 다시 풀어보니 접근법을 너무 어렵게 가져가서 힘든 부분이 있었다. 단순하게 생각하는게 필요할것 같다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18..

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

부분집합의 개념이 사용된 문제이다. 이 문제는 부분집합의 개념으로 구현할수 있는 문제이다. 즉 하나의 행에 대해 1. 변화를 안준다. 2. 0으로 다바꾼다. 3. 1로 다바꾼다. 를 가질수 있고 전체 경우의 수를 구해보면 3^(행의수) 를 가지게 된다. 전체 경우의 수를 구함에 있어 재귀를 사용하여 구해주었다. 재귀를 함에 있어 최적화를 시키려면 가지치기가 상당히 중요하다. 이 문제에선 변화를 주는 횟수를 세어주는 count 변수가 작을때를 구하게 되는 문제인데, 가지치기를 위해 현재 가지고 있는 count보다 큰경우는 바로 return을 해주는 방식으로 가지를 쳐주었다. 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..

간단한 BFS 문제 같지만 방문고려요소가 상당히 많은 문제이다. 방문을 위한 조건이 1. 현재방에서 인접한 방이고 2. 불이 켜져있어야 함으로 배열을 near,light,visit로 세가지를 만들었다. 그리고 0,0에서 시작 후 첫번째로 near를 이용하여 근접한 방을 체크해주었고, 두번째로 현재방에서 불을 킬수있는 방을 불을 키면서 near이면 queue에 넣어주었다. 그후 세번째로 현재방에서 다시 근접한 불켜진 방들을 방문하였다. 이러한 방식을 이용하여 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..