재귀3 시계 맞추기 시계 맞추기 4x4개의 격자 형태로 배치된 16개의 시계가 있다. 각 시계들은 3,6,9 혹은 12시를 가리키고 있는데 모든 시계가 12시가 되도록 만들려고 한다. 시계를 조작하는 방법은 10개로 구성된 스위치를 조작하는 방법 뿐이다. 각 스위치들은 최소 3개에서 여러개의 시계와 연결되어 있다. 스위치를 누를 때마다, 해당 스위치와 연결된 시계는 3시간씩 앞으로 움직인다. 모든 시계를 12시로 만드려면 최소한 스위치를 몇 번이나 눌러야 하는지 출력하라. 풀이 방법 문제를 있는 그대로 풀려고 하면 완전 탐색으로 불가능하다. 이유는 ? 완전 탐색을 사용하기 위해서는 스위치를 누르는 횟수의 모든 조합을 다 열거할 수 있어야 하는데, 각 스위치를 몇 번 누르는지는 상관없게 된다면 무한대의 조합이 나오게 된다. .. 2019. 11. 12. 보글게임 - 완전 탐색 주어진 5x5 격자 위에 문자들이 있다. 최대 8방향으로 문자들을 연결해서 찾으려는 단어가 존재하는지 검사하라. 찾으려는 단어가 격자위에 존재하는지 검사하기 위해서는 완전 탐색 해야한다. 처음 시작 좌표 값과 단어를 입력으로 할 시에 격자 위에 존재하는지 검사하는 알고리즘을 구현. 각 문자마다 최대 8방향을 검사하기 때문에 격자가 커지면 커질수록 시간 복잡도는 기하급수적으로 상승하게 된다. (지수 복잡도) 완전 탐색을 재귀를 이용해서 구현했다. char board[5][5] = { {'U', 'R', 'L', 'P', 'M'}, {'X', 'P', 'R', 'E', 'T.. 2019. 10. 24. 재귀 소개 및 DP의 맛 알고리즘 문제를 풀다보면 맞닥뜨리는 흔한 문제는 재귀와 DP다. 하지만 일반적으로 재귀적 사고를 한다는 것 자체가 쉽지 않다. 다양한 문제를 풀면서 내가 느낀건 반복 되는게 있어야 한다. => 문제를 더 작게 만들 수 있어야 한다. 탈출 지점이 있어야 한다. 여기서 더 중요한 건 2번이다. 탈출 지점이 정확하게 없으면 재귀적으로 풀 수 없다. 재귀의 대명사 피보나치 수열을 풀어봤다. def fibo(n): if n 2019. 5. 8. 이전 1 다음
