전체 글

[백준] IOIOI

https://www.acmicpc.net/problem/5525 5525번: IOIOI N+1개의 I와 N개의 O로 이루어져 있으면, I와 O이 교대로 나오는 문자열을 PN이라고 한다. P1 IOI P2 IOIOI P3 IOIOIOI PN IOIOI...OI (O가 N개) I와 O로만 이루어진 문자열 S와 정수 N이 주어졌을 때, S안에 PN이 몇 www.acmicpc.net 우선 문제부터 요약하면, I와 O로만 이루어진 문자열이 주어질 때, 해당 문자열에서 IOI가 반복되는 패턴을 반복수에 따라 P1, P2등으로 정의할 때, PN이 주어진 문자열에서 몇번 등장하는지 카운팅을 하는 문제입니다. 일단 문자열의 길이가 100만개 까지 가능하기 때문에 O(N)이나 O(NlogN) 정도 까지의 복잡도만 사용이..

[백준] Σ

https://www.acmicpc.net/problem/13172 13172번: Σ 모듈러가 11에서 1,000,000,007이 되어 답이 달라졌지만, 역시 3을 곱한 다음 1,000,000,007으로 나눈 나머지는 7이 된다. www.acmicpc.net 우선 문제부터 요약하면, 기약 분수들을 여러개 더하게 되면 통분 등으로 인해 분모등이 원하는 범위 안에서 유지되도록 관리하기가 어렵습니다. 그래서 페르마 소정리를 이용한 역원을 통해 다르게 표현하여 좀더 간단하게 더하려고 하는데, 이렇게 다르게 표현한 것들을 더한 결과를 구하는 문제입니다. 실제로 문제를 한번 읽어보는 것이 정확합니다. 사실 수학적인 지식 보다는 문제에서 무엇을 우리에게 구하라고 이야기하는 지만 정확하게 파악하면 되는 문제입니다. 문..

[백준] 파이프 옮기기 1

https://www.acmicpc.net/problem/17070 17070번: 파이프 옮기기 1 유현이가 새 집으로 이사했다. 새 집의 크기는 N×N의 격자판으로 나타낼 수 있고, 1×1크기의 정사각형 칸으로 나누어져 있다. 각각의 칸은 (r, c)로 나타낼 수 있다. 여기서 r은 행의 번호, c는 열의 www.acmicpc.net DP를 이용하는 문제입니다. 우선 문제부터 간단하게 요약하면, 문제에서 주어진 규칙대로 파이프를 움직여서 파이프의 한쪽 끝이 가장 오른쪽 아래에 올 때까지 이동시켜야 합니다. 이 때, 목표 지점에 도달할 수 있는 경우의 수를 return 해야하는 문제입니다. 특정 칸에 도달할 때, 어떤 방식을 통해 도달하는지를 이용해 dp table을 구성하면 됩니다. 무슨 이야기인지 그..

[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;..