본문 바로가기

분류 전체보기

 (265)
백준9020 - 골드바흐의 추측 https://www.acmicpc.net/problem/9020 9020번: 골드바흐의 추측 문제 1보다 큰 자연수 중에서 1과 자기 자신을 제외한 약수가 없는 자연수를 소수라고 한다. 예를 들어, 5는 1과 5를 제외한 약수가 없기 때문에 소수이다. 하지만, 6은 6 = 2 × 3 이기 때문에 소수가 아니다. 골드바흐의 추측은 유명한 정수론의 미해결 문제로, 2보다 큰 모든 짝수는 두 소수의 합으로 나타낼 수 있다는 것이다. 이러한 수를 골드바흐 수라고 한다. 또, 짝수를 두 소수의 합으로 나타내는 표현을 그 수의 골드바흐 파티션이라고 한다. www.acmicpc.net 40000까지의 소수를 구하고 입력 받은 수 num을 반 나눠서 한쪽은 1씩 더하고 한쪽은 1씩 뺀다. 시작은 num / 2부터 하..
백준14225 - 부분수열의 합 https://www.acmicpc.net/problem/14225 14225번: 부분수열의 합 수열 S가 주어졌을 때, 수열 S의 부분 수열의 합으로 나올 수 없는 가장 작은 자연수를 구하는 프로그램을 작성하시오. 예를 들어, S = [5, 1, 2]인 경우에 1, 2, 3(=1+2), 5, 6(=1+5), 7(=2+5), 8(=1+2+5)을 만들 수 있다. 하지만, 4는 만들 수 없기 때문에 정답은 4이다. www.acmicpc.net 전에 풀었던 2437번과 완전 풀이가 같은 문제다. 그리디를 이용하여 풀었다. 입력 받은 수를 우선 오름차순으로 정렬을 한다. 그 다음 현재까지 더한 숫자보다 1 더 큰 수가 현재 인덱스 숫자보다 작으면 그것이 답이다. #include #include #include ..
백준15663 - N과 M(9) https://www.acmicpc.net/problem/15663 15663번: N과 M (9) 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해야 한다. www.acmicpc.net 수열문제인데 굉장히 재밌는 문제였다. 중복된 원소를 제거해야 되었다. 나는 우선적으로 입력한 원소들을 오름차순으로 정렬 하였다. 그런 후 각각의 케이스마다 처음 선택한 원소를 저장하여 이전에 사용했던 원소인지 검사한다. 이전에 사용했던 원소이면 건너뛰고 사용하지 않은 원소이면 탐색을 시작한다. 방문한 곳을 재방문하지 않도록 dfs를 사용하여 탐색하였다. 중요한 점은 전에 출력했던 원소를..
백준11375 - 열혈강호 https://www.acmicpc.net/problem/11375 11375번: 열혈강호 강호네 회사에는 직원이 N명이 있고, 해야할 일이 M개가 있다. 직원은 1번부터 N번까지 번호가 매겨져 있고, 일은 1번부터 M번까지 번호가 매겨져 있다. 각 직원은 한 개의 일만 할 수 있고, 각각의 일을 담당하는 사람은 1명이어야 한다. 각각의 직원이 할 수 있는 일의 목록이 주어졌을 때, M개의 일 중에서 최대 몇 개를 할 수 있는지 구하는 프로그램을 작성하시오. www.acmicpc.net 이분 매칭을 이용하여 풀었다. 나동빈님 블로그에서 참고하였다. 이분 매칭은 a 집단에서 b 집단을 일대일로 각 원소를 매칭하는데 최대로 매칭해 줄 수 있는 방법을 찾는 방법이다. dfs를 이용하여 구현한다. 구현 원리는 ..
백준11060 - 점프 점프 https://www.acmicpc.net/problem/11060 11060번: 점프 점프 재환이가 1×N 크기의 미로에 갇혀있다. 미로는 1×1 크기의 칸으로 이루어져 있고, 각 칸에는 정수가 하나 쓰여 있다. i번째 칸에 쓰여 있는 수를 Ai라고 했을 때, 재환이는 Ai이하만큼 오른쪽으로 떨어진 칸으로 한 번에 점프할 수 있다. 예를 들어, 3번째 칸에 쓰여 있는 수가 3이면, 재환이는 4, 5, 6번 칸 중 하나로 점프할 수 있다. 재환이는 지금 미로의 가장 왼쪽 끝에 있고, 가장 오른쪽 끝으로 가려고 한다. 이때, 최소 몇 번 점프를 해 www.acmicpc.net 경우의 수가 생각보다 많은 문제였다. 1차원 dp를 사용하여 풀었다. #include #include using namespace ..
백준1697 - 숨바꼭질 https://www.acmicpc.net/problem/1697 1697번: 숨바꼭질 문제 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 때 걷는다면 1초 후에 X-1 또는 X+1로 이동하게 된다. 순간이동을 하는 경우에는 1초 후에 2*X의 위치로 이동하게 된다. 수빈이와 동생의 위치가 주어졌을 때, 수빈이가 동생을 찾을 수 있는 가장 빠른 시간이 몇 초 후인지 www.acmicpc.net bfs를 이용하여 푼 문제다. 앞, 뒤, 두 배인 곳으로 이동하는 방법이 존재한다. 방문한 곳은 다시 방문하지 않도록 탐색을 하는 방법으로..
백준9251 - LCS https://www.acmicpc.net/problem/9251 9251번: LCS LCS(Longest Common Subsequence, 최장 공통 부분 수열)문제는 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다. 예를 들어, ACAYKP와 CAPCAK의 LCS는 ACAK가 된다. www.acmicpc.net 최장 공통 부분 수열을 구현하는 문제다. 2차원 dp를 사용하면 쉽게 풀 수 있다. #include #include #include using namespace std; int mat[1001][1001] = { 0 }; int main() { string s1, s2; cin >> s1 >> s2; /* 두 문자가 같으면 좌측 위에 있는 숫자 + 1 ..
백준2294 - 동전2 https://www.acmicpc.net/problem/2294 2294번: 동전 2 첫째 줄에 n, k가 주어진다. (1 ≤ n ≤ 100, 1 ≤ k ≤ 10,000) 다음 n개의 줄에는 각각의 동전의 가치가 주어진다. 동전의 가치는 100,000보다 작거나 같은 자연수이다. 가치가 같은 동전이 여러 번 주어질 수도 있다. www.acmicpc.net 2차원 dp를 이용하여 풀었다. 동전 i원일 때 j원을 만들 수 있는지 여부를 따졌다. i - 1원일 때 j원을 만들 수 있었는지 없었는지 판단하는 것이 중요하다. i원으로 j원을 만들 수 있는 지 판별하는 방법은 다음과 같다. 1. 0번지를 1로 초기화하여 i원 동전 혼자 j원을 만들 수 있는 경우를 대비한다. 2. i원 보다 액수가 작은 j원은 i..

티스토리툴바