알고리즘/문제풀이 (50) 썸네일형 리스트형 [백준] Q16724 피리 부는 사나이 JAVA https://www.acmicpc.net/problem/16724 16724번: 피리 부는 사나이 첫 번째 줄에 지도의 행의 수를 나타내는 N(1 ≤ N ≤ 1,000)과 지도의 열의 수를 나타내는 M(1 ≤ M ≤ 1,000)이 주어진다. 두 번째 줄부터 N개의 줄에 지도의 정보를 나타내는 길이가 M인 문자열이 주 www.acmicpc.net 1. 문제의 유형 및 이해 그래프 탐색, disjoint set 맵을 벗어나지 않고 맵에 적힌 방향으로 계속해서 움직이는 회원들을 위해 SAFEZONE을 설치하여 어느구역에 있더라도 SAFEZONE으로 들어가 더이상 움직이지 않게 하고 싶다. SAFE ZONE의 최소 개수를 구하는 문제 맵을 벗어나지 않고 계속해서 움직이는 어떠한 cycle이 존재한다. cycl.. [백준] Q12100 2048(Easy) JAVA https://www.acmicpc.net/problem/12100 12100번: 2048 (Easy) 첫째 줄에 보드의 크기 N (1 ≤ N ≤ 20)이 주어진다. 둘째 줄부터 N개의 줄에는 게임판의 초기 상태가 주어진다. 0은 빈 칸을 나타내며, 이외의 값은 모두 블록을 나타낸다. 블록에 쓰여 있는 수는 2 www.acmicpc.net 1. 문제의 유형 및 이해 구현, 완전탐색, 시뮬레이션 유행했던 2048 게임을 구현하는 문제이다. 문제에서 주어진 조건들을 생각하며 순차적으로 구현한다. 최대 5번 이동해서 만들 수 있는 가장 큰 블록의 값을 구하는 프로그램을 작성하자. 한 번 이동시 4회의 이동을 가진다. 최대 5번이기 때문에 45=1024 안에 해결이 가능하다. 2. 문제 접근 방법 문제.. [백준] Q12015 가장 긴 증가하는 부분수열 2 JAVA https://www.acmicpc.net/problem/12015 12015번: 가장 긴 증가하는 부분 수열 2 첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ Ai ≤ 1,000,000) www.acmicpc.net 1. 문제의 유형 및 이해 이분탐색 유명한 LIS(Longest Increasing Subsequence) 알고리즘 입니다. 주어진 수열에서 가장 긴 증가하는 부분 수열을 찾으면 됩니다. 알려진 방법으로 LIS알고리즘을 푸는 방법은 크게 3가지 dp, 이분탐색, segment tree가 있습니다. dp의 경우 O(N2) 으로 N의 범위가 커진다면 해결하는데 어려움이 있습니다. https://.. [백준] Q10775 공항 JAVA https://www.acmicpc.net/problem/10775 10775번: 공항 예제 1 : [2][?][?][1] 형태로 도킹시킬 수 있다. 3번째 비행기는 도킹시킬 수 없다. 예제 2 : [1][2][3][?] 형태로 도킹 시킬 수 있고, 4번째 비행기는 절대 도킹 시킬 수 없어서 이후 추가적인 도킹은 불 www.acmicpc.net 1. 문제의 유형 및 이해 그리디, disjoint set 공항에는 G개의 게이트가 있고 1부터 G까지 번호를 가진다. P개의 비행기가 '순서대로' 도착하고, i번째 비행기를 1번부터 g번 게이트 중 하나에 영구적으로 도킹하려고 한다. 비행기가 도킹할 수 없다면 공항이 폐쇄되고, 이후 어떤 비행기도 도착할 수 없다. 가장 많은 비행기를 도킹시키고자 할 때 최대 몇.. [백준] Q9527 1의 개수 세기 JAVA https://www.acmicpc.net/problem/9527 9527번: 1의 개수 세기 두 자연수 A, B가 주어졌을 때, A ≤ x ≤ B를 만족하는 모든 x에 대해 x를 이진수로 표현했을 때 1의 개수의 합을 구하는 프로그램을 작성하시오. 즉, f(x) = x를 이진수로 표현 했을 때 1의 개수라 www.acmicpc.net 1. 문제의 유형 및 이해 bitmasking, dp, 누적합 f(x) = x를 이진수로 표현했을 때 1의 개수. $A [백준] Q1647 도시 분할 계획 JAVA https://www.acmicpc.net/problem/1647 1647번: 도시 분할 계획 첫째 줄에 집의 개수 N, 길의 개수 M이 주어진다. N은 2이상 100,000이하인 정수이고, M은 1이상 1,000,000이하인 정수이다. 그 다음 줄부터 M줄에 걸쳐 길의 정보가 A B C 세 개의 정수로 주어지는데 A번 www.acmicpc.net 1. 문제의 유형 및 이해 최소 스패닝 트리 마을 N개의 집과 그 집들을 연결하는 M개의 길로 이루어져 있다. 길은 어느방향이든 다닐 수 있고, 각 길마다 유지하는데 유지비가 든다 -> Undirected Weighted graph 마을을 분할 하고자 한다. 마을 분할할때는, 각 분리된 마을 안에 집들이 서로 연결되어야 한다. (모든 노드들이 연결되어야 한다 .. [백준] Q1806 부분합 JAVA https://www.acmicpc.net/problem/1806 1806번: 부분합 첫째 줄에 N (10 ≤ N < 100,000)과 S (0 < S ≤ 100,000,000)가 주어진다. 둘째 줄에는 수열이 주어진다. 수열의 각 원소는 공백으로 구분되어져 있으며, 10,000이하의 자연수이다. www.acmicpc.net 1. 문제의 유형 및 이해 투포인터 10,000이하 자연수로 이루어진 길이 N자리 수열이 주어진다. 이 수열에서 연속된 수들의 부분합 중에서 그 합이 S이상이 되는 것 중 가장짧은 길이를 구하는 프로그램 $10 이전 1 2 3 4 5 6 ··· 8 다음 목록 더보기