전체 글

[백준] 로또

https://www.acmicpc.net/problem/6603 6603번: 로또 입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스는 한 줄로 이루어져 있다. 첫 번째 수는 k (6 < k < 13)이고, 다음 k개 수는 집합 S에 포함되는 수이다. S의 원소는 오름차순으로 www.acmicpc.net 우선 문제부터 간단하게 요약하면, k 값과 k개의 숫자가 주어지면 여기에서 6개를 뽑는 가짓수를 사전순으로 출력해야 하는 문제입니다. 기본적인 combination문제이므로 뽑거나 뽑지 않거나를 dfs를 사용하여 구현하면 됩니다. 아래의 풀이에서 추가해도 되는 부분은, 만약 남은 것들을 모두 뽑아도 6개를 뽑지 못하는 경우 더이상 상태 발전을 하지 않도록 구현이 가능할 듯 합니다. 하지..

[백준] 단어 수학

https://www.acmicpc.net/problem/1339 1339번: 단어 수학 첫째 줄에 단어의 개수 N(1 ≤ N ≤ 10)이 주어진다. 둘째 줄부터 N개의 줄에 단어가 한 줄에 하나씩 주어진다. 단어는 알파벳 대문자로만 이루어져있다. 모든 단어에 포함되어 있는 알파벳은 최대 www.acmicpc.net 우선 문제부터 간단하게 요약하면, 단어들이 주어지게 되는데, 이 단어들은 알파벳으로 주어지게 됩니다. 이 알파벳에 0~9 까지의 숫자들을 매핑시켜서 합이 최대가 되도록 하면 되는 문제입니다. 우선, 당연히 높은 자리 숫자에 큰 값이 들어 가야한다는 아이디어에서 출발해야 합니다. 그래서 input을 받을 때, 단어마다 각각의 가중치를 계산합니다. 예를 들면, ABC가 input으로 들어오게 되..

[백준] 부등호

https://www.acmicpc.net/problem/2529 2529번: 부등호 여러분은 제시된 부등호 관계를 만족하는 k+1 자리의 최대, 최소 정수를 첫째 줄과 둘째 줄에 각각 출력해야 한다. 단 아래 예(1)과 같이 첫 자리가 0인 경우도 정수에 포함되어야 한다. 모든 입력 www.acmicpc.net 우선 문제부터 간단하게 요약하면, 부등호 k개가 주어지면, 해당 부등호 사이 사이에 0~9 사이의 숫자를 넣어 부등호 관계가 성립하도록 하는 최대 정수와 최소 정수를 구해야 하는 문제입니다. 최대와 최소를 구해야 하므로, 숫자를 어떻게 뽑아도 무조건 만족하는 것이 있을 것이기 때문에 최대는 9부터 감소시키면서 총 k+1개의 숫자로, 최소는 0부터 증가시키면서 k+1개의 숫자를 사용하여 구하면 되..

[LeetCode] Zigzag Conversion

https://leetcode.com/problems/zigzag-conversion/ Zigzag Conversion - LeetCode Can you solve this real interview question? Zigzag Conversion - The string "PAYPALISHIRING" is written in a zigzag pattern on a given number of rows like this: (you may want to display this pattern in a fixed font for better legibility) P A H N A P L S I I leetcode.com 우선 문제부터 간단하게 요약하면, 주어진 string을 주어진 row 수만큼의 범위 내에서..

[LeetCode] Path Sum II

https://leetcode.com/problems/path-sum-ii/description/ Path Sum II - LeetCode Can you solve this real interview question? Path Sum II - Given the root of a binary tree and an integer targetSum, return all root-to-leaf paths where the sum of the node values in the path equals targetSum. Each path should be returned as a list of the n leetcode.com 우선 문제부터 간단하게 요약하면, binary tree가 주어지면, 해당 트리의 root부..

[백준] 3의 배수

https://www.acmicpc.net/problem/1769 1769번: 3의 배수 문제가 잘 풀리지 않을 때, 문제를 바라보는 시각을 조금만 다르게 가지면 문제가 쉽게 풀리는 경험을 종종 해 보았을 것이다. 여러 가지 방법이 있지만 그 중 하나로 우리가 풀고 싶은 문제를 www.acmicpc.net 우선 문제부터 간단하게 요약하면, 3의 배수 판별법으로 1~1,000,000 자리수를 판별하려 할 때, 몇번의 변환이 일어나는가에 대한 문제입니다. 우선 input으로 들어오는 1백만 자리 숫자는 int 뿐만 아니라 long long 등의 자료구조로도 커버할 수 없습니다. 그래서 이 input을 한번 변환을 거쳐 int등으로 바꾼 다음 처리를 하면 됩니다. 실제 구현은 아래와 같습니다. #include..

[백준] 줄 세우기

https://www.acmicpc.net/problem/2252 2252번: 줄 세우기 첫째 줄에 N(1 ≤ N ≤ 32,000), M(1 ≤ M ≤ 100,000)이 주어진다. M은 키를 비교한 회수이다. 다음 M개의 줄에는 키를 비교한 두 학생의 번호 A, B가 주어진다. 이는 학생 A가 학생 B의 앞에 서야 한다는 의 www.acmicpc.net 우선 문제부터 간단하게 요약하면, 학생들을 줄 세우는데, 두 학생의 키 비교 결과만 주어질 때, 해당 모든 조건을 만족하도록 학생들을 줄세워 출력하는 문제입니다. 전형적인 위상정렬의 문제로 위상정렬을 구현하면 됩니다. 실제 구현은 아래와 같습니다. #include #include using namespace std; int N, M; queue nodeQ..

[백준] 용액

https://www.acmicpc.net/problem/2467 2467번: 용액 첫째 줄에는 전체 용액의 수 N이 입력된다. N은 2 이상 100,000 이하의 정수이다. 둘째 줄에는 용액의 특성값을 나타내는 N개의 정수가 빈칸을 사이에 두고 오름차순으로 입력되며, 이 수들은 모두 - www.acmicpc.net 우선 문제부터 간단하게 요약하면, -1,000,000,000 ~ 1,000,000,000 의 범위를 가지는 숫자들이 정렬되어 구성된 순열이 주어지면, 해당 순열의 두 수를 더해서 0과 가장 가까운 경우가 되는 경우를 출력해야 하는 문제입니다. 투포인터 알고리즘을 이용하여, 만약 현재 양쪽의 값을 더했을 때, 양수라면 right pointer --, 음수라면 left pointer ++ 을 함..