JUNGOL - 1257 전깃줄(중)
최장 증가 부분 수열(LIS:Longest Increasing Subsequence) 응용 문제다. LIS 구현할 때, 다음 숫자를 업데이트 시킬 위치를 찾는 과정에서 cpp STL <algorithm>의 lower_bound()를 이용해 O(LogN)으로 처리해야만 전...
Pages > Algorithm Collection
JUNGOL - 1225 사람감시
double 자료형의 사용과 유효숫자를 고려하여 천분률로 count 하는 것이 포인트다. 코딩 문제에서 두 점의 거리를 구하거나 반지름의 길이를 구하거나 할 때, 굳이 sqrt로 루트를 씌우지 말고, 제곱인 채로 두는 것이 이득이다.
JUNGOL - 2097 지하철
최단 거리 알고리즘 문제. Dijkstra로 풀이 하였으며, 경로 기억을 위한 약간의 코드 추가만 이루어졌다.
JUNGOL - 2109 꿀꿀이 축제
Dijkstra를 두 번 쓰는 문제다. ‘꿀꿀이’들이 오고 가고 했을 때 총합이 작아야 하고, 이 총합 중에서 max 값을 갖는 꿀꿀이의 거리를 구하는 문제.
JUNGOL - 1946 음악프로그램
위상정렬(Topological Sorting) 문제이다. 입력 받을 때, ‘Parent’ Node의 수를 count 하고, 부모가 없는 Node 부터 queue에 넣어 BFS로 탐색한다. 현재 노드에서 갈 수 있는 모든 노드의 ‘Parent’ count를 차감 하고, 만약 coun...
PROGRAMMERS - 사칙연산
동적 계획법(Dynamic Programming) 문제. DP는 항상 풀이 설계하는데 많은 어려움을 겪는거 같다. 무엇을 어떻게 Memoization 시킬 것인가는 정말 많은 문제를 풀어보는 방법 밖에 없는 것 같다.
PROGRAMMERS - 호텔 방 배정
Union-Find or Disjoint-set 문제. 이 알고리즘을 쓰지 않으면 빈 방을 찾는 과정에서 시간 복잡도가 증가하여 효율성 테스트를 통과할 수 없다.
PROGRAMMERS - 징검다리
이분탐색(Binary Search) 문제. 일단 이 문제는 Binary Search 카테고리 힌트가 없었다면, 풀지 못했을 것 같다.
PROGRAMMERS - 무지의 먹방 라이브
heapq를 import 하여 문제를 해결한다. 완판(싸이클)으로 가장 작은 길이의 접시를 소진할 수 있는지를 ‘while’문에서 검사한다.
PROGRAMMERS - 단어 퍼즐
dp 문제. 언제나 그렇듯.. dp는 문제 해결방향을 막 바로 생각해내기가 어렵다.
PROGRAMMERS - 도둑질
또 다시 dp 문제. 첫 번째 집을 택하는 것을 ‘flag’로 가져가야하나? 싶었는데 그냥 가져가는 경우 / 안가져가는 경우 나눠서 dp 배열을 두 개로 만들면 되는거였다.
INTERVIEW - 01
생애 첫 개발자 인터뷰 후기 겸 해결하지 못한 부분들 답답해서 정리.
ALGORITHM - Binary Search
‘Search’ 알고리즘의 기본. Binary Search
LeetCode - 1. Two Sum
간단하지만은 않은 문제. O(n2) 보다 효율적이게 풀어라!
LeetCode - 2. Add Two Numbers
주어진 Linked List 클래스의 Traversal과, 숫자를 다시 Linked List로 만드는 것이 관건.
ALGORITHM - Bubble Sort
‘Sort’ 알고리즘의 기본. Bubble Sort
ALGORITHM - Binary Tree
python에서 Tree 클래스를 세팅하는 법을 알아 보자.
INTERVIEW - Coding Test (2021 Sep)
2021년도 9월 둘째 주 주말은 잊지 못할 주말이 될 것 같다. 무려 코딩테스트 3개가 몰려 있던 주말이었다.
ALGORITHM - Selection Sort
Selection Sort. Bubble Sort과 거의 비슷하게 간단한 기본적인 정렬 방법.
ALGORITHM - Insertion Sort
Insertion Sort. 도서관 사서가 책을 정리하듯이 매 스텝에서 원소의 적절한 위치를 찾아서 넣는 방법.
ALGORITHM - Merge Sort
Merge Sort O(nlogn)을 보장하는 효율적인 정렬 방식.
LeetCode - 748. Shortest Completing Word
크게 어렵진 않은데 이것저것 신경쓸게 있다.
LeetCode - 1209. Remove All Adjacent Duplicates in String II
Medium. ‘word cnt’를 주면서 중복 수인 ‘k’와 일치하는지 확인 후 일치 한다면 스택에서 ‘pop()’시키는 것이 포인트. ‘pop()’ 이후에는 다시 현재 스택의 마지막 ‘word’와 일치하는지 체크하며 카운트를 늘려 나간다.
PROGRAMMERS - N으로 표현
언제나 Dynamic Programming은 어렵다. ‘DP’는 단시간안에 풀라고 만든 문제가 아닌 것 같다.
LeetCode - 70. Climbing Stairs
Easy. Blind 75 LeetCode Questions. Dynamic Programming의 정말 기초적인 문제로 처음 접하는 사람에게 설명할 때 유용할 문제인 것 같다.
LeetCode - 121. Best Time to Buy and Sell Stock
Easy. Blind 75 LeetCode Questions. Array 문제는 효율성을 따지면 Time Over가 뜨는 경우가 많으므로 항상 시간 복잡도를 고려해 주어야 한다.
LeetCode - 57. Insert Interval
Medium. Blind 75 LeetCode Questions. Interval
LeetCode - 104. Maximum Depth of Binary Tree
Easy. Blind 72 LeetCode Questions. Tree
LeetCode - 23. Merge k Sorted Lists
Hard. Blind 75 LeetCode Questions. Linked List