🪨 🪨 🪨

선택 정렬은 정렬되지 않은 영역에서 최솟값을 선택한 뒤, 정렬되지 않은 영역의 첫번째 요소와 바꾸고 고정시키는 과정을 반복하는 정렬 방식이다. 물론 최댓값을 이용한 정렬도 가능하다. 시간 복잡도는 버블 정렬과 마찬가지로 O(n**2)이다. 아래의 배열에 대한 오름차순 선택 정렬을 실시해보자. 먼저, 전체 구간에서 가장 작은 요소를 선택한다. 1이 선택될 것이다. 이렇게 선택된 1을 가장 왼쪽에 위치한 2와 서로 맞바꾼 뒤, 고정시킨다. 다시 정렬되지 않은 영역에서 가장 작은 요소를 선택한다. 1은 이미 고정되었으므로 2가 최솟값이다. 순서가 고정 되지 않은 배열의 제일 왼쪽에 위치한 요소와 서로 자리를 바꾸어준다. 2 역시 앞으로 위치를 바꾸지 않을 것이다. 위치가 고정된 것이다. 같은 과정을 계속 반복..

버블 정렬은 배열 내 인접한 두 요소를 비교하는 과정을 반복하여 제일 큰 요소를 맨 끝으로 이동시키는 정렬 방식이다. 시간복잡도는 O(N**2)로 효율적인 정렬 방식은 아니다. 아래의 배열을 버블 정렬을 이용해 오름차순으로 나타내보자. 지금부터 인덱스는 i로 표현하겠다. 먼저, i = 0과 i = 1의 요소를 비교한다. 더 큰 수가 왼쪽에 있으므로 서로 위치를 바꿔준다. i = 1과 i = 2를 비교한다. 더 큰 수가 오른쪽에 있으므로 다음으로 넘어간다. i = 2와 i = 3을 비교한다. 더 큰 수가 왼쪽에 있으므로 서로 위치를 바꿔준다. i = 3과 i = 4를 비교한다. 마찬가지로 더 큰 수가 왼쪽에 있으므로 서로 위치를 바꿔준다. (len(array) - 1) 번의 시행을 통해 가장 큰 요소인 5..

https://www.acmicpc.net/problem/1919 1919번: 애너그램 만들기 두 영어 단어가 철자의 순서를 뒤바꾸어 같아질 수 있을 때, 그러한 두 단어를 서로 애너그램 관계에 있다고 한다. 예를 들면 occurs 라는 영어 단어와 succor 는 서로 애너그램 관계에 있는데, occurs www.acmicpc.net 각각의 단어 포함된 알파벳의 종류와 개수를 카운팅한 뒤, 그 차이를 이용하면 답을 구할 수 있다. #1: key값이 알파벳 소문자이고, value값이 0인 dictionary를 만들었다. #2: 첫번째 단어를 input 받고, 그 단어에서 알파벳이 하나 나올 때마다 해당 알파벳에 대한 dictionary value값이 1씩 증가하도록 했다. #3: 두번째 단어를 input..

https://www.acmicpc.net/problem/2292 2292번: 벌집 위의 그림과 같이 육각형으로 이루어진 벌집이 있다. 그림에서 보는 바와 같이 중앙의 방 1부터 시작해서 이웃하는 방에 돌아가면서 1씩 증가하는 번호를 주소로 매길 수 있다. 숫자 N이 주어졌 www.acmicpc.net 주어진 숫자가 벌집의 중앙(1)에서부터 몇 번째 줄에 나타나는 지를 찾아야 하는 문제이다. 수학문제이기 때문에 규칙 부터 찾아보았다. 숫자(N) 답 규칙(마지막 수와 관련된) 1 1 1 + 6 * 0 2 ~ 7 2 1 + 6 * 0 + 6 * 1 8 ~ 19 3 1 + 6 * 0 + 6 * 1 20 ~ 37 4 1 + 6 * 0 + 6 * 1 + 6 * 2 38 ~ 61 5 1 + 6 * 0 + 6 * 1..

https://www.acmicpc.net/problem/2563 2563번: 색종이 가로, 세로의 크기가 각각 100인 정사각형 모양의 흰색 도화지가 있다. 이 도화지 위에 가로, 세로의 크기가 각각 10인 정사각형 모양의 검은색 색종이를 색종이의 변과 도화지의 변이 평행하도록 www.acmicpc.net 처음에는 수학 문제로 접근해서 색종이의 면적을 다 더한 뒤, 겹치는 부분의 면적을 체크해서 빼려고 했다. 하지만 색종이 3개 이상이 동시에 겹치거나 할 때, 모든 경우를 확인하기가 어려워서 그냥 2차원 배열 노가다로 풀었다. #1 : 100 * 100의 2차원 array를 만들었다. > array 내의 요소들은 각각 도화지를 1/100으로 나눈 한 칸을 의미한다. #2 : 각각의 색종이가 차지하는 부..