K

큐를 사용한 문제 # 카드2 # N장의 카드가 순서대로 존재한다. 맨 윗장을 버리고, 다음 장을 맨 밑으로 넣는 작업을 반복한다. # 마지막에 남는 카드의 숫자를 출력하시오. from collections import deque n = int(input()) myque = deque() for i in range(1, n+1): myque.append(i) while len(myque) != 1: myque.popleft() myque.append(myque.popleft()) print(myque[0])

# 스택 수열 # 1 ~ n까지의 수를 이용해 수열을 만든다. 스택의 연산을 이용하여 만들 수 있는지 판단하라. # 스택에는 오름차순으로 입력되며, 수열은 1 이상 n 이하의 정수로 이루어져 있으며, 같은 수가 두 번 나오는 일은 없다. # push 연산은 +로, pop 연산은 -로, 불가능하다면 NO를 출력한다. n = int(input()) array = [0] * n for i in range(n): array[i] = int(input()) stack = [] num = 1 answer = [] result = True for i in range(n): # 필요한 수가 현재 자연수보다 크다면 스택에 자연수 삽입 및 자연수++ while array[i] >= num: stack.append(num)..

Do it! 알고리즘 코딩 테스트 - 파이썬 편 (김종관) 책을 이용하여 알고리즘 공부 중입니다 😃 https://www.youtube.com/watch?v=JwOFYxirPPU&list=PLFgS-xIWwNVX-zm4m6suWC9d7Ua9z7fuT&index=12 스택 Last In First Out, LIFO, 후입선출 한 쪽에서만 삽입과 삭제가 이루어짐 top: 삽입과 삭제가 일어나는 위치, 가장 끝(위) s.append(data): top 위치에 새로운 데이터를 삽입하는 연산 s.pop(): top 위치에 현재 있는 데이터를 삭제&확인하는 연산 깊이 우선 탐색(DFS), 백트래킹 종류의 코딩 테스트에 효과적 개념 자체가 재귀 함수 알고리즘 원리와 일맥상통함 큐 First In First Out, ..

# 최솟값 찾기 # N개의 수와 L이 주어진다. D(i) = A(i-L+1) ~ A(i) 중의 최솟값이라고 할 때, D에 저장된 수를 출력하시오. # 첫째 줄에는 N, L이 주어지고, 둘째 줄에는 N개의 수가 주어진다. from collections import deque N, L = map(int, input().split()) mydeque = deque() now = list(map(int, input().split())) for i in range(N): while mydeque and mydeque[-1][0] > now[i]: mydeque.pop() mydeque.append((now[i], i)) if mydeque[0][1]

# DNA 비밀번호 # 첫 번째 줄에 민호가 임의로 만든 DNA 문자열 길이 |S|와 비밀번호로 사용할 부분문자열의 길이 |P| 가 주어진다. (1 ≤ |P| ≤ |S| ≤ 1,000,000) # 두번 째 줄에는 민호가 임의로 만든 DNA 문자열이 주어진다. # 세번 째 줄에는 부분문자열에 포함되어야 할 {‘A’, ‘C’, ‘G’, ‘T’} 의 최소 개수가 공백을 구분으로 주어진다. # 각각의 수는 |S| 보다 작거나 같은 음이 아닌 정수이며 총 합은 |S| 보다 작거나 같음이 보장된다. # 첫 번째 줄에 민호가 만들 수 있는 비밀번호의 종류의 수를 출력해라. checkList = [0] * 4 # 부분문자열에 포함되어야 할 최소 개수 myList = [0] * 4 # 부분문자열 문자의 개수 checkS..

투 포인터를 활용한 문제 이 문제의 핵심은 본인을 제외했는가 인 것 같다. 예를 들어, 0 3 5 8 11이 주어졌을 때 답은 2(8, 11)이다. 그러나 본인을 제외하는 예외처리를 하지 않는다면, 0 + 3 = 3, 0 + 5 = 5 등 0이 카운팅 되어서 답안에 중복이 생긴다. 그렇기 때문에 if num[i] + num[j] == num[k] 안에서 if i != k and j != k를 통해 한 번 더 거르는 작업이 필요하다. # 좋다 # N개의 수 중 어떤 수가 다른 수 두 개의 합으로 나타낼 수 있으면 그 수를 '좋다'고 한다. # N개의 수 중 몇 개가 좋은 수인지 출력하시오. 수가 같아도 위치가 다르면 다른 수이다. # 첫째 줄에는 수의 개수 N, 둘째 줄에는 N개의 수가 주어진다. impo..

투 포인터를 활용한 문제 제한시간은 2초지만 N의 범위가 15,000까지기 때문에 O(nlogn)의 시간복잡도 내에 풀면 된다. 파이썬의 정렬 라이브러리인 sort를 이용할 수 있다. 파이썬의 정렬 라이브러리는 병합정렬 기반으로 O(nlogn)의 시간복잡도를 가진다. 정렬 후 맨 앞과 맨 끝 인덱스를 기준으로 비교를 시작한다. 둘의 합이 M이 됐다면 cnt++ 후 각 값을 1씩 옮긴다. 둘의 합이 M보다 작다면 시작 인덱스 i++를 한다. 둘의 합이 M보다 크다면 끝 인덱스 j--를 한다. # 주몽 # 두 숫자를 합쳐 M이 되어야 한다. N개의 숫자와 M이 주어졌을 때 몇 개의 조합이 만들어지는지 구하시오. # 첫째 줄에는 숫자의 개수N이 주어진다. 두 번재 줄에는 M이 주어진다. 세 번째 줄에는 N개의..

투 포인터를 활용한 문제 start와 end 포인터를 이용해서 문제를 해결했다. 합이 n과 같다면 cnt++을 한 후 end++ 합이 n보다 크다면 합에서 start 값을 빼준 후 start++ 합이 n보다 작다면 end++ 후 sum에 값 더하기 sum에 더하는게 먼저인지 end++이 먼저인지 판단하는게 중요한 듯하다. # 수들의 합 5 # 어떠한 자연수 N은 몇 개의 연속된 자연수의 합으로 나타낼 수 있다. 이 N에 대해서 몇 개의 연속된 자연수의 합으로 나타낼 수 있는지 가지수를 알고 싶다. # 첫 줄에 정수 N이 주어진다. 가지수를 출력하시오. n = int(input()) start = 1 end = 1 sum = 1 cnt = 1 while end != n: if sum == n: cnt +=..

나머지가 같은 수를 고른다면, 그 둘 사이의 값은 나머지가 0이 된다는 게 메인 포인트같다. 예를 들어.. 1 2 3 1 2 의 숫자가 주어진다면, 구간합은 1 3 6 7 9가 된다. 1 3 6 7 9 를 3으로 나눈 값은 1 0 0 1 0 이 된다. 만약 구간을 A[0] ~ A[3] 으로 정했다면, 7(1,2,3,1) - 1 = 6이 되고, 나머지는 0이 된다. # 나머지가 같은 경우 중 2개를 뽑는 경우의 수 계산 에서 if문 범위를 > 1 로 한 이유는 범위로 뽑는 수는 시작과 끝 2개인데, 나머지가 같은 수가 2개 이상 존재해야 2개를 뽑을 수 있기 때문이다. # 나머지 합 # N개의 수가 주어진다. 연속된 부분 구간의 합이 M으로 나누어 떨어지는 구간의 개수를 구하는 프로그램을 작성하시오. # ..

문제 이해가 너무 안됐다. 글을 모호하게 써둔 것 같음..;; (2,2) ~ (3,4)의 합을 구할 때 (3,1)이 빠지는 이유를 .. 흠 그래서 처음엔 구간 합을 총 누적으로 계산했었다. n, m = map(int, input().split()) origin = list() z = 0 result = list() # 원본 배열 입력 for i in range(0, n): a = list(map(int, input().split())) origin.append(a) # 합배열 생성 sum = [[0]*(n+1)] for i in range(0, n): a = list() for j in range(0, n): z += origin[i][j] a.append(z) sum.append(a) # 합배열 각 행..