프로그래민👨‍💻

BFS를 이용하여 모든 경우를 탐색해는 방식으로 해결한 문제이다. 전체 퍼즐이 가지는 경우의 수가 9! 가지이므로 전체 경우를 다봐보는 경우를 생각해보았다. 일단 주어진 입력을 보았을때 0을 움직이는 BFS를 생각할수 있었다. 그렇게 하여 생각해낸것이 움직여서 나올 수 있는 2차원 배열 모양을 하나의 경우로 생각하였고, 0이 움직일수 있는 위치는 4방향이어서 하나의 2차원 배열에서 최대 4가지 모양을 가질수있다고 생각하였다. 그러한 모양에 대해 방문체크를 해주어야 했는데, 2차원 배열을 int의 형태로 만들어서 체크를 해주었다. 즉, 123456780 부터 087654321 까지의 숫자로 만들어주었고, 0이 맨앞에 오는 경우때문에 0을 9로 대체하여 구했다. visit을 만들때 문제가 있었는데 이땐 Ma..

비트마스킹을 이용한 완전탐색으로 해결한 문제이다. 이 문제를 맨처음 봤을땐 아이디어가 잘 생각안지 않았다. 곰곰히 생각해보니 어차피 빈칸 하나에 대해선 가로 방향 또는 새로 방향을 가질 수 있으므로 전체가지수를 2^(가로X세로) 로 생각하고 모든 경우에 대해 값을 계산해보는 방법을 생각해냈다. 2가지의 경우를 가지기 때문에 비트마스킹을 이용하여 모든 subSet을 가로는 -1, 세로는 1로 표현하여 dir이란 배열에 대입해주어 계산하였다. 그 후 해당 경우에서 가로, 세로를 따로 계산하여 더한값을 최종답으로 갱신해주며 풀었다. 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 3..

BFS를 이용하여 빈칸을 찾는 문제이다. M에서 시작하여 다음파이프로 이동하면서 만나는 첫번째 빈칸에서 적합한 파이프를 찾는 문제이다. 그 빈칸의 파이프는 해당 빈칸과 연결된 모든 파이프들을 서로 연결시킬수 있는 모양이므로 체크해줘야할 조건이 상당히 많았다. 조건을 체크하는 과정에서 어이없게 실수하는 부분이 있어서 상당히 오랜시간 푼 문제였다. 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..

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

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

부분집합의 개념이 사용된 문제이다. 이 문제는 부분집합의 개념으로 구현할수 있는 문제이다. 즉 하나의 행에 대해 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..

자료구조를 이용하여 쉽게 풀수있는 문제이다. Map자료구조를 이용하여 교집합과 합집합을 구하는 문제이다. 만일 두문자열다 가지고 있는 원소이면 교집할일땐 min값을, 합집합일땐 max값을 주어주는 방식으로 풀었다. 문제를 꼼꼼히 읽는게 중요한것 같다. 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..

간단한 시뮬레이션 문제이다. 자신을 기준 오른쪽, 대각선아래, 아래를 확인해가며 반복하여 찾는 단순 구현 문제이다. map을 down시키는 과정에 유의하며 구현하면 쉽게 구할수 있는 문제이다. 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 package programmers; public class Solution_2..

단순 구현 문제이다. 단순 구현 문제이긴 하지만 조건들이 까다롭고 문제이해가 오래 걸려서 구현함에 있어 고생을 하였다. 이 문제를 품에 있어 시간을 60진수로 간주하고 int화 시켜서 문제를 접근하였다. 그리고 bus들을 map에 저장하여 남은 자리를들을 체크해주었고, 크루들을 한명씩 체크하며 버스의 마지막자리에 탈때의 시간, 그리고 남는 버스자리의 시간들을 비교하여 콘이 탈 시간의 최대값을 찾았다. 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 6..

이문제는 복잡한 구현 문제이다. 문제에 주어진 대로 구현을 하면 되는데, 구현을 함에 있어 재귀와 다양한 함수를 활용하였다. 재귀와 백트래킹을 같이 사용하였는데 2차원 배열의 백트래킹을 할땐 재귀함수 안에서 지역변수로 temp[][] 를 선언하고 원래 2차원 배열을 복사해놓고 재귀가 끝나면 다시 붙여넣는 작업을 통해 백트래킹을 구현할 수 있다. 이 부분에 있어 전역변수로 하다가 코드가 꼬이는 현상이 발생했는데 필히 지역변수를 사용해야 한다. 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..