전체 글

1517 - 버블 소트https://www.acmicpc.net/problem/1517문제N개의 수로 이뤄진 수열 A[1], A[2], ..., A[N]버블 소트: 서로 인접해 있는 두 수를 바꿔가며 정렬하는 방식ex. 3 2 1 -> 2 3 1 -> 2 1 3 -> 1 2 3입력첫째 줄: N (1 다음 줄: N개의 정수 A[1], A[2], ..., A[N] (0 출력: swap 횟수풀이버블 정렬에서 발생하는 swap 횟수 = 역순 쌍(inverse) 개수 합병 정렬(Merge Sort)배열을 반으로 분할 -> 각 절반을 재귀적으로 정렬 -> 정렬된 두 배열 병합(merge)시간 복잡도: O(N log N) mergeSort(lt, rt)[lt ~ rt] 구간 정렬`lt >= rt`: 원소가 1개 ..

백준 3109 - 빵집https://www.acmicpc.net/problem/3109문제빵집이 있는 곳은 RxC 격자로 표현할 수 있음/ 첫째 열은 근처 빵집의 가스관이고, 마지막 열은 원웅이의 빵집빵집과 가스관 사이에 건물이 있을 수 있고, 건물이 있는 경우 파이프를 놓을 수 없음가스관과 빵집을 연결하는 모든 파이프라인은 첫째 열에서 시작해야 하고, 마지막 열에서 끝나야 함각 칸은 오른쪽, 오른쪽 위 대각선, 오른쪽 아래 다각선으로 연결할 수 있고, 각 칸의 중심끼리 연결가스관과 빵집을 연결하는 파이프라인을 여러 개 설치하는데 이 경로는 겹칠 수 없고, 서로 접할 수 없음 = 각 칸을 지나는 파이프는 하나여야 함입력첫째 줄: R, C (1 다음 R개 줄: 빵집 근처 모습 (`x`: 건물/ `.`: 빈..

17143 - 낚시왕https://www.acmicpc.net/problem/17143문제RxC인 격자판에서 낚시왕이 상어 낚시/ 격자판의 각 칸은 (r, c)로 나타낼 수 있는데 r은 행, c는 열이고 (R, C)는 가장 오른쪽 아래칸에는 상어가 최대 1마리 들어있을 수 있고 상어는 크기와 속도를 가지고 있음낚시왕은 처음에 1번 열의 한 칸 위에 있음1초 동안 순서대로 일어나며, 낚시왕은 가장 오른쪽 열의 오른쪽 칸에 이동하면 이동 멈춤1. 낚시왕 오른쪽으로 한 칸 이동2. 낚시왕이 있는 열에 있는 상어 중 땅과 제일 가까운 상어 잡음/ 상어 잡으면 격자판에서 사라짐3. 상어 이동상어는 입력으로 주어진 속도로 이동하고, 속도의 단위는 칸/초상어가 이동하려고 하는 칸이 격자판의 경계를 넘는 경우 방향을 ..

16946 - 벽 부수고 이동하기 4https://www.acmicpc.net/problem/16946문제NxM의 행렬로 표현되는 맵에서 0은 이동할 수 있는 곳, 1은 이동할 수 없는 벽이 있는 곳을 나타냄한 칸에서 다른 칸으로 이동하려면, 두 칸이 인접해야 하고 두 칸이 변을 공유할 때 인접하다고 함- 벽을 부수고 이동할 수 있는 곳으로 변경- 그 위치에서 이동할 수 있는 칸의 개수 셈한 칸에서 이동할 수 있는 칸은 상하좌우로 인접한 칸입력: 첫째 줄에 N, M (1 출력: 맵의 형태로 정답 출력/ 원래 빈 칸인 곳은 0, 벽인 곳은 이동할 수 있는 칸의 개수를 10으로 나눈 나머지풀이벽마다 BFS -> 시간 초과 => 0 영역을 미리 그룹화`int[][] group`: 각 칸이 속한 그룹 번호`in..

2342 - Dance Dance Revolutionhttps://www.acmicpc.net/problem/2342문제DDR은 그림과 같은 모양의 발판이 있고, 주어진 스텝에 맞춰 나가는 게임발판은 하나의 중점(0)을 기준으로 위(1), 아래(3), 왼쪽(2), 오른쪽(4)으로 연결되어 있음처음에 게이머는 두 발을 중앙에 모으고 있음(0 위치)게임이 시작되면, 지시에 따라 왼쪽/오른쪽으로 발을 움직이는데 두 발이 동시에 움직임 X/ 두 발이 같은 지점에 있는 것 X ex. 한 발 1, 다른 한 발 3/ 3을 연속으로 눌러야 함 -> 3의 위치에 있는 발로 반복해서 눌러야 함발이 움직이는 위치에 따라 드는 힘이 다름중앙 -> 다른 지점: 2/ 다른 지점 -> 인접한 지점: 3(L -> 위/아래) / 반대..

2146 - 다리 만들기https://www.acmicpc.net/problem/2146 문제한 섬과 다른 섬을 잇는 다리 하나만을 만들기로 하였고, 다리를 가장 짧게 하여 돈을 아끼려고 함NxN 크기의 이차원 평면상에 존재하는 이 나라는 여러 섬으로 이뤄져 있음 섬: 동서남북으로 육지가 붙어있는 덩어리가장 짧은 다리: 다리가 격자에서 차지하는 칸의 수가 가장 작은 다리입력첫 줄: 지도의 크기 N (1 다음 N줄: N개의 숫자 빈칸을 사이에 두고 주어짐 (0: 바다, 1: 육지)출력: 가장 짧은 다리의 길이풀이섬 라벨링현재 `map`에는 0: 바다, 1: 육지 -> 어느 섬에서 시작했는지 알 수 없음=> 각 섬을 서로 다른 번호로 변경`map[i][j] == 1 && !visited[i][j]`: 섬이고..