msmn

알고리즘 분류: 문자열, 그리디, 수학 문제 링크: www.acmicpc.net/problem/1541 1541번: 잃어버린 괄호 첫째 줄에 식이 주어진다. 식은 ‘0’~‘9’, ‘+’, 그리고 ‘-’만으로 이루어져 있고, 가장 처음과 마지막 문자는 숫자이다. 그리고 연속해서 두 개 이상의 연산자가 나타나지 않고, 5자리보다 www.acmicpc.net '-' 기호가 나온 후 모든 연산을 '-'로 해주면 최솟값이 되기 때문에 sign으로 체크해주었다. #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include..

알고리즘 분류: 브루트포스 문제 링크: www.acmicpc.net/problem/2231 2231번: 분해합 어떤 자연수 N이 있을 때, 그 자연수 N의 분해합은 N과 N을 이루는 각 자리수의 합을 의미한다. 어떤 자연수 M의 분해합이 N인 경우, M을 N의 생성자라 한다. 예를 들어, 245의 분해합은 256(=245+2+4+5)이 www.acmicpc.net #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #define ll long long #define INF 1e9 usi..

알고리즘 분류: 브루트포스, 백트래킹, 순열 문제 링크: www.acmicpc.net/problem/2798 2798번: 블랙잭 첫째 줄에 카드의 개수 N(3 ≤ N ≤ 100)과 M(10 ≤ M ≤ 300,000)이 주어진다. 둘째 줄에는 카드에 쓰여 있는 수가 주어지며, 이 값은 100,000을 넘지 않는 양의 정수이다. 합이 M을 넘지 않는 카드 3장 www.acmicpc.net 3중 포문으로 브루트포스를 구현해도 풀리는 문제이다. 백트래킹과 순열 2가지로 문제를 풀었다. 1. 백트래킹 #include #include #include #include #include #include #include #include #include #include #include #include #include #in..

알고리즘 분류: 기하학, 수학 문제 링크: www.acmicpc.net/problem/1002 1002번: 터렛 각 테스트 케이스마다 류재명이 있을 수 있는 위치의 수를 출력한다. 만약 류재명이 있을 수 있는 위치의 개수가 무한대일 경우에는 -1을 출력한다. www.acmicpc.net 두 원의 6가지 관계를 고려한다. [경우의 수] 1. 일치: -1 2. 멀리 떨어짐: 0 3. 외접: 1 4. 내접: 1 5. 두점: 2 6. 큰 원 내부에 작은 원이 있고 겹치지 않음: 0 총 6가지 경우의 수로 나누어 푼다. 5, 6번 처리가 실수하기 쉬우므로 주의할 것! #include #include #include #include #include #include #include #include #include #..

알고리즘 분류: DP 문제 링크: www.acmicpc.net/problem/2579 2579번: 계단 오르기 계단 오르기 게임은 계단 아래 시작점부터 계단 꼭대기에 위치한 도착점까지 가는 게임이다. 과 같이 각각의 계단에는 일정한 점수가 쓰여 있는데 계단을 밟으면 그 계단에 쓰여 있는 점 www.acmicpc.net dp[a][b]: "현재 b개의 계단을 연속해서 밟고 마지막 계단이 a일 때 최대합"이라 정의하여 풀었다. #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #defin..

분류: 백트래킹, 순열 문제: www.acmicpc.net/problem/15650 15650번: N과 M (2) 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해 www.acmicpc.net 2가지 방식으로 풀었다. 1번은 백트래킹, 2번은 순열 C++의 next_permutation을 활용한 풀이 1. 백트래킹 #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include ..

분류: 재귀, 분할정복 문제: www.acmicpc.net/problem/2630 2630번: 색종이 만들기 첫째 줄에는 전체 종이의 한 변의 길이 N이 주어져 있다. N은 2, 4, 8, 16, 32, 64, 128 중 하나이다. 색종이의 각 가로줄의 정사각형칸들의 색이 윗줄부터 차례로 둘째 줄부터 마지막 줄까지 주어진다. www.acmicpc.net #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #define ll long long #define INF 1e9 using nam..

분류: 정렬, 맵 문제: www.acmicpc.net/problem/2108 2108번: 통계학 첫째 줄에 수의 개수 N(1 ≤ N ≤ 500,000)이 주어진다. 그 다음 N개의 줄에는 정수들이 주어진다. 입력되는 정수의 절댓값은 4,000을 넘지 않는다. www.acmicpc.net 최빈값 처리를 위해 맵에 숫자/빈도수를 저장해주고 pair 벡터로 옮겨서 빈도수로 정렬해주었다. 이 때, 같은 빈도수가 있다면 두 번째로 작은 수를 출력하도록 했다. #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include ..

분류: 그래프 탐색 문제: www.acmicpc.net/problem/1260 1260번: DFS와 BFS 첫째 줄에 정점의 개수 N(1 ≤ N ≤ 1,000), 간선의 개수 M(1 ≤ M ≤ 10,000), 탐색을 시작할 정점의 번호 V가 주어진다. 다음 M개의 줄에는 간선이 연결하는 두 정점의 번호가 주어진다. 어떤 두 정점 사 www.acmicpc.net 방문할 수 있는 정점이 여러 개인 경우 정점 번호를 작은 것부터 방문하므로 구현의 편의를 위해 인접행렬을 활용했다. #include #include #include #include #include #include #include #include #include #include #include #include #include #include #inc..

분류: 문자열, 트라이(Trie), 정렬, 해시맵 문제: www.acmicpc.net/problem/5052 5052번: 전화번호 목록 첫째 줄에 테스트 케이스의 개수 t가 주어진다. (1 ≤ t ≤ 50) 각 테스트 케이스의 첫째 줄에는 전화번호의 수 n이 주어진다. (1 ≤ n ≤ 10000) 다음 n개의 줄에는 목록에 포함되어 있는 전화번호가 www.acmicpc.net 3가지 방법으로 풀어본 문제이다. 정렬을 사용한 방식이 가장 효율성이 높았다. 1. 정렬 #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #..