Algorithm38 (백준) 뱀 문제 'Dummy' 라는 도스게임이 있다. 이 게임에는 뱀이 나와서 기어다니는데, 사과를 먹으면 뱀 길이가 늘어난다. 뱀이 이리저리 기어다니다가 벽 또는 자기자신의 몸과 부딪히면 게임이 끝난다. 게임은 NxN 정사각 보드위에서 진행되고, 몇몇 칸에는 사과가 놓여져 있다. 보드의 상하좌우 끝에 벽이 있다. 게임이 시작할때 뱀은 맨위 맨좌측에 위치하고 뱀의 길이는 1 이다. 뱀은 처음에 오른쪽을 향한다. 뱀은 매 초마다 이동을 하는데 다음과 같은 규칙을 따른다. 먼저 뱀은 몸길이를 늘려 머리를 다음칸에 위치시킨다. 만약 이동한 칸에 사과가 있다면, 그 칸에 있던 사과가 없어지고 꼬리는 움직이지 않는다. 만약 이동한 칸에 사과가 없다면, 몸길이를 줄여서 꼬리가 위치한 칸을 비워준다. 즉, 몸길이는 변하지 않는.. 2021. 1. 6. (leetcode) two-sum 덧셈하여 타겟을 만들 수 있는 배열의 두 숫자 인덱스를 리턴하라. 입력 nums = [2,7,11,15], target = 9 출력 [0,1] class Solution: def twoSum(self, nums: List[int], target: int) -> List[int]: nums_map = {} # 딕셔너리에 값을 키로 넣고 인덱스를 값으로 넣는다 # target 에서 num을 뺀 값이 딕셔너리에 존재하면 num과 그 값을 출력하면 정답이다. for i, num in enumerate(nums): nums_map[num] = i for i, num in enumerate(nums): # 이 문제에선 두 숫자를 리턴해야 하므로 # 만약 target - num이 자기 자신이라면 안되므로 조건문에서 .. 2021. 1. 5. 구간 합 계산 (Prefix Sum) 구간 합 빠르게 계산하기 Prifix Sum이란 리스트의 앞에서부터 특정 위치까지의 합을 의미한다. 문제 N개의 정수로 구성된 수열이 있고, M개의 쿼리 정보가 주어진다. 각 쿼리는 L과 R로 구성된다. [L, R] 구간에 해당하는 데이터들의 합을 모두 구하는 문제이다. 시간제한은 O(N+M) 이다. 원리 1. Prefix Sum을 계산하여 임의의 배열 P에 저장한다. 2. 매 M개의 쿼리 정보를 확인할 때, 구간 합은 P[R] - P[L - 1] 이다. 10 20 30 40 50 Prefix Sum을 계산하면 아래와 같다. 0 10 30 60 100 150 P[0] P[1] P[2] P[3] P[4] P[5] 코드 # 데이터 개수 n과 데이터 입력 n = 5 data = [10, 20, 30, 40, .. 2021. 1. 5. 투 포인터 (two pointer) 기법 투 포인터로 특정한 합을 가지는 부분 연속 수열 찾기 투 포인터 기법이란 리스트에 순차적으로 접근해야 할 때 두 개의 점을 이용해 위치를 기록하면서 처리하는 기법이다. 이 문제는 O(N) 의 시간복잡도로 해결할 수 있다. (O(N)는 선형시간 알고리즘이다.) 문제 아래와 같이 자연수로 구성된 N개의 수열이 있다. 합이 M인 부분 수열의 개수를 구하시오. 1 2 3 2 5 원리 1. 시작점(start), 끝점(end)이 첫 번째 원소의 인덱스(0)를 가리키도록 한다. 2. 현재 부분 합이 M과 같다면 카운트를 증가시킨다. 3. 현재 부분 합이 M보다 작거나 같다면 end를 1 증가시킨다. 4. 현재 부분 합이 M보다 크다면, start를 1 증가시킨다. 5. 모든 경우를 확인할 때까지 2번부터 4번까지의 .. 2021. 1. 5. 이전 1 ··· 4 5 6 7 8 9 10 다음