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

[백준 / C언어] 15650번: N과 M (2)

https://www.acmicpc.net/problem/15650 15650번: N과 M (2) 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해 www.acmicpc.net 난이도: solved.ac 실버 3 알고리즘 분류 백트래킹 접근 방법 뒤에 나오는 수가 앞에 나온 수보다 커야 한다 따라서 last라는 변수를 두었고, 뒤에 나오는 수는 last보다 더 큰 수가 나오도록 해야 한다 M개의 for문을 사용하는 대신 재귀 함수를 이용해 구현한다 구현 find라는 재귀 함수를 만들었다 변수 num은 현재 수열의 길이를 의미하고 last는 나열된 숫자들 중 가장 마지막..

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

[백준 / C언어] 1966번: 프린터 큐 (배열을 이용해서 풀기)

https://www.acmicpc.net/problem/1966 1966번: 프린터 큐 여러분도 알다시피 여러분의 프린터 기기는 여러분이 인쇄하고자 하는 문서를 인쇄 명령을 받은 ‘순서대로’, 즉 먼저 요청된 것을 먼저 인쇄한다. 여러 개의 문서가 쌓인다면 Queue 자료구조에 www.acmicpc.net 난이도: solved.ac 실버 3 접근 방법 배열을 이용하면 어렵지 않게 풀 수 있다 입력받은 수들을 저장할 배열(queue)과 각 우선순위가 몇 개씩 있는지 저장할 배열(prior)을 이용한다 그리고 커서(cur)를 이용해 queue의 맨 앞 원소부터 한 칸씩 이동하며 제거할지 말지 결정한다 cur가 가리키는 문서의 우선순위가 가장 높아 제거해야 한다면 해당 문서의 우선순위 개수를 하나 감소시키고..

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

[백준 / C언어] 11279번: 최대 힙(배열로 구현)

https://www.acmicpc.net/problem/11279 11279번: 최대 힙 첫째 줄에 연산의 개수 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 N개의 줄에는 연산에 대한 정보를 나타내는 정수 x가 주어진다. 만약 x가 자연수라면 배열에 x라는 값을 넣는(추가하는) 연산이고, x가 0 www.acmicpc.net 난이도: solved.ac 실버 2 자료구조 힙(Heap)을 구현하는 문제다 일반 이진트리(Binary Tree)는 input이 100,000개일 때 높이(depth)가 2^100000 - 1가 될 수 있지만 (한쪽으로만 연결된 경우에) 힙은 완전 이진트리(Complete Binary Tree)라서 input이 100,000개여도 높이는 log(2)100,000 밖에 되지 ..

• format_list_bulleted PS/백준
• · 2023. 5. 31.
• textsms