🌟 들어가기 전알고리즘 공부를 하면서 가장 많이 쓰는 탐색 기술!!레벨이 오르면 가장 많이 쓰는게 BFS와 DFS이다.하지만 가장 간단하고 기본적인 탐색 기술은 아무래도 완전탐색이 아닌가 싶다. 기본이 되면서도 가벼운 완전탐색과 이진탐색을 알아보기로 하였다. 🔍 세부 내용완전 탐색모든 경우의 수를 탐색하여 답을 찾는 방식이다.예를 들어 [1,2,3,4,5]의 배열이 있으면 5라는 숫자를 찾으려면 배열을 모두 돌아야만 찾을 수가 있다. 이렇게 모든 배열을 탐색하는 방법도 완전 탐색에 들어간다.완전 탐색은 모든 원소를 순회해야 하므로 O(N)이라는 시간 복잡도를 가지고 있다. 그래서 코딩테스트 문제를 풀 때 완전탐색을 하는 경우에는 시간 초과 이슈가 발생할 수도 있다. 예시)/* 배열에서 특정 숫자 찾기..

스케줄링 알고리즘은 운영 체제에서 프로세스에게 CPU를 할당하는 방식을 결정하는 알고리즘입니다. 다양한 스케줄링 알고리즘이 존재하지만, 가장 기본적인 세 가지 알고리즘인 FCFS(First-Come, First-Served), SJF(Shortest Job First), RR(Round Robin) 알고리즘에 대해 알아보겠습니다. FCFS(First-Come, First-Served) FCFS 알고리즘은 가장 간단한 스케줄링 알고리즘으로, 프로세스가 도착한 순서대로 CPU를 할당하는 방식입니다. 즉, 선입선출(First-Come, First-Served) 방식으로 CPU를 할당합니다. 이 알고리즘은 대화식 작업에 적합하지 않으며, 프로세스의 실행 시간이 긴 경우에는 평균 대기 시간이 길어지는 단점이 있습..

슬라이딩 윈도우 알고리즘(Sliding Window Algorithm)이란? 연속적인 구간의 문제를 효과적으로 해결하기 위한 알고리즘 이 알고리즘은 일정한 크기의 윈도우를 이용하여 연속적인 구간 문제를 해결 슬라이딩 윈도우 알고리즘 구현 단계 시작점과 끝점을 초기화합니다. 윈도우의 크기를 설정합니다. 윈도우를 이동하면서 구간의 값을 계산합니다. 구간의 값을 이용하여 원하는 결과를 도출합니다. 끝점이 배열의 마지막 인덱스에 도달할 때까지 위 과정을 반복합니다. 슬라이딩 윈도우 알고리즘 사용 예 배열에서 최소값을 찾는 문제 문자열에서 최소 윈도우를 찾는 문제 스트림에서 슬라이딩 윈도우를 적용하여 데이터를 처리하는 문제 등에 사용 2023.02.26 - [프로그래머스/Kotlin]Level3 - 징검다리 건너..

BFS와 DFS는 그래프 탐색 알고리즘 중 대표적인 두 가지 방법입니다. 프로그래머스 문제를 풀다보면 해답으로 꼭 있는 것이 BFS 혹은 DFS입니다. 그런 문제를 풀 때마다 나에게 익숙한 DFS를 사용하여풀었는데, 정확한 개념 정리가 필요할 것 같아 정리해보았습니다. * 아래 코드 설명 - Node는 그래프의 노드를 나타내는 클래스 - 각 노드는 그래프 상에서 연결된 다른 노드들의 리스트를 가지고 있음 - start는 탐색을 시작할 노드를 나타내는 변수 - visited는 이미 방문한 노드들의 집합을 나타내는 변수 BFS (너비 우선 탐색) BFS(너비 우선 탐색)는 시작 정점으로부터 가까운 정점을 먼저 탐색하는 방법입니다. 즉, 현재 정점에서 인접한 정점을 큐에 추가하고, 큐에서 하나씩 뽑아 탐색을 ..

플로이드 와샬(Floyd-Warshall) 알고리즘은 모든 정점에서 모든 다른 정점까지의 최단 경로를 구하는 알고리즘 입니다. 이 알고리즘은 다익스트라(Dijkstra) 알고리즘과는 달리 음의 가중치를 가진 그래프에서도 사용할 수 있습니다. 이 알고리즘은 동적 계획법을 사용하여 구현되며, 시간 복잡도는 O(n^3)입니다. 알고리즘의 동작 방식은 아래와 같습니다. 그래프의 인접 행렬을 만듭니다. 3중 반복문을 이용하여 모든점을 순회합니다. i에서 j로 가는 최단 거리를 d[i][j]라고 할 때, d[i][j] = min(d[i][j], d[i][k] + d[k][j])의 점화식을 이용하여 d[i][j]를 갱신합니다. 이 때, k는 1부터 n까지의 정점입니다. 이제 Kotlin으로 플로이드 와샬 알고리즘을 ..

#1. 선택 정렬 : 제자리 정렬 알고리즘 중 하나 ​ 1. 주어진 리스트 중에 최소값을 찾는다. 2. 그 값을 맨 앞에 위치한 값과 교체한다. 3. 맨 처음 위치를 뺀 나머지 리스트를 같은 방법으로 교체한다. ​ if) 9 1 6 8 4 3 2 0 => 최솟값 : 0, 9와 0 교체 0 1 6 8 4 3 2 0 => 최솟값 : 1, 그대로 . . . ( 반복) ​ for (int i=0; i