코딩테스트/파이썬 알고리즘

오늘은 순서대로가 아니라 코테에서 자주 등장하는 이진(이분)탐색에 대해서 작성해볼 것이다. 이진탐색은 교재 p.186 Chapter 7에서 등장한다. 순차탐색 - 리스트 안에 있는 특정 target을 찾기 위해 앞에서부터 데이터를 하나씩 차례대로 확인 - 보통 정렬되어 있지 않은 데이터에서 target을 찾을 때 사용. - 앞에서부터 데이터를 확인하기 때문에 데이터가 N개일 때 최악의 경우 시간복잡도는 O(N) 이진탐색 - 배열 내부의 데이터가 정렬되어 있어야만 사용할 수 있는 알고리즘. - 정렬이 되어있다면 매우 빠르게 데이터를 찾을 수 있는 알고리즘. - 데이터를 찾기위해 (시작점, 끝점, 중간점)을 이용하여 탐색. - 한번 확인할 때 마다 확인하는 원소의 개수가 절반씩 줄어들기 때문에 시간복잡도가 ..

첫번째 알고리즘은 교재의 chapter3에 해당하는 그리디이다. Greedy(그리디)는 쉽게 말해서 "당장 좋은 것만 선택하는 것 == 현재 상황에서 지금 당장 좋은 것만 고르는 것" 우선 그리디는 여러 경우 중 하나를 결정해야 할 때마다 그 순간에 최적이라고 생각되는 것을 선택해 나가는 방식으로 진행하여 최종적인 해답에 도달하는데, 그렇기 때문에 최종적(전역적)으로 최적이라는 보장은 없다. 그러나 대부분 그리디로 풀 수 있는 문제들은 "가장 큰 순서대로", "가장 작은 순서대로" 이런 조건을 제공해준다. 그리디의 대표적인 문제로 [거스름돈]이 있다. 거스름돈(p 87) 🔔 문제 당신은 음식점의 계산을 도와주는 점원이다. 카운터에는 거스름돈으로 사용할 500원, 100원, 50원, 10원짜리 동전이 무한..

얼마전부터 부트캠프 코딩테스트 시험을 위해 코딩테스트 준비를 시작했다. 위 책을 통해서 알고리즘이나, 주요 문제등을 풀어보고 팁들을 얻어가며 백준, 프로그래머스 등 다양한 문제들을 풀어가면서 준비해야겠다. 이전에 올린 알고리즘 정리글과는 별개로 정리하면서 예전에 정리한 것들도 다시 한번 읽어봐야겠다. 2년전이라 다 까먹음;; 백준에서 푼 문제만 깃허브에 [백준허브]를 이용해서 자동으로 올리고, 해당 교재에 해당하는 풀이는 블로그에만 기록하겠다. [유튜브 강의-나동빈님] [교재 문제 답안] GitHub - ndb796/python-for-coding-test: [한빛미디어] "이것이 취업을 위한 코딩 테스트다 with 파이썬" 전체 [한빛미디어] "이것이 취업을 위한 코딩 테스트다 with 파이썬" 전체 ..

오늘은 heap에 대해서 알아보겠다. 우선 heap을 한단어로 설명하자면 규칙을 가진 이진트리이다. 이진트리가 무엇이냐면 각각의 노드가 최대 2개의 자식노드를 가진 트리를 말한다. 자식노드는 왼쪽 자식과 오른쪽 자식노드로 나뉜다. 다음으로 규칙으로는 최소힙과 최대힙이 있는데, 최소힙은 부모 노드의 키값이 자식 노드의 키값보다 항상 작은 힙을 말하고 최대힙은 부모 노드의 키값이 자식 노드의 키값보다 항상 큰 힙을 말한다. 위 그림처럼 두개의 자식노드만 가지면서 왼쪽 자식은 부모노드의 index*2 위치에 넣고, 오른쪽 자식은 부모노드의 index*2+1위치에 넣는다. 우선 힙은 첫번째 인덱스를 0으로 하면 계산이 복잡해져서 1로 두고 10을 인덱스 1위치에 넣는다. 다음으로 15는 1*2위치인 인덱스 2에..

오늘은 deque 라이브러리에 대해서 알아볼 것이다. 예전에 que큐에 대해서는 글을 작성했었는데 큐는 선입선출 방식으로 작동한다. deque(데큐)는 양방향 큐라고 생각하면 편하다. 말 그대로 데이터의 앞, 뒤에서 접근할 수 있는 큐이다. deque를 사용하기 위해서는 라이브러리를 가져와야 한다. 아래와 같이 import한뒤 deque 자료구조형을 선언해주면 된다. from collections import deque data=deque() deque 자료구조에서 쓸 수 있는 메서드는 여러가지가 있다. from collections import deque data=deque() data.append() item을 데크의 오른쪽 끝에 삽입 data.appendleft(item): item을 데크의 왼쪽 ..

오늘은 투포인터 알고리즘을 알아볼 것이다. 투포인터 알고리즘은 두개의 포인터(인덱스)를 설정해놓고 위치를 기록하면서 처리하는 알고리즘이다. 이 알고리즘은 문제로 설명하는게 더 빠를 것 같아서 문제로 설명을 해보도록 하겠다. 백준의 수들의 합문제이다. 1. 우선 시작점(left)과 끝점(right)을 배열의 첫번째를 가리키도록 한다. 2. 구간의 부분합이 목표값(m)과 같다면 저장한다. 3. 현재 부분합이 m보다 작다면 구간을 늘려야 하므로 끝점(right)을 +1 한다. 4. 현재 부분합이 m보다 크거나 같다면 구간을 줄여야 하므로 시작점(left)를 +1 한다. 이렇게 모든 경우를 확인하면 목표값과 같은 경우들이 저장되어있을거고 그중 가작 작은 구간을 포함하면된다. 내가 얼마전 푼 백준의 부분합 문제는..