문제로 이동 이 문제의 핵심 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[..

문제로이동 MissingInteger coding task - Learn to Code - Codility Find the smallest positive integer that does not occur in a given sequence. app.codility.com 목차 문제 설명 양수인 정수 중에서 배열에 없는 가장 작은 값을 출력하는 문제입니다. 너무 간단한 문제라 바로 예제부터 보겠습니다. [1,2,3]의 경우 배열에 없는 가장 작은 정수인 4가 나옵니다. [-1,-3]의 경우 배열에 없는 가장 작은 정수인 1이 나옵니다. [1,3,6,4,1,2]의 경우 배열에 없는 가장 작은 정수인 5가 나옵니다. 접근 방법 어쨌든 모든 배열을 탐색해야 하므로 O(N)의 시간 복잡도를 갖습니다. 입력 범위..

문제로이동 FrogRiverOne coding task - Learn to Code - Codility Find the earliest time when a frog can jump to the other side of a river. app.codility.com 목차 문제 설명 solution 함수에 X, A 값이 주어집니다. 개구리가 강을 건너기 위한 최소한의 시간을 출력하는 문제입니다. 개구리의 초기 위치는 index 0이며, X 위치까지 도달하기 위해서는 반드시 모든 위치에 낙엽이 떨어져야 합니다. 바로 예시를 보겠습니다. A[0] = 1 A[1] = 3 A[2] = 1 A[3] = 4 A[4] = 2 A[5] = 3 A[6] = 5 A[7] = 4 위와 같이 매 시간별 낙엽이 떨어지는 위치가 ..

문제로이동 PermCheck coding task - Learn to Code - Codility Check whether array A is a permutation. app.codility.com 목차 문제 설명 N개의 정수 배열 A가 주어집니다. 단, 중복되는 수는 없으며 연속되지 않는 정수를 찾아내는 문제입니다. 두 가지 상황을 예로 들자면, A[0] = 4 A[1] = 1 A[2] = 3 A[3] = 2 위 Example의 경우 총 4개(최대 4)의 정수가 주어졌으며 1부터 4까지 모든 수가 존재합니다. 반대의 경우를 봅시다. A[0] = 4 A[1] = 1 A[2] = 3 위 Example의 경우 총 3개(최대 4)의 정수가 주어졌으며 2를 제외한 모든 수가 존재합니다. 이 때, N까지 모든 ..

문제로이동 21611번: 마법사 상어와 블리자드 마법사 상어는 파이어볼, 토네이도, 파이어스톰, 물복사버그, 비바라기 마법을 할 수 있다. 오늘 새로 배운 마법은 블리자드이고, 크기가 N×N인 격자에서 연습하려고 한다. N은 항상 홀수이고, ( www.acmicpc.net 목차 문제 설명 가장 최근에 나왔던 삼성 SW 역량 기출 문제로 알고 있습니다. 약 1시간 15분 가량 소요되었던 문제이며 굉장히 재밌게 풀었습니다만 시간을 좀 더 단축해야겠다는 생각이 강하게 들었습니다. 이번 문제는 각 기능별(함수)로 설명 하겠습니다. 그리고 작동되는 순서는 아래 나열된 순서와 동일합니다. 위치별 인덱싱 이 문제를 해결하면서 상어를 중심으로 소용돌이 모양으로 구슬을 이동하고, 변화하고, 폭발하고의 과정이 거쳐지는 것..