본문 바로가기

Develop Study/Algorithm33

(24.11.05) DFS 응용과 백트래킹 DFS알고리즘에 대해서 학습을 했지만,어떠한 조건에 따라서는 백트래킹의 여부에 대해서 고찰을 할 필요가 있어조금 이해하는데 어려웠지만 한번더 점검을 해보면서 DFS를 적용하는 문제를 풀고백트래킹에 대해서 다시 정리해보려고 했다.DFS (Depth-First Search, 깊이 우선 탐색)한 노드에 대해서 끝까지 자식 노드를 탐색한 뒤에 다음 노드로 넘어가는 전체 탐색 알고리즘이러한 전체 탐색의 알고리즘은 어떤 목표를 찾아가는 조건이 있을 경우 모든 경우의 수를 찾는 방향따라서, 완전 탐색을 통해 최적의 답을 찾는 로직에서도 유용하게 사용할 수 있음DFS의 직접적인 활용DFS는 가중치가 존재하지 않는 그래프에서 사용이 뜻은 여러가지의 선택의 경우의 수를 선택하는 상황(가중치가 X)에서 완전탐색을 가능하게 .. 2024. 11. 5.
(24.09.26) 정렬 알고리즘 : Quick Sort, Merge Sort Java에서 이미 Collecions 클래스를 통해서 이미 sort 메서드에서 내부적으로 진행하고 있는 정렬에대해서사실상 코딩 테스트나 실무에서는 크게 중심적으로는 사용하지는 않는 알고리즘이지만, 어떻게 작동이 된는 것인지, 그리고 분할한 뒤에 재귀적인 반복과 통합하는 방식의 정렬로알고리즘에 대해서 인식하고 이러한 방식을 참고해서 로직에서 참고할 수 있기 때문에, 따로 같이 블로그에 공부해서 스스로 코드도 작성하면서 정리퀵 정렬 Quick Sort데이터들을 어떤 기준이 되는 Pivot 데이터를 정해서 그 데이터 기준으로 작으면 왼쪽 크면 뒤로 미루는 분할 시켜 정렬하는 방식을 반복하면서 정렬하는 방식피봇은 대게 첫번째 또는 마지막 인덱스 값으로 선택순서를 보장하지 않고 오로지 정렬만을 하는 방식상대적으로.. 2024. 9. 26.
(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.
(24.08.26) 코딩테스트 - 알고리즘 준비 Sparta Coding Club의 내일배움캠프를 최종 프로젝트를 끝으로 종료가 되어이제부터는 이력서, 포트폴리오 작성과 취업을 취한 대비를 본격적으로 진행을 해야한다. 무조건적으로 내 스스로가 준비를 해야하는 것이기 때문에내배캠에서 잠시 최종 프로젝트를 진행하면서 잠시 멈췄던 Code Kata의 연장선으로 코딩테스트 공부를 시작한다. 알고리즘, 그리고 관련 정보는 블로그, Notion에 정리를 하고,기존에 TIL에 정리를 했던 것들도 다시 한번 살펴보면서 알고리즘 기준으로 정리를 할 계획 관련 코딩테스트관련한 강의와 여러 자료를 찾아보면서 환경 구성과 어떻게 진행을 해야할지 잠시 오늘 정리를 하고,내일부터 본격적으로 코딩테스트에 도전을 할 계획이다. 테스트코드 알고리즘 유형 분석구현 유형특정 알고리즘이.. 2024. 8. 26.

티스토리툴바