본문 바로가기

C25

[BOJ 17144] 미세먼지 안녕! https://www.acmicpc.net/problem/17144 17144번: 미세먼지 안녕! 미세먼지를 제거하기 위해 구사과는 공기청정기를 설치하려고 한다. 공기청정기의 성능을 테스트하기 위해 구사과는 집을 크기가 R×C인 격자판으로 나타냈고, 1×1 크기의 칸으로 나눴다. 구사과는 뛰어난 코딩 실력을 이용해 각 칸 (r, c)에 있는 미세먼지의 양을 실시간으로 모니터링하는 시스템을 개발했다. (r, c)는 r행 c열을 의미한다. 공기청정기는 항상 1번 열에 설치되어 있고, 크기는 두 행을 차지한다. 공기청정기가 설치되어 있지 않은 칸에는 미세먼 www.acmicpc.net 위 문제는 1초마다 미세먼지가 상하좌우로 확산되고, 공기청정기에서 바람이 나와서 미세먼지를 청소한다. T초가 지났을 때의 미세.. 2020. 3. 25.
[BOJ 15685] 드래곤 커브 https://www.acmicpc.net/problem/15685 15685번: 드래곤 커브 첫째 줄에 드래곤 커브의 개수 N(1 ≤ N ≤ 20)이 주어진다. 둘째 줄부터 N개의 줄에는 드래곤 커브의 정보가 주어진다. 드래곤 커브의 정보는 네 정수 x, y, d, g로 이루어져 있다. x와 y는 드래곤 커브의 시작 점, d는 시작 방향, g는 세대이다. (0 ≤ x, y ≤ 100, 0 ≤ d ≤ 3, 0 ≤ g ≤ 10) 입력으로 주어지는 드래곤 커브는 격자 밖으로 벗어나지 않는다. 드래곤 커브는 서로 겹칠 수 있다. 방향은 0, 1, 2, www.acmicpc.net [0, 100] 내에서 사각형의 4개의 점이 드래곤 커브의 일부인 사각형의 개수를 찾는 문제이다. 드래곤 커브를 모두 그린 다음에 .. 2020. 3. 25.
[BOJ 14891] 톱니바퀴 https://www.acmicpc.net/problem/14891 14891번: 톱니바퀴 총 8개의 톱니를 가지고 있는 톱니바퀴 4개가 아래 그림과 같이 일렬로 놓여져 있다. 또, 톱니는 N극 또는 S극 중 하나를 나타내고 있다. 톱니바퀴에는 번호가 매겨져 있는데, 가장 왼쪽 톱니바퀴가 1번, 그 오른쪽은 2번, 그 오른쪽은 3번, 가장 오른쪽 톱니바퀴는 4번이다. 이때, 톱니바퀴를 총 K번 회전시키려고 한다. 톱니바퀴의 회전은 한 칸을 기준으로 한다. 회전은 시계 방향과 반시계 방향이 있고, 아래 그림과 같이 회전한다. 톱니바퀴를 회전시키려 www.acmicpc.net 위 문제는 N번 톱니바퀴를 회전한 후, 각 톱니바퀴의 12시 방향의 극에 따라 점수를 계산하는 문제이다. 주어지는 입력은 톱니바퀴의 .. 2020. 3. 25.
[C/C++] 10진법 -> N진법 변환 Theory X진법 수를 X로 나누면 한 자리씩 소수점으로 이동하게 된다. 아래 예제를 보면 알 수 있다. 10진법 123 / 10 = 12.3 12.3 / 10 = 1.23 2진법 1011 / 2 = 101.1 또한 어떤 수를 10진법으로 표기를 하든, 2진법으로 표기를 하든, 16진법으로 표기를 하든 결국 다 표현하는 방식만 다를 뿐, 같은 값을 가진다. 10진법 11이라는 숫자를 2의 배수의 합으로 표현을 해보자. $$ 11 = 1 \cdot 2^3 + 0 \cdot 2^2 + 1 \cdot 2^1 + 1 \cdot 2^0$$ 위와 같이 표현이 되는데, 이 때 11이라는 10진법 수를 2로 나눈 나머지는 구하면 $2^n$ 부분이 각 1씩 떨어지고 가장 작은 부분인 $ 2^0 $부분의 계수가 나오게 .. 2020. 1. 30.
[정렬] 선택 정렬 (Selection Sort) 원소를 넣을 위치를 정해놓고 어떤 원소를 넣을지 찾아서 정렬한다. 오름차순의 경우, 가장 작은 값을 찾아서 왼쪽부터 정렬을 하거나, 가장 큰 값을 찾아 오른쪽부터 정렬을 하는 방식이다. 1. i = ( 1 ~ (n - 1) )인덱스까지 탐색 2. j = ( (i + 1) ~ n ) 인덱스까지 탐색 3. j의 값 중에 가장 작은 값을 찾아 i번째의 값과 위치를 바꾼다. 4. 위 과정 반복 코드 구현 #include void PrintArray(int* arr, int size) { for (int i = 0; i < size; i++) { printf("%d ", arr[i]); } printf("\n"); } void Selection(int* arr, int size) { int min, tmp; fo.. 2020. 1. 20.
[정렬] 삽입 정렬 (Insertion Sort) 두 번째 자료부터 시작하여 앞에 자료들과 비교하여 알맞은 위치에 자료를 넣는 형식의 정렬이다. 비교를 하는 앞의 배열은 이미 정렬이 되어있다. 즉, n번째 자료를 비교할 때 0 ~ (n - 1) 번째 자료는 정렬이 되어있다. 손에 카드를 들고 정렬하는 방식과 유사하다. 1. i = (1 ~ n)인덱스까지 탐색 2. j = ( (i - 1) ~ 0 ) 인덱스까지 탐색 3. j번째 값이 i번째 값보다 크면 j + 1의 값에 j의 값을 할당하고, 크지 않으면 해당 위치에 i번째 값을 삽입 4. 위 과정 반복 코드 구현 #include void PrintArray(int* arr, int size) { for (int i = 0; i < size; i++) { printf("%d ", arr[i]); } pri.. 2020. 1. 20.
[정렬] 버블 정렬 (Bubble Sort) 소개 서로 인접한 두 원소를 검사하여 정렬하는 알고리즘이다. 다른 정렬 알고리즘에 비해 느린 편이지만, 코드가 간단하다. 정렬 과정 첫 번째 탐색 1. 5와 3을 비교 2. 앞에 있는 5가 더 크므로 5와 3의 위치를 바꾼다. 3. 5와 1을 비교 4. 앞에 있는 5가 더 크므로 5와 1의 위치를 바꾼다. 5. 5와 9를 비교 6. 뒤에 있는 9가 더 크므로 위치를 변경하지 않는다. 7. 9와 7을 비교 8. 앞에 있는 9가 더 크므로 9와 7의 위치를 바꾼다. 9. 첫 번째 순회가 끝난 배열 첫 번째 탐색의 과정을 보면 가장 큰 수가 맨 뒤로 이동하게 된다. 즉, 매 순회마다 정렬된 수를 제외한 가장 큰 수가 맨 뒤로 가 뒤에서부터 정렬이 된다. 그러므로 맨 순회마다 배열의 전체를 탐색할 필요 없이 정.. 2019. 11. 21.

티스토리툴바