🍄 알고리즘 시간복잡도 및 요약 카테고리이름시간복잡도설명자료구조유니온 파인드O(α(N))서로소 집합 자료구조, 경로 압축 + union by rank자료구조우선순위 큐 (힙)삽입/삭제: O(log N), 조회: O(1)최대/최소값을 빠르게 관리하는 큐자료구조링크드 리스트삽입/삭제: O(1), 탐색: O(n)노드 포인터 기반 구조, 삽입·삭제 효율적자료구조Trie삽입/탐색: O(L)문자열 저장 트리, 접두사 탐색에 최적완전탐색DFSO(V + E)깊이 우선 탐색, 스택/재귀 기반완전탐색BFSO(V + E)너비 우선 탐색, 큐 기반백트래킹백트래킹O(조건에 따라 다양)상태 공간 트리 탐색, 가지치기 통해 효율화탐색이진 탐색O(log N)정렬된 배열에서 중간 기준 이분 탐색최단경로다익스트라O((V + E) lo..

그동안 알고리즘 공부하며 공부한 것들 정리 🍄 문제 풀면서 느낀 팁파이썬은 1초에 대충 2천만 번 연산 가능하다고 보면 됨시간 복잡도는 꼭 계산해보기구현 문제일수록 문제 꼼꼼히 봐야 함테스트 케이스 다양하게 넣어보기. 특히 최소, 최대, 엣지 케이스 🍄 자주 쓰는 파이썬 내장 함수/모듈itertools: permutations, combinations, count heapq: 우선순위 큐 구현할 때 bisect: 이진 탐색할 때collections: deque, Counter math: factorial, sqrt, gcd, pi, sin, cos 등등 sum, min, max 이런 기본 함수들도 은근 많이 씀  🍄 파이썬 팁 mutable / immutable 정리 mutable: list, di..

○ 탐색 알고리즘 코딩테스트 단골 문제 BFS, DFS 흔히 BFS, DFS + 재귀 문제만 잘 풀어도 코딩테스트에 통과할 수 있다고 하는데요. 그만큼 단골문제로 등장하는 BFS(너비 우선 탐색), DFS(깊이 우선 탐색)에 대해 알아보고 관련 백준 예제도 풀어도보도록 하겠습니다. 우선 탐색 이란 무엇인가. 프로그래밍을 할 때 데이터베이스 안의 수 많은 자료에서 원하는 자료를 찾으려면 어떻게 해야할까요? 만약 데이터가 정렬이 되어있다면 이진탐색을 통해서 최대 로그N의 연산만으로 찾을 수 있겠지만, 정렬이나 분류가 되어있지 않는 자료라면 이야기가 달라집니다. 원하는 자료를 찾을 때 까지 하나씩 직접 확인하며 찾아야합니다. 이러한 무식한 방법이 바로 깊이 우선 탐색(DFS)와 너비 우선 탐색(BFS) 입니다..

● Greedy Algorithm 그리디(Greedy) 알고리즘은 'greedy'(탐욕, 욕심쟁이)라는 뜻에서 유추할 수 있듯이 멀리 생각하지 않고 지금 당장의 단계에서 가장 좋은(최선의) 선택을 하는 문제해결 방법입니다. 각 단계에서 가장 좋은 선택을 했을 때 전체적으로 최선의 해결방법이 되길 바라는 알고리즘입니다. 그리디 알고리즘은 동적프로그래밍(다이나믹, DP)에서 지나치게 많은 연산과정을 거치는 것을 보완하기 위해 나온 개념이지만, 모든 문제에서 그리디 알고리즘이 최선의 선택을 보장하는 것은 아니라는 단점이 있습니다. 사실 대다수의 경우 올바른 답을 주진 않지만 쉽고 적은 연산으로 문제를 해결하는데 좋은 결과를 보장한다는 점에서 많이 사용되는 개념입니다. 예시1 - 백준 11047 동전0 그리디 ..