viamemine

스택의 ADT라는 것을 정의해보고 실제 스택이 동작하는 원리를 설명해보겠습니다.ADT는 abstract data type (추상 자료형)입니다. 추상 자료형이란 인터페이스만 있고 실제로 구현은 되지 않은 자료형 입니다. 언어에 따라 표준 라이브러리에서 스택 제공 여부는 다릅니다. 파이썬의 경우 스택을 제공하진 않지만 대안으로 리스트 메서드인 append() 메서드, push() 메서드로 스택을 대체할 수 있습니다. deque은 한쪽으로만 데이터 삽입, 삭제 할 수 있는 스택과는 다르게 양쪽에서 데이터를 삽입하거나 삭제할 수 있는 자료구조 입니다. 스택의 ADT(연산과 상태)스택 세부 동작에 대해 자세히 알아보기 스택에 데이터를 추가하는 경우를 생각해봅시다. 푸시 연산을 수행할 때  스택 내부에서 일어나는..

my_list = [1, 2, 3]my_list = my_list + [4, 5] # [1, 2, 3, 4, 5]배열 선언일반적인 방법 arr = [0, 0, 0, 0, 0, 0] arr = [0] * 6 리스트 생성자를 사용하는 방법arr = list(range(6)) # [0, 1, 2, 3, 4, 5] 리스트 컴프리헨션을 활용하는 방법 arr = [0 for _ in range(6)] # [0, 0, 0, 0, 0, 0]  2차원 배열리스트 컴프리헨션을 활용하면 다음과 같이 선언할 수도 있습니다.# 크기가 3 * 4인 리스트를 선언하는 예arr = [[i]*4 for i in range(3)] # [[0, 0, 0, 0], [1, 1, 1, 1], [2, 2, 2, 2]]   1차원 배열이..

시간 복잡도(time complexity)알고리즘의 성능을 나타내는 지표로, 입력 크기에 대한 연산 횟수의 상한을 의미합니다. 시간 복잡도는 낮으면 낮을수록 좋습니다. 입력 크기에 따른 연산 횟수의 추이를 활용해서 시간 복잡도를 표현하는 방법을 점근적 표기법이라고 합니다.  코딩 테스트 필수 문법빌트인 데이터 타입(built-in data type)은 언어 자체에서 제공하는 데이터 타입과 컬렉션 데이터 타입이 있습니다.기본 데이터 타입: int, float, string컬렉션 데이터 타입: list, tuple, set, dictionary 정수형 비트 연산print(a & b) # AND / 4print(a | b) # OR / 13print(a ^ b) # XOR / 9print(~a..

DP 사용조건- 큰 문제를 작은 문제로 나눌 수 있음- 작은 문제에서 구한 정답은 그것을 포함하는 큰 문제에서도 동일함  탑다운(Top-Down) 방식- 작은 문제를 재귀적으로 해결d = [0] * 100 # 한 번 계산된 결과를 memoization하기 위한 list 초기화def fibo(x): # 피보나치 함수를 재귀함수로 구현 (탑다운) if x == 1 or x == 2: return 1 if d[x] != 0: # 이미 계산한 적 있는 문제라면 그대로 반환 return d[x] d[x] = fibo(x - 1) + fibo(x - 2) # 아직 계산하지 않은 문제라면 점화식에 따라 결과 반환 return d[x]print(fibo(99))  ..

선택 정렬 - 매번 가장 작은 것을 선택하여 맨 앞과 교체하는 방법- 시간 복잡도: O(N^2)for i in range(len(array)): min_index = i for j in range(i+1, len(array)): if array[min_index] > array[j]: min_index = j array[i], array[min_index] = array[min_index], array[i]  삽입 정렬- 데이터를 하나씩 확인하며, 각 데이터를 적절한 위치에 삽입하는 방법- 시간 복잡도: O(N^2), 데이터가 정렬되어 있는 경우 O(N)for i in range(1, len(array)): for j in range(i, 0, -1)..

내장 함수- evalresult = eval("(3+5) * 7") # 56 - sortedresult = sorted([9,1,8,5,4]) # [1,4,5,8,9]result = sorted([9,1,8,5,4], reverse=True) # [9,8,5,4,1]result = sorted([('홍길동', 35), ('이순신', 75), ('아무개', 50)], key=lambda x: x[1], reverse=True) # [('이순신', 75), ('아무개', 50), ('홍길동', 35)] - .sort(): 내부 값이 바로 변경됨data = [9,1,8,5,4] data.sort() # [1,4,5,8,9]   itertools- permutations(순열): 서로 다른 n개 중에 r개를 선..

더보기더보기해당 게시글은 https://covenant.tistory.com/143 을 참고하여 작성했습니다. 이번 챕터는 문제 풀이 중간 중간에 들어가는 꼭 ! 기억해야 풀이 시간이 줄어드는 순열, 조합, 빈도계산, 덱, 우선순위 큐에 대해 알아보겠습니다.  1. 순열, 조합1-1. 순수한 방법for문 2개를 사용해서 nC2를 구하는 방법은 다음과 같습니다.for i in range(0, N-1): for j in range(i+1, N): print(i, j) 백준 9613번 GCD 합 문제를 풀 수 있습니다. GCD는 다음 챕터에서 살펴볼 것입니다.그렇다면 nC3은? nC4는...? for문을 사용해서는 한계가 있습니다. 1-2. itertools을 사용한 조합from iter..

더보기더보기해당 글은 https://covenant.tistory.com/142 를 참고하여 작성하였습니다.  1. 정수1-1. 최대, 최소ans = ???for num in arr: if ans > num: ans = numprint(ans) 배열 arr에 있는 값을 for문으로 순회하고 있습니다. 마지막에 출력되는 ans에 arr에 저장되어 있는 값 중 최솟값이 저장되게 하고 싶습니다. 그렇다면 첫번째 줄 ans에 무엇을 저장해야 할까요 ? arr에 있는 최댓값보다 큰 수가 저장되면 됩니다.ans = 999999 ans에 임의로 큰 값을 쓰는 방법도 있습니다. 보통은 문제에서 주어지는 입력 범위 값보다 큰 값을 설정합니다. 예를 들어 arr에는 100,000을 넘지 않는 값이 저장된..

더보기더보기해당 글은 https://covenant.tistory.com/141 를 참고하여 작성하였음을 알려드립니다. 코딩테스트는 객체 지향적으로 코드를 짤 필요도 없고, 직접 자료구조를 구현할 필요도 없습니다. 주어진 시간 내 간결함과 정확함이 생명입니다. 파이썬으로 코딩테스트를 준비하시는 분들에게 도움이 될만한 자료들을 공유합니다. 1. 다양한 입력코딩테스트에서 기본은 주어진 테스트 케이스를 입력 받는 것입니다.  1-1. 나누어 입력받기다음 입력값이 주어졌을 때 각각 변수에 값을 입력받는 법을 보겠습니다. 1 2 a, b = map(int, input().split()) C, JAVA의 경우 데이터 타입(int, long long ...)에 따라서 저장할 수 있는 최대 정수의 범위가 결정되지만 파..