2580번: 스도쿠

2580번: 스도쿠사용 언어: C++ 풀이문제 요약9×9 스도쿠 판에서, 일부 칸이 비어 있고(0으로 표시됨), 규칙에 맞게 모든 칸을 채워야 함.각 행에 1~9가 한번씩각 열에 1~9가 한번씩각 3×3 구역에 1~9가 한번씩풀이백트래킹 기법을 이용하여 모든 빈 칸에 대해 가능한 수를 대입하고,불가능한 경우 이전 상태로 돌아가서 다른 수를 시도.핵심 아이디어빈 칸을 순서대로 탐색하며 가능한 숫자를 시도숫자를 채울 때마다, 행/열/구역 사용 여부를 표시가능한 경우 다음 칸으로 재귀 호출실패하면 상태를 되돌리고 다음 숫자 시도 (백트래킹)구현 포인트각 행/열/3×3 구역에 대해 숫자 사용 여부를 확인하기 위해bool row[9][10], col[9][10], square[9][10] 배열을 사용한다.(i /..

24060번: 알고리즘 수업 - 병합 정렬 1

24060번: 알고리즘 수업 - 병합 정렬 1사용 언어: C++ 풀이Merge Sort (병합 정렬) 문제.기본 병합 정렬 구현 문제. 핵심은 정렬이 완료된 배열이 아니라, 정렬 중 원소가 배열 A에 저장되는 순간을 추적해서,K번째로 저장되는 값을 출력하는 것.병합 과정에서 A[i] = tmp[t]가 실행될 때마다 저장 횟수(cnt)를 세고,cnt == K가 되면 해당 값을 result에 저장한다.만약 저장 횟수가 K보다 작으면 -1 출력.#include using namespace std;int A[500001], tmp[500001];int N, K, cnt = 0, result = -1;void merge(int p, int q, int r) { int i = p, j = q + 1, t = ..

1978번: 소수 찾기 (BOJ C++)

1978번: 소수 찾기 사용 언어: C++ 풀이 아래의 코드는 O(n)이지만, O(루트n)에 코드를 짤 수 있다. 해당 숫자의 루트 n까지만 확인하면 된다는 사실을 사용하는 것이다. for(int i=2; i*i> num; bool flag; while(num--) { int isPrime; flag = true; cin >> isPrime; if(isPrime == 1) continue; for(int i=2; i

1259번: 팰린드롬수 (BOJ C++)

1259번: 팰린드롬수 사용 언어: C++ 풀이 #include #include using namespace std; int main(void) { ios::sync_with_stdio(0); cin.tie(0); stack stack; while(1) { string a; cin >> a; if(a == "0") break; if(a.length() == 1) { cout

2096번: 내려가기 (BOJ C++)

2096번: 내려가기사용 언어: C++ 문제 N줄에 0 이상 9 이하의 숫자가 세 개씩 적혀 있다. 내려가기 게임을 하고 있는데, 이 게임은 첫 줄에서 시작해서 마지막 줄에서 끝나게 되는 놀이이다.먼저 처음에 적혀 있는 세 개의 숫자 중에서 하나를 골라서 시작하게 된다. 그리고 다음 줄로 내려가는데, 다음 줄로 내려갈 때에는 다음과 같은 제약 조건이 있다. 바로 아래의 수로 넘어가거나, 아니면 바로 아래의 수와 붙어 있는 수로만 이동할 수 있다는 것이다. 이 제약 조건을 그림으로 나타내어 보면 다음과 같다.별표는 현재 위치이고, 그 아랫 줄의 파란 동그라미는 원룡이가 다음 줄로 내려갈 수 있는 위치이며, 빨간 가위표는 원룡이가 내려갈 수 없는 위치가 된다. 숫자표가 주어져 있을 때, 얻을 수 있는 최대..

1181번: 단어 정렬 (BOJ C/C++)

1181번: 단어 정렬 사용 언어: C++ 문제 알파벳 소문자로 이루어진 N개의 단어가 들어오면 아래와 같은 조건에 따라 정렬하는 프로그램을 작성하시오. 길이가 짧은 것부터 길이가 같으면 사전 순으로 입력 첫째 줄에 단어의 개수 N이 주어진다. (1 ≤ N ≤ 20,000) 둘째 줄부터 N개의 줄에 걸쳐 알파벳 소문자로 이루어진 단어가 한 줄에 하나씩 주어진다. 주어지는 문자열의 길이는 50을 넘지 않는다. 출력 조건에 따라 정렬하여 단어들을 출력한다. 단, 같은 단어가 여러 번 입력된 경우에는 한 번씩만 출력한다. 풀이 #include using namespace std; bool comp(string a, string b){ if(a.size() != b.size()) return a.size() <..

14500번: 테트로미노 (BOJ C/C++)

14500번: 테트로미노 사용 언어: C++ 문제 폴리오미노란 크기가 1×1인 정사각형을 여러 개 이어서 붙인 도형이며, 다음과 같은 조건을 만족해야 한다. 정사각형은 서로 겹치면 안 된다. 도형은 모두 연결되어 있어야 한다. 정사각형의 변끼리 연결되어 있어야 한다. 즉, 꼭짓점과 꼭짓점만 맞닿아 있으면 안 된다. 정사각형 4개를 이어 붙인 폴리오미노는 테트로미노라고 하며, 다음과 같은 5가지가 있다. 아름이는 크기가 N×M인 종이 위에 테트로미노 하나를 놓으려고 한다. 종이는 1×1 크기의 칸으로 나누어져 있으며, 각각의 칸에는 정수가 하나 쓰여 있다. 테트로미노 하나를 적절히 놓아서 테트로미노가 놓인 칸에 쓰여 있는 수들의 합을 최대로 하는 프로그램을 작성하시오. 테트로미노는 반드시 한 정사각형이 정..

1920번: 수 찾기 (BOJ C/C++)

1920번: 수 찾기 사용 언어: C++ 문제 N개의 정수 A[1], A[2], …, A[N]이 주어져 있을 때, 이 안에 X라는 정수가 존재하는지 알아내는 프로그램을 작성하시오. 입력 첫째 줄에 자연수 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 줄에는 N개의 정수 A[1], A[2], …, A[N]이 주어진다. 다음 줄에는 M(1 ≤ M ≤ 100,000)이 주어진다. 다음 줄에는 M개의 수들이 주어지는데, 이 수들이 A안에 존재하는지 알아내면 된다. 모든 정수의 범위는 -231 보다 크거나 같고 231보다 작다. 출력 M개의 줄에 답을 출력한다. 존재하면 1을, 존재하지 않으면 0을 출력한다. 풀이 1 반복문을 이용한 이진탐색 #include using namespace std; int n,..