[백준 / C언어] 2617번: 구슬 찾기 (DFS 풀이)

https://www.acmicpc.net/problem/2617 2617번: 구슬 찾기 모양은 같으나, 무게가 모두 다른 N개의 구슬이 있다. N은 홀수이며, 구슬에는 번호가 1,2,...,N으로 붙어 있다. 이 구슬 중에서 무게가 전체의 중간인 (무게 순서로 (N+1)/2번째) 구슬을 찾기 위해서 www.acmicpc.net 난이도: solved.ac 골드 4 알고리즘 분류 그래프 탐색 (DFS) 접근 방법 및 구현 무게가 중간이 될 수 없는 구슬은 해당 구슬보다 더 가볍거나 무거운 구슬의 개수가 N / 2개보다 많아야 한다. 더 가볍거나 무거운 구슬의 개수는 DFS를 이용해 구할 수 있다. 입력으로 들어오는 구슬의 관계는 2차원 배열을 이용해 방향그래프로 나타내었다. 아래와 같은 입력이 주어진다고 ..

• format_list_bulleted PS/백준
• · 2023. 7. 8.
• textsms

[백준 / C언어] 18870번: 좌표 압축 (구조체 이용)

https://www.acmicpc.net/problem/18870 18870번: 좌표 압축 수직선 위에 N개의 좌표 X1, X2, ..., XN이 있다. 이 좌표에 좌표 압축을 적용하려고 한다. Xi를 좌표 압축한 결과 X'i의 값은 Xi > Xj를 만족하는 서로 다른 좌표 Xj의 개수와 같아야 한다. X1, X2, ..., XN에 www.acmicpc.net 난이도: solved.ac 실버 2 알고리즘 분류 정렬, 값 / 좌표 압축 접근 방법 및 구현 Coord라고 하는 구조체(struct)를 만들어 배열로 만들어주었다. 이 구조체의 원소는 x, loc, compress가 있는데, 각각 입력받은 숫자, 입력받은 순서, 압축된 숫자를 의미한다. 좌표 압축을 하기 위한 순서는 다음과 같다. 1. 값(x)..

• format_list_bulleted PS/백준
• · 2023. 7. 7.
• textsms

[백준 / C언어] 14891번: 톱니바퀴 (삼성 SW 기출)

https://www.acmicpc.net/problem/14891 14891번: 톱니바퀴 총 8개의 톱니를 가지고 있는 톱니바퀴 4개가 아래 그림과 같이 일렬로 놓여져 있다. 또, 톱니는 N극 또는 S극 중 하나를 나타내고 있다. 톱니바퀴에는 번호가 매겨져 있는데, 가장 왼쪽 톱니바퀴 www.acmicpc.net 난이도: solved.ac 골드 5 알고리즘 분류 구현, 시뮬레이션 접근 방법 한 톱니바퀴의 양 옆 톱니바퀴는 반대 방향으로 돈다. 예를 들어 3번 톱니바퀴가 시계 방향으로 돈다면, 2번 톱니바퀴와 4번 톱니바퀴는 반시계 방향으로 돈다. 그리고 톱니바퀴의 톱니는 8개로 이루어져 있으며, 앞 톱니바퀴의 3번째 톱니(3시 방향)와 현재 톱니바퀴의 7번째 톱니(9시 방향)가 서로 맞닿아있다. 맞닿아..

• format_list_bulleted PS/백준
• · 2023. 7. 7.
• textsms

[백준 / C언어] 14719번: 빗물

https://www.acmicpc.net/problem/14719 14719번: 빗물 첫 번째 줄에는 2차원 세계의 세로 길이 H과 2차원 세계의 가로 길이 W가 주어진다. (1 ≤ H, W ≤ 500) 두 번째 줄에는 블록이 쌓인 높이를 의미하는 0이상 H이하의 정수가 2차원 세계의 맨 왼쪽 위치 www.acmicpc.net 난이도: solved.ac 골드 5 알고리즘 분류 구현, 시뮬레이션, 투포인터 접근 방법 물이 차려면 양쪽의 높이보다 더 낮은 높이를 가져야 한다. 이때 차는 물은 양쪽의 높이에서 더 낮은 쪽의 높이를 가진다. 그리고 항상 특정 지점을 둘러싼 곳에서, 두 번째로 높은 지점의 높이로 물이 찬다. 아래 그림에서 1번부터 5번 사이의 구간을 보자. 1번부터 5번 사이에서 두 번째로 높..

• format_list_bulleted PS/백준
• · 2023. 7. 6.
• textsms

[백준 / C언어] 2527번: 직사각형

https://www.acmicpc.net/problem/2527 2527번: 직사각형 4개의 줄로 이루어져 있다. 각 줄에는 8개의 정수가 하나의 공백을 두고 나타나는데, 첫 4개의 정수는 첫 번째 직사각형을, 나머지 4개의 정수는 두 번째 직사각형을 각각 나타낸다. 단 입력 직사 www.acmicpc.net 난이도: solved.ac 실버 1 알고리즘 분류 수학, 기하학, 많은 조건 분기 접근 방법 두 개의 사각형 A, B가 있다고 해보자. 먼저 공통부분이 없는 d의 경우에 어떤 모양을 갖고 있는지 살펴보자. 아래와 같은 네 가지의 경우에 공통부분을 갖지 않게 된다. 그리고 꼭지점끼리만 접하는 c의 모양은 어떻게 되는지 살펴보자. 아래와 같이 네 가지의 경우만 가능하다. 그리고 선분끼리 접하는 경우인..

• format_list_bulleted PS/백준
• · 2023. 7. 4.
• textsms

[백준 / C언어] 14940번: 쉬운 최단거리 (BFS)

https://www.acmicpc.net/problem/14940 14940번: 쉬운 최단거리 지도의 크기 n과 m이 주어진다. n은 세로의 크기, m은 가로의 크기다.(2 ≤ n ≤ 1000, 2 ≤ m ≤ 1000) 다음 n개의 줄에 m개의 숫자가 주어진다. 0은 갈 수 없는 땅이고 1은 갈 수 있는 땅, 2는 목표지점이 www.acmicpc.net 난이도: solved.ac 실버 1 알고리즘 분류 그래프 탐색 (BFS) 접근 방법 및 구현 목표 지점인 2부터 BFS을 시작해서 목표 지점까지의 거리가 몇 인지 visited에 적어준다. BFS 탐색을 끝내고 나서는 map = 0(= 갈 수 없는 땅)이 아니면서 visited가 0인 지점은 도달하지 못하는 곳을 의미하므로 해당 부분의 visited는 ..

• format_list_bulleted PS/백준
• · 2023. 7. 2.
• textsms