BOJ 11067 모노톤길 [Java]

BOJ 11067 모노톤길 1. 문제 링크 https://www.acmicpc.net/problem/11067 2. 문제 해설 문제에서 설명한 모노톤길의 정의에 의해 x 좌표 방향으로는 무조건 증가한다. 다만, y 좌표의 경우에는 길의 모양에 따라 증가할 수도 있고 감소할 수도 있다. 그렇기 때문에, y축 방향으로 어떻게 정렬을 해주는 지가 이 문제의 핵심이다. 문제 풀이의 흐름을 아래에서 설명하겠다. 1. 일단 입력 받은 좌표들을 x 좌표 오름차순으로 정렬하고, x 좌표가 같다면 y 좌표 오름차순으로 정렬한다. 2. 현재 정렬된 좌표 순서에 따라 모노톤길을 처음부터 따라간다고 생각해보자. 6번 (3, 3) 좌표에서 7번 좌표를 갈 때 (5, 3)으로 가는 것을 기대하지만, 현재 정렬된 순서에 따르면 (..

→2022.09.13

기본 정렬(선택 정렬, 버블 정렬, 삽입 정렬)

목차 선택 정렬(Selection sort) 1-1. 선택 정렬이란? 1-2. 선택 정렬 구현 버블 정렬(Bubble sort) 2-1. 버블 정렬이란? 2-2. 버블 정렬 구현 삽입 정렬(Insertion sort) 3-1. 삽입 정렬이란? 3-2. 삽입 정렬 구현 시간복잡도 비교 1. 선택 정렬(Selection sort) 1-1. 선택 정렬이란? 자리가 정해져 있는 정렬 알고리즘이다. 주어진 배열이나 리스트에서 최솟값을 찾고 그 값을 맨 앞의 값과 위치를 바꾼다. 같은 방법으로 나머지 값들을 정렬한다. 아래에 8, 5, 1, 3, 6이 담겨 있는 배열을 선택 정렬로 정렬해보자. 우선, 제일 앞에 있는 8의 위치를 i라고 하고, j는 i다음 위치부터 존재하는 최솟값의 위치를 가져온다. 그리고 그 위치..

→2021.07.10