Coding Test
-
자료구조 #1 StackCoding Test/자료구조 2021. 5. 17. 21:23
Stack 자료구조의 개념 1. Stack 의 특성 물건을 쌓아 올리듯 자료를 쌓아 올린 형태의 자료구조 스택에 저장된 자료는 선형구조를 가진다 선형구조 : 자료 간의 관계가 1:1 의 관계를 가짐 비선형구조 : 자료 간의 관계가 1:N 의 관계를 가짐(ex. 트리) 스택에 자료를 삽입하거나 스택에서 자료를 꺼낼 수 있다 마지막에 삽입한 자료를 가장 먼저 꺼냄 후입선출 (LIFO, Last-In-Last_Out) 이라고 부름 2. Stack 의 구현 자료구조 자료를 선형으로 저장할 저장소가 필요하다 파이썬에서는 리스트를 사용할 수 있다 저장소 자체를 스택이라 부르기도 한다 마지막에 삽입된 원소의 위치를 top 이라 부름 연산 삽입 저장소에 자료를 저장하고 보통 push 라고 부른다 삭제 저장소에서 자료를..
-
CodingTest #1 그리디 알고리즘Coding Test/알고리즘 2021. 5. 11. 20:21
그리디 알고리즘 그리디 알고리즘(탐욕법)은 현재 상황에서 지금 당장 좋은 것만 고르는 방법을 의미합니다. 일반적인 그리디 알고리즘은 문제를 풀기 위한 최소한의 아이디어를 떠올릴 수 있는 능력을 요구합니다. 그리디 해법은 그 정당성 분석이 중요합니다. 단순히 가장 좋아 보이는 것을 반복적으로 선택해도 최적의 해를 구할 수 있는지 검토합니다. 문제 상황 루트 노드부터 시작하여 거쳐 가는 노드 값의 합을 최대로 만들고 싶습니다. Q. 최적의 해는 무엇인가요? 일반적인 상황에서 그리디 알고리즘은 최적의 해를 보장할 수 없을 때가 많습니다. 하지만 코딩 테스트에서의 대부분의 그리디 문제는 탐욕법으로 얻은 해가 최적의 해가 되는 상황에서, 이를 추론할 수 있어야 풀리도록 출제됩니다. 거스름 돈 문제 설명 당신은 음..
-
CodingTest #1 자주 사용하는 라이브러리Coding Test/문제 2021. 5. 11. 20:13
실전에서 유용한 표준 라이브러리 1. 내장 함수 기본 입출력 함수부터 정렬 함수까지 기본적인 함수들을 제공한다. 2. itertools 반복되는 형태의 데이터를 처리하기 위한 기능들을 제공한다. 순열과 조합 라이브러리는 코딩 테스트에서 자주 사용된다. 3. heapq 힙(Heap) 자료구조를 제공한다. 일반적으로 우선순위 큐 기능을 구현하기 위해 사용된다. 4. bisect 이진 탐색(Binary Search) 기능을 제공한다. 5. collections 덱(deque), 카운터(counter) 등의 유용한 자료구조를 포함한다. 6. math 필수적인 수학적 기능을 제공한다. 팩토리얼, 제곱근, 최대공약수(GCD), 삼각함수 관련 함수부터 파이(pi)와 같은 상수를 포함한다. 내장 함수 sum() # s..