본문 바로가기

백준(C언어)/23년 7월20

[C] 백준 - 2468번: 안전 영역 7월 28일(금) - 그래프와 순회 (2468번) 2468번: 안전 영역 재난방재청에서는 많은 비가 내리는 장마철에 대비해서 다음과 같은 일을 계획하고 있다. 먼저 어떤 지역의 높이 정보를 파악한다. 그 다음에 그 지역에 많은 비가 내렸을 때 물에 잠기지 않는 www.acmicpc.net ㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡ 최초 생각 정리 - 이전에 풀이했던 "1012번: 유기농 배추" 혹은 "2667번: 단지번호붙이기"문제와 유사한 풀이를 예상 - dfs 방식으로 풀이를 진행하며 - 입력은 N과 N x N개의 2차원 배열을 area[ ][ ]에 받는다 하지만 내릴 수 있는 비의 양 = 즉 depth 를 0부터 100까지 모두 돌리는 것은 비효율적일.. 2023. 7. 28.
[C] 백준 - 17387번: 선분 교차 2 7월 27일(목) - 기하학 (17387번) 17387번: 선분 교차 2 첫째 줄에 L1의 양 끝 점 x1, y1, x2, y2가, 둘째 줄에 L2의 양 끝 점 x3, y3, x4, y4가 주어진다. www.acmicpc.net ㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡ 최초 생각 정리 - 이전에 풀이했던 "17386번: 선분 교차 1" 문제와 비슷한 풀이를 예상 - 다만 3개의 점이 하나의 직선상에 위치하며 교차하는 경우를 조건에 추가해야한다 [C] 백준 - 17386번: 선분 교차 1 7월 20일(목) - 기하학 (17386번) 17386번: 선분 교차 1 첫째 줄에 L1의 양 끝 점 x1, y1, x2, y2가, 둘째 줄에 L2의 양 끝 점 x3, y.. 2023. 7. 27.
[C] 백준 - 16953번: A -> B 7월 26일(수) - 그리디 알고리즘 (16953번) 16953번: A → B 첫째 줄에 A, B (1 ≤ A < B ≤ 109)가 주어진다. www.acmicpc.net ㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡ 최초 생각 정리 - A와 B의 크기비교가 가장 중요한 조건이라는 판단을 하게되었다 - A==B인 상황이라면, 그때 변수 count를 출력하고 AB인 상황이라면, 더 이상 연산을 진행하기는 것이 불가능한 상황이므로 바로 -1을 출력한다 - 따라서 A 다른 풀이 참고해볼 것 ㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡ 풀이 - 1 #define _CRT_SECURE_NO_WARNINGS #pragma w.. 2023. 7. 26.
[C] 백준 - 10799번: 쇠막대기 7월 25일(화) - 자료 구조 (10799번) 10799번: 쇠막대기 여러 개의 쇠막대기를 레이저로 절단하려고 한다. 효율적인 작업을 위해서 쇠막대기를 아래에서 위로 겹쳐 놓고, 레이저를 위에서 수직으로 발사하여 쇠막대기들을 자른다. 쇠막대기와 레이저 www.acmicpc.net ㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡ 최초 생각 정리 - 괄호의 열고 닫음의 짝을 이용해서, 이전에 입력받았던 괄호의 성격에 따라서 조건을 나누어서 체크해야한다 - 따라서 스택을 활용한 풀이를 예상 - 입력은 string을 받은 뒤, for문을 string의 크기만큼 돌려준다 - for문안에서는 1) 입력받은 string[ i ]가 ' ( '인 경우와 아닌 경우 2) 입력받.. 2023. 7. 25.
[C] 백준 - 9084번: 동전 7월 24일(월) - 다이나믹 프로그래밍 (9084번) 9084번: 동전 우리나라 화폐단위, 특히 동전에는 1원, 5원, 10원, 50원, 100원, 500원이 있다. 이 동전들로는 정수의 금액을 만들 수 있으며 그 방법도 여러 가지가 있을 수 있다. 예를 들어, 30원을 만들기 위해서는 www.acmicpc.net ㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡ 최초 생각 정리 - 다이나믹 프로그래밍 형식을 활용한 풀이를 예상 - dp[ i ] 를 구해야하는 경우, dp[ i ] = dp[ i ] + dp[ i - cost[ j ] ] 형태의 식을 얻어낼 수 있다 - 입력은 테스트케이스마다 N과 N가지의 동전 금액, 그리고 만들어야하는 금액인 M을 입력받는다 .. 2023. 7. 24.
[C] 백준 - 4963번: 섬의 개수 7월 21일(금) - 그래프와 순회 (4963번) 4963번: 섬의 개수 입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스의 첫째 줄에는 지도의 너비 w와 높이 h가 주어진다. w와 h는 50보다 작거나 같은 양의 정수이다. 둘째 줄부터 h개 줄에는 지도 www.acmicpc.net ㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡ 최초 생각 정리 - 이전에 풀이했던 "1012번: 유기농 배추" 문제의 풀이와 유사한 뱡향의 풀이를 예상 - 즉 dfs 방식으로 풀이를 진행하며, 해당 과정에서 인접한 섬의 조건을 위해서 dx와 dy 배열을 활용해야할 것 - 입력은 while문 안에서 테스트 케이스마다 이중 for문을 통해서 map의 w와 h, 구성요.. 2023. 7. 21.
[C] 백준 - 17386번: 선분 교차 1 7월 20일(목) - 기하학 (17386번) 17386번: 선분 교차 1 첫째 줄에 L1의 양 끝 점 x1, y1, x2, y2가, 둘째 줄에 L2의 양 끝 점 x3, y3, x4, y4가 주어진다. 세 점이 일직선 위에 있는 경우는 없다. www.acmicpc.net ㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡ 최초 생각 정리 - 선분 교차여부를 무엇으로 판단해야할지 감이 잡히지 않아서 검색한 결과, CCW 알고리즘의 활용을 알게됨 - CCW 알고리즘을 이미 사용한 적이 있지만 그 의미를 정확히 모르고 사용했었기에, 이에 대한 공부부터 시작 - 3개의 점의 방향성을 시계방향 / 반시계방향 / 일직선 3가지로 나눌 수 있다는 점을 활용해야한다 - 이를 통해서.. 2023. 7. 20.
[C] 백준 - 1946번: 신입 사원 7월 19일(수)-그리디 알고리즘(1946번) 1946번: 신입 사원 첫째 줄에는 테스트 케이스의 개수 T(1 ≤ T ≤ 20)가 주어진다. 각 테스트 케이스의 첫째 줄에 지원자의 숫자 N(1 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 N개 줄에는 각각의 지원자의 서류심사 성 www.acmicpc.net ㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡ 최초 생각 정리 - 문제자체에 대한 이해를 정확히 하는 것이 중요하다 - 1차 점수와 2차 점수 중 적어도 하나가 다른 지원자보다 떨어지지 않는자만 선발한다 이는 결국 1차 점수를 이용해서 정렬을 해놓은 뒤, 해당 상황에서 2차 점수를 가지고 카운팅을 해주어야한다 - 한 명의 지원자에게 1차_점수와 2차_.. 2023. 7. 19.
[C] 백준 - 1158번: 요세푸스 문제 7월 18일(화) - 자료 구조 (1158번) 1158번: 요세푸스 문제 첫째 줄에 N과 K가 빈 칸을 사이에 두고 순서대로 주어진다. (1 ≤ K ≤ N ≤ 5,000) www.acmicpc.net ㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡ 최초 생각 정리 - 저번주에 풀이했던 "10845번: 큐" 문제에서의 큐 자료구조를 활용하는 것을 예상 - 하지만 "11866번: 요세푸스 문제0"에서 풀이를 진행했던 경우와 마찬가지로 선형 큐로 풀이를 진행하는 경우, dequeue할 때 마다 남아있는 값들의 위치를 다시 조절해주어야 함 - 따라서 원형 큐를 사용하기로 함 [C] 백준 - 10845번: 큐 7월 11일(화) - 자료 구조 (10845번) 10845번:.. 2023. 7. 18.

티스토리툴바