본문 바로가기
반응형

dev8

[알고리즘/Algorithm] 슬라이딩 윈도우(Sliding Window) / BOJ 2559 수열 안녕하세요,이번에는 코딩테스트를 준비하다가 투포인터와 헷갈리는 개념이 있어서 공부해보았습니다.(투포인터도 조만간 정리해야겠습니다 !)슬라이딩 윈도우도 정리를 시작 해 보겠습니다 !슬라이딩 윈도우 Sliding Window🔹 개념 슬라이딩 윈도우는 배열이나 문자열에서 연속구간을 다룰 때 쓰는 대표적인 테크닉 입니다.한 번에 전 범위를 훑지 않고, '창(window)-구간'를 왼쪽/오른쪽으로(좌측, 우측 경계만 조금씩 이동) 밀면서 정답을 갱신합니다.이러한 방식으로 시간복잡도를 크게 줄일 수 있습니다. 🔹 핵심 아이디어1. 연속 구간(subarray / substring)의 값을 다룬다.- e.g. 합, 길이, 조건 만족 여부 등2. 창(window), 즉 특정 범위의 구간의 좌측, 우측 경계를 조금씩 .. 2025. 9. 24.
[알고리즘/Algorithm] 그리디(Greedy:탐욕) 알고리즘(패러다임) 안녕하세요!이번에는 그리디(Greedy, 탐욕)에 대해서 공부해보려고 합니다.엄연히 말하면 그리디는 알고리즘 그 자체라기 보다는, "알고리즘 설계 기법(패러다임)"입니다. 이러한 그리디 기법을 활용한 알고리즘이 많아서 따로 정리해보려고 이렇게 포스팅을 해봅니다 !!그리디(Greedy)란?🔹 Greedy(탐욕) 알고리즘(패러다임)이란?매 단계에서 당장 최선으로 보이는 선택(국소 최적)을 하고그 선택을 되돌리지 않으며다음단계로 나아가는 방법정확히는 "알고리즘 설계 기법(패러다임)"목표: 이러한 국소 최적 선택들의 연쇄가 전역 최적해로 이어지도록 하는 것.🔹 Greedy 핵심 성질-> Greedy가 성립하기 위한 조건은 무엇이 있을까요?Greedy-choice property지금 시점에서의 최선의 선택이 .. 2025. 9. 16.
[알고리즘/Algorithm] 깊이 우선 탐색 - DFS / BOJ 2606 바이러스 안녕하세요!드디어 그래프 이론을 활용한 알고리즘 공부를 하고 있습니다.이론을 정리하고 문제 푸는 게 재미있지만 시간이 좀 걸리는 작업이기는 하네요 ㅎㅎ제가 한창 알고리즘 공부할 때 정말 재미있게 배웠던 그래프 알고리즘 중,가장 많이 활용되고 기본적으로 쓰이는 탐색 알고리즘을 공부해보겠습니다 :)이번에는 DFS 알고리즘을 정리해보려고 합니다~DFS의 정의 (깊이 우선 탐색)🔹 깊이 우선 탐색/DFS(Depth-First-Search) 란?: 그래프 또는 트리에서 한 정점에서 시작하여, 한 방향으로 갈 수 있는 곳 까지 끝까지 깊이 탐색한 후,더 이상 갈 곳이 없으면 다시 돌아와서(백트래킹) 다른 경로를 탐색하는 알고리즘입니다. 🔹 DFS의 특징항목설명탐색 방식깊이 우선 (먼저 한 쪽 끝까지 파고 듦)자.. 2025. 6. 16.
[자료구조 | Data Structure] 그래프 이론 Graph Theory 안녕하세요,오늘은 알고리즘에 사용되는 자료구조를 정리해보려고 합니다.알고리즘 문제 풀이에 대표적으로 사용되는 자료구조증 하나, 그래프에 대하여 정리해보겠습니다.그래프(Graph), 혹은 그래프 이론(Graph Theory)라고 불리는 이 자료구조는, DFS, BFS 문제를 푸는 데 기초가 되는 이론이고,나아가 위상정렬 등의 문제를 푸는 데도 기초가 됩니다.트리 문제도 그래프 이론에서 출발하죠!그래서 저도 기초를 다시 다지기 위해서 정리해봅니다. :)그래프 이론(Graph Theory) 기초 개념 정리그래프는 현실 세계의 네트워크, 관계, 연결구조를 수학적으로 표현한 자료구조 입니다.소셜 네트워크, 지도, 컴퓨터 네트워크, 알고리즘 문제 등에서 필수적으로 사용됩니다. 그래프란?: 그래프란 정점(Vertex.. 2025. 5. 26.
반응형

티스토리툴바