yeony's story

Better Worse O(1) , O(log n), O(n), O(n^2), O(n^3), O(2^n) 상수, 로그, 직선(선형), 선형로그, 제곱, 지수 요새 기술이 발전해서, 공간 복잡도보다는 시간복잡도가 훨 중요하다! 그래서, 시간을 최소화하여 효율적으로 코드를 작성해야 좋은 코드라고 할 수 있다고 한다. (알고리즘은 무엇을 만들기 위한 일련의 과정) 시간 복잡도에서 가장 중요한 것은? 정해진 표현식에 가장 큰 영향을 미치는 n의 단위이다. O(n) 최고차항만 가져오기 O(N+M) ex2) int a = 0; #1 for (i = 0; i i; j--) { # N-i a = a + i + j; } } ''' i=0 , j=N~2 (i+2) ..

입력값 1 2 1 2 1 2 belt = deque(list(map(int, input().split()))) # deque([1, 2, 1, 2, 1, 2]) 입력값 1 2 1 2 1 2 3 4 3 4 3 4 belt = deque(list(map(int, input().split())) for _ in range(2)) # deque([[1, 2, 1, 2, 1, 2], [3, 4, 3, 4, 3, 4]]) 입력값 3 (N값) robot = deque(i for i in range(N)) print(robot) # deque([0, 1, 2]) 입력값 3 (N값) robot=deque([i] for i in range(N)) print(robot) # deque([[0], [1], [2]]) 입력값 ..

- 입력받는 데이터가 1줄에 1개 있을 경우 ex) 1 num=int(input()) - 입력받는 데이터가 1줄에 2개 이상일 경우 (2개라고 가정함, 입력받는 데이터가 숫자일 경우) ex) 1 2 n1,n2=map(int,input().split()) (입력받는 데이터가 문자일 경우) ex) R R R U D D list1=input().split() # 결과값 # ['R', 'R', 'R', 'U', 'D', 'D'] (입력 받는 데이터가 숫자이고, 리스트로 받을 경우) array=[] array=list(map(int,input().split()) - 2차원 배열 맵 초기화하기 n,m=map(int,input().split()) # n은 행, m은 열 map_list=[[0]*m for _ in r..

import sys sys.setrecursionlimit(100000)

import sys input_data=sys.stdin.readline().rstrip() print(input_data) 입력 데이터의 개수가 많을 땐 input()함수 사용 삐--! readline()함수를 사용하면 시간 초과를 피할 수 있다 ** readline()을 사용하여 입력 하게 되면, 엔터가 줄바꿈기호로 입력되는데 rstrip()을 이용해서 공백 문자를 제거해줘야한다.

1. 스택과 큐 (1) 스택 - 후입선출 - 삽입은 append(n) , 삭제는 pop() (2) 큐 - 선입선출 - 파이썬에선 큐 구현을 위해 deque 라이브러리를 사용한다. - 삽입 append(n), 삭제 popleft() - queue 라이브러리 대신 deque 라이브러리를 사용하는 이유? (from collections import deque) >> deque는 스택과 큐의 장점을 모두 채택한 것이라서 데이터를 넣고 빼는 속도가 훨씬 빠르기 때문! >> 코테에서는 collections 모듈과 같은 기본 라이브러리 사용을 허용함 : 코테 라이브러리에 대한 내용이 자세히 잘 나와있어서 주소 첨부! https://velog.io/@koyo/python-docs-6 [내가 보려고 적는 파이썬] 주요 ..

1. 그리디 ( =탐욕법) : 현재 상황에서 가장 좋아보이는 것만을 선택하는 알고리즘 > 그리디 알고리즘 유형 문제는 매우 다양하기에 암기만 한다고 해서 문제를 다 풀 수 있는 건 절대 아니다 * 그리디 알고리즘은 기준에 따라 좋은 것을 선택하는 알고리즘이기에 문제에 알게 모르게 기준을 제시해준다 (예를 들면, 가장 큰 순서대로 또는 가장 작은 순서대로 ...) 이 기준들은 정렬 알고리즘을 사용할 때 만족시킬 수 있으므로 주로 그리디 알고리즘은 정렬 알고리즘과 짝을 지어 문제가 출제 된다. 2. 구현 : 머릿속에 있는 알고리즘을 정확하고 빠르게 프로그램으로 작성하는 방법이다. 구현이란 머릿속에 있는 알고리즘을 소스 코드로 바꾸는 과정을 의미함 완전 탐색, 시뮬레이션 유형을 모두 구현 유형으로 묶어서 다룬..

참고 출처 : 이것이 코딩테스트다 with 파이썬 다이나믹 프로그래밍 : 동적 계획법 피보나치 수열은 재귀함수로도 구현이 가능하지만, 숫자가 커질수록 연산수가 늘어남.. 그래서 피보나치 수열은 보통 다이나믹 프로그래밍을 사용해서 구현함. 항상 다이나믹 프로그래밍을 사용할 수 있는 것은 아니다. 다음 조건을 만족할 때만 다이나믹 프로그래밍을 사용할 수 있다. 1. 큰 문제를 작은 문제로 나눌 수 있다. 2. 작은 문제에서 구한 정답은 그것을 포함하는 큰 문제에서도 동일하다. 피보나치 수열을 메모이제이션 기법을 사용해서 해결하기 (메모이제이션은 다이나믹 프로그래밍 구현 방법 중 하나이다.) => 메모이제이션 기법은, 한 번 구한 결과를 메모리 공간에 메모해두고 같은 식을 다시 호출하면 메모한 결과를 그대로 ..

참고 출처 : 이것이 코딩테스트다 with 파이썬 # 부품 찾기 [이진탐색] : 재귀함수 이용할 것 1. 함수 인자에 리스트, 타겟, 0 (초기 start값), n-1 (end값)을 매개변수로 넘겨준다. 2. def function 함수 - start 값이 end보다 크면, None 값을 반환 - 만약 리스트[mid] 값이 target이랑 값이 같으면 mid를 반환한다. - 만약 ... 크다면 function(리스트, 타켓, start, mid-1) => end 값이 mid-1로 변경 - 만약 ... 작다면 start 값이 mid+1로 변경 책 답지 #떡볶이 떡 만들기 => 이진 탐색 문제이자, 파라메트릭 서치 유형의 문제 파라메트릭 서치는 최적화 문제를 결정 문제로 바꾸어 해결하는 기법이다. 원하는 조..

순차 탐색>> 리스트 안에 있는 특정한 데이터를 찾기 위해 앞에서부터 데이터를 하나씩 차례대로 확인 >> 최악의 경우 시간 복잡도 O(N) 이진 탐색 >> 반으로 쪼개면서 탐색하기 >> 찾으려는 데이터와 중간점 위치에 있는 데이터를 반복적으로 비교해서 원하는 데이터 찾기 이진 탐색은 원소의 개수가 절반씩 줄어든다 따라서 시간 복잡도는 O(logN) 이진탐색 구현 방법은 재귀함수 이용, 반복문 이용 처리해야할 데이터의 개수나 값이 1000만 단위 이상이면, 이진 탐색과 같이 O(logN)의 속도를 내는 알고리즘을 떠올려야함 문제에 자주 나오니 외우길 권장 트리 자료구조>> 큰 데이터를 처리하는 소프트웨어는 대부분 데이터를 트리 자료구조로 저장해서 이진 탐색과 같은 탐색 기법을 이용해 빠르게 탐색 가능 이진..