본문 바로가기

전체 글

 (73)
[백준] Q1562 계단 수 JAVA https://www.acmicpc.net/problem/1562 1562번: 계단 수 첫째 줄에 정답을 1,000,000,000으로 나눈 나머지를 출력한다. www.acmicpc.net 1. 문제의 유형 및 이해 비트마스킹, dp, bitmasking을 이용한 dp 수의 인접한 모든 자리의 차이가 1인 수를 계단수라고 한다. N이 주어질 때, 길이가 N이면서 0부터 9까지 숫자가 모두 등장하는 계단수는 총 몇개인가? 0으로 시작하는 수는 계단수가 아니다. 처음에 dp로 접근하기는 용이할 수 있는 문제라고 생각한다. 앞자리가 x이고 길이가 N인 계단수라면, 앞자리가 x-1 또는 x+1이고 길이가 N-1인 계단수 라고 생각이 가능하고 dp[앞자리][길이] = dp[앞자리-1][길이] + dp[앞자리 +1]..
[백준] Q1799 비숍 JAVA https://www.acmicpc.net/problem/1799 1799번: 비숍 첫째 줄에 체스판의 크기가 주어진다. 체스판의 크기는 10이하의 자연수이다. 둘째 줄부터 아래의 예와 같이 체스판의 각 칸에 비숍을 놓을 수 있는지 없는지에 대한 정보가 체스판 한 줄 단위로 www.acmicpc.net 1. 문제의 유형 및 이해 구현, 백트래킹 N-Queen 문제와 유사하면서도 조건이 달려있는 문제입니다. N-Queen 문제처럼 놓을 수 있는 곳에 비숍을 놓아가면서 놓을 수 있는지 확인하면서 진행하면 됩니다. Queen 과 달리 비숍의 경우 움직일 수 있는 상태공간은 대각선으로 특정할 수 있습니다. 다만 대각선이라 기존의 n queen 과는 다른 방법으로 가능한지 여부를 체크해 주어야 합니다. 2. 문제..
[백준] Q1509 팰린드롬 분할 JAVA https://www.acmicpc.net/problem/1509 1509번: 팰린드롬 분할 세준이는 어떤 문자열을 팰린드롬으로 분할하려고 한다. 예를 들어, ABACABA를 팰린드롬으로 분할하면, {A, B, A, C, A, B, A}, {A, BACAB, A}, {ABA, C, ABA}, {ABACABA}등이 있다. 분할의 개수의 최솟값을 출력하 www.acmicpc.net 1. 문제의 유형 및 이해 dp 어떤 문자열을 팰린드롬으로만 분할하려고할 때, 분할 개수의 최소값을 구하는 문제이다. 문자열의 최대길이는 2500. 예를 들어, ABACABA를 팰린드롬으로 분할하면, {A, B, A, C, A, B, A}, {A, BACAB, A}, {ABA, C, ABA}, {ABACABA}등이 있다. 어떤 문..
[백준] Q1208 부분수열의 합 2 JAVA https://www.acmicpc.net/problem/1208 1208번: 부분수열의 합 2 첫째 줄에 정수의 개수를 나타내는 N과 정수 S가 주어진다. (1 ≤ N ≤ 40, |S| ≤ 1,000,000) 둘째 줄에 N개의 정수가 빈 칸을 사이에 두고 주어진다. 주어지는 정수의 절댓값은 100,000을 넘지 않는다. www.acmicpc.net 1. 문제의 유형 및 이해 완전탐색? 중간에서 만나기, 이분탐색 N개의 정수로 이루어진 수열에서 크기가 양수인 부분 수열 중에서 그 수열의 원소를 다 더한 값이 S가 되는 경우의수를 구하는 프로그램 작성. 문제와 조건을 보면서 고려해야할 점이 몇가지 있었습니다. '크기가 양수인' '부분 수열' 에 집중을 해서 주어진 수열에서 하나 이상 고른 부분 수열을 골라..
[백준] 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번이기 때문에 $4^5 = 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($N^2$) 으로 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번 게이트 중 하나에 영구적으로 도킹하려고 한다. 비행기가 도킹할 수 없다면 공항이 폐쇄되고, 이후 어떤 비행기도 도착할 수 없다. 가장 많은 비행기를 도킹시키고자 할 때 최대 몇..

티스토리툴바