모눈종이에 사각사각

정렬은 데이터를 특정한 기준에 따라 순서대로 나열하는 것이다. 정렬의 종류에는 여러 가지가 있는데, 그중에서 선택정렬, 삽입정렬, 퀵정렬, 계수정렬에 대해 알아볼 것이다. 정렬을 하면 이진 탐색이 가능해지기 때문에 잘 알아두면 도움이 많이 될 것 같다. 우선 정렬의 종류를 알아보기 전에 정렬 알고리즘의 두 가지 성질을 먼저 알아볼 것이다. 🍁 정렬 알고리즘의 두 가지 성질 1. stable vs unstable - 같은 숫지면 입력된 순서가 정렬 후에도 그대로 유지되도록 하는 게 더 바람직하다! -> stable하다! 2. in-place vs not in-place - 정렬을 하면서 추가로 사용하는 메모리의 양 - in-place는 기존 리스트에서 정렬을 하는 것이고, not in-place는 리스트를..

코딩 테스트에서 많이 출제되는 알고리즘 중 하나인 DFS와 BFS에 대해 알아보고자 한다. 계속 공부하지만 문제를 풀 때마다 헷갈리기에, 이번 포스팅을 계기로 확실하게 개념을 익히는 것이 목표이다. 🍀 DFS(Depth-First Search, 깊이 우선 탐색) DFS는 그래프에서 깊은 부분을 우선적으로 탐색하는 알고리즘이다. 특정한 경로를 탐색하다가 특정한 상황에서 최대한 깊숙이 들어가서 노드를 방문한 후, 다시 돌아가 다른 경로를 탐색한다. [스택 자료구조를 이용한 DFS 동작 과정] 탐색 시작 노드를 스택에 삽입 -> 방문 처리 스택의 최상단 노드에 방문하지 않은 인접 노드가 있으면 그 인접 노드를 스택에 넣고 방문 처리 -> 방문하지 않은 인접 노드가 없으면 스택에서 최상단 노드를 꺼냄 2번의 과..

이번 포스팅에서는 그리디 알고리즘에 대해 알아보고자 한다. 그리디 알고리즘은 현재 상황에서 지금 당장 좋은 것만 고르는 방법이다. 매 순간 가장 좋아보이는 것을 선택하며, 현재의 선택이 나중에 미칠 영향은 고려하지 않는다. 따라서 그리디 해법은 그 정당성 분석이 중요하다. 단순히 가장 좋아 보이는 것을 반복적으로 선택해도 최적의 해를 구할 수 있는지 검토해야 한다. 🍀 거스름 돈 문제 거스름 돈으로 사용할 돈은 500원, 100원, 50원, 10원짜리 동전이 무한히 존재한다. 손님에게 거슬러 줘야 할 돈이 N원일 때, 거슬러 줘야 할 동전의 최소 개수를 구하라. 단, 거슬러 줘야 할 돈 N은 항상 10의 배수이다. -> 그리디 알고리즘을 활용해 풀 수 있는 대표적인 문제 🍀 정당성 분석 그리디 알고리즘을..