정렬 알고리즘 리스트의 값을 오름차순으로 재배치 하는 것으로, 다음과 같다. 이 때, 정렬 알고리즘은 두 가지 기준에 따라 Stable Sort, in-place Sort로 나뉘어진다.
선택 정렬은 현재 인덱스에 들어갈 값을 선택하여 정렬하는 알고리즘이다. 추가 메모리를 사용하지 않기 때문에 In-place 정렬이지만, 동일한 값들의 순서가 변할 수 있기 때문에 Unstable 정렬이다.
버블 정렬은 코드가 반복하면서 배열의 원소가 뒷쪽으로 밀려나는 모습이 마치 거품이 떠오르는 모습과 같다고 하여 붙여진 이름이다. Stable Sort이면서 In-place Sort인 버블 정렬은 다른 정렬에 비해 속도가 느리지만, 구현이 간단하여 자주 사용되곤 한다.
버블 정렬의 비효율성을 개선하기 위해 등장한 삽입 정렬은 정렬되지 않은 값을 정렬된 값들과 비교하여, 알맞은 자리에 삽입해주는 정렬이다.Stable 정렬이면서 In-place 정렬이며, 버블 정렬의 비교 및 교환 횟수를 줄임으로써 높은 효율을 보여준다.(N-1) + (
병합 정렬은 분할 정복 기법과 재귀 알고리즘을 활용한 정렬 알고리즘이다주어진 배열의 원소가 하나 밖에 남지 않을 때까지 분할하고, 이를 재배열하면서 원래 크기의 배열로 합병한다. Stable 정렬이지만, 작은 단위로 쪼갠 배열을 저장할 추가 공간을 사용하기 때문에 No
퀵 정렬은 다른 정렬 알고리즘에 비해 아주 준수한 수행 시간을 보이기 때문에 가장 많이 사용하는 정렬 알고리즘 중 하나이다. 병합 정렬과 마찬가지로 분할 정복과 재귀 알고리즘을 이용한다.unstable 하며 알고리즘이 호출될 때마다 새로운 리스트를 생성하며 리턴하기 때
📝 문제 https://www.acmicpc.net/problem/23881 아이디어 문제의 제목에서도 확인할 수 있듯이 선택 정렬을 활용하여 해답을 구하는 문제이다. 풀이 방법 💬 접근법 교환 횟수를 체크할 count 변수와 최종적으로 출력될 값 answer
https://www.acmicpc.net/problem/23968버블 정렬의 기본적인 개념을 이용한다.먼저, 원소가 교환되는 과정을 살펴보기 위해 교환 횟수를 의미하는 변수 cnt를 선언하고, 정답으로 출력된 answer를 선언한다.다음으로 배열의 원소 개수
📝 문제 https://www.acmicpc.net/problem/2583 💬 풀이 방법 알고리
https://www.acmicpc.net/problem/2178그래프의 탐색을 활용하는 문제다. 깊이 우선 탐색(DFS)는 경로가 여러개 존재할 경우 모든 경로를 완전 탐색하고 그 중에서 최솟값을 찾는다. 따라서 시간이 굉장히 오래 걸리는 데에 비해 너비 우
https://www.acmicpc.net/problem/15312아스키 코드를 활용하여 입력 받은 알파벳의 획수를 알아낸다. 이후 while 반복문 내에서 남은 숫자가 2가 될 때까지 인접한 수를 더해주는 간단한 문제다. 첫 시도에는 데이터의 자료형을 반복적
현재 상황에서 지금 당장 좋은 것만 고르는 방법으로, 매 순간 가장 좋아 보이는 것을 선택한다. 이 때, 현재의 선택이 나중에 미칠 영향에 대해서는 고려하지 않는다.그리디 알고리즘은 기준에 따라 좋은 것을 선택하는 알고리즘이기 때문에 문제에서 '가장 큰 순서대로', '
📌 구현 코딩 테스트에서 구현은 머릿속에 있는 알고리즘을 소스코드로 바꾸는 과정을 의미한다. 일반적으로 구현 유형의 문제는 풀이를 떠올리는 것은 쉽지만 소스코드로 옮기기 어려운 경우가 많다. 이것이 취업을 위한 코딩테스트다에서는 완전 탐색과 시뮬레이션을 모두 구현
📌 정렬 알고리즘 이것이 취업을 위한 코딩테스트다에서 제공한 문제를 풀어보았다. 대부분의 프로그래밍 언어에서 제공하는 정렬 라이브러리는 가장 효율적이게 구현되어 있다. 파이썬의 정렬 라이브러리는 병합 정렬에 삽입 정렬의 아이디어를 더한 하이브리드 방식의 알고리즘을
https://www.acmicpc.net/problem/5698입력 받은 문자열을 띄어쓰기 단위로 나눠서 앞자리를 비교한다.입력 받은 값에 순회를 돌며 하나씩 처리한다. 이 때, 입력 값이 \*이라면 종료한다.문자열을 띄어쓰기 단위로 나누고 각 단어 앞자리를
https://www.acmicpc.net/problem/3049대각선의 개수, 교차점으로 만들어지는 도형 등 별별 규칙을 다 찾아봤는데 알고 보니 조합이었다. 하..굉장히 허무하지만 암튼 풀었다..$${}nC{4}$$처음엔 이렇게 작성했는데, 다른 분이 제출
https://www.acmicpc.net/problem/2548처음엔 브루트포스 알고리즘을 이용해 단순히 하나씩 값을 찾아보는 방법으로 문제를 해결했다. 하지만 2,404ms 만큼의 시간을 소모했기 때문에 더 좋은 방법이 없을까 고민했다.고민해본 결과 이 문
https://www.acmicpc.net/problem/1912dynamic programming을 활용하는 문제. 배열에 순회를 돌며 값을 합산한다. 이 때 배열의 현재 값과 현재 값 + 합산한 값 중 더 큰 수를 dp 배열에 저장한다.
https://www.acmicpc.net/problem/1890DFS와 DP를 함께 활용해야 시간 초과 오류가 발생하지 않는다.x, y 좌표 0, 0부터 시작하여 각 지점에서 목적지까지 도달할 수 있는 경로의 수를 dp 배열에 저장한다.탐색 알고리즘의 흐름은
https://www.acmicpc.net/problem/1759백트래킹과 정규식을 활용한 방법먼저, 입력 받은 문자열을 오름차순으로 정렬한 뒤 순회를 돌린다. pw 문자열에 차례로 문자를 추가하고 idx를 1씩 올리면서 search 함수를 재귀 호출 한다.
https://www.acmicpc.net/problem/1012먼저 tc와 m, n, k를 뽑아낸 뒤 문제를 해결하기 위해 배추밭field 세팅을 한다.이제 배추밭 격자에 대해 순회를 돌며 배추가 있는 칸, 즉 field\[y]\[x] === 1인 곳에서 s
📖 문제 https://www.acmicpc.net/problem/1149 ☃️ 풀이 한참을 고민하던 문제. 질문 게시판에 올려진 글들을 보고 힌트를 얻었다.거의 답을 확인한 수준이지만.. 각 단계마다 RGB 색상으로 집을 색칠하는 비용이 각각 주어지고, 해당 비
📖 문제 https://www.acmicpc.net/problem/7576 ☃️ 풀이 고민에 고민에 고민을 거듭한 문제. 계속해서 시간 초과가 발생하여 애를 좀 먹었다. 일단 bfs를 활용하는 문제라는 건 확실히 알고 있었고, 처음 생각한 알고리즘은 다음과 같다.
https://www.acmicpc.net/problem/1541문제를 이해하지 못해서 해설 포스팅을 찾아보다 풀이 방법을 스포당했다.\- 이후에 나오는 수만 전부 더하면 최소값을 유도할 수 있다.가독성을 저하시키는 숏코딩의 문제점을 여실히 보여주는 코드 작성
https://www.acmicpc.net/problem/1406처음엔 명령 하나하나에 대해 문자열을 변형하는 식으로 일일이 처리했다. 그랬더니 시간초과가 발생했다.그래서 초기 문자열을 문자 단위 배열left로 나누고, 빈 배열 right을 하나 만들어서 다음
https://www.acmicpc.net/problem/7562처음에는 DFS로 시도 했다가 계속 Maximum Call Stack 에러가 발생했다. 사방이 아닌 팔방을 탐색해야 했기 때문에 재귀를 너무 깊게 탐색하는 것이 원인이라고 판단했다.그래서 BFS로