전체 글158 너비 우선 탐색 (BFS) 너비 우선 탐색 (Breadth First Search)너비 우선 탐색(Breadth First Search)은 그래프(Graph)나 트리(Tree)를 탐색하는 알고리즘입니다. BFS 동작 원리시작 노드를 방문하고 큐(Queue)에 추가합니다.큐에서 노드를 하나 꺼냅니다.방문하지 않은 인접 노드를 모두 방문하고 큐에 추가합니다. 큐가 빌 때까지 2~3 과정을 반복합니다.BFS 구현그래프를 예시로 코드를 작성하도록 하겠습니다. import java.util.*;public class BFS { // 그래프를 인접 리스트로 표현 static class Graph { private int V; // 노드 수 private LinkedList[] adj; // 인접 리스트 .. 2024. 11. 10. 깊이 우선 탐색(DFS) 깊이 우선 탐색(DFS)DFS(Depth First Search)는 그래프(Graph)나 트리(Tree)에서 사용되는 탐색 알고리즘입니다. DFS의 동작 원리시작 노드를 방문합니다. (시작 노드 방문)방문하지 않은 노드가 있으면 해당 노드로 이동합니다. (인접 노드 탐색)더 이상 방문할 노드가 없을 때까지 탐색을 반복합니다. (반복)더 이상 방문할 노드가 없으면 이전 노드로 돌아갑니다. (백트래킹)모든 노드를 탐색할 때까지 반복합니다 (모든 노드 탐색) DFS 구현 방법 위와 같이 노드가 있다 가정하겠습니다. import java.util.*;public class DFS { // 그래프를 인접 리스트로 표현 static class Graph { private int V; // 노.. 2024. 11. 9. 힙 정렬(Heap Sort) 힙 정렬(Heap Sort) 알고리즘을 공부하면서 정렬 알고리즘을 정리하고자 합니다. 이에 네 번째로 정리할 정렬 알고리즘은 힙 정렬입니다. 힙 정렬이란?힙 정렬은 완전 이진 트리 구조를 기반으로 한 선택 정렬의 변형입니다. 힙 정렬은 힙 자료구조를 사용하여 정렬을 수행합니다. 동작 원리힙 생성(Build Heap)배열을 최대 힙 또는 최소 힙의 형태로 변환합니다.최대 힙 : 부모 노드의 값이 자식 노드의 값보다 항상 크거나 같음최소 힙 : 부모 노드의 값이 자식 노드의 값보다 항상 작거나 같음정렬 과정힙의 루트 노드(최대 힙의 경우 가장 큰 값)를 배열의 끝으로 이동시킵니다.힙의 크기를 줄이고 다시 힙 소것ㅇ을 유지하도록 조정합니다.이 과정을 반복하여 정렬된 배열을 만듭니다.예시힙 만들기힙새로 추가된.. 2024. 11. 7. 삽입 정렬(Insertion Sort) 삽입 정렬(Insertion Sort) 알고리즘을 공부하면서 정렬 알고리즘을 정리하고자 합니다. 이에 세 번째로 정리할 정렬 알고리즘은 삽입 정렬입니다. 삽입 정렬이란?삽입 정렬은 배열을 순차적으로 탐색하면서 각 원소를 그 이전의 부분 배열에 적절한 위치에 삽입하여 정렬하는 알고리즘입니다. 동작 원리배열의 두 번째 원소부터 시작해서 첫 번째 원소와 비교한 후 적절한 위치에 삽입합니다.그 다음 원소를 비교하여 이미 정렬된 부분 배열의 적절한 위치에 삽입합니다.이 과정을 배열의 끝까지 반복합니다.예시[31, 25, 12, 22, 11] 이 처음 상태인 배열입니다. [31, 25, 12, 22, 11] 두 번째 원소를 부분 리스트에서 적절한 위치에 삽입합니다. [, 31, 12, 22, 11] 세 번째 원소.. 2024. 11. 6. 선택 정렬(Selection Sort) 선택 정렬(Selection Sort) 알고리즘을 공부하면서 정렬 알고리즘을 정리하고자 합니다. 이에 두 번째로 정리할 정렬 알고리즘은 선택 정렬입니다. 선택 정렬이란?선택 정렬은 배열을 순차적으로 탐색하면서 최소값 찾아 맨 앞에 위치한 값과 교체하는 방식입니다. 동작 원리배열의 첫 번째 원소부터 시작하여 나머지 원소들 중에 가장 작은 원소를 찾아 첫 번째 원소와 교환합니다.두 번째 원소부터는 이미 정렬된 부분을 제외한 나머지 배열을 탐색하여 가장 작은 값을 찾아 두 번째 원소와 교환합니다.이 과정을 배열 끝까지 반복하면서 정렬이 완료됩니다.예시패스테이블최솟값0[9, 1, 6, 8, 4, 3, 2, 0]01[0, 1, 6, 8, 4, 3, 2, 9]12[0, 1, 6, 8, 4, 3, 2, 9]23[0.. 2024. 11. 5. 버블 정렬(Bubble Sort) 버블 정렬(Bubble Sort) 알고리즘을 공부하면서 정렬 알고리즘을 정리하고자 합니다. 이에 첫 번째로 정리할 정렬 알고리즘은 버블 정렬입니다. 버블 정렬이란?버블 정렬은 인접한 두 원소를 비교하여 크기 순서대로 정렬하는 알고리즘입니다. 동작 원리배열을 처음부터 끝까지 순차적으로 비교합니다.두 원소를 비교하여 만약 순서가 잘못되었다면 두 원소를 교환합니다.이 과정은 배열 끝까지 진행되고 한 번의 패스가 끝나면 가장 큰 값이 맨 뒤로 이동합니다.반복적으로 비교하면서 각 패스를 통해 진행됩니다.예시[7, 2, 0, 1, 5, 6, 4] 와 같이 정렬되지 않은 배열이 있다고 가정합니다. 알고리즘은 배열의 첫 두 숫자 (7, 2)를 비교합니다. 여기서 7 > 2로 정렬되지 않았으므로 두 수의 자리를 바꿉.. 2024. 11. 4. 그리디 알고리즘(Greedy Algorithm) 서론 그리디란 무엇이고 어떻게 적용하는지 간단히 정리하고자 합니다. 출처 : 나무위키 그리디 그리디 알고리즘그리디 알고리즘 (욕심쟁이 알고리즘, Greedy Algorithm)이란 "매 선택에서 지금 이 순간 당장 최적인namu.wiki 코딩 테스트를 준비하면서 예전에 공부했던 그리디 알고리즘을 정리하면서 공부하고자 합니다. 1. 그리디 알고리즘이란?그리디 알고리즘(욕심쟁이 알고리즘, Greedy Algorithm)이란 "매 선택에서 지금 이 순간 당장 최적인 답을 선택하여 적합한 결과를 도출하자"라는 모토를 가지는 알고리즘 설계 기법이다.출처 : 나무위키 그리디 알고리즘은 문제를 해결할 때 현재 단계에서 최선이라 생각되는 선택을 반복적으로 수행하여 최적의 해답에 도달하는 알고리즘입니다. 매 단계.. 2024. 11. 3. 약수 구하는 방법 서론 코딩 테스트를 준비하면서 여러 문제를 풀어보고 있는데 약수를 구하는 문제가 자주나와서 정리하고자 합니다. 약수란?수론에서 약수(約數 : divisor) 또는 인수(因數 : factor, 전 용어: 승자(乘子))는 어떤 수를 나누어떨어지게 하는 수를 말한다. 출처 : 위키백과 약수 - 위키백과, 우리 모두의 백과사전위키백과, 우리 모두의 백과사전. 수론에서 약수(約數, 영어: divisor) 또는 인수(因數, 영어: factor, 전 용어: 승자(乘子))는 어떤 수를 나누어떨어지게 하는 수를 말한다. 다항식의 약수나 가환환의ko.wikipedia.org 간단하게 설명하면 주어진 수 n보다 작으면서 n을 나눌 때 0으로 나누어 떨어지는 수를 말합니다. 예시로 12의 약수는 1, 2, 3, 4, 6,.. 2024. 11. 2. 프로그래머스 LV 0 정복 서론프로그래머스LV0 코딩테스트 연습 | 프로그래머스 스쿨개발자 취업의 필수 관문 코딩테스트를 철저하게 연습하고 대비할 수 있는 문제를 총망라! 프로그래머스에서 선발한 문제로 유형을 파악하고 실력을 업그레이드해 보세요!school.programmers.co.kr 올해 8월에 졸업하면서 자격증 취득과 프로젝트를 진행했고 현재 취업을 준비 중에 있습니다. 많은 회사들이 코딩 테스트를 치르면서 실력있는 개발자를 고르고 있습니다. 이에 회사 취업을 위해 코딩 테스트를 준비했습니다. 현재 실력으로 매우 쉽지만 기초를 튼튼하게 만들기 위해서 LV 0 부터 차근히 쌓기 위해서 문제를 도전했습니다. 결과LV 0 문제를 대부분 풀었습니다. 100문제가 넘게 풀었고 이제 다음 단계인 레벨 1을 풀고자 합니다. 2024. 11. 1. 이전 1 2 3 4 5 6 ··· 18 다음
