[백준 / C언어] 17070번: 파이프 옮기기 1 (dp, 다이나믹 프로그래밍)

https://www.acmicpc.net/problem/17070 17070번: 파이프 옮기기 1 유현이가 새 집으로 이사했다. 새 집의 크기는 N×N의 격자판으로 나타낼 수 있고, 1×1크기의 정사각형 칸으로 나누어져 있다. 각각의 칸은 (r, c)로 나타낼 수 있다. 여기서 r은 행의 번호, c는 열의 www.acmicpc.net 난이도: solved.ac 골드 5 알고리즘 분류 다이나믹 프로그래밍 (dp), 그래프 탐색 (DFS) 접근 방법 각 칸 별로 옮길 수 있는 방법의 수가 정해져 있으므로 dp를 이용해 풀어야겠다고 생각했다. 파이프를 옮겼을 때 가로 상태이려면 이전 상태가 가로 또는 대각선 상태여야 한다. 그리고 대각선 상태라면 이전 상태가 가로 또는 대각선 또는 세로 상태여야 하고, 세로..

• format_list_bulleted 백준
• · 2023. 6. 30.
• textsms

[백준 / C언어] 2668번: 숫자고르기 (DFS로 풀이)

https://www.acmicpc.net/problem/2668 2668번: 숫자고르기 세로 두 줄, 가로로 N개의 칸으로 이루어진 표가 있다. 첫째 줄의 각 칸에는 정수 1, 2, …, N이 차례대로 들어 있고 둘째 줄의 각 칸에는 1이상 N이하인 정수가 들어 있다. 첫째 줄에서 숫자를 적절 www.acmicpc.net 난이도: solved.ac 골드 5 알고리즘 분류 그래프 탐색, DFS (깊이 우선 탐색) 접근 방법 방향이 있는 그래프로 생각하면 쉽다. 사이클이 있는 노드들의 개수를 세는 문제다. 문제에 있는 표에서 1행의 숫자들을 노드라고 생각하고, 2행에 있는 숫자들을 1행에 있는 노드에서 연결된 노드라고 보면 된다. 구현 1번 노드부터 N번 노드까지 각 노드를 시작점으로 해서 화살표를 따라가..

• format_list_bulleted 백준
• · 2023. 6. 29.
• textsms

[백준 / 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 백준
• · 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 백준
• · 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 백준
• · 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 백준
• · 2023. 6. 16.
• textsms