Python_Algorithm

빅 오(Big O)는 입력값이 무한대로 향할 때 함수의 상한을 설명하는 수학적 표기 방법이다. 입력의 크기가 충분히 클 경우에 알고리즘의 효율성에 따라 수행 시간이 크게 차이가 날 수 있기 때문에 코드를 작성할 때에 빅 오를 고려하며 작성한다면 더 좋은 코드를 만들어

파이썬은 어떤 자료형들을 가지고 있는지, 파이썬의 자료형들은 어떤 특징을 가지고 있는지 알아보았다.파이썬의 자료형 중 주요 자료형 중심으로 살펴보았다. 파이썬에서는 숫자 정수형으로 int만을 제공한다. 'int보다 큰 값은 어떤 자료형에 보관해야 하는가?'라는 생각이

리스트와 딕셔너리는 파이썬을 사용하다보면 가장 빈번하게 접하게 되는 자료형이다. 코딩 테스트에서 이 2가지 자료형은 거의 모든 문제에 빠짐없이 사용된다고 해도 과언이 아니다. 리스트와 딕셔너리에 대해서 자세히 알아보았다.파이썬의 리스트는 말 그대로 순서대로 저장하는 시

문자열 조작이란 문자열을 변경하거나 분리하는 등의 여러 과정을 말한다. 대부분의 언어에서는 별도의 문자열 자료형과 문자열을 조작하기 위한 다양한 기능들을 기본적으로 제공하고 있기 때문에 굳이 제약을 두지 않는 한 언어에서 제공하는 기본 기능들을 잘 활용하는 편이 가장

이전 글에 이어서 파이썬 알고리즘 풀이에서 가장 많이 등장하는 로직 중 하나인 문자열 조작에 대해 더 알아보았다.금지된 단어를 제외한 가장 흔하게 등장하는 단어를 출력하라. 대소문자 구분을 하지 않으며 구두점(마침표, 쉼표 등) 또한 무시한다.입력값에는 대소문자가 섞여

자료구조는 크게 메모리 공간 기반의 연속 방식과 포인터 기반의 연결 방식으로 나뉜다. 배열은 이 중에서 연속 방식의 가장 기본이 되는 자료형이다. 연결 방식의 가장 기본이 되는 자료형은 연결 리스트이다. 추상 자료형의 실제 구현 대부분은 배열 또는 연결 리스트를 기반으

이전 글에 이어서 배열 문제를 조금 더 공부해보았다.높이를 입력받아 비 온 후 얼마나 많은 물이 쌓일 수 있는지 계산하라.이 문제는 높이와 너비를 모두 살펴보게 되면 O(n^2)라는 큰 시간이 소요된다. 그렇기 때문에 효율적인 코드를 찾아야 한다. 효율적인 방법 중 하

연결 리스트는 컴퓨터과학에서 배열과 함께 가장 기본이 되는 대표적인 선형 자료구조 중 하나이다. 추상 자료형 구현의 기반이 된다. 동적으로 새로운 노드를 삽입하거나 삭제하기가 간편하며 연결 구조를 통해 물리 메모리를 연속적으로 사용하지 않아도 되기 때문에 관리하기도 쉽

연결 리스트를 이어서 공부해보았다.역순으로 저장된 연결 리스트의 숫자를 더하라.연결 리스트를 문자열로 이어 붙인 후 숫자로 변환하여 이를 계산하고, 다시 연결 리스트로 바꾸면 쉽게 풀 수 있을 것 같다. 물론 형 변환이 많고 역순으로 돌려야하는 과정이 필요하기 때문에

스택과 큐는 프로그래밍이라는 개념이 탄생할 때부터 사용된 가장 고전적인 자료구조 중 하나로 이 중에서도 스택은 거의 모든 응용 프로그램을 만들 때 사용되는 자료구조이다. 스택은 LIFO(Last In First Out)로 처리되며 접시가 쌓이는 것을 생각하면 쉽게 이해

전 글에 이어서 스택과 큐를 이용한 문제를 통해 스택과 큐를 익혀보자.큐를 이용해 다음 연산을 지원하는 스택을 구현하라.우선 스스로 이 문제를 풀어보았다.스택의 구조보다는 스택의 연산이 구현되도록만 생각하고 작성하였다.혼자 힘으로 풀었을 때에는 스택의 연산만을 생각하고

데크는 더블 엔디드 큐의 줄임말로, 글자 그대로 양쪽 끝을 모두 추출할 수 있는 큐를 일반화한 형태의 추상 자료형(ADT)이다.데크는 양쪽에서 삭제와 삽입을 모두 처리할 수 있으며 스택과 큐의 특징을 모두 가지고 있다. 이 추상 자료형의 구현은 배열이나 연결 리스트 모

해시 테이블에 대해 이어서 더 알아보았다.다음의 기능을 제공하는 해시맵을 디자인하라.이전 글에서 다뤘던 내용 중 해시 테이블을 디자인 하는 방법에는 2가지가 있었다. 하나는 개별 체이닝 방식이었고, 하나는 오픈 어드레싱 방식이었다. 이 중 개별 체이닝 방식을 통해 해결

그래프 이론에서 그래프란 객체의 일부 쌍들이 연관되어 있는 객체 집합 구조를 말한다.그래프 문제 하면 오일러 경로를 빼놓을 수 없다. n개의 섬과 m개의 다리가 있을 때 m개의 다리를 한번만 건너서 도달하는 것을 요구하는 문제이다. 오일러는 이 문제에서 모든 정점이 짝

그래프에 대한 공부를 이어서 하였다.전체 수 n을 입력받아 k개의 조합을 리턴하라.우선 혼자서 itertools를 이용하여 풀어보았다.조합의 수를 구하는 수식은 n!/(k!(n-k)!)이다. 이 문제의 예시를 적용하면 6개의 결과값이 나와야 한다. 이렇게 개수를 구하는

최단 경로 문제는 각 간선의 가중치 합이 최소가 되는 두 정점(또는 노드) 사이의 경로를 찾는 문제이다.최단 경로는 지도 상의 한 지점에서 다른 지점으로 갈 때 가장 빠른 길을 찾는 것과 비슷한 문제이다. 쉽게 말해 내비게이션에서 목적지로 이동할 때, 경로 탐색을 하면

트리는 계층형 트리 구조를 시뮬레이션 하는 추상 자료형(ADT)으로, 루트 값과 부모-자식 관계의 서브 트리로 구성되며, 서로 연결한 노드의 집합이다.트리는 나무의 뿌리에서 위로 뻗어나가는 형상처럼 생겨서 트리라는 명칭이 붙었고, 트리 구조를 구현할 때는 나무의 형상과

트리에 대해 조금 더 알아보았다.동일한 값을 지닌 가장 긴 경로를 찾아라.트리의 리프 노드까지 DFS로 탐색해 내려가고 값이 일치할 경우 거리를 차곡차곡 쌓아 올려가며 백트래킹하는 방식으로 풀이가 가능하다. DFS 재귀 탐색은 다음과 같이 작성해야 한다.이렇게 재귀 호

트리에 대하여 이어서 알아 보았다.이진 트리를 배열로 직렬화하고, 반대로 역직렬화하는 기능을 구현하라. 즉 다음과 같은 트리는 1, 2, 3, null, null, 4, 5 형태로 직렬화할 수 있을 것이다.직렬화와 역직렬화를 구현하기 위해서는 이진 트리의 특징과 표현을

트리에 대하여 이어서 알아 보았다.오름차순으로 정렬된 배열을 높이 균형 이진 탐색 트리로 변환하라.이 문제를 풀기 위해서는 이진 탐색 트리의 특징에 대해 정확하게 파악하고 있어야 한다. 이진 탐색 트리는 이진 검색의 마법을 적용한 이진 트리이고, 따라서 이진 탐색 트리

힙은 힙의 특성 (최소 힙에서는 부모가 항상 자식보다 작거나 같다)을 만족하는 거의 완전한 트리인 특수한 트리 기반의 자료구조이다.힙은 트리 기반의 자료구조이다. 파이썬에서 우선순위 큐를 사용할 때 heapq 모듈을 사용하는데 이것이 바로 파이썬에서의 힙이다. 파이썬에

트라이는 검색 트리의 일종으로 일반적으로 키가 문자열인 동적 배열 또는 연고나 배열을 저장하는데 사용되는 정렬된 트리 자료구조이다.트라이는 실무에 매우 유용하게 쓰이는 자료구조로, 특히 자연어 처리(NLP) 분야에서 문자열 탐색을 위한 자료구조로 널리 쓰인다. 트라이는

정렬 알고리즘은 목록의 요소를 특정 순서대로 넣는 알고리즘이다. 대개 숫자식 순서와 사전식 순서로 정렬한다.버블 정렬은 화이트보드 코딩 인터뷰에 자주 등장했던 정렬 알고리즘이다. 비효율적인 정렬 알고리즘이기 때문에 실무에 거의 사용하지 않는다. 따지고 보면 버블 정렬은

정렬에 대해 이어서 알아보았다.연결 리스트를 O(n log n)에 정렬하라.이 문제는 시간 복잡도 O(n log n)로 제한 시간을 줬기 때문에 버블 정렬과 같은 알고리즘은 사용할 수 없다. 병합 정렬이나 퀵 정렬을 이용해야 하는데 병합 정렬로 먼저 작성해본다. 병합

정렬에 대해 이어서 알아보았다.항목들을 조합하여 만들 수 있는 가장 큰 수를 출력하라.이 문제는 특이한 정렬 기법을 적용해야 한다. 맨 앞에서부터 자릿수 단위로 비교해서 크기 순으로 정렬한다. 즉, 9와 30 중 맨 앞자리가 9가 더 크므로 9가 먼저 나와야 한다. 쉽

이진 탐색이란 정렬된 배열에서 타겟을 찾는 검색 알고리즘이다. 이진 검색은 값을 찾아내는 시간 복잡도가 O(log n)이라는 점에서 대표적인 로그 시간 알고리즘이며, 이진 검색 트리와도 유사한 점이 많다. 그러나 이진 탐색 트리가 정렬된 구조를 저장하고 탐색하는 자료구

이진 검색에 대해 조금 더 알아보았다.두 배열의 교집합을 구하라.우선 이진 검색을 이용하여 문제를 혼자 풀어보았다. 성능을 위해 길이가 더 짧은 배열을 순회하며 길이가 더 긴 배열을 이진 검색하며 해당 수가 있을 경우 결과 집합에 추가하도록 하였다.파이썬에서 제공하는

원래 비트를 조작하는 것은 하드웨어와 관련이 깊다. 1937년 클로드 섀넌은 전기회로 스위치의 on/off를 이용한 스위칭 회로를 연구하면서 True, False의 2개 값으로 논리 연산을 설명하는 부울대수를 회로에 적용했고, 논리 게이트를 만들어냈다. 이를 이용한 논

비트 조작에 대해 이어서 알아보았다.딱 하나를 제외하고 모든 엘리먼트는 2개씩 있다. 1개인 엘리먼트를 찾아라.단 1개의 엘리먼트를 찾는 적당한 연산자가 있다. 바로 XOR 연산이다. XOR은 입력값이 서로 다르면 True, 서로 동일하면 False를 반환한다. 이를

슬라이딩 윈도우란 고정 사이즈의 윈도우가 이동하면서 윈도우 내에 있는 데이터를 이용해 문제를 풀이하는 알고리즘을 의미한다. 원래 네트워크에서 사용되던 알고리즘이지만, 문제 풀이에 응용할 수 있다.슬라이딩 윈도우 기법은 투 포인터 기법과 함께 알고리즘 문제 풀이에 매우

슬라이딩 윈도우에 대해 조금 더 알아보았다.문자열 S와 T를 입력받아 O(n)에 T의 모든 문자가 포함된 S의 최소 윈도우를 찾아라.먼저 브루트 포스로 풀어보면, 최소 윈도우라고 했으니 일단 T의 크기부터 시작해 점점 크기를 키워가며 모든 윈도우 크기에 대해 탐색해야

해시 테이블 또는 해시 맵은 키를 값에 매핑할 수 있는 구조인 연관 배열 추상 자료형 (ADT)을 구현하는 자료구조이다. 해시 테이블의 가장 큰 특징은 대부분의 연산이 분할 상환 분석에 따른 시간 복잡도가 O(1)이라는 점이다. 이는 데이터 양에 관계 없이 빠른 성능을