문제 풀이/백준 (BOJ)

[백준/BOJ] 9184번: 신나는 함수 실행 ( 동적 계획법 ) - C++ 문제 풀이

문제 설명 문제 링크: http://www.acmicpc.net/problem/9184  풀이문제 설명에서 말했듯이, 재귀 함수를 사용하면 구현은 쉬우나 결과를 출력하기까지 너무 오래 걸리는 단점이 있습니다.이유를 자세히 들여다보면 같은 결과를 구하는 연산을 반복해서 수행하느라 대부분의 시간을 낭비하고 있다는 점을 알 수 있습니다. 그래서 이 문제는 동적 계획법을 사용하여 푸는 것이 좋겠습니다. 동적 계획법이란 전체의 문제를 작은 부분 문제로 나누어 계산한 후 결과를 저장합니다. 그리고 작은 부분의 문제를 다시 푸는 대신 저장된 결과 값을 사용하여 전체의 문제를 빠르게 푸는 방법입니다. 재귀 함수를 사용하는 방식과 동적 계획법은 더 작은 부분 문제를 해결해서 큰 문제를 해결한다는 점에서 유사한 면이 있습..

2024. 4. 30.

문제 풀이/백준 (BOJ)

[백준/BOJ] 18258번: 큐 2 ( Queue 자료 구조 사용하기 ) - C++ 문제 풀이

문제 설명 문제 링크: http://www.acmicpc.net/problem/18258 풀이문제에서는 큐(queue)를 구현해서 문제를 풀라고 되어있지만, std::queue 클래스를 사용해서 문제를 풀었다.문자열을 읽어서 그 문자열에 따라 std:: queue 클래스의 각 기능을 사용하면 간단히 처리된다.한번 큐(queue)를 구현해 보라는 문제인 거 같다. 나머지 글도 대부분 queue 자료 구조와 std::queue 클래스 사용법에 대하여 적을 생각이다. 큐(queue)는 컨테이너의 한 종류로서 큐에 맨 먼저 입력된 데이터가 먼저 출력될 수 있는 자료 구조입니다.맨 먼저 입력된 데이터가 먼저 출력되어야 하는 FIFO (First Input First Out) 구조로서, 자료 접근에 제한된 기능을 ..

2024. 4. 23.

문제 풀이/백준 (BOJ)

[백준/BOJ] 28278번 : 스택 2 ( Stack 자료 구조 사용하기 ) - C++ 문제 풀이

문제 설명 문제 링크: http://www.acmicpc.net/problem/28278 28278번: 스택 2 첫째 줄에 명령의 수 N이 주어진다. (1 ≤ N ≤ 1,000,000) 둘째 줄부터 N개 줄에 명령이 하나씩 주어진다. 출력을 요구하는 명령은 하나 이상 주어진다. www.acmicpc.net 풀이 문제에서는 스택을 구현해서 문제를 풀라고 되어있지만, std::stack 클래스를 사용해서 문제를 풀었다. 숫자를 읽어서 그 숫자에 따라 std::stack 클래스의 각 기능을 사용하면 간단히 처리된다. 한번 스택을 구현해 보라는 문제인 거 같다. 나머지 글도 대부분 stack 자료 구조와 std::stack 클래스 사용법에 대하여 적을 생각이다. 스택(Stack)은 컨테이너의 한 종류로서 스택에..

2024. 4. 23.

문제 풀이/백준 (BOJ)

[백준/BOJ] 17103번: 골드바흐 파티션 ( 에라토스테네스의 체 사용법 ) - C++ 문제 풀이

문제 설명 문제 링크: http://www.acmicpc.net/problem/17103 17103번: 골드바흐 파티션 첫째 줄에 테스트 케이스의 개수 T (1 ≤ T ≤ 100)가 주어진다. 각 테스트 케이스는 한 줄로 이루어져 있고, 정수 N은 짝수이고, 2 < N ≤ 1,000,000을 만족한다. www.acmicpc.net 풀이 이 문제는 짝수 N 보다 작은 소수들을 구하고 작은 소수들 중 더했을 때 N이 되는 두 소수쌍 (골드바흐 파티션)의 개수를 구하는 문제이다. 이때, 두 소수쌍의 순서는 무시한다. 예를 들어, 짝수 8이 주어지면 8보다 작은 소수들은 2, 3, 5, 7이 있다. 이 중에 더했을 때 8이 되는 두 소수가 존재한다는 것이 골드바흐의 추측이고, 실제로 3과 5가 골드바흐 파티션이..

2024. 4. 20.

문제 풀이/백준 (BOJ)

[백준/BOJ] 1181번: 단어 정렬 - C++ 문제 풀이

문제 풀이 문제 링크:  https://www.acmicpc.net/problem/1181 풀이단어들을 입력받아 주어진 2개의 조건에 따라 정렬하는 문제이다.길이가 짧은 단어부터길이가 같으면 사전 순으로단, 출력 시 같은 단어는 무시한다. 이 글에선 std::string 개체를 이용해서 처리할 생각이다. 정렬하는 조건 모두 string의 함수를 이용하면 쉽게 검사가 가능하다.  정렬이 필요하기 때문에 sort 함수에 대한 기본적인 사용법은 알아야 합니다.이에 관한 정보는 여기에서 참조하실 수 있습니다. [C++] STL sort 함수 사용법기본 사용법 sort 함수는 지정된 범위에 있는 요소를 기본적인 오름차순 또는 지정한 정렬 기준에 따라 정렬합니다. sort 함수를 사용하기 위해서는 우선 헤더파일을 ..

2024. 4. 17.

문제 풀이/백준 (BOJ)

[백준/BOJ] 18870번: 좌표 압축 - C++ 문제 풀이

문제 설명 문제 링크:  https://www.acmicpc.net/problem/18870 풀이처음에는 다른 방식으로 풀었다가 "시간 초과"를 받고 문제가 무엇인지 한참 생각한 문제입니다.제출한 코드를 위의 입력 예시 정도의 데이터로 검토하는 것이 아닐까라고 간단히 생각했는데 그렇지 않은 모양입니다. 이 문제는 입력된 숫자보다 작은 숫자들의 개수를 구하는 문제이다. 그런데 작은 숫자들이 중복된 경우 하나의 숫자로 카운트한다. 예를 들어보면4332221숫자 4에 대한 정답은 3이다. 왜냐하면 숫자 3가 2회 나오지만 1회로 카운트한다. 마찬가지로 숫자 2도 1회로 카운트, 마지막 숫자 1도 1회로 카운트돼서 모두 3이다. 4보다 작으면서 서로 다른 숫자의 개수를 4에 대한 값으로 출력하면 된다.마찬가지로..

2024. 4. 16.

문제 풀이/백준 (BOJ)

[백준/BOJ] 2798번, 2839번: 브루트 포스 - C++ 문제 풀이

● 2798번: 블랙잭 문제 설명 문제 링크: https://www.acmicpc.net/problem/2798 2798번: 블랙잭 첫째 줄에 카드의 개수 N(3 ≤ N ≤ 100)과 M(10 ≤ M ≤ 300,000)이 주어진다. 둘째 줄에는 카드에 쓰여 있는 수가 주어지며, 이 값은 100,000을 넘지 않는 양의 정수이다. 합이 M을 넘지 않는 카드 3장 www.acmicpc.net 풀이 너무 어렵게 생각할 필요 없다. 브루트 포스 방식으로 문제를 푸는 것이므로 모든 가능성이 있는 경우를 찾아서 합을 구하고, 지정된 값과 가장 가깝다면 리턴하는 문제이다. 그럼 첫 번째 카드 a번째 카드라고 하고, 두 번째 카드를 b번째 카드, 세 번째 카드를 c번째 카드라고 했을 때 항상 a < b < c 순서가 ..

2024. 4. 11.

문제 풀이/백준 (BOJ)

[백준/BOJ] 10951번: A+B -4 -C++ 문제 풀이

문제 설명 문제 링크: https://www.acmicpc.net/problem/10951 10951번: A+B - 4두 정수 A와 B를 입력받은 다음, A+B를 출력하는 프로그램을 작성하시오.www.acmicpc.net 풀이문제만 읽었을 때는 구체적으로 원하는 것을 명확히 알기 어려웠다. 이 문항이 "단계별로 풀어보기"의 "반복문" 단계에 속해 있다는 것을 확인하고서야 방향을 잡을 수 있었다. 입력이 끝날 때까지 한 번에 두 개씩 정수를 읽어 합을 구한 후 출력하는 문제이다.입력이 끝나는 시점이 언제인가를 알아낼 수 있다면 문제는 아주 간단하다.int nReaded = 0, A, B;while(true){ nReaded = scanf("%d %d", &A, &B); if (nReaded == 2){ ..

2024. 4. 8.

문제 풀이/백준 (BOJ)

[백준/BOJ] 2581번: 소수 - C++ 문제 풀이

문제 설명 문제 링크: http://www.acmicpc.net/problem/2581 2581번: 소수 M이상 N이하의 자연수 중 소수인 것을 모두 찾아 첫째 줄에 그 합을, 둘째 줄에 그 중 최솟값을 출력한다. 단, M이상 N이하의 자연수 중 소수가 없을 경우는 첫째 줄에 -1을 출력한다. www.acmicpc.net 풀이 정의를 보면 소수는 1보다 큰 자연수 중 1과 자기 자신만을 약수로 가지는 수이다. 이 정의에 따라 소수를 구하는 함수를 만들고, 메인 함수에서 M부터 N까지 루프를 거치면서 소수면 총합에 더하고, 현재 가장 작은 소수보다 더 작으면 최소 소수를 갱신하면 되는 문제이다. 그런데 작은 수부터 소수 검사를 하면 최소 소수를 찾기 위해 비교하는 코드가 필요하므로 큰 수부터 검사하는 게 ..

2024. 4. 4.