viamemine

시간 복잡도(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://www.acmicpc.net/problem/1918  풀이 오늘은 stack, queue, deque의 문제 유형인 후위 표기식을 풀어보겠습니다. 연산자 우선순위1. () 2. * /3. + - stack을 이용하여 연산자의 우선순위를 고려하여 문제를 해결해보도록 하겠습니다.  리스트에 식전체를 넣어 for문을 통해 한 문자씩 확인합니다.1. ()를 확인2. * / 인지를 확인하고, 먼저 들어온 같은 우선순위에 있는 * /는 모두 출력 문자열에 추가3. 현재 연산자를 stack에 추가4. + - 인지를 확인하고, + - 보다 낮은 우선순위의 연산자가 없기 때문에 자신보다 우선순위가 높은 연산자들을 모두 출력 문자열에 추가5. )를 발견하면 ( 와 ) 사이에 있는 모든 연산자들을 출력..

Queue 설명 먼저 들어온 데이터가 먼저 나가는 구조이다.선입선출(FIFO:First In First Out) 구조라고 한다. Stack은 한 쪽이 막혀있어 입구와 출구가 하나라면,Queue는 입구와 출구가 따로있다. Queue는 연결 리스트(linked list)로 구현이 되는데 python에서 queue 구현을 위해 deque() 함수를 제공한다.Import하여 쉽게 사용하면 된다.  List 자료구조가 있는데 왜 굳이 queue를 사용할까 ? Linked list는 제일 앞의 요소를 꺼낼 때 head 노드를 두 번째 노드로 바꾸고 head 노드였던 자료는 queue에서 빠져나온다. 이는 빅오 표기법에 따라 O(1)이라는 매우 빠른 연산이 가능하다. 하지만 array list는 순서대로 배열되어 있..

Stack 설명 Stack은 먼저 들어온 데이터는 제일 늦게 나가게 되고, 맨 마지막에 들어온 자료가 제일 먼저 나가는 자료구조이다.후입선출(LIFO: Last In First Out) 구조라고 한다. Stack은 한 쪽 끝에서만 자료를 넣거나 뺄 수 있도록 제한된 선형으로 나열된 자료구조이다.  Python에서 stack의 자료구조는 배열 순서에 따른 배열 리스트(array list)와논리 순서에 따른 연결 리스트(linked list) 두 가지로 활용되는데,알고리즘 코딩테스트에서는 주로 배열 리스트(array list) 형식인 list 자료구조로 stack을 사용한다.  Stack 기본 연산Stack의 입출력은 .append() 리스트 제일 뒤에 데이터 입력과.pop() 리스트 제일 뒤에 데이터 출력..

더보기더보기해당 게시글은 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 ...)에 따라서 저장할 수 있는 최대 정수의 범위가 결정되지만 파..