Lavine's Dev Site

Problem https://www.acmicpc.net/problem/14499 14499번: 주사위 굴리기 첫째 줄에 지도의 세로 크기 N, 가로 크기 M (1 ≤ N, M ≤ 20), 주사위를 놓은 곳의 좌표 x, y(0 ≤ x ≤ N-1, 0 ≤ y ≤ M-1), 그리고 명령의 개수 K (1 ≤ K ≤ 1,000)가 주어진다. 둘째 줄부터 N개의 줄에 지 www.acmicpc.net 크기가 N×M인 지도가 존재한다. 지도의 오른쪽은 동쪽, 위쪽은 북쪽이다. 이 지도의 위에 주사위가 하나 놓여져 있으며, 주사위의 전개도는 아래와 같다. 지도의 좌표는 (r, c)로 나타내며, r는 북쪽으로부터 떨어진 칸의 개수, c는 서쪽으로부터 떨어진 칸의 개수이다. 2 4 1 3 5 6 주사위는 지도 위에 윗 면..

Problem https://www.acmicpc.net/problem/2178 2178번: 미로 탐색 첫째 줄에 두 정수 N, M(2 ≤ N, M ≤ 100)이 주어진다. 다음 N개의 줄에는 M개의 정수로 미로가 주어진다. 각각의 수들은 붙어서 입력으로 주어진다. www.acmicpc.net N×M크기의 배열로 표현되는 미로가 있다. 1 0 1 1 1 1 1 0 1 0 1 0 1 0 1 0 1 1 1 1 1 0 1 1 미로에서 1은 이동할 수 있는 칸을 나타내고, 0은 이동할 수 없는 칸을 나타낸다. 이러한 미로가 주어졌을 때, (1, 1)에서 출발하여 (N, M)의 위치로 이동할 때 지나야 하는 최소의 칸 수를 구하는 프로그램을 작성하시오. 한 칸에서 다른 칸으로 이동할 때, 서로 인접한 칸으로만 이..

Problem https://www.acmicpc.net/problem/2589 2589번: 보물섬 보물섬 지도를 발견한 후크 선장은 보물을 찾아나섰다. 보물섬 지도는 아래 그림과 같이 직사각형 모양이며 여러 칸으로 나뉘어져 있다. 각 칸은 육지(L)나 바다(W)로 표시되어 있다. 이 지도에서 www.acmicpc.net 보물섬 지도를 발견한 후크 선장은 보물을 찾아나섰다. 보물섬 지도는 아래 그림과 같이 직사각형 모양이며 여러 칸으로 나뉘어져 있다. 각 칸은 육지(L)나 바다(W)로 표시되어 있다. 이 지도에서 이동은 상하좌우로 이웃한 육지로만 가능하며, 한 칸 이동하는데 한 시간이 걸린다. 보물은 서로 간에 최단 거리로 이동하는데 있어 가장 긴 시간이 걸리는 육지 두 곳에 나뉘어 묻혀있다. 육지를 나..

버블 정렬 (Bubble Sort) 정렬 순서 (오름차순 정렬 기준) 인접한 원소 두 개((arr[0], arr[1]), (arr[1], arr[2]) ~ (arr[n-2], arr[n-1]))를 쌍으로 지어 앞에 위치한 원소가 뒤의 원소보다 크다면 swap한다. 1회전을 끝내게 되면 배열 내의 가장 큰 원소가 가장 마지막에 배치된다. (뒤에서부터 정렬이 완료된다.) 따라서 1~2과정을 정렬되지 않은 원소가 1개가 될때까지 반복한다. 예시 장점 구현이 쉽고 이해하기 쉽다. In-place Sorting Algorithm 주어진 배열 내에서 이루어지기 때문에 공간복잡도 O(n) 안정 정렬 (Stable Sorting) 중복 값이 입력 순서와 동일하게 정렬 됨 단점 O(n2)의 시간복잡도 정렬을 위해 swa..

선택 정렬 (Selection Sort) 정렬 순서 (오름차순 정렬 기준) 주어진 리스트에서 최소 값을 찾는다. 최소 값을 유효 범위 내에서 맨 앞의 값과 swap한다. swap된 위치를 제외 한 나머지 공간이 1개가 될때까지 1 ~ 2를 반복한다. 예시 장점 구현이 쉽고 이해하기 쉽다. In-place Sorting Algorithm 주어진 배열 내에서 이루어지기 때문에 공간복잡도 O(n) 단점 O(n2)의 시간복잡도 불안정 정렬 (Unstable sorting) 중복 값 순서 보장 못함 시간 복잡도 외부 루프: (n-1)번 반복 최솟값 탐색: n-1, n-2, n-3, ... ,2, 1 T(n) = 1 + 2 + ... + (n-2) + (n-1) = n(n-1)/2 ∈ O(n2) Code (C/C+..

정렬 알고리즘(Sorting Algorithm) 정렬 알고리즘이란 n개로 이루어진 배열이 주어져있을 때, 이를 번호순 혹은 사전 순 같이 일정 순서대로 열거를 해주는 알고리즘을 의미한다. 데이터를 정렬하는 이유는 탐색 및 데이터 편집 시 시간을 절약하기 위해서이다. 예를 들어 정렬이 안되어 있는 데이터를 탐색하려면 데이터를 순차적으로 조사해야 하지만 정렬이 되어있을 경우 이진탐색과 같은 알고리즘을 사용하여 탐색시간을 효율적으로 줄일 수 있기 때문이다. 삽입 정렬 (Insertion Sort) 정렬 순서 비교 대상이 되는 원소를 잡고 앞에 있는 원소들과 비교를 한다. 비교대상이 되는 원소가 이전 위치의 원소보다 작다면 swap 마지막 인덱스 원소까지 1~2를 반복한다. 예시 장점 구현이 쉽고 이해하기 쉽다..