[도서] 코딩테스트 합격자 되기 _ 파이썬 편

\-> 어떤 위치에 있는 데이터든 한 번에 접근 가능, random access에 유용일반적인 방법리스트 생성자를 사용하는 방법arr=0 for \_ in range(6) \`\`\`배열은 인덱스가 0부터 시작파이썬에서는 배열을 코드와 함께 설명할 때 리스트를 사용2차

정수 배열을 정렬해서 반환시간복잡도 : O(NlonN)이 문제에서는 시간복잡도를 한 번쯤 확인하고 고려해보는 것이 핵심 !파이썬은 1초에 1000만번 (10^7) 연산\-> 제한 시간이 1초면 1000만번 연산 이상인 알고리즘을 선택해야함n! 최대 10번2^n 최대 2

스택 : 쌓는다 ! 먼저 입력한 데이터를 제일 나중에 꺼낼 수 있는 자료구조 (FILO)삽입하는 연산을 push, 꺼내는 연산을 pop pushpopisFullisEmptytop : 최근에 삽입한 데이터의 위치 저장최근에 삽입한 데이터를 대상으로 뭔가 연산을 해야할

열린 괄호나 닫힌 괄호가 마구 뒤섞인 문자열이 주어졌을 때,소괄호가 정상으로 열고 닫혔다면 True, 그렇지 않다면 False 구현" 열린 괄호는 자신과 가장 가까운 닫힌 괄호를 만나면 상쇄 "가장 가까운 (최근) 이라는 키워드를 보고 스택을 떠올려야 !시간복잡도 :

큐 : 줄을 세운다 !먼저 들어간 데이터가 먼저 나오는 자료구조 (FIFO)삽입하는 연산을 push, 꺼내는 연산을 pop1.isFull()2.isEmpty()3.push()4.pop()5.front : 마지막에 팝한 위치6.rear : 최근에 푸시한 데이터 위치7.d

N명의 사람이 원 형태로 서있고, 각각 1~N까지 번호표를 갖고 있음임의의 숫자 K가 주어졌을 때 1번 번호표를 가진 사람을 기준으로 K번째 사람을 없앰시간복잡도 : O(N\*K)시간복잡도는 K-1번 팝하고 푸시하는 걸 N번 반복하므로 O(N\*K)cf ) range는

-1) 해시의 개념 해시 : 해시 함수를 사용해서 변환한 값을 인덱스로 삼아 키와 값을 저장해서 빠른 데이터 탐색을 제공하는 자료구조 -> 키를 통해서 데이터에 바로 접근 가능

n개의 양의 정수로 이루어진 리스트 arr와 정수 target이 주어졌을 때 이 중에서 합이 target인 두 수가 arr에 있는지 찾고, 있으면 True 없으면 False를 반환내가 처음에 생각한 아이디어 : arr을 딕셔너리로 만들고 for문 두개로 탐색해서 dic

트리는 데이터를 저장하고 탐색하기에 유용한 구조를 갖고 있는 자료구조프로그래밍 분야에서 트리는 계층 구조를 표현하는 용도로 많이 사용트리는 나무 기둥에서 가지가 뻗어나가는 모습을 거꾸로 뒤집어 놓은 모양노드 : 트리를 구성하는 요소루트 노드 : 노드 중 가장 위에 있는

이진 트리를 표현한 리스트 nodes를 인자로 받음이진 트리에 대하여 전위 순회, 중위 순회, 후위 순회 결과를 반환하는 함수 구현시간 복잡도 : O(N)전위, 중위, 후위 연산 모두 각 노드를 한 번씩 방문하므로 시간 복잡도는 O(N)첫번째 인수 lst를 이용하여 이

집합은 순서와 중복이 없는 원소들을 갖는 자료구조{1,6,6,6,4,3}은 집합으로 생각할 때 중복을 제외해서 {1,6,4,3} ( 순서 바껴도 됨 )집합의 종류유한집합 : 원소 개수가 유한한 경우무한집합 : 원소 개수가 무한한 경우공집합 : 아무런 원소도 없는 경우이

### 문제 33

-1) 그래프의 개념 그래프는 노드와 간선을 이용한 비선형 데이터 구조 보통 데이터 간의 관계를 표현하는데 사용 데이터를 노드로, 노드 간의 관계나 흐름을 간선으로 표현 간선은 방향이 있을 수도 있고 없을 수도 있음 만약 관계나 흐름에서 정도를 표현할 필요가 있

### 문제 38 깊이 우선 탐색 순회 시작 노드는 start로 graph는 [출발 노드, 도착 노드] 쌍들이 들어있는 리스트 반환값은 그래프의 시작 노드부터 모든 노드를 깊이 우선 탐색으로 진행한 순서대로 노드가 저장되어야 defaultdict는 특정 기본값을 가지

깊이 우선 탐색, 너비 우선 탐색 방법은 데이터를 전부 확인하는 방법\-> 완전 탐색 : 모든 경우의 수를 탐색하는 방법 - 대부분 비효율적백트래킹이란?어떤 가능성이 없는 곳을 알아보고 되돌아 가는 것백트래킹 알고리즘이란?가능성이 없는 곳에서는 되돌아가고, 가능성이 있

N을 입력 받아 1부터 N까지의 숫자 중에서 합이 10이 되는 조합을 리스트로 반환하는 함수 작성같은 숫자는 한 번만 선택 가능, 오름차순으로 정렬, N은 1이상 10 이하9x9 스토쿠 보드를 다 채워 완성된 스도쿠 보드를 반환하는 함수 작성1\. 가로줄, 세로줄에는

정렬이란 사용자가 정의한 순서로 데이터를 나열하는 것사용자가 정의한 순서는 오름차순이나 내림차순일 수도 있고 임의의 조건이 될 수도 있음정렬이 필요한 이유정렬을 하면 원하는 데이터를 쉽게 찾을 수 있다!데이터의 전체 영역에서 정렬된 영역과 정렬되지 않은 영역을 나누고

인자로 받은 문자열 s를 계수정렬로 정렬하여 반환하는 함수 구현계수정렬은 문자를 정렬할 때 매우 효율적인 알고리즘a의 아스키코드 값은 97이므로, 그대로 빈도수 배열에 저장하려면 97번째부터 빈도 수를 저장해야함a를 일괄로 빼면 인덱스 0부터 빈도수를 저장할 수 있음

시뮬레이션이란 문제에 주어진 상황을 완벽하게 이해하고 이를 코드로 구현하는 과정다른 알고리즘은 성능에 중점을 둔 반면, 시뮬레이션은 구현에 중점을 맞춤시뮬레이션 문제를 푸는 방법시뮬레이션 문제는 문제 자체에 접근하는 방식을 공부해야함아래 두 가지 염두에 두고 문제 풀기

### 문제 62 배열 회전하기 2차원 배열 arr을 시계 방향으로 90도 * n번 회전하는 함수 구현 -> 일반화 식 생각할 때 그림 그려서 하기 헷갈림 ** ### 문제 63 두 행렬을 곱한 후 전치 행렬 만들기 matrix1과 matrix2는 정수값으로 이루어진

-1) 동적 계획법 개념 전체 문제를 한 번에 해결하는 것이 아니라 작은 부분 문제들을 해결하고, 이를 활용하여 전체 문제를 해결하는 방법 동적 계획법을 효율적으로 활용하려면 아래 두 가지 조건을 만족해야 큰 문제를 작은 문제로 나누었을 때 동일한 작은 문제가 반복해

문제 70 LCS 길이 계산하기 주어진 두 개의 문자열 str1과 str2에 대해 최장 공통 부분 수열의 길이를 계산하는 함수 구현 문제 71 LIS 길이 계산하기 정수 배열 nums에서 LIS의 길이를 찾는 함수 구현

그리디는 "탐욕스러운" 이라는 뜻그리디 알고리즘은 결정 순간마다 눈 앞에 보이는 최선의 선택을 하며 선택은 번복하지 않음" 지역 최적해를 추구한다 "\-> 부분적으로 최적해를 구한다고 할 수 있지만 전체적으로 최선의 해인지는 확답 x그리디 알고리즘이 최적해를 보장하려면

상점에세 계산을 마치고 거스름돈을 돌려받아야거스름돈을 최소한의 화폐 수로 받고 싶음거스름돈 amount 가 있을 때 화폐 단위 1,10,50,100을 최소한으로 사용한 화폐 리스트 반환무게와 가치가 있는 짐 items와 배낭 weight_limit이 주어질 때 부분 배