프로그래민👨‍💻

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

이문제는 복잡한 구현 문제이다. 문제에 주어진 대로 구현을 하면 되는데, 구현을 함에 있어 재귀와 다양한 함수를 활용하였다. 재귀와 백트래킹을 같이 사용하였는데 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..

처음에 보고 아이디어를 떠올리기 상당히 어려웠던 문제이다. 이 문제에서 전체 경우의 수를 따져본다면 전체 6팀이 경기를 하기때문에 총 15경기가 열리고, 경기마다 승,무,패 의 경우가 있기에 전체 3^15가지의 경우가 생기게 된다. 그러므로 백트래킹을 사용하여 승무패를 계속 재귀적으로 호출하면서 전체경우의 수랑 현재 테이블이랑 같아지는지 확인하여 구할수 있다. 백트래킹 문제라 전혀 생각지 못한 문제였다. 문제를 깊이 생각할 필요가 있다고 느꼈다. 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..

단순구현과 백트래킹이 합쳐진 문제이다. 이문제는 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..

모든 경우를 다해보는 브루트포스 문제이다. 브루트포스는 기본적으로 다음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..

재귀를 사용해야만 풀수있는 문제이다. 14888.연산자 끼워넣기 와 비슷한 문제이지만 이문제는 연산자의 갯수가 최대 4N개가 주어질 수 있으므로 순열 또는 조합의 방법을 사용할 수 가 없다. 따라서 재귀를 사용해야하는데, 재귀의 조건은 연산자의 종류인 총 4가지가 될 수가 있다. 즉, 숫자와 숫자사이에서 가지고 있는 연산자의 갯수에 따라 4개중 어떤것을 호출하냐를 결정할 수 있다. 기저조건으로는 마지막 index까지 도달했을 경우로 두었다. 보통 재귀는 '했다', '안했다'를 재귀의 요소로 두지만, 이 경우는 '4가지중 어떤것을 했다' 로 두고 풀었다. 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 3..

이 문제는 재귀를 사용하는 문제이다. 재귀를 함에 있어 1)선택하고 , 2)선택하지 않고를 기준으로 재귀를 반복하였다. 기저조건으로는 날짜 N의 범위를 넘어갈때를 체크하였다. 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 package online.base; import java.io.BufferedReader; import java.io.InputStreamReader; import java.util.StringTokenizer; public cl..

문제에 주어진 대로 하면 되는 시뮬레이션이다. 단순 구현 문제이기 때문에 문제에 주어진 조건그대로를 수행하게 된다면 풀 수 있는 문제이다. 하나의 톱니바퀴가 돈다면 양쪽으로 끝지점 까지 영향을 끼칠 수 있으므로 left함수와 right함수를 만들어서 양 끝 인덱스 까지 재귀를 하는 방식으로 구현하였다. 구현함에 있어 고려할 부분이 상당히 많아서 풀이하는 시간을 상당히 많이 소요하였다. 꼼꼼함이 필요한 문제같다. 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 5..

재귀를 사용하는 기본적인 문제이다. 기저조건으로 size가 1이되는 경우 맨왼쪽 위 기준으로 9칸씩 채우도록 해주었다. 또한, 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 package chap06; import java.io.BufferedReader; import java.io.InputStreamReader; public class Main_bj_2447_별찍기10 { static char[][] map; public static void..

재귀를 이용하여 분할정복을 하는 문제이다. 아이디어를 생각하기까지 오랜시간이 걸렸다. 삼각형의 가장 꼭대기 점을 기준으로 아래에 있는 두 개의 삼각형을 호출해주는 형식으로 풀었다. 그리고 기저조건으로는 높이로 가져가는 size가 3이 되면 출력해주도록 해주었다. 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 package chap06; import java.io.BufferedReader; import java.io.InputStreamReader; public clas..