[백준 / C언어] 2468번: 안전 영역 (BFS로 풀이)

https://www.acmicpc.net/problem/2468 2468번: 안전 영역 재난방재청에서는 많은 비가 내리는 장마철에 대비해서 다음과 같은 일을 계획하고 있다. 먼저 어떤 지역의 높이 정보를 파악한다. 그 다음에 그 지역에 많은 비가 내렸을 때 물에 잠기지 않는 www.acmicpc.net 난이도: solved.ac 실버 1 알고리즘 분류 BFS, DFS (그래프 탐색) 접근 방법 각 영역의 높이를 입력 받을 때 해당 높이를 따로 기억하여 높이가 1일 때부터 100일 때까지 중 입력 받은 높이일 때만 전체 영역을 BFS로 탐색한다. 모든 경우에서 안전 영역의 개수가 가장 많을 때를 저장해 출력한다. 구현 높이 배열 arr_h를 만들어, 각 지역의 높이를 입력받을 때 해당 높이의 index ..

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

[백준 / C언어] 9184번: 신나는 함수 실행

https://www.acmicpc.net/problem/9184 9184번: 신나는 함수 실행 입력은 세 정수 a, b, c로 이루어져 있으며, 한 줄에 하나씩 주어진다. 입력의 마지막은 -1 -1 -1로 나타내며, 세 정수가 모두 -1인 경우는 입력의 마지막을 제외하면 없다. www.acmicpc.net 난이도: solved.ac 실버 2 알고리즘 분류 다이나믹 프로그래밍 (dp) 구현 배열의 index는 0부터 시작하므로 50을 더해 0부터 100까지의 index를 가진 3차원 배열 dp를 만들어주었다 문제에서 주어진 pseudo 코드를 그대로 옮기면 안된다 나는 두 번째 if문을 따로 처리해주었다 (이유: pseudo 코드의 순서대로 진행하면 w(20,20,20)이 만들어지지 않았는데 w(20,2..

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

[백준 / C언어] 1309번: 동물원 (dp)

https://www.acmicpc.net/problem/1309 1309번: 동물원 첫째 줄에 우리의 크기 N(1≤N≤100,000)이 주어진다. www.acmicpc.net 난이도: solved.ac 실버 1 알고리즘 분류 다이나믹 프로그래밍 (dp) 접근 방법 이 문제에서 중요한 부분은 가로 또는 세로로 붙여서 배치시킬 수 없다는 것이다 따라서, 사자를 배치하는 경우는 아래 세 가지로 나눌 수 있다 1) 이전 칸에서 왼쪽에 배치한 경우 2) 이전 칸에서 오른쪽에 배치한 경우 3) 이전 칸 둘 다 배치하지 않은 경우 1번의 경우에는 이전에 왼쪽에 배치되어 있으므로 왼쪽에 또 배치시킬 수 없다 따라서 오른쪽 칸에 배치시키거나 아예 둘 다 비워놓는 경우만 가능하다 2번의 경우에는 이전에 오른쪽에 배치되어..

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

[백준 / C언어] 11758번: CCW

https://www.acmicpc.net/problem/11758 11758번: CCW 첫째 줄에 P1의 (x1, y1), 둘째 줄에 P2의 (x2, y2), 셋째 줄에 P3의 (x3, y3)가 주어진다. (-10,000 ≤ x1, y1, x2, y2, x3, y3 ≤ 10,000) 모든 좌표는 정수이다. P1, P2, P3의 좌표는 서로 다르다. www.acmicpc.net 난이도: solved.ac 골드 5 알고리즘 분류 기하학 접근 방법 벡터의 외적 + 신발끈 공식을 사용한다 세 개의 점 P1, P2, P3가 있다고 할 때, P1에서 P2로 가는 벡터를 a, P1에서 P3로 가는 벡터를 b라고 하자 이때 a와 b 사이의 각도를 세타(θ)라고 하자 그리고 벡터 a와 벡터 b의 외적의 크기를 구한다 ..

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

[백준 / C언어] 10994번: 별 찍기 - 19

https://www.acmicpc.net/problem/10994 10994번: 별 찍기 - 19 예제를 보고 규칙을 유추한 뒤에 별을 찍어 보세요. www.acmicpc.net 난이도: solved.ac 실버 4 알고리즘 분류 구현, 재귀 규칙 한 변의 길이가 4*N - 3인 N개의 정사각형으로 둘러쌓인 모양이다 구현 2차원 배열을 만들어서 각 N에 맞는 정사각형들을 그려준다 N = 4라면, 먼저 한 변의 길이가 4*4 - 3인 정사각형을 그려주고 그 다음 N = 3짜리인 한 변의 길이가 4*3 - 3인 정사각형을 그려주고 N = 2짜리인 한 변의 길이가 4*2 - 3인 정사각형을 그려주고 N = 1짜리인 한 변의 길이가 4*1 - 3인 정사각형을 그려준다 위처럼 왼쪽 변, 아래쪽 변, 오른쪽 변, ..

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

[백준 / C언어] 2166번: 다각형의 면적 (신발끈 공식)

https://www.acmicpc.net/problem/2166 2166번: 다각형의 면적 첫째 줄에 N이 주어진다. 다음 N개의 줄에는 다각형을 이루는 순서대로 N개의 점의 x, y좌표가 주어진다. 좌표값은 절댓값이 100,000을 넘지 않는 정수이다. www.acmicpc.net 난이도: solved.ac 골드 5 알고리즘 분류 기하학 구현 신발끈 공식을 이용하면 매우 쉽게 풀 수 있다 그럼 신발끈 공식이 뭐냐! https://ko.wikipedia.org/wiki/%EC%8B%A0%EB%B0%9C%EB%81%88_%EA%B3%B5%EC%8B%9D 신발끈 공식 - 위키백과, 우리 모두의 백과사전 위키백과, 우리 모두의 백과사전. 신발끈 공식(―公式)은 좌표평면 상에서 꼭짓점의 좌표를 알 때 다각형의..

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