일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
1 | 2 | 3 | 4 | 5 | 6 | |
7 | 8 | 9 | 10 | 11 | 12 | 13 |
14 | 15 | 16 | 17 | 18 | 19 | 20 |
21 | 22 | 23 | 24 | 25 | 26 | 27 |
28 | 29 | 30 | 31 |
- 재귀
- backtracking
- Greedy
- 너비우선탐색
- 백트래킹
- BOJ
- stack
- acm
- 알고리즘문제해결전략
- DFS
- 세그먼트트리
- 다이나믹프로그래밍
- BFS
- 스택
- 알고스팟
- 누적합
- DP
- priority_queue
- 완전탐색
- 이분탐색
- 유니온파인드
- 분리집합
- 종만북
- 그리디
- 문자열
- 분할정복
- 동적계획법
- Algospot
- union-find
- 백준
- Today
- Total
목록Problem Solving/BOJ 문제풀이 (34)
DAMPER's blog
https://www.acmicpc.net/problem/2162 2162번: 선분 그룹 첫째 줄에 N(1 ≤ N ≤ 3,000)이 주어진다. 둘째 줄부터 N+1번째 줄에는 양 끝점의 좌표가 x1, y1, x2, y2의 순서로 주어진다. 각 좌표의 절댓값은 5,000을 넘지 않으며, 입력되는 좌표 사이에는 빈칸이 하 www.acmicpc.net 문제 설명 선분의 양끝의 점 2개를 N번 입력받고 선분끼리 만나면 선분 그룹안에 속한다고 한다. 이 때, 선분 그룹의 갯수와 크기가 가장 큰 그룹의 선분 갯수를 출력하면 된다. 여기서 필요한 것은 두 선분이 만나는 것을 체크하는 것과 그룹을 만드는 것이다. 두 선분이 만나는지 아닌지를 판단하는 CCW와 그룹을 만드는 Disjoint-Set을 사용했다. 평소에 Di..
https://www.acmicpc.net/problem/16724 16724번: 피리 부는 사나이 첫 번째 줄에 지도의 행의 수를 나타내는 N(1 ≤ N ≤ 1,000)과 지도의 열의 수를 나타내는 M(1 ≤ M ≤ 1,000)이 주어진다. 두 번째 줄부터 N개의 줄에 지도의 정보를 나타내는 길이가 M인 문자열이 주 www.acmicpc.net 문제 설명 바닥에 쓰여진 방향대로만 움직일 수 있으며, 해당 방향으로 이동했을 때 이루어지는 사이클 또는 집합의 개수를 구하는 문제이다. Union-Find 자료구조를 이용해서 문제를 풀 수 있다. 모든 node를 돌면서 해당 방향으로 움직였을 때의 위치를 이미 방문한 곳이라면 merge()를 통해 병합 후 다른 노드로 이동한다. 처음 방문한 곳이 아니라면 병합..
https://www.acmicpc.net/problem/9527 9527번: 1의 개수 세기 두 자연수 A, B가 주어졌을 때, A ≤ x ≤ B를 만족하는 모든 x에 대해 x를 이진수로 표현했을 때 1의 개수의 합을 구하는 프로그램을 작성하시오. 즉, f(x) = x를 이진수로 표현 했을 때 1의 개수라 www.acmicpc.net 문제 설명 두 자연수 A, B가 주어졌을 때, A부터 B까지의 수에 대해 2진수로 표현했을 때 1의 개수의 합을 구하는 문제이다. 문제에 따르면, \( f(x) \) 를 다음과 같이 정의할 수 있다. => \( x \)를 이진수로 표현했을 때 1의 개수 문제에서 원하는 값은 다음 식의 결과이다. \( \sum_{x=A}^Bf(x) \) A부터 B까지 모든 자연수에 대한 \..
https://www.acmicpc.net/problem/2342 2342번: Dance Dance Revolution 입력은 지시 사항으로 이루어진다. 각각의 지시 사항은 하나의 수열로 이루어진다. 각각의 수열은 1, 2, 3, 4의 숫자들로 이루어지고, 이 숫자들은 각각의 방향을 나타낸다. 그리고 0은 수열의 마 www.acmicpc.net 문제 설명 중앙(0), 상(1), 하(3), 좌(2), 우(4)로 된 발판이 있다. 두 발이 같은 지점에 있는 것을 불가능하다. 처음에 양발이 모두 중앙에 위치하고, 발을 이동시킬 때마다 cost가 발생한다. 중앙에서 네방향으로 갈 때 = 2 인접한 발판으로 갈 때 = 3 반대편 발판으로 갈때 = 4 그리고 같은 지점을 한번 더 누를 때는 1 cost가 발생한다...
https://www.acmicpc.net/problem/4386 4386번: 별자리 만들기 도현이는 우주의 신이다. 이제 도현이는 아무렇게나 널브러져 있는 n개의 별들을 이어서 별자리를 하나 만들 것이다. 별자리의 조건은 다음과 같다. 별자리를 이루는 선은 서로 다른 두 별을 일 www.acmicpc.net 문제 설명 N개의 별에 대한 (x, y) 좌표가 있다. 이 별들을 직선으로 이어 별자리를 만든다고 한다. 별자리를 만들 때는 다음 조건을 따른다. 별자리를 이루는 선은 서로 다른 두 별을 일직선으로 이은 형태이다. 모든 별들은 별자리 위의 선을 통해 서로 직/간접적으로 이어져 있어야 한다 선을 하나 이을 때마다 두 별 사이의 거리만큼의 비용이 든다고 할 때, 별자리를 만드는 최소 비용을 구하시오. ..
https://www.acmicpc.net/problem/17425 17425번: 약수의 합 두 자연수 A와 B가 있을 때, A = BC를 만족하는 자연수 C를 A의 약수라고 한다. 예를 들어, 2의 약수는 1, 2가 있고, 24의 약수는 1, 2, 3, 4, 6, 8, 12, 24가 있다. 자연수 A의 약수의 합은 A의 모든 약수를 더 www.acmicpc.net 어떤 수 \( x\) 의 약수의 합을 구하는 함수를 \( f(x)\) 라 하자. \( x\)보다 작거나 같은 수들의 약수의 합들을 모두 더한 수를 구하는 함수를 \( g(x)\)라 하자. \( g(x) = \sum_{k=1}^x f(k) \) 자연수 \( N\)이 주어졌을 때, \( g(N) \)을 구하는 문제이다. naive한 방법으로 문제..