문제로 이동 이 문제의 핵심 1. 윷놀이 맵을 어떻게 구현할 것인가? 2. 두가지 루트로 이동을 어떻게 할 것인가? 시간 단축 윷놀이 맵을 어떻게 구현할 것인가에 따라 달라졌습니다. 어떻게보면 당연한 말이지만 O(1)로 다음 위치를 판단하게 할 것인지 아니면 재귀함수를 사용해 (마치 LinkedList처럼) 다음 위치를 판단하게 할 것인지 고민했습니다. 여러 시도 끝에 O(1)이 가장 빠른 속도를 보였습니다. 그 과정을 이 글에서 설명합니다. 1차 시도 (968ms) # 출발,도착 포함 33개 / 자식 index, 자신 점수 field = [[0, 0]] * 33 def init_field(): global field for i in range(0, 21): field[i] = [[i + 1, i * 2..

문제 페이지 접근방법 백트래킹 이미 문제에도 명시가 되어 있듯이 정답이 3보다 큰 값이거나 불가능한 경우에 -1을 출력합니다. 즉, 재귀함수의 depth에 제약을 걸어 가지치기를 할 수 있다는 말입니다. 저는 depth가 3에 도달하게 되면 더 이상 재귀 함수를 돌지 않게 설정했습니다. 로직 2차원 Array 형태로 사다리 Map을 그려준다 우측으로 이동하는 사다리는 1, 좌측으로 이동하는 사다리는 -1을 넣어준다. 내려가는 사다리는 0이다. 모든 설치 가능한 구역에 사다리를 설치하는 브루트포스 문제이다. 그렇기 때문에 모든 구간을 순회하는 DFS를 사용한다. 각 사다리 별로 번호에 맞게 내려오는지 확인한다. 만약 맞다면, 정답을 갱신한다 만약 틀리다면, 가로 사다리를 계속해서 설치한다. Python C..

문제로 이동 접근 방법 누적합+이분탐색 카테고리여서 이분 탐색을 어떻게 사용할지 고민했습니다. 1. 전처리 배열 1개의 경우, 누적합을 구하기 위해 A[0] ~ A[n] 까지 배열을 순회하며 누적합을 넣어주지만 해당 문제를 이렇게 접근해버리면 안된다는 것은 알고 계실겁니다. # 일반적인 배열 1개의 누적합 arr = [0,1,2,3,4,5,6,7,8,9] for i in range(1,len(arr)): arr[i] = arr[i-1]+arr[i] # result : [0,1,3,6,10,15,21,28,36,45] 2개의 배열이기 때문에 이런 의문이 생길 수 있습니다. "각 배열의 비교 범위를 어떻게 선택할 것인가?" B 배열의 탐색 index가 하나 증가하게 되면 A 배열의 index는 처음으로 돌아..

문제로 이동 이번 글에서는 문제에 대한 설명과 풀이보다 골드 난이도임에도 불구하고 무려 11WA를 받게된 이유, 그리고 드디어 Solved 할 수 있었던 이유를 찾고 포스팅 했습니다. 혹시 "맞는데 왜 틀려" 늪에 빠져있다면 이 글을 보았을 때 도움이 될 수 있습니다😀 과거의 흔적 틀렸던 이유 1. RecursionError Python의 경우 재귀 함수의 깊이가 1000으로 고정되어 있습니다. 만약 1000번보다 더 큰 재귀를 돌기 위해선 Recursion을 설정해줘야 합니다. 5개월 전 당시엔 이를 DFS로 풀다가 놓쳤던 것 같네요 2. 시간초과 및 틀렸습니다 과거의 코드를 보니 빙산이 분리되는 구간에서 줄일 수 있는 로직이 보였고, 애초에 너무 복잡하게 생각을 했는지 코드가 직관적이지 못합니다 ㅠㅠ..

문제로이동 1016번: 제곱 ㄴㄴ 수 어떤 수 X가 1보다 큰 제곱수로 나누어 떨어지지 않을 때, 제곱ㄴㄴ수라고 한다. 제곱수는 정수의 제곱이다. min과 max가 주어지면, min과 max를 포함한 사이에 제곱ㄴㄴ수가 몇 개 있는지 출력한다. www.acmicpc.net 문제 설명 에라토스테네스의 체 응용 문제입니다. 최대 범위는 1백만, 최대 수는 1조이기 때문에 정수형(long long)과 시간초과에 주의해야 합니다. 제곱 수로 나누어 떨어지지 않을 때 제곱ㄴㄴ수라 한다. 제곱수는 아시다시피 아래와 같습니다. 2*2 = 4 3*3 = 9 4*4 = 16 ... 에라토스테네스의 체는 아래와 같습니다. 단순하게도 특정 범위에서 제곱수를 에라토스테네스의 체로 걸러내는 방식을 구현하면 됩니다. 즉, 2의 ..

문제로이동 MaxCounters coding task - Learn to Code - Codility Calculate the values of counters after applying all alternating operations: increase counter by 1; set value of all counters to current maximum. app.codility.com 목차 문제 설명 체감상 Lesson4 테스트 문제 중 해결하는데 가장 오래걸렸습니다. 입력 값으로 N과 배열 A가 입력됩니다. 최종적으로 N개 만큼의 카운터를 출력해야 하고 N=5일 때 (0, 0, 0, 0, 0)과 같은 형식으로 출력 이 카운터를 어떻게 연산하느냐가 관건입니다. 예제를 보며 기능을 설명하겠습니다. A[..