K

Do it! 알고리즘 코딩 테스트 - 파이썬 편 (김종관) 책을 이용하여 알고리즘 공부 중입니다 😃 https://www.youtube.com/watch?v=lM6BFazUHjA&list=PLFgS-xIWwNVX-zm4m6suWC9d7Ua9z7fuT&index=15 정렬 알고리즘 정의 버블 bubble 데이터의 인접 요소끼리 비교하고, swap 연산을 수행하며 정렬하는 방식 선택 selection 대상에서 가장 크거나 작은 데이터를 찾아가 선택을 반복하면서 정렬하는 방식 삽입 insertion 대상을 선택해 정렬돈 영역에서 선택 데이터의 적절한 위치를 찾아 삽입하면서 정렬하는 방식 퀵 quick pivot 값을 선정해 해당 값을 기준으로 정렬하는 방식 병합 merge 이미 정렬된 부분 집합들을 효율적으로..

문제에 주어진 것과 유사하게 코드를 작성하면 시간초과가 발생한다. import sys input = sys.stdin.readline n = int(input()) num = [0] * n for i in range(n): num[i] = int(input()) cnt = 1 for j in reversed(range(n)): flag = False for i in range(n - 1): if num[i] > num[i + 1]: flag = True tmp = num[i] num[i] = num[i + 1] num[i + 1] = tmp if flag == False: print(cnt) exit() cnt += 1 버블 정렬을 통해 문제를 풀면 시간 초과가 발생하므로, 새로운 접근 방식이 필요하다...

버블 정렬을 이용한 문제 범위를 1개씩 줄여가며 정렬을 수행한다. 해당 인덱스의 요소와 다음 인덱스의 요소를 비교하여 오름차순으로 정렬한다. # 수 정렬하기 # N개의 수가 주어졌을 때, 이를 오름차순으로 정렬하는 프로그램을 작성하시오. # 첫째 줄에 수의 개수 N이 주어진다. 둘째 줄부터 N개의 줄에는 수가 주어진다. 이 수는 절댓값이 1,000보다 작거나 같은 정수이며, 중복되지 않는다. # 첫째 줄부터 N개의 줄에 오름차순으로 정렬한 결과를 한 줄에 하나씩 출력한다. import sys input = sys.stdin.readline n = int(input()) num = [0] * n for i in range(n): num[i] = int(input()) for j in range(n, 0, ..

Do it! 알고리즘 코딩 테스트 - 파이썬 편 (김종관) 책을 이용하여 알고리즘 공부 중입니다 😃 https://www.youtube.com/watch?v=h2_Lc8a8Ffw&list=PLFgS-xIWwNVX-zm4m6suWC9d7Ua9z7fuT&index=14 정렬 알고리즘 정의 버블 bubble 데이터의 인접 요소끼리 비교하고, swap 연산을 수행하며 정렬하는 방식 선택 selection 대상에서 가장 크거나 작은 데이터를 찾아가 선택을 반복하면서 정렬하는 방식 삽입 insertion 대상을 선택해 정렬돈 영역에서 선택 데이터의 적절한 위치를 찾아 삽입하면서 정렬하는 방식 퀵 quick pivot 값을 선정해 해당 값을 기준으로 정렬하는 방식 병합 merge 이미 정렬된 부분 집합들을 효율적으로..

우선순위 큐를 이용한 문제 파이썬에서 우선순위 큐를 사용하기 위해선 queue 모듈의 PriorityQueue 클래스를 임포트 해야 한다. 파이썬에서는 데이터의 순서가 정렬의 우선순위가 된다. myQueue.put((abs(request), request)) 에서 abs(request)가 절댓값을 나타내므로, 먼저 절댓값을 기준으로 정렬한다. 그 후 request를 기준으로 정렬하므로 절댓값이 같다면 음수 -> 양수 순서로 정렬된다. # 절댓값 힙 # 배열에서 절댓값이 가장 작은 값을 출력하고, 그 값을 배열에서 제거한다. 절댓값이 가장 작은 값이 여러개일 때는, 가장 작은 수를 출력하고, 그 값을 배열에서 제거한다. # 첫째 줄에 연산의 개수 N(1≤N≤100,000)이 주어진다. 다음 N개의 줄에는 ..

스택을 이용한 문제 스택에는 인덱스의 번호만 저장 스택의 top을 이용해 배열의 값 불러옴 ( A[stack[-1]] ) # 오큰수 # A[i]에 대해 오른쪽에 있는 수 중 A[i]보다 크면서 가장 왼쪽에 있는 수를 오큰수라고 한다. # N개의 수가 주어졌을 때 이들의 오큰수를 모두 출력하시오. n = int(input()) array = list(map(int, input().split())) stack = [] result = [0] * n for i in range(n): # 스택이 비어있지 않고, top 번호의 배열 값이 현재 배열 값보다 작다면, top 번호의 오큰수는 현재 배열 값 while stack and array[stack[-1]] < array[i]: result[stack.pop()..

큐를 사용한 문제 # 카드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]