study (19) 썸네일형 리스트형 [탐색의 종류] 완전탐색/이분탐색/깊이우선탐색/너비우선탐색 1) 완전탐색: 브루트 포스라고도 불리며 컴퓨터의 빠른계산 성능을 활용하여 가능한 모든 경우의 수를 탐색풀리지 않는 문제는 없으나 효율성 관점에서 최악.. - 완전탐색 구현방법ㆍ 반복문ㆍ 재귀함수(완전탐색 외에도 동적계획법, 백트래킹, 탐욕법에서도 사용)# 반복문으로 구현def solution(trump): for i in range(len(trump): if trump[i] == 8: return i return -1 # 재귀함수로 구현def solution(trump, loc): if trump[loc] == 8: return loc else: return solution(trump, loc+1) 2) 이분탐색이진검색이라고도 표현하며 오름.. 스택, 큐, 덱 1) 스택(Stack) - 데이터를 접시쌓듯이 차곡차곡 쌓는다 - 맨 마지막에 들어온 데이터 먼저 차출됨(LIFO) 선입후출 - FILO(First In Last Out)구조로 삽입과 삭제 연산이 동일한 한군데에서 발생 - 삽입/삭제 연산에 있어 시간복잡도가 O(1) - 이전에 활용한 데이터를 역으로 추적하거나 처음 들어온 데이터보다 나중에 들어온 데이터가 빨리나갈 때 사용 - List의 pop() 을 활용하면 Stack처럼 사용할 수 있음 - Python에서 LifoQueue라는 구현체가 있음 - 활용예시: 브라우저 뒤로가기 앞으로가기, 깊이 우선 탐색(DFS) # 스택 직접 구현 class Stack(list): push = list.append def peek(self): # 가장 마지막에 있는 데.. 시간복잡도(Big-O) 시간복잡도를 표기하는 방법Big-O(빅-오) ⇒ 상한 점근Big-Ω(빅-오메가) ⇒ 하한 점근Big-θ(빅-세타) ⇒ 그 둘의 평균위 세 가지 표기법은 시간 복잡도를 각각 최악, 최선, 중간(평균)의 경우에 대하여 나타내는 방법Big-O빅오 표기법은 최악의 경우를 고려하므로, 프로그램이 실행되는 과정에서 소요되는 최악의 시간까지 고려할 수 있기 때문이다.“최소한 특정 시간 이상이 걸린다” 혹은 “이 정도 시간이 걸린다”를 고려하는 것보다 “이 정도 시간까지 걸릴 수 있다”를 고려해야 그에 맞는 대응이 가능하다.Big-O 표기법은 ‘입력값의 변화에 따라 연산을 실행할 때, 연산 횟수에 비해 시간이 얼마만큼 걸리는가?’를 표기하는 방법이다. 표기 예시형태O(1)상수O(log n)로그O(n)선형O(n log .. 백트래킹 백트래킹?현재 상태에서 가능한 모든 경로를 따라 들어가 탐색하다, 원하는 값과 불일치하는 부분이 발생하면 더 이상 탐색을 진행하지 않고 전 단계로 돌아가는, 즉 이름 그대로 방금 왔던 길을 되짚어가는, backtrack1 하는 알고리즘이다. Promising : 트리 구조를 기반으로 DFS로 깊이 탐색을 진행하면서 각 루트에 대해 조건에 부합하는지 체크한다.Pruning (가지치기): 해당 트리에서 조건에 맞지않는 노드는 더 이상 DFS로 깊이 탐색을 진행하지 않고 가지치기를 한다. 해를 구하는 도중 해가 아니어서 막히면 막히기 전으로 다시 돌아가서 해를 찾는 기법가상의 트리에서 해를 구하기 위해 부모 노드에서 자식 노드까지 뻗어나간다. 만약 해당 노드가 조건에 맞지 않는다면 다시 부모노드로 돌아간다.해.. 삼항연산자 입력된 세 정수 a, b, c 중 가장 작은 값을 출력하는 프로그램을 작성해보자. 단, 3항 연산을 사용한다. 따라서 3항 연산을 중첩해(괄호로 묶는 등..) 이용하면 여러 값들을 순서대로 비교해 가장 큰/작은 값을 계산할 수 있다. 예를 들어 (a if a>b else b) if ((a if a>b else b)>c) else c 와 같은 계산식은 a, b, c 의 값 중 가장 큰 값으로 계산된다. “연산자 우선순위”를 검색하면 우선순위와 결합방향이 나온다. 예를 들어 변수에 어떤 값을 대입하는 대입(assign) 연산자 = 의 우선순위는 가장 낮고, 오른쪽에서 왼쪽의 결합방향을 가진다. a, b, c = input().split() a = int(a) #변수 a에 저장되어있는 값을 정수로 바꾸어 다시.. 비프시프트연산 왼쪽 비트시프트()가 될 때에는 왼쪽에 0(0 또는 양의 정수인 경우)이나 1(음의 정수인 경우)이 개수만큼 추가되고, 가장 오른쪽에 있는 1비트는 사라진다. 예시 n = 10 print(n1) #10을 반으로 나눈 값인 5 가 출력된다. print(n2) #10을 반으로 나눈 후 다시 반으로 나눈 값인 2 가 출력된다. 정수 10의 2진수 표현은 ... 1010 이다. 10 > 1 을 계산하면 ... 101 이 된다. 이 값은 10진수로 5이다. ** python에서 실수 값에 대한 비트시프트 연산은 허용되지 않고 오류가 발생한다. (실수 값도 컴퓨터 내부적으로는 2진수 형태로 저장되고 비트시프트 처리가 될 수 있지만, python 에서는 허용하지 않는다.) 정수 2개(a, b)를 입력받아 a를 2b배.. input 대신 sys.stdin.readline 시간복잡도 본격적으로 for문 문제를 풀기 전에 주의해야 할 점이 있다. 입출력 방식이 느리면 여러 줄을 입력받거나 출력할 때 시간초과가 날 수 있다는 점이다. , 이때는 맨 끝의 개행문자까지 같이 입력받기 때문에 문자열을 저장하고 싶을 경우 .rstrip()을 추가로 해 주는 것이 좋다. import sys n = sys.stdin.readline() 10진수, 8진수, 16진수 10진수를 8진수, 16진수로 출력하기 '%x'%n print('%X%n) 대문자 형태 문자열로 출력 %x 16진수(hexadecimal) %o 8진수(octal) 16진수를 10진수로 ㅂ a = input() n = int(a,16) 이전 1 2 3 다음
