본문 바로가기

전체보기62

[99클럽 코테 스터디 34일차 TIL] 스택/큐(재귀) ✏️  오늘의 문제 : 341. Flatten Nested List Iterator 📌 주안점리스트가 마구잡이로 nested 되어있다. 그러한 리스트를 처음부터 끝까지 정방향 순회하는 클래스를 구현하는 문제리스트는 두가지 방식으로 구현이 가능하다배열링크드 리스트문제에서 요구한 것은, next()에서 결과 리스트에 값 추가, hasNext()에서 다음 순서 원소 검사간단하게 1차원 리스트를 만들어 차례대로 값을 넣어놓고, 메소드에서는 새로운 배열을 순회이 방법은 구현은 간단하지만, class의 목적과 부합하진 않을 수 있다.클래스 생성 오버헤드가 크다. 만약 클래스의 목적이 끝까지 순회하는 것이 아니라면 initiallize하는데에만 시간을 더 쓸것이기에.혹은 순회 과정과 값 출력을 동시에 하도록.이방법.. 2024. 6. 23.
[99클럽 코테 스터디 32일차 TIL] 정렬 ✏️  오늘의 문제 : 869. Reordered Power of 2  📌 주안점주어지는 정수 n을 구워삶아 2의k승으로 표현이 가능하다면 되는 문제처음 드는 생각은, n의 모든 가짓수마다 2의 k승을 구한다.그러나 적절한 n을 찾는것보다 같은 길이의 문자열인 2의 k승에서만 비교하는 것이 더 효율적이다.그래서, 2의 k승의 k를 1씩 늘려가며 n과 숫자열의 길이가 같을 때를 찾는다.이후 n의 숫자가 어떻게 구성되어있는지 numlist[10] 배열에 담는다.numlist[i] = 숫자 i의 갯수if numlist[i] = 0 for i in range(10)이라면, True return📌 해결 방법numlist[10] 배열 생성숫자를 글자로, 글자를 숫자로 바꾸는 변환 과정이 조금 번거롭지만 글자로 .. 2024. 6. 21.
[백준] 10026 적록색약 (DFS) 시간 허비한점, 보완할 점, 기억할 점접근 방식은 생각보다 쉽게 파악했다. 모든 노드에서 DFS를 실행하는데, DFS의 끝조건을 모두 탐색했을시로 설정했다. 한 점에서 한 색(R,G,B) 기준으로 탐색을 마치면, 연결된 하나의 색 구역을 파악할 수 있다.DFS를 구현하기 위해 재귀를 돌렸는데, 입력되는 그래프는 N*N 그래프로 모든 노드에 대해서 DFS를 돌린다면 쉽게 재귀 초과가 발생할 수 있다.스택으로 바꾸어서 구현했고, 변환 자체는 오래 걸리지 않았다.스택으로 바꿀 때, 다음 정점 판단이 기존 파라미터로 전달에서 글로벌 stack 자료구조에 의존하는 방식으로 바뀌었기에, 탐색에 앞서 stack에 push해주는 연산을 까먹지 말자DFS에서 visited 배열을 따로 생성하여 방문 여부를 파악하는 방식.. 2024. 6. 20.
[99클럽 코테 스터디 31일차 TIL] 정렬 ✏️  오늘의 문제 : 347. Top K Frequent Elements  📌 주안점dictionary를 사용해 key는 number, value는 빈도수로 설정한다.이후 dictionary를 sort한 결과중 상위 k개까지 리턴 📌 해결방법defaultdict(int)로 빈도수 파악하기 위한 자료구조 설정sorted 함수로 정렬한다.python 의 sorted함수는 O(nlogn) 시간 복잡도의 알고리즘 중에서도 최적화가 잘된 정렬함수상위 k개의 결과를 반환한다.from collections import defaultdictclass Solution: def topKFrequent(self, nums: List[int], k: int) -> List[int]: dic = defa.. 2024. 6. 20.

티스토리툴바