본문 바로가기

Programming/BOJ277

[C/C++] 백준 #2239 스도쿠(백트래킹) #2239 스도쿠 문제는 고전적인 백트래킹을 사용해서 푸는 문제입니다. 문제의 링크입니다. https://www.acmicpc.net/problem/2239 2239번: 스도쿠 스도쿠는 매우 간단한 숫자 퍼즐이다. 9×9 크기의 보드가 있을 때, 각 행과 각 열, 그리고 9개의 3×3 크기의 보드에 1부터 9까지의 숫자가 중복 없이 나타나도록 보드를 채우면 된다. 예를 들어 다 www.acmicpc.net 스도쿠는 가로와 세로가 각각 9칸을 가지고 있는 숫자 퍼즐입니다. 스도쿠의 숫자는 법칙이 있는데, 각각의 가로줄에 1부터 9까지의 숫자가 오직 한번씩만 사용되어야 하고, 각각의 세로줄에도 같은 법칙이 성립합니다. 그리고 3x3 짜리 작은 정사각형 안에도 1부터 9까지의 숫자가 오직 한번씩만 사용되어야 .. 2023. 4. 18.
[C/C++] 백준 #2225 합분해(동적 계획법) #2225 합분해 문제는 경우의 수를 찾는 문제입니다. 경우의 수를 찾는 문제들의 특성은 동적 계획법하고 상당히 잘 맞습니다. 문제는 동적 계획법을 어떻게 구성할 것인가죠. 그리고 꽤 많은 경우 간단하게 한번에 계산할 수 있는 경우의 수를 찾을 수도 있습니다. 물론 그것이 계승(factorial) 형태로 나오면 큰 의미도 없습니다. 문제의 링크입니다. https://www.acmicpc.net/problem/2225 2225번: 합분해 첫째 줄에 답을 1,000,000,000으로 나눈 나머지를 출력한다. www.acmicpc.net 문제의 요구사항은 간단합니다. 0부터 N까지의 수중에 K개를 뽑아서 합이 N을 만드는 경우의 수입니다. 중복된 수도 허용하고, 더하는 순서가 다르면 서로 다른 경우로 봅니다... 2023. 4. 17.
[C/C++] 백준 #2217 로프(탐욕 알고리즘) #2217 문제는 정렬을 사용한 탐욕 알고리즘으로 풀 수 있는 문제입니다. 문제의 링크입니다. https://www.acmicpc.net/problem/2217 2217번: 로프 N(1 ≤ N ≤ 100,000)개의 로프가 있다. 이 로프를 이용하여 이런 저런 물체를 들어올릴 수 있다. 각각의 로프는 그 굵기나 길이가 다르기 때문에 들 수 있는 물체의 중량이 서로 다를 수도 있다. 하 www.acmicpc.net n개의 로프가 있는데, 여러줄을 사용하면, 들어올리고자 하는 물건의 무게를 똑같이 분담하면서 물건을 올릴 수가 있습니다. 로프마다 견딜 수 있는 하중이 따로 있어서, 현재 가지고 있는 로프로 가능한 무거운 물건을 올리고자 할 때, 그 무게가 얼마인가입니다. 예를 들어서 무게를 3, 7, 6, 4.. 2023. 4. 17.
[Python] 백준 #2212 센서(탐욕 알고리즘) 이번 문제는 문제의 뜻을 해석하느라고 아주 어려웠네요. https://www.acmicpc.net/problem/2212 2212번: 센서 첫째 줄에 센서의 개수 N(1 ≤ N ≤ 10,000), 둘째 줄에 집중국의 개수 K(1 ≤ K ≤ 1000)가 주어진다. 셋째 줄에는 N개의 센서의 좌표가 한 개의 정수로 N개 주어진다. 각 좌표 사이에는 빈 칸이 하나 있 www.acmicpc.net 문제는 수직선상에 있는 N개의 점들을 K개의 그룹으로 나누었을 때, 각각의 그룹의 길이의 합을 최소로 하는 문제입니다. 가장 쉬운 것은 두점사이의 거리가 가장 먼 것들에 대해서 K-1개 선택해서 나누면 됩니다. 문제의 예제처럼 1 6 9 3 6 7 위치들의 점이 있다고 한다면, 이것을 순서대로 정렬하면, 1 3 6 6.. 2023. 4. 17.
[C/C++] 백준 #2210 숫자판 점프(집합, 백트래킹) #2210은 실버 문제로 난이도는 높지 않습니다. 백트래킹 알고리즘을 이용해서 모든 경우의 수를 찾아내었고, 집합을 이용해서 중복을 제거해서 풀었습니다. 문제 링크입니다. https://www.acmicpc.net/problem/2210 2210번: 숫자판 점프 111111, 111112, 111121, 111211, 111212, 112111, 112121, 121111, 121112, 121211, 121212, 211111, 211121, 212111, 212121 이 가능한 경우들이다. www.acmicpc.net 기본적으로 2차원 배열에서 백트래킹은 경계조건하고 상하좌우 움직임 등만 잘 처리하면 큰 무리가 없습니다. 집합 자료구조는 C++에서 제공하는 것이 두가지인데, 일반 집합 자료구조는 se.. 2023. 4. 17.
[C/C++] 백준 #2207 가위바위보(2-SAT) #2207 문제는 문제 설명이 조금 어렵습니다. 사실, 모든 경우에 필승전략은 k번째 주먹, k번째 가위를 말하면 반드시 맞으니까, 필승전략이 되겠죠. 문제는 바로 이러한 필승 전략을 요구하는 것으로 보이지만, 실제는 그것이 아니라, 학생들이 말한 내용이 필패전략(즉, 한명이라도 맞추지 못하는)이 될 수 있는지 검사하라는 것입니다. 문제의 링크입니다. https://www.acmicpc.net/problem/2207 2207번: 가위바위보 첫째 줄에 두 정수 N, M이 주어진다. 다음 N개의 줄에는 각각의 학생들의 선택을 나타내는 두 정수 x, y(1 ≤ |x|, |y| ≤ M)이 주어진다. x가 양수일 경우에는 원장선생님이 x번째에 가위를 낼 거라는 www.acmicpc.net 필패전략이 되지 않으려면.. 2023. 4. 16.
728x90

티스토리툴바