프로그래민👨‍💻

소수와 팰린드롬을 구하는 문제이다. 소수를 구할땐 크게 2가지 방법으로 구할 수 있다. 첫번째는 이수가 소수인지 그수의 루트N까지 직접 나누어 보는 방법이 있고, 두번째는 에라토스테네스의채를 사용하는 방법이 있다. 이 문제에서는 두가지 모두 구현하고 실제 코드에선 첫번째 방법을 사용하였다. 그리고 팰린드롬은 회문이라 한다. 즉, 거꾸로해도 같은 문자의 순서를 가지면 팰린드롬이라 한다. 예를 들면 123321 이나 75957 등이 있다. 단순히 비교하는 것이기에 처음과 끝에서 인덱스를 비교함으로 구하였다. 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..

시뮬레이션 문제이다. 주사위는 10번을 굴리고, 말은 4개를 가지고 있으므로 전체 경우의 수는 4^10을 가지게 된다. 따라서 이 문제는 백트래킹을 통한 완전탐색을 할 수 있는 문제이다. 다만 주의할점은 윷놀이판을 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..

DFS를 이용하여 풀수 있는 문제이다. 일단 문제에서 10번이하로 움직인다는 조건을 주었다. 조건을 가지고 생각해보았을때 현재 구슬을 굴릴수 있는 방향은 4방향이 있고 10번을 굴린다 생각하면 전체가지수는 4^10이 나오게 된다. 4^10은 1,048,576‬ 로써 충분히 완전탐색을 할수 있는 시간이 나온다. 하지만 좀더 최적화가 가능하기에 생각을 해보았다. 맨처음 구슬을 굴릴땐 4방향 다 굴릴수 있지만 그다음부턴 2방향으로만 굴릴수있다. 예를 들어 맨처음 위쪽으로 굴렸다 가정해보자면, 구슬은 벽을 맞닿을때까지 구르기 때문에 다음번엔 위쪽으로 굴리는 것은 무의미한 경우를 가지게 된다. 또한, 반대방향이 아래쪽으로 굴리는 경우는 다시 그 전 상태로 되돌아가기 때문에 그것 또한 무의마하게 된다. 그래서 결론..

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

인접리스트의 DFS로 풀수있었던 문제이다. 리프노드에서 리프노드까지 가는 가장 긴경우를 지름이라 할 수 있는데 그것을 찾는 문제였다. 맨처음엔 가장 긴 간선을 기준으로 찾아보는 방법을 시도했는데, 가장 긴 간선이 꼭 포함되라는 보장이 없으므로 틀린방법으로 접근하였었다. 도움을 받아 풀었는데 다음과 같은 방법으로 풀었다. 1.루트에서 가장 멀리있는 리프노드의 인덱스를 찾고, 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 4..

비트마스킹을 이용한 완전탐색으로 해결한 문제이다. 이 문제를 맨처음 봤을땐 아이디어가 잘 생각안지 않았다. 곰곰히 생각해보니 어차피 빈칸 하나에 대해선 가로 방향 또는 새로 방향을 가질 수 있으므로 전체가지수를 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..

2개로 팀을 나눠서 답을 구하는 문제이다. 스타트와 링크 문제와는 다르게 정확히 두개의 팀이 같은 팀원수를 가지는 것이 아니라 다른 두개의 팀으로 나눠지기만 하면 되는 문제이다. 그래서 이문제를 비트마스킹으로 접근하였다. 비트 마스킹을 이용하여 예를 들면 N=4일때 0001 부터 1110 까지 수를 구하고 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 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 6..

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

이 문제는 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,..