yeony's story

참고 출처 : 이것이 코딩테스트다 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)의 속도를 내는 알고리즘을 떠올려야함 문제에 자주 나오니 외우길 권장 트리 자료구조>> 큰 데이터를 처리하는 소프트웨어는 대부분 데이터를 트리 자료구조로 저장해서 이진 탐색과 같은 탐색 기법을 이용해 빠르게 탐색 가능 이진..

참고 출처 : 이것이 코딩테스트다 with 파이썬 1. 기준에 따라 데이터를 정렬 정렬이란? 데이터를 특정한 기준에 따라서 순서대로 나열하는 것을 의미한다. 면접에서 단골문제로 자주 등장한다. 리스트를 뒤집는 연산은 O(N)의 복잡도로 간단히 수행할 수 있다. 정렬은 이진탐색의 전처리과정이다. 정렬 종류 : 선택 정렬, 삽입 정렬, 퀵 정렬, 계수 정렬 (1) 선택 정렬 : 매번 가장 작은 것을 선택한다는 의미. 가장 작은 것을 선택해서 앞으로 보내는 과정을 반복해서 수행하다 보면, 전체 데이터의 정렬이 이루어진다. 스와프? 특정한 리스트가 주어졌을 때 두 변수의 위치를 변경하는 작업이다. 선택정렬의 시간복잡도는 O(N^2) #2중 반복문이 사용되었기 때문 (2) 삽입 정렬 : 특정한 데이터를 적절한 위..

스택 (후입선출) append() // pop() 큐 (선입선출) 파이썬을 큐 규현 시 collections 모듈에서 제공하는 deque 자료구조 활용 queue 라이브러리보다 효율적이다. 재귀함수 : 자기 자신을 다시 호출하는 함수. 파이썬에서는 무한대로 재귀 호출 진행 불가 재귀함수는 수학 시간에 한 번씩 언급되는 프랙털 구조와 비슷하다. 재귀함수에서는 종료 조건을 꼭 명시해야 한다. 스택 구조를 활용해야하는 경우 재귀함수를 이용해서 간편하게 대부분 구현이 가능하다. 팩토리얼이 재귀 함수의 대표적인 예시문제 n이 0이거나 1일 때 값은 1 2부터는 n*factorial(n-1) 탐색 알고리즘 DFS/BFS DFS : 깊이 우선 탐색(Depth-first search), 그래프에서 깊은 부분을 우선적으..

mlist=[list(input()) for _ in range(4)]

참고 문헌 : 이것이 코딩테스트다 with 파이썬 구현이란? : 머릿속에 있는 알고리즘을 소스코드로 바꾸는 과정이다. 구현 ( 완전탐색, 시뮬레이션 ) 완전 탐색 : 모든 경우의 수를 다 계산 시뮬레이션 : 문제에서 제시한 알고리즘을 한 단계씩 차례대로 수행 알고리즘 풀 때 시간제한과 데이터의 개수를 먼저 확인 후, 예측을 해야한다. 구현 문제 접근 방법 >> 사소한 입력 조건을 문제에 명시, 문제의 길이가 꽤 긴 편이다. API 개발 문제 = 구현 유형 비슷 n,m=int(input().split()) >> n과 m에 각각 숫자 넣을 수 있음. 방향 문제는 dx,dy 리스트 만들어서 하기 for plan in plans: >> 이중리스트일 때 사용 고려해볼 것 # col=int(ord(input_dat..

참고 출처 : 이것이 코딩테스트다 with 파이썬 그리디 알고리즘 = 탐욕법 >> 가장 큰 순서대로 or 가장 작은 순서대로와 같이 기준을 제시해줌. 그리디 알고리즘 대표 문제 : 거스름돈 >> 가장 큰 화폐 단위부터 돈을 거슬러준다. >> for문과 list를 이용해서 간단하게 작성하기 연습... coin_types 리스트에는 나눠야 하는 동전의 종류를 넣는다. count는 동전이 개수 문제 유형을 파악하기 어려울 때 그리디 알고리즘 문제를 의심 -> 이게 아니라면 다이나믹 프로그래밍이나 그래프 알고리즘 등으로 문제를 해결할 수 있는 지 체크 체크 >> 굳이 2중리스트를 만들지 않아도 min함수를 이용하면 간편하게 할 수 있음. 함수 1행씩 검사할때마다 가장 작은 수를 찾아내고, result와 좀 전에..