Today_I_Learned/Algorithm
-
99클럽 코테 스터디 8일차 TIL: 배열, 1286. Iterator for CombinationToday_I_Learned/Algorithm 2024. 6. 18. 00:21
문제https://leetcode.com/problems/iterator-for-combination/description/ 통과 여부Fail 나의 접근법 Backtrack 을 이용하여 CombinationIterator 생성자 호출 시 conbinationLength 길이만큼의 가능한 모든 조합을 미리 구하여 멤버 필드로 저장한다.next() 와 hasNext() 문자열 조합 멤버 필드로부터 요소를 하나씩 가져와 return 한다.
-
99클럽 코테 스터디 7일차 TIL: 배열, 1282. Group the People Given the Group Size They Belong ToToday_I_Learned/Algorithm 2024. 6. 17. 00:06
문제https://leetcode.com/problems/group-the-people-given-the-group-size-they-belong-to/description/ 통과 여부Pass 나의 접근법 2차원 List 인 tmp 를 생성한다.groupSizes 를 순회하며 'groupSizes 의 값 -> tmp 의 Index 가 되는 요소(List)에 groupSizes 의 인덱스 번호를 추가' 를 반복한다.tmp 를 순회하며 각 요소 배열을 인덱스 번호의 길이로 나눈다.class Solution: def groupThePeople(self, groupSizes: List[int]) -> List[List[int]]: answer = [] tmp = [[] for _ ..
-
99클럽 코테 스터디 6일차 TIL: 배열, LeetCode 2433. Find The Original Array of Prefix XorToday_I_Learned/Algorithm 2024. 6. 16. 09:45
문제https://leetcode.com/problems/find-the-original-array-of-prefix-xor/description/ 통과 여부Pass 나의 접근법 XOR 연산자의 특성을 알고 있으면 쉽게 풀 수 있는 문제 ( A ^ B = C 일 때, A ^ C = B )하지만 나는 ^ (XOR 연산자) 를 몰라 검색 시간이 필요했다.class Solution: def findArray(self, pref: List[int]) -> List[int]: arr = [pref[0]] for i in range(1, len(pref)): arr.append(pref[i]^pref[i-1]) return arr
-
99클럽 코테 스터디 5일차 TIL: 배열, Leetcode 1476. Subrectangle QueriesToday_I_Learned/Algorithm 2024. 6. 15. 10:43
문제https://leetcode.com/problems/subrectangle-queries/description/ 통과 여부Pass 나의 접근법 문제만 이해되면 풀이는 특별할 것 없이 단순했던 문제.두 번째 Input 의 0번 요소로 2차원 List 인 self.rectangle 을 초기화updateSubrectangle(row1, col1, row2, col2, newValue) 는 2 중 for문을 돌려 self.rectangle[row1][col1] 부터 self.rectangle[row2][col2] 까지 newValue 로 초기화문제는 해결되었지만, 코테가 이렇게 쉬울리 없다는 이상한 의심이 들어 더 빠른 방법이 있는 지 재도전 해 볼 예정이다.class SubrectangleQueries:..
-
99클럽 코테 스터디 4일차 TIL : Graph, 프로그래머스, 순위Today_I_Learned/Algorithm 2024. 6. 13. 23:01
문제https://school.programmers.co.kr/learn/courses/30/lessons/49191 프로그래머스코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.programmers.co.kr 통과 여부Fail 나의 접근법 (해결 못 함)'방향'과 '순위' 에 꽂혀 위상 정렬 문제라고 생각하고 문제 풀기 시작[[], [이긴 상대1, 2,...], [], ...] 처럼 각 선수 별로 이긴 상대를 List에 담은 2차원 List 로 초기화나 > 상대일 때, 상대 > 타 선수 이면, 나 > 타 선수 이므로 위 2차원 List 를 순회하면서 각 선수 별로 이긴 상대를 Update 함. 각 ..
-
99클럽 코테 스터디 3일차 TIL: Graph, Dijkstra, 프로그래머스, 가장 먼 노드Today_I_Learned/Algorithm 2024. 6. 12. 23:40
문제https://school.programmers.co.kr/learn/courses/30/lessons/49189 프로그래머스코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.programmers.co.kr통과 여부Pass 나의 접근법Dijkstra 채택( Dijkstra 의 조건1. 어느 한 Node 로 부터 나머지 모든 Node 간의 거리를 구해야 함. 조건2. Node 간 거리는 모두 양수여야 함.)최대 거리를 나타내는 변수 longgest 를 두고, 시작점과 어느 한 Node 의 거리가 longgest 의 값보다 크면 해당 거리로 longgest 를 갱신한다.longgest 와 동일한 거리가 ..
-
99클럽 코테 스터디 1일차 : 그리디, 구명보트(프로그래머스)Today_I_Learned/Algorithm 2024. 6. 6. 10:57
문제https://school.programmers.co.kr/learn/courses/30/lessons/42885 프로그래머스코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.programmers.co.kr 참고한 그리디 설명 영상https://www.inflearn.com/course/lecture?courseSlug=%EB%91%90%EC%9E%87-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-%EC%BD%94%EB%94%A9%ED%85%8C%EC%8A%A4%ED%8A%B8-%EC%94%A8%EC%81%A0%EC%81%A0&unitId=148427 학습 페이지 www.infl..
-
MST 탐색(프림 Prim / 크루스칼 Kruskal)Today_I_Learned/Algorithm 2023. 4. 16. 23:35
1. 일반적인 MST 한 번에 하나의 안전한 간선(Cycle을 발생시키지 않는 간선)을 추가하여 Tree A 를 완성하고 이 때 완성된 Tree A가 MST인지 확인. GENERIC-MST(G, w) A = NULL while A does not form a spanning tree do find an edge (u, v) that is safe for A A = A + (u, v) return A * G 는 Graph 를 의미 2. 프림 알고리즘 개념 현재 선택한 집합 A와 인접하면서, Cut 을 가로지르는 light edge(인접한 Vertex 와의 간선들 중 가중치가 가장 작은 간선)를 선택하여 MST 를 탐색하는 알고리즘. 전제 집합 A는 항상 Tree (Vertex 와 Edge 을 갖는 집합) ..