코딩테스트

[백준] 단어 수학

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 ++ 을 함..

[백준] 부분합

https://www.acmicpc.net/problem/1806 1806번: 부분합 첫째 줄에 N (10 ≤ N < 100,000)과 S (0 < S ≤ 100,000,000)가 주어진다. 둘째 줄에는 수열이 주어진다. 수열의 각 원소는 공백으로 구분되어져 있으며, 10,000이하의 자연수이다. www.acmicpc.net 우선 문제부터 간단하게 요약하면, 길이 N의 수열이 주어질 때, 이 수열에서 연속된 수들의 부분합 중 그 합이 S 이상이 되는 것중 가장 짧은 것의 길이를 출력해야 하는 문제입니다. 어렵지 않은 투포인터와 누적합을 이용하는 문제입니다. 실제 구현은 아래와 같습니다. 주의 해야 하는 점은 만약 합을 만들지 못하는 경우 0 을 출력해야 한다는 점만 주의해서 코드를 구성하면 됩니다. #i..