[백준 / 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

[백준 / C언어] 10026번: 적록색약 (BFS 풀이)

https://www.acmicpc.net/problem/10026 10026번: 적록색약 적록색약은 빨간색과 초록색의 차이를 거의 느끼지 못한다. 따라서, 적록색약인 사람이 보는 그림은 아닌 사람이 보는 그림과는 좀 다를 수 있다. 크기가 N×N인 그리드의 각 칸에 R(빨강), G(초록) www.acmicpc.net 난이도: solved.ac 골드 5 알고리즘 분류 DFS, BFS 구현 적록색약이 아닌 눈으로 볼 때와 적록색약인 눈으로 볼 때의 두 경우를 각각의 함수 eyes1, eyes2로 만들었다 eyes1은 일반 BFS 함수와 동일하고, eyes2는 R과 G를 동일한 색으로 봐야하므로 큐에 맨 처음으로 들어가는 색깔이 R이나 G인 경우에는 B를 제외한 색(R 또는 G)일 때만 탐색을 이어나가고, ..

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

[백준 / C언어] 15651번: N과 M (3)

https://www.acmicpc.net/problem/15651 15651번: N과 M (3) 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해 www.acmicpc.net 난이도: solved.ac 실버 3 알고리즘 분류 백트래킹 문제 설명 1부터 N까지의 숫자를 중복 허용하여 M개 골라 나열하는 문제다 이때 나열된 수열은 총 N^M개가 된다 구현 출력할 수열을 배열 arr에 저장한다 1부터 N까지의 숫자를 for 문을 이용해 arr에 넣어주고 함수 NnM을 재귀 호출한다 NnM의 인수로 cnt라는 변수가 사용되는데, 이는 현재 배열에 저장된 수열의 길이를 의미한..

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