반응형 problemsolving13 [알고리즘/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] 최단경로: 다익스트라(Dijkstra) / BOJ 1753 최단경로 안녕하세요!이번에는 최단경로를 구하는 알고리즘 중 하나를 공부해보려고 합니다! 그 중 첫 번째로, 다익스트라(Dijkstra) 알고리즘을 공부해보겠습니다 !다익스트라는 그리디 알고리즘 원리를 이용하는데요, 추후 그리디(Greedy)도 포스팅 해보겠습니다 :)다익스트라(Dijkstra) 알고리즘🔹 다익스트라 알고리즘 기본 개념* 목적: 하나의 시작 정점에서 다른 모든 정점까지의 최단경로를 구하는 알고리즘입니다. * 조건: 간선의 가중치가 음수가 없어야 합니다.- 음수 가중치가 있다면 잘못된 결과가 발생합니다.- 음수 가중치가 있을 때에는 다익스트라가 아닌 Bellman-Ford 등을 사용해야 합니다. * 알고리즘 유형: 그리디(Greedy) 알고리즘을 활용합니다. * 아이디어: "현재까지 알려진 가장 짧.. 2025. 9. 9. [알고리즘/Algorithm] 파라메트릭 서치(Parametric Search) / BOJ 2110 공유기 설치 안녕하세요:)이번에는 이전에 정리했던 이분탐색의 확장 개념인 파라메트릭 서치를 공부해 정리해보려고 합니다. 이분탐색 포스팅이 궁금하신 분들은 이 링크의 포스팅을 먼저 확인해보시길 추천드립니다!http://melodyblue.tistory.com/40 [알고리즘/Algorithm] 이분 탐색(이진 탐색) / Binary Search Algorithm 이론 정리 및 예제 풀이알고리즘 문제풀이를 공부하면서, 역시나 정리가 필수라는 생각이 계속 들었습니다!차근차근 정리해보겠습니다 :)이번에는 이분 탐색(이진 탐색) 인 Binary Search에 대해 정리해보겠습니다. 이분melodyblue.tistory.com 그럼 이제 파라메트릭 서치를 공부하고 예제도 풀어보겠습니다 :) ㅋㅋㅋ파라메트릭 서치(Parametr.. 2025. 7. 28. 이전 1 2 3 4 다음 반응형
