Min IT's Devlog

풀이 일자: 23.03.17 난이도: [Medium] 분류: [Hash Table, String, Trie] 문제 내용 Trie라는 class를 구현해보는 문제로 삽입과 탐색, 부분탐색 함수의 내용을 구현하면 된다. 문제 해결 흐름 1. 구현해야 하는 내용은 분명하므로 어떤 자료구조를 이용하여 이를 구현할건지를 생각해보면 될 것 같다. → 크게 3가지를 떠올렸는데 1) 배열에 넣는 것 만으로도 배열의 인덱스가 이진트리의 역할을 하도록 하는 방법 → 하나씩 insert 되기 때문에 insert하면서 정렬을 하는 건 시간낭비일 것 같아서 탐색도 linear하게 삽입도 linear하게 처리해보았다. class Trie: def __init__(self): self.trie = list(); def insert..

풀이 일자: 23.03.15 난이도: [Medium] 분류: [BFS] 문제 내용 이진 트리의 root Node가 주어졌을 때, 해당 이진 트리가 완전이진트리 여부를 리턴하는 문제였다. 완전이진트리 - 마지막 level전까지는 모든 노드가 다 채워져있어야 하고 마지막 level은 굳이 다 채울 필요는 없지만 왼쪽부터 차례대로 채워야 한다. 문제 해결 흐름 1. 우선 같은 level에서 확인해야 하고 각 node를 확인하기 위해 알고리즘을 선택해야한다. → BFS를 채택하여 이를 해결한다. 2. 순회를 하면서 안되는 경우가 발생하면 바로 False를 리턴한다. → 1) 같은 부모노드를 갖는 자식노드 중 오른쪽 노드만 존재하는 경우 False → 2) slbling관계의 서로 붙어있는 부모노드 사이를 가정했..

풀이 일자: 23.03.12 난이도: [Hard] 분류: [Linked List/ Divide and Conquer/ Heap / Merge Sort] 문제 내용 k개의 Linked-List가 담긴 array가 주어지면 모든 linkedlist를 숫자가 증가하는 순서대로 합치는 문제이다. 문제 해결 흐름 1. 가장 Naive한 방법은 lists에 있는 것을 다 읽어서 순서대로 붙여나가는 방법일 것이다. → linkedlist를 하나씩 읽어서 list에 넣고 이를 정렬하여 Linked-list를 만드는 방법이 있을 것이다. → 이 방법은 문제가 Hard 난이도이기 때문에 TLE가 나올 것임을 예상하고 사용하지 않았으나 공식 풀이에 포함되어 있는 것으로 보아 문제는 없을 것 같다. 2. 위의 방법에서 조금 ..

풀이 일자: 23.03.10 난이도: [Medium] 분류: [Linked List, Reservoir Sampling, Randomized, Math] 문제 내용 문제의 내용은 한 방향의 linkedList가 주어졌을 때 임의의 노드를 리턴하는데 linkedlist의 모든 노드는 모두 같은 선택될 확률을 가지고 있어야 한다. Follow up: Linked List가 극단적으로 크고 길이를 모르는 경우를 가정해보고 O(1)의 space complexity가 되도록 푸는 문제 문제 해결 흐름 1. 일단 Follow-up을 무시하고 풀어본다면.. → class 내부의 constructor에서는 linked-list를 끝까지 읽으면서 arr에 저장해놓고 파이썬 내의 내장함수인 random.choice를 사용..

풀이 일자: 23.03.09 난이도: [Medium] 분류: [Hash Table, Two Pointer] 문제 내용 LinkedList의 head가 주어졌을 때 cycle이 시작되는 노드를 리턴하고 cycle이 없으면 null을 리턴하는 문제이다. Follow-up으로 자료구조 이용하지 않고 풀기. 문제 해결 흐름 1. 우선 포인터를 하나만 사용한다면 cycle이 없는지는 확인이 가능한데 그거 외에는 가능한게 없다. → Two-pointer를 사용해야겠다. 2. Two-pointer을 사용하는데 cycle이 있음을 확인하려면 두 개의 포인터의 이동 속도가 달라야겠다. → 포인터 하나는 한 칸씩 움직이고 나머지 하나는 두 칸씩 움직인다. 3. 이거랑 관련된 알고리즘이 있다. → 플로이드-마샬 알고리즘으로..

풀이 일자: 23.03.08 난이도: [Medium] 분류: [Binary Search] 문제 내용 n개의 바나나 무더기가 존재하고 piles[i]의 의미는 i번째 무더기에 존재하는 바나나의 개수를 의미한다. 이를 지키는 가드가 h시간 후에 올 예정이며 이에 Koko는 시간당 k의 속도로 매 시간마다 하나의 무더기를 골라 바나나를 먹을 예정이다. 만약 선택한 무더기에 있는 바나나의 수가 k보다 적은 경우 해당 무더기에 남아있는 바나나만 먹게 된다. 이러한 와중에 Koko는 바나나를 최대한 천천히 먹되 Gaurd가 오기 전까지 모든 바나나를 먹으려고 할 때의 최소 k를 구하는 문제이다. piles = [3,6,7,11], h = 8 만약 k가 4라고 가정한다면, [1,2,2,3] 즉 8번만에 다 먹게 되며..

풀이 일자: 23.03.07 난이도: [Medium] 분류: [Binary Search] 문제 내용 time의 배열의 요소의 개수만큼의 bus가 있고 각각의 bus가 한번 trip을 돌 때의 시간이 각각의 배열 요소가 된다. 버스는 동시에 출발하며 서로 영향을 주지 않고 모든 버스의 trips의 합이 totalTrips이 되는 최소 시간을 구하는 문제이다. 문제의 예시를 그대로 든다면, Input: time = [1,2,3], totalTrips = 5 Time = 1이면 [1,0,0]번의 Trip을 각각 돌았을 것이기에 totalTrips는 1이 된다 Time = 2이면 [2,1,0]번의 Trip을 각각 돌았을 것이기에 totalTrips는 3이 된다 Time = 3이면 [3,1,1]번의 Trip을 각..

풀이 일자: 23.03.05 난이도: [Hard] 분류: [Hash table, BFS] 문제 내용 arr이라는 배열이 주어졌을 때 다음과 같은 규칙으로 움직여서 배열의 끝까지 갈 때 가장 적은 step을 구하는 문제 1. 현재 위치 기준 앞뒤로 이동 가능하다. ( index범위 내에서) 2. 같은 배열값을 가지고 있는 다른 인덱스 위치로 이동 가능하다. 문제 해결 흐름 1. 어떤 알고리즘이 해당 문제에 적합할지 생각해보자. → 가장 단거리의 길을 찾는 것이 목표이므로 이를 위해 사용하는 알고리즘은 대충 DP와 그래프 순회정도이다. 2. DP의 경우 항상 최후의 수단으로 생각하고 일단 그래프 순회로 풀어보자. → DP의 경우 우선 점화식을 찾아야 하고 여러 가지를 고려해야하기에 다른 사용가능한 알고리즘을..

풀이 일자: 23.03.03 난이도: [Medium] 분류: [Two Pointer, String, String Match] 문제 내용 문제의 내용으로는 needle과 haystack이라는 변수에 담긴 문자열이 주어졌을 때 needle이 haystack에 포함되는 경우 포함되는 부분의 첫 인덱스를 리턴하고 포함하지 않는 경우 -1을 리턴하는 문제다. 문제 해결 흐름 1. 간단하게 생각해보면 열심히 순회를 하면서 needle과 같은게 나오는지 확인하면 된다.(Sliding Window) → 조금 더 생각해보면 while문으로 돌려서 현재의 인덱스(i) + len(needle) int: ans = -1; i = 0; while(i + len(needle) 가장 간단하게 떠올릴 수 있는 방법 Time Comp..

풀이 일자: 23.03.02 난이도: [Medium] 분류: [Two Pointer] 문제 내용 알파벳이 들어있는 배열이 주어졌을 때 이를 String으로 변환하는 문제이다. 연속되는 반복적인 알파벳을 각각 하나의 그룹으로 묶었을 때, 해당 그룹의 길이가 1이면 그대로 해당 알파벳을 넣고 1이상이면 해당 알파벳과 그 그룹의 길이를 넣는 문제이다. ( 만약 10이상이면 자리수별로 쪼개서 넣어야 한다.) 이에 대한 정보를 초기에 주어지는 chars라는 배열에 넣어 처리해야 하며 리턴값은 s의 길이가 된다. 즉, 예를 들어본다면 chars = ["a","b","b","b","b","b","b","b","b","b","b","b","b"] 위의 배열이 있다고 가정하자. 이를 압축하는 기준에 따라 압축한다면, 우..