본문 바로가기

Today I Learned109

(24.09.05) 코딩테스트 알고리즘 정리(유니온 파인드 알고리즘) 유니온 파인드 Union-Find 알고리즘은 코딩테스트 대비에서 거의 출제빈도가 적은 알고리즘으로 알고 있다. 하지만, 지금까지 가중치에 따른 Graphy 구조에서 어떤 "경로" 관해서 집중한 알고리즘이 있다면,이번엔 같은 그룹 즉, 같은 루트에 해당하는 자료에서 특정 주어진 경로의 루트 값의 비교를 통해 같은 그룹인지 아닌지를 파악할 수 있도록 하는 알고리즘을 집중해서 찾아보고 학습을 해봤다. 생각보다 개인적올 이해하기가 살짝 어려워서 코드를 하나하나 쳐가면서 내가 스스로 낸 문제를 작성할 수 있었다.유니온 파인드 Union-Find서로소 집합(Disjoint Set)의 자료구조를 다루는데 사용되는 알고리즘연결된 요소 즉, 그룹을 빠르게 찾아낼 수 있는 알고리즘그룹은 하나의 부모에 여러 요소가 포함되어.. 2024. 9. 5.
(24.09.04) 코딩테스트 알고리즘 정리(동적 계획법 Dynamic Programming / 다익스트라 알고리즘) 개발 이력서/Portfolio 동시에 준비 + 기존 완성 프로젝트 Update/점검 상황에서 매일 알고리즘 학습을 하는게 워낙 어려운 일이 아닌 것 처럼 느껴져서 심리적으로 압박이 크다. 코딩테스트 준비이기도 하지만, 학습하면서, 로직에서 구현되어야할 알고리즘을 배우는 것도 나름 흥미가 있고,학습한 동적 계획법 처럼 어떤 특정 패턴의 알고리즘이 아닌 로직을 구성하는 방법에 관한 것들도실제 코드를 작성하는데 도움이 될 것으로 생각해서 내 언어로 하나하나 정리하면서 학습 동적 계획법 Dynamic Programming하나의 문제를 큰 문제를 여러개의 문제로 쪼개서 결과를 저장 → 다시 해결에 사용하는 방식DFS에서의 재귀방식을 사용할 시, 과하게 많은 로직이 반복이 되거나, 또는 많은 양의 반복문을 계속해서.. 2024. 9. 4.
(24.09.02) 코딩테스트 알고리즘 정리(전체탐색 : BFS/DFS) 코딩테스트에서 많이 사용되는 알고리즘 중 전체탐색을 하는 BFS DFS 전체탐색 알고리즘을 찾아보고 직접 코드를 짜보면서 학습했다. 아래의 모든 내용은 스스로 정리를 한것이고,이해하기 어려웠기 때문에 코드를 직접 주석과 함께 쓰면서 공부를 하면서 정리하는데 시간이 조금 걸렸지만, 전체를 탐색하고 특정 조건이 주어졌을 때, 그 조건을 만족시켜 해당하는 경로(Node)를 탐색시키는 것을 목적으로 둔다는 점에서BFS는 이웃경로 탐색으로 최단거리, 최단 경로 문제DFS는 조건이 걸린 모든 경로 구하기문제 = 미로 문제 를 스스로 내서스스로 알고리즘을 짜면서 학습을 진행을 했다. BFS (Breadth-First Search, 너비 우선 탐색)그래프의 모든 노드를 레벨 단위로 탐색하는 알고리즘따라서 재귀적으로 동.. 2024. 9. 2.
(24.08.28) 코딩테스트 알고리즘 정리(구현:누적합,유클리드,에라토스테네스의체, 구간탐색:이분탐색,슬라이딩윈도우, Greedy:동전교환 알고리즘) 이전까지는 거의 코드 카타를 맨땅에 헤딩하듯이 풀어서다시 살펴보니, 간단하게 알고리즘으로 풀수 있는 로직을 굳이 O(N^2) 시간 복잡도로 하나씩 대조하거나 하는 식의 로직이 많았기 때문에,필수 알고리즘 기초부터 다시 정리를 하기 시작했다. 검색을 통해 정리를 하고, 스스로 코드를 적으면서 정리를 한 뒤, 응용된 문제들을 푸는 방식으로 진행을 해야여러 알고리즘이 섞인 코딩테스트 문제도 해결할 수 있을 것이라고 판단해서 블로그 TIL과 Notion에 정리를 하도록 한다.  누적합 Prefix Sum더보기특정 배열 등의 자료 구조 구간의 누적된 합, 즉 계속 지속적으로 더하는 알고리즘배열의 여러 구간에 대해 부분합을 빠르게 계산“ 이전까지의 누적합을 다음 누적합에 사용한다” 라는 알고리즘이기 때문에 항상 누.. 2024. 8. 28.

티스토리툴바