본문 바로가기

개인 공부/TIL25

TIL : Two-Pointer 알고리즘 (7) 💻 알고리즘 ✔️ Two-Pointer 알고리즘이란? 리스트에 순차적으로 접근할 때 두 개의 점 위치를 기록하면서 처리하는 알고리즘! 간단히 말해서 포인터 두 개를 사용해서 데이터에 접근하겠다는 소리이다. 💡 특징 포인터 2개가 같은 방향으로 이동 → 특정 값과 일치하는 배열을 찾는 경우 포인터 2개가 양끝에서 출발해서 만남 → 특정 값과 일치하는 합을 찾는 경우 모든 범위를 확인하지 않고 O(n^2), 포인터가 각각 N번만 이동하기 때문에 O(N) ✔️ 포인터가 같은 방향으로 이동 def two_pointer(array, target): end, sum_ = 0, 0 cnt = 0 for start in range(len(array)): while sum_ < target and end < len(ar.. 2022. 8. 8.
TIL : Union-Find 알고리즘, Disjoint Set 자료구조 (6) 📚 자료구조 ✔️ Disjoint Set이란? 여집합이 없는 부분집합을 저장하고 조작하는 자료 구조. 한 마디로, 서로소 집합 자료구조 세 가지 연산을 가진다. 초기화, make-set(x) : x를 유일한 원소로 하는 새로운 set을 만든다. 합치기, union(x, y) : x가 속한 set과 y가 속한 set을 합친다. 찾기, find(x) : x가 속한 set의 루트 노드 값을 리턴한다. 💡 특징 부모 노드가 자식 노드를 가리키는 트리 구조와 다르게 분리 집합은 자식 노드가 부모 노드를 가리킨다. 💻 알고리즘 ✔️ Union-Find 알고리즘이란? 그래프 알고리즘 중 하나로 두 노드가 같은 그래프에 속하는지 판별하는 알고리즘이다. 다시 말하면, disjoint set을 표현할 때 사용하는 알고리즘.. 2022. 8. 7.
TIL : 다익스트라 알고리즘 (5) 💻 알고리즘 ✔️ 다익스트라 알고리즘 그래프 이론 알고리즘 중 목적지에서 다른 노드로 이동할 때 최단 경로를 계산하는 알고리즘이다! 이 알고리즘의 특징과 동작 원리는 다음과 같다. 💡 특징 최단 거리를 기록할 추가적인 테이블이 필요하다. 그리디 알고리즘과 비슷한 면이 있다. 💡 동작 원리 출발 노드를 정하고 최단거리 테이블을 초기화한다. 방문하지 않은 노드 중 거리가 가장 짧은 노드를 선택한다. 거리를 계산해서 더 짧은 거리라면 최신화해준다. 2번, 3번 과정을 반복한다. import heapq def dijkstra(graph, start): # 최단거리 계산용 리스트, INF는 무한대를 의미한다. distance = [INF] * (size + 1) distance[start] = 0 queue = .. 2022. 8. 1.
Today I Learned : 파이썬 (4) 🐍 파이썬 ✔️ 2차원 배열 max 값 ### 2차원 배열에서 최대값 찾기 feat. max() arr= [[1,2], [3,4]] max_ =max(max_, max(map(max, arr))) ✔️ 깊은 복사, 얕은 복사 파이썬에는 객체를 2가지로 분류할 수 있다. 바로 mutable과 immutable. list, dictionary, set 이렇게 3가지만 mutable하고 나머지는 모두 immutable이다. 차이는 변경이 가능한지인데, immutable은 값이 같으면 변수명만 다르고 같은 참조를 한다는 것이다. 깊은 복사와 얕은 복사를 이해하기 위해서 이 개념이 필요하다. 얕은 복사란, 변수를 복사했는데 같은 곳을 참조할 때를 말한다. 대입연산자('='), 슬라이싱([:]), copy(), c.. 2022. 7. 17.
Today I Learned : 파이썬 (3) 🐍 파이썬 ✔️ enumerate() '열거하다'라는 뜻을 가진 함수이다! 순서가 있는 자료형(list, set, tuple, dictionary, string)을 입력 받고 인덱스와 원소를 튜플 형태로 리턴! 인덱스와 원소를 다른 변수에 할당하고 싶다면 unpacking을 해야 한다! 시작 인덱스를 바꾸고 싶다면 start에 시작하고 싶은 숫자를 넘기면 된다! ### Example for i in enumerate(['A', 'B', 'C']): print(i) .... (0, 'A') (1, 'B') (2, 'C') ### Example2 for idx, element in enumerate(['A', 'B', 'C']): print(idx, element) .... 0 A 1 B 2 C ### Ex.. 2022. 7. 5.
Today I Learned : 코딩테스트, 파이썬, 소수 (2) 💻 코딩테스트 네부캠을 지원해서 오랜만에 코테를 봤는데 오랜만에 하는 알고리즘이라 그런지 많은 부족함을 느꼈다. 나름 고민해서 분석한 결과 몇 가지 문제점이 있다! ❌ 문제점 시간 배분을 잘 못한다. 파이썬 빌트인 함수 이해도 부족 미숙한 파이썬 문법 절대적인 경험치 부족 당장 다음 코테까지 시간이 부족하므로 당장은 문제를 풀면서 해결하는 수 밖에 없는 것 같다. 🐍 파이썬 set은 집합을 나타내는 자료구조이다! cpp를 주언어로 했었다가 넘어와서 그런지 정말 파이썬이 좋은 언어라고 느낀점은 내가 생각하는 거의 그대로 표현이 된다는 점이다. ex. set(a) - set(b) itertools 라이브러리에 순열(permutation)과 조합(combination)을 만들어낼 수 있다! 사용법은 permu.. 2022. 7. 1.

티스토리툴바