코딩테스트/C++ 문제풀이

[LeetCode] Construct Binary Tree from Preorder and Inorder Traversal

https://leetcode.com/problems/construct-binary-tree-from-preorder-and-inorder-traversal/description/ Construct Binary Tree from Preorder and Inorder Traversal - LeetCode Construct Binary Tree from Preorder and Inorder Traversal - Given two integer arrays preorder and inorder where preorder is the preorder traversal of a binary tree and inorder is the inorder traversal of the same tree, construct..

[LeetCode] 3Sum Closest

https://leetcode.com/problems/3sum-closest/description/ 3Sum Closest - LeetCode 3Sum Closest - Given an integer array nums of length n and an integer target, find three integers in nums such that the sum is closest to target. Return the sum of the three integers. You may assume that each input would have exactly one solution. Examp leetcode.com 우선 문제부터 간단하게 요약하면, 숫자들이 주어지면, 해당하는 숫자들중 3개를 더해서 tar..

[백준] N과 M (9)

https://www.acmicpc.net/problem/15663 15663번: N과 M (9) 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해 www.acmicpc.net 문제부터 요약하면, N개의 숫자가 주어질 때, 조건에 알맞게 M개를 뽑아서 사전순으로 출력해야 합니다. 이 문제의 조건은 중복되는 수열이 없도록 출력해야 하는 것이 조건이였습니다. 일반적인 DFS의 로직에서 used 배열을 두어서 각 숫자마다 사용 가능 횟수를 체크해서 사용 가능한 경우에만 상태 발전이 이루어지도록 하여 구현하였습니다. 실제 구현은 아래와 같습니다. #include #includ..

[백준] Java vs C++

https://www.acmicpc.net/problem/3613 3613번: Java vs C++ Java 예찬론자 김동규와 C++ 옹호가 김동혁은 서로 어떤 프로그래밍 언어가 최고인지 몇 시간동안 토론을 하곤 했다. 동규는 Java가 명확하고 에러가 적은 프로그램을 만든다고 주장했고, 동혁이는 www.acmicpc.net String parsing문제입니다. 우선 문제부터 요약하면, java와 c++의 naming 규칙에 따라 지어진 변수 이름을 서로 변환 하는 코드를 작성해야 합니다. 이 때, 변수 이름이 두 언어의 변수 명명 조건과 어긋나는 경우엔 Error를 출력해야 합니다. 생각 보다 조건들을 많이 생각해야 해서 까다로운데, 반례 게시글에 있듯이 이 조건들에 주의해서 코딩을 해야 합니다. //..

[백준] N과 M (12)

https://www.acmicpc.net/problem/15666 15666번: N과 M (12) 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해 www.acmicpc.net 문제부터 간단하게 요약하면, 중복 조합으로 숫자를 M개 뽑아서 오름차순으로 출력해야 하는 문제였습니다. DFS를 이용하여 구현하였습니다. 코드는 아래와 같습니다. #include #include #include using namespace std; int N, M; int num_array[10]; int num_array_[10]; int print_num[10]; int cur_index;..

[백준] 마라톤 1

https://www.acmicpc.net/problem/10655 10655번: 마라톤 1 젖소 박승원은 2번째 혹은 3번째 체크포인트를 건너뛸 수 있는데, 여기서 두 번째 체크포인트를 건너뛸 경우 경로는 (0,0) -> (11,-1) -> (10,0) 이 되며 거리는 14이다. 박승원은 이것보다 더 짧게 달릴 www.acmicpc.net 우선 문제부터 간단하게 요약하면, 출발지에서 도착지까지 체크포인트를 순서대로 거쳐서 가는데, 한 체크포인트를 건너뛰고 도착지로 갈 때, 최단 경로가 몇이 나오는지를 구해야 합니다. 각각의 체크포인트 사이의 구간을 구하고, 한 구간을 건너 뛰었을 때의 구간사이의 거리를 구해서 얼마나 줄어드는지를 계산해서 최대로 줄어드는 경우를 구하는 방식으로 계산하였습니다. 실제 구현..

[백준] 공주님의 정원

https://www.acmicpc.net/problem/2457 2457번: 공주님의 정원 첫째 줄에는 꽃들의 총 개수 N (1 ≤ N ≤ 100,000)이 주어진다. 다음 N개의 줄에는 각 꽃이 피는 날짜와 지는 날짜가 주어진다. 하나의 날짜는 월과 일을 나타내는 두 숫자로 표현된다. 예를 들어서, www.acmicpc.net 우선 문제부터 간단하게 요약하면, 꽃들의 피고 지는 시간이 주어졌을 때, 문제에서 준 정원에 특정 시기동안 꽃이 최소 하나이상 피어있도록 하는 최소 꽃의 갯수를 구해야 하는 문제입니다. 피는 날짜를 기준으로 꽃들을 정렬해 놓고, 처음엔 피는 날짜가 3월 1일 보다 작거나 같은 꽃들에 대해 지는 날짜가 가장 긴 꽃을 골라주고, 이후엔 이전에 골랐던 꽃이 지는날 다음날에 대해 3월..

[백준] 경비원

https://www.acmicpc.net/problem/2564 2564번: 경비원 첫째 줄에 블록의 가로의 길이와 세로의 길이가 차례로 주어진다. 둘째 줄에 상점의 개수가 주어진다. 블록의 가로의 길이와 세로의 길이, 상점의 개수는 모두 100이하의 자연수이다. 이어 한 줄 www.acmicpc.net 우선 문제부터 요약하면, 직사각형 모양의 땅의 가장 바깥 경계에 동근이가 근무를 서고, 경계에 상점들 또한 존재합니다. 동근이와 상점들 사이의 최단거리의 합을구해야 하는 문제입니다. 원탁모양이라고 생각해서, 좌상단을 0, 그리고 시계방향으로 0, 1, 2, 3 등으로 숫자가 매핑될 수 있도록 하였습니다. 그렇게 각각의 좌표들을 변환 시킨 후, 양 방향으로 이동하는 거리중 최솟값을 뽑아서 계속 더해주는 ..