삽입 정렬 알고리즘 삽입 정렬은 안정 정렬(중복된 값이 입력 순서 혹은 정렬 전 순서와 동일하게 정렬)에 속하며, 다른 원소와의 비교만으로 정렬을 수행하는 비교 정렬입니다. 알고리즘을 알아보기 전 대략적인 개념을 잡아보겠습니다. 퀵 정렬에서는 '이미 정렬된 배열' 이라는 개념을 사용하여 정렬을 수행합니다. 이미 정렬된 배열에 원소 하나를 삽입하는 것은 배열의 마지막 혹은 처음부터 순차적으로 탐색하여 알고리즘은 대략 다음과 같이 이루어집니다. 배열을 두 부분으로 나눕니다. 왼쪽 배열은 '정렬된 배열', 오른쪽 배열은 '정렬되지 않은 배열'입니다 최초 상태에서 정렬된 배열의 길이는 1입니다. '정렬되지 않은 배열'의 최좌측 원소를 선택하여 '정렬된 배열'에 삽입될 위치를 찾아 삽입합니다. 해당 과정에서 순..
Algorithm
참고 - 후위 표기식 만들기 https://ttl-blog.tistory.com/629 [알고리즘] 후위 표기법 만들기 (Infix를 Postfix로 바꾸기) 수식의 표기법 Infix (중위 표기법) Infix 표기법은 연산자가 연산값 사이에 들어 있으며, 연산의 순서를 지정하기 위해 괄호가 필요합니다 예시 : 3 * (7 - 5) Prefix (전위 표기법) Prefix 표기법은 연산 ttl-blog.tistory.com 후위 표기식을 계산하는 알고리즘은 매우 간단합니다. 후위 표기식 계산법 후위 표기식의 계산에는 스택을 사용하는 것이 쉽고 효율적입니다. 과정은 다음과 같습니다. 연산자가 나타날 때까지 스택에 연산값(피연산자)을 삽입합니다. 연산자가 나타나면 다음 과정을 진행합니다. 스택에서 연산자에 ..
수식의 표기법 Infix (중위 표기법) Infix 표기법은 연산자가 연산값 사이에 들어 있으며, 연산의 순서를 지정하기 위해 괄호가 필요합니다 예시 : 3 * (7 - 5) Prefix (전위 표기법) Prefix 표기법은 연산자가 연산값 앞에 등장하며 괄호가 불필요합니다 예시 : * 3 - 7 5 Postfix (후위 표기법) Postfix 표기법은 연산자가 연산값 뒤에 등장하며 괄호가 불필요합니다. 또한 이는 컴파일러가 수식을 계산하는데 사용하는 표기법입니다. 예시 : 3 7 5 - * Infix를 Postfix로 바꾸기 사람은 대부분 Infix 방식의 표기법이 익숙하고 편할 것입니다. 그러나 컴퓨터는 Postfix 방식의 표기법을 쉽게 이해하고 계산할 수 있기에, 컴퓨터에게 계산을 맡길 때에는 P..
퀵 정렬은 분할 정복 알고리즘(Divide and Conquer)의 하나이면서, 매우 중요하게 다뤄지는 정렬 방법입니다. 퀵 정렬 알고리즘 퀵 정렬은 불안정 정렬(중복된 값이 입력 순서 혹은 정렬 전 순서와 동일하게 정렬되지 않음)에 속하며, 다른 원소와의 비교만으로 정렬을 수행하는 비교 정렬입니다. 알고리즘은 대략 다음과 같이 이루어집니다. 리스트 안에 있는 하나의 요소를 선택합니다. 해당 요소는 Pivot 이라 부릅니다. (아무 원소나 선택해도 됩니다.) Pivot을 기준으로 Pivot보다 작은 원소는 모두 Pivot의 왼쪽으로, 큰 원소들은 모두 Pivot의 오른쪽으로 옮깁니다.(Divide) Pivot을 제외한 왼쪽과 오른쪽 부분의 리스트에 대해 다시 1,2 의 과정을 반복합니다. (Conquer..
분할 정복 알고리즘(Divide and Conquer) 분할 정복 알고리즘은 그대로 해결할 수 없는 문제를 작은 문제로 분할하여 문제를 해결하는 알고리즘을 의미합니다. 분할 정복 알고리즘은 다음 세 단계로 설계됩니다. Divide : 문제가 분할이 가능한 경우에, 2개 이상의 문제로 나누는 방법을 의미합니다. Conquer : 나누어진 두개의 문제를, 각각 다시 새로운 하나의 문제로 보고, 이 또한 Divide가 가능하다면, Divide를 수행합니다. 그렇지 않으면 문제를 해결합니다. Combine : Conquer 한 문제들을 통합하여, 기존 문제의 답을 얻어냅니다. 분할 정복 알고리즘은 보통 재귀함수를 통해 구현되며 재귀호출이 아닌 스택, 큐 등의 자료구조를 이용하여 구현할 수도 있습니다. 재귀함수는..
알고리즘은 컴퓨터에게 편한 관점이 아닌 사람에게 유용한 관점에서, 원하는 일을 처리하는 방법을 표현한 것을 의미합니다. 알고리즘을 결국은 프로그램으로 구현하여야 컴퓨터가 처리할 수 있기에 알고리즘과 프로그램은 서로 불가분의 관계에 있다고 볼 수 있습니다. 알고리즘 어떠한 문제를 해결하기 위한 여러 명령어들의 유한집합입니다. 언젠가는 끝나야 하는 속성을 지닙니다. 알고리즘의 조건 알고리즘은 다음 조건을들 만족해야 합니다. 입력 (Input) : 일방적으로 외부에서 주어지며, 0개 이상이어야 합니다. 출력 (Output) : 결과가 한 개 이상 있어야 합니다. 명확성 (Definiteness) : 명령은 명확하고 모호하지 않아야 하며, 결과를 예측 가능해야 합니다. 유한성 (Finiteness) : 명령을 ..
평범한 배낭 https://www.acmicpc.net/problem/12865 12865번: 평범한 배낭 첫 줄에 물품의 수 N(1 ≤ N ≤ 100)과 준서가 버틸 수 있는 무게 K(1 ≤ K ≤ 100,000)가 주어진다. 두 번째 줄부터 N개의 줄에 거쳐 각 물건의 무게 W(1 ≤ W ≤ 100,000)와 해당 물건의 가치 V(0 ≤ V ≤ 1,000) www.acmicpc.net 풀이 import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.ArrayList; import java.util.Arrays; import java.util.Comparator; i..
가장 긴 바이토닉 부분 수열 https://www.acmicpc.net/problem/11054 11054번: 가장 긴 바이토닉 부분 수열 첫째 줄에 수열 A의 크기 N이 주어지고, 둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ N ≤ 1,000, 1 ≤ Ai ≤ 1,000) www.acmicpc.net 풀이 import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.ArrayList; import java.util.Arrays; import java.util.List; /** * Created by ShinD on 2022-02-26. */ publi..
