Earn this, Earn it.

파이썬의 타입 힌트 타입스크립트를 공부하다보니 파이썬에서도 타입 힌드라는 것을 지원한다는 것을 알게되었다. (PEP 484 문서에 추가됨) 이 기능은 파이썬 버전 3.5부터 사용할 수 있으며, '타입에 대한 힌트'를 주는 것이라 볼 수 있다. def fn(a: int) -> bool: ... 위와 같이 타입 힌트를 사용하게 되면 함수의 파라미터 a가 정수임을 분명하게 알 수 있으며 리턴 값으로 True 또는 False를 리턴할 것이라는 점도 확실히 알 수 있다. 다만 이는 타입 힌트일 뿐, 다음과 같이 사용할 수도 있다. a: str = 1 이에 대해서 타입 힌트에 대한 오류가 있는지 없는지 자동으로 확인해주는 mypy를 사용하면 타입 힌트가 잘못 지정된 경우 Incompatible return valu..

이진 검색(Binary Search)이란? 정렬된 배열에서 타겟을 찾는 검색 알고리즘이다. 이진 검색은 값을 찾아내는 시간 복잡도가 O(log n)이라는 점에서 대표적인 로그 시간 알고리즘이며, 이진 탐색 트리 (Binary Search Tree)와도 유사한 점이 많다. 그러나 이진 탐색 트리가 정렬된 구조를 저장하고 탐색하는 '자료구조'라면, 이진 검색은 정렬된 배열에서 값을 찾아내는 '알고리즘' 자체를 지칭한다. 이진 탐색 트리는 1억 개의 아이템도 단 27번이면 모두 찾아낼 수 있다... 또 다른 유의점은 2^n은 금방 커질 수 있다는 것이다. 27번째 수부터 1억이 넘어가기 시작하고 기하급수적으로 커진다. O(2^n)은 얼핏 보면 O(n^2)과 비슷해 보이지만 실제로는 훨씬 더 크므로 시간 복잡도..

슬라이딩 윈도우란? 고정 사이즈의 윈도우가 이동하면서 윈도우 내에 있는 데이터를 이용해 문제를 풀이하는 알고리즘을 말한다. 알고리즘 관련 서적에서는 알려져 있지 않으나, 네트워크에서 주로 사용되던 알고리즘을 문제 풀이에 이용한 것이라 할 수 있다. 이는 투 포인터와 함께 알고리즘 문제 풀이에서 유용하게 사용될 수 있다. 이 둘의 개념이 유사해보일 수 있지만, 보통 고정 사이즈 윈도우를 사용하는 경우를 슬라이딩 윈도우라고 구분하면 좋다. 또한, '정렬된 배열을 대상'으로 하는 투 포인터와 달리 슬라이딩 윈도우는 '정렬 여부에 관계 없이' 활용된다는 차이가 있다. 물론 교과서에 정의된 내용이 아니기 때문에 실무에서 주로 이런 형태로 쓰일 뿐, 때로는 서로 혼용되어 쓰이기도 한다. 슬라이딩 윈도우와 투 포인터..

스택(Stack)과 큐(Queue) 스택과 큐란 무엇인가? 스택 : 후입 선출 (LIFO), 파이썬의 리스트로 커버 가능 큐 : 선입 선출 (FIFO), 데크(deque)를 이용해야 좋은 성능 (리스트는 동적 배열로 구현되어 있어 큐의 연산을 수행하기에는 효율적이지 않다) 데크(Deque) 데크란 무엇인가? 데크는 양쪽에서 삭제와 삽입을 모두 처리할 수 있는 자료구조로, 스택과 큐의 특징을 모두 갖는다. 구현은 배열이나 연결 리스트 모두 가능하다. 파이썬에서는 collections 모듈에서 deque로 지원한다. list = [1,2,3,4] deque = collections.deque(list,maxlen=10) // 최대 길이를 지정할 수 있다. deque.pop() deque.append() de..

2021년 7월 24일 글 브루트포스(Brute Force) 브루트포스란 나올 수 있는 모든 경우의 수를 계산하여 조건에 맞는 값을 가져와 알고리즘을 푸는 방식이다. 다른 말로 완전탐색이라고 한다. 브루트포스 알고리즘의 장점은 무조건 결과를 찾을 수 있다는 점이나, 모든 경우의 수를 계산하기에 딱히 알고리즘이라 볼 수 없을 뿐더러 효율성이 매우 떨어진다. 즉, 코딩테스트시 브루트포스 알고리즘을 쓰는 경우는 높은 확률로 더 좋은 알고리즘이 존재할 것이며 대부분의 사람들이 구현만 할 수 있으며 짤 수 있으므로 잘 안 나온다고 볼 수 있다. 그리고 브루트포스 보다는 수학적 알고리즘을 섞어서 내는 경우가 많으므로 딱히 이 부분을 준비한다기보다 최후의 보루로 남겨두는 편이 안전할 것이다. DFS와 BFS 이들은 ..

2021년 7월 18일 글 문제 문제 설명 원점(0,0)에서 시작해서 아래처럼 숫자가 적힌 방향으로 이동하며 선을 긋습니다. ex) 1일때는 오른쪽 위로 이동 그림을 그릴 때, 사방이 막히면 방하나로 샙니다. 이동하는 방향이 담긴 배열 arrows가 매개변수로 주어질 때, 방의 갯수를 return 하도록 solution 함수를 작성하세요. 제한사항 배열 arrows의 크기는 1 이상 100,000 이하 입니다. arrows의 원소는 0 이상 7 이하 입니다. 방은 다른 방으로 둘러 싸여질 수 있습니다. 풀이 아이디어 1) 선을 긋는 것을 어떻게 표현할까? - 선을 긋는다고 생각하지 말고 다른 방법을 떠올려보자. 2) 방을 찾으려면 어떤 방법을 써야할까? - 기존의 점과 만날 때 방이 하나씩 생긴다? 3)..

2021년 7월 18일 글 문제 문제 설명 n명의 권투선수가 권투 대회에 참여했고 각각 1번부터 n번까지 번호를 받았습니다. 권투 경기는 1대1 방식으로 진행이 되고, 만약 A 선수가 B 선수보다 실력이 좋다면 A 선수는 B 선수를 항상 이깁니다. 심판은 주어진 경기 결과를 가지고 선수들의 순위를 매기려 합니다. 하지만 몇몇 경기 결과를 분실하여 정확하게 순위를 매길 수 없습니다. 선수의 수 n, 경기 결과를 담은 2차원 배열 results가 매개변수로 주어질 때 정확하게 순위를 매길 수 있는 선수의 수를 return 하도록 solution 함수를 작성해주세요. 제한사항 선수의 수는 1명 이상 100명 이하입니다. 경기 결과는 1개 이상 4,500개 이하입니다. results 배열 각 행 [A, B]는 ..

2021년 7월 18일 글 문제 문제 설명 n개의 노드가 있는 그래프가 있습니다. 각 노드는 1부터 n까지 번호가 적혀있습니다. 1번 노드에서 가장 멀리 떨어진 노드의 갯수를 구하려고 합니다. 가장 멀리 떨어진 노드란 최단경로로 이동했을 때 간선의 개수가 가장 많은 노드들을 의미합니다. 노드의 개수 n, 간선에 대한 정보가 담긴 2차원 배열 vertex가 매개변수로 주어질 때, 1번 노드로부터 가장 멀리 떨어진 노드가 몇 개인지를 return 하도록 solution 함수를 작성해주세요. 제한사항 노드의 개수 n은 2 이상 20,000 이하입니다. 간선은 양방향이며 총 1개 이상 50,000개 이하의 간선이 있습니다. vertex 배열 각 행 [a, b]는 a번 노드와 b번 노드 사이에 간선이 있다는 의미..