프로그래민👨‍💻

이차원 행렬상에서 특정조건의 최장길이를 구하는 문제이다. 최장길이를 구하는 문제는 DFS와 백트래킹으로 풀면 쉽게 풀 수 있다. 맨처음 이문제를 접근하였을 때 BFS와 3차원 visit배열로 접근하였다. 이 방법으로도 풀리긴 하지만 DFS와 2차원 visit 배열의 백트래킹을 사용하면 훨씬 간결한 코드를 얻을 수 있다. 이 문제에선 주의할점이 두가지 있는데, 첫째 산을 깎을수 있다는 점과 둘째 깎을때 꼭 K만큼이 아니라 K이하 만큼 깎을수 있다는 점이다. 두가지를 유념하여 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 3..

상당히 많은 시간을 투자했던 문제이다. 우선 간단하게 N의크기가 10이하인것을 보고 백트래킹으로 접근하려했다. 하지만 최악의 경우가 10!정도가 나오는데 이것 말고도 안쪽에서의 String 연산때문에 시간초과를 해결할 수 없었다. 그래서 StringBuilder를 사용하여 결국 문제는 해결하였지만 최악의 시간복잡도를 가지고 해결하게 된 셈이 되었다. 아래가 다음 코드이다. 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..

단순구현과 백트래킹이 합쳐진 문제이다. 이문제는 2048을 구하는 단순구현과 4가지 방향으로 5번을 가봐야하는 과정이합쳐진 문제였다. 2차원 배열을 이용하여 재귀를 도는 백트래킹은 처음 구현해봐서 어떻게 해야하는지 고민을 많이했다. dfs()란 함수에서 이차원 배열을 저장할 temp[][] 를 이용하여 해결하였다. 즉 재귀함수호출전 temp에 map을 다 저장하고 재귀함수 호출뒤 map에 temp를 다시 복원시키는 방법을 사용하였다. 간단한 방법이지만 생각하는 부분에 있어서 많은 시간을 사용하였다. 구현뿐만 아니라 전반적으로 다시 봐야할 필요가 있는 문제인 것 같다. 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..

처음 문제를 접했을 때 설계에 상당히 많은 시간을 사용하였다. 단순 문자열 파싱 문제인지 알았는데, 자세히 보니 전혀 다른 문제였다. 출력의 경우의 수를 자세히 보다 보니 특정한 규칙을 찾게 되었다. 이차원 배열이 있고, 가로축을 user_id, 세로축을 banned_id라고 하고 패턴이 매칭되면 1을 둔다고 가정한다면, 맨처음 입력 예시에선 다음과 같이 적용이 된다. "frodo" "fradi" "crodo" "abc123" "frodoc" "fro*d*" 1 1 0 0 0 "abc1**" 0 0 0 1 0 이에 따른 출력은 2가지 경우로 frodo, abc123 과 fradi, abc123 가 나오게 된다. 여기서 찾은 규칙은 패턴이 매칭되는 1에 한해서 각행마다 하나의 열을 선택하게 되고, 다음행에..

모든 경우를 다해보는 브루트포스 문제이다. 브루트포스는 기본적으로 다음4가지로 구현할 수 있다. 1. for문 2. 순열 3. 재귀 4. 비트마스크 이 문제에서는 만들 수 있는 숫자를 모두 해봐야하 알 수 있는 브루트포스 문제여서 숫자를 만들때 재귀를 이용하여 풀었다. 그리고 모든 숫자의 경우에서 answer를 계속 갱신해주는 방식으로 해주었다. 이 문제는 특히 주의할 점이 상당히 많다. 시작점이 100이라는 것과 또한 2번째 입력이 0 일수도 있다는 것 그리고 재귀를 호출할때 0을 제외하므로 맨마지막에 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..

인접리스트를 활용한 DFS문제이다. 맨처음 문제접근을 BFS로 하였는데, 이 문제에선 5개의 이어진 노드를 찾는 것이여서 DFS를 활용하여 depth가 5가 될때까지를 찾는게 맞는 방향이라 생각해 DFS로 바꾸어 풀었다. 이 문제에서는 주의할 것은 다양한 방법으로 여러갈래로 찾을 수 있기에 visit[i]=false로 다시 바꾸어 주는 작업이 필수적이다. 이것을 해주지 않아 계속 틀렸었다. 예를 들어 위와 같은 그래프가 있고 1번 정점부터 탐색한다고 생각하자. 첫번째 DFS를 실행시킨 결과가 1-2-4-5-3 이라고 생각한다면 depth는 최대 4까지 밖에 찾지를 못한다. 그렇기에 종료조건을 만족하지 못하고, 재귀가 끝나면서 다시 재귀호출을 하게 된다. 1-2 이상황에서 4를 방문했었기네 1-2-3을 해..

그래프를 사용하여 DFS와 BFS를 하는 기본 문제이다. 그래프를 인접리스트로 구현하여 DFS와 BFS각 각 구현하였다. DFS를 구현할 때는 stack을 사용하는 대신 재귀의 형태로 구현하였다. BFS를 구현할 때에는 queue를 사용하여 구현하였다. DFS에서는 방문할때 바로 visit 체크를 해주었고, BFS에서는 queue에 offer하는 동시에 visit 체크를 해주었다. 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 ..

여러가지 기법이 혼합되어 있는 문제이다. 우선 전체 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..

기본적인 부분수열의 합문제이다. 두가지 방법으로 풀어보았다. 첫번째로는 비트마스킹을 이용하여 모든 부분수열을 구하는 방식으로 구현하였다. 두번째로는 재귀적인 DFS 방식으로 현재항을 더해주는 경우, 현재항을 더해주지 않는 경우로 나누어 2번씩 호출해주는 방식으로 풀었다. 이때 기저조건으로는 마지막인덱스에 도달하였을 경우 종료시키게 해주었다. 시간은 비트마스킹을 사용하는 첫번째 코드보다 두번째 재귀적인 DFS를 사용한 코드가 빨랐다. 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 package ch..

그래프를 구현하는 문제였다. 그래프를 구현하기 위해 메모리측면을 고려하여 배열보단 리스트를 사용하였다. 리스트로 그래프를 구성한 후 재귀를 이용한 DFS를 이용하여 모든 정점을 방문하도록 하였다. 방문하는 과정에서 flag를 인자로 주어 두팀으로 나눌 수있도록하였다. 모든 DFS끝난 후 바로 이어서 다시 방문하여서 만일 같은 flag를 가지고 있다면 조건을 만족하지 않는 식으로 구성하였다. 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 6..