본문 바로가기

algorithm

 (54)
[백준/BOJ] 1038 감소하는 수 문제 출처 : https://www.acmicpc.net/problem/1038 1038번: 감소하는 수 음이 아닌 정수 X의 자릿수가 가장 큰 자릿수부터 작은 자릿수까지 감소한다면, 그 수를 감소하는 수라고 한다. 예를 들어, 321과 950은 감소하는 수지만, 322와 958은 아니다. N번째 감소하는 수를 www.acmicpc.net 음이 아닌 정수의 가장 큰 자릿수 부터 가장 작은 자릿수까지 각 자릿수가 모두 감소하는 수를 감소하는 수라고 한다. 이 때, N번째 감소하는 수를 찾는 문제다. 풀이 N이 최대 1,000,000이길래 처음에는 DP로 생각했는데, 좀만 더 생각해보면 탐색횟수가 그렇게 크지 않다는 것을 알 수 있다. (DP식이 나오긴 하는걸로봐서 DP로 풀릴거 같긴 함) 음이 아닌 정수가..
[백준 / BOJ] 23040 누텔라 트리 (Easy) 문제 출처 : https://www.acmicpc.net/problem/23040 23040번: 누텔라 트리 (Easy) 첫째 줄에 트리의 정점의 개수 $N$이 주어진다. ($2 \le N \le 100\,000$) 이후 $(N-1)$개 줄에 걸쳐 각 간선이 잇는 두 정점의 번호 $u_i$, $v_i$가 공백을 사이에 두고 주어진다. ($1 \le u_i \le N$, $1 \le v_i \le N$, www.acmicpc.net 빨간색과 검은색 정점들로 이루어진 트리가 있다. 시작은 검은색 정점, 나머지 정점은 모두 빨간색인 경우 이를 누텔라 경로라고한다. 트리에서 누텔라 경로의 갯수를 찾는 문제였다. 풀이 시간초과를 주의해야했던 문제였다. 논리는 아래와 같다. 검은색 정점에서 시작해, 거쳐간 빨간색 ..
[백준 / BOJ] 19542 전단지 돌리기 문제 출처 : https://www.acmicpc.net/problem/19542 19542번: 전단지 돌리기 현민이는 트리 모양의 길 위에서 오토바이를 타고 전단지를 돌리려고 한다. 현민이의 목표는 케니소프트에서 출발하여 모든 노드에 전단지를 돌리고, 다시 케니소프트로 돌아오는 것이다. 현민 www.acmicpc.net 현민이는 트리 모양의 길 위에서 오토바이를 타고 전단지를 돌리려고 한다. 현민이는 KENNYSOFT위치에서 시작하여 전단지를 다 돌리고 KENNYSOFT로 돌아오며, 이때, 전단지를 던져 거리가 D미만인 노드에 전단지를 한번에 돌릴 수 있다. 현민이가 전단지를 모든 노드에 돌리고 KENNYSOFT로 돌아오는 최단 경로를 구하는 문제다. 풀이 트리탐색으로 풀리는 문제였다. 1년전에 풀려고..
[백준 / BOJ] 1561 놀이 공원 문제 출처 : https://www.acmicpc.net/problem/1561 1561번: 놀이 공원 첫째 줄에 N(1 ≤ N ≤ 2,000,000,000)과 M(1 ≤ M ≤ 10,000)이 빈칸을 사이에 두고 주어진다. 둘째 줄에는 각 놀이기구의 운행 시간을 나타내는 M개의 자연수가 순서대로 주어진다. 운행 시간은 1 이상 30 www.acmicpc.net 놀이공원에 N명의 사람과, M개의 놀이기구가 있다. M개의 놀이기구는 각각 운행시간이 있으며, N명의 사람은 놀이기구를 "현재 탑승가능한 놀이기구중 빠른번호 순서"로 탑승하려고한다. 이때, 마지막사람이 탑승할 놀이기구의 번호를 출력하는 문제다. 풀이 처음 문제를 봤을때는, 스킵하는 방식의 dp를 이용한 문제일거라고 생각했는데, N이 최대 2,00..
[백준 / BOJ] 4577 소코반 문제 출처 : https://www.acmicpc.net/problem/4577 4577번: 소코반 소코반은 1982년에 일본에서 만들어진 게임으로, 일본어로 창고지기라는 뜻이다. 이 게임은 캐릭터를 이용해 창고 안에 있는 박스를 모두 목표점으로 옮기는 게임이다. 목표점의 수와 박스의 수 www.acmicpc.net "소코반"이라는 게임을 플레이하는 시뮬레이터를 만들어야한다. 행과 열 R,C가 주어지고, 소코반의 상태가 주어진다. . 빈공간 # 벽 + 비어있는 목표점 b 박스 B 목표점 위에 있는 박스 w 캐릭터 W 목표점 위에 있는 캐릭터 이후, 캐릭터의 이동방향이 주어진다. UDLR(각각 up, down, left, right) 이때, 소코반게임이 끝나거나 캐릭터 이동이 끝났을때의 보드 상태를 출력하..
[백준 / BOJ] 20924 트리의 기둥과 가지 문제 출처 : https://www.acmicpc.net/problem/20924 20924번: 트리의 기둥과 가지 첫 번째 줄에는 노드의 개수 $N$($1 \le N \le 200\,000$)과 루트 노드의 번호 $R$($1 \le R \le N$)이 주어진다. 이후 $N-1$개의 줄에 세 개의 정수 $a$, $b$, $d$($1 \le a, b \le N$, $ a \ne b$)가 주어진다. 이는 $a$번 www.acmicpc.net N개의 노드와 N-1개의 간선으로 이루어진 트리가 있다. 이 트리의 루트를 타고 이동하다가, 처음으로 2개 이상의 노드가 연결된 노드가 발견될 경우, 이를 기가 노드라고 하며, 이전 경로를 기둥경로 라고 한다. 기가 노드에서시작해서 기둥 경로를 제외하고, 리프노드까지의 ..
[백준 / BOJ] 20922 겹치는 건 싫어 문제 출처 : https://www.acmicpc.net/problem/20922 20922번: 겹치는 건 싫어 홍대병에 걸린 도현이는 겹치는 것을 매우 싫어한다. 특히 수열에서 같은 원소가 여러 개 들어 있는 수열을 싫어한다. 도현이를 위해 같은 원소가 $K$개 이하로 들어 있는 최장 연속 부분 수열 www.acmicpc.net N개의 수가 있는 수열이 주어진다. 이 수열중 같은 정수를 K개 이하로 포함한 최장 연속 부분 수열의 길이를 구하는 문제다. 풀이 투 포인터로 풀은 문제다. 최장 연속 부분 수열이기때문에, 답이 될수있는 수열은 모두 붙어있어야한다. 따라서, 투 포인터로 left,right값을 지정한 후에 탐색하면 2N시간만에 답을 구할 수 있다. 메인 소스코드 private int getLon..
[백준 / BOJ] 20920 영단어 암기는 괴로워 문제 출처 : https://www.acmicpc.net/problem/20920 20920번: 영단어 암기는 괴로워 첫째 줄에는 영어 지문에 나오는 단어의 개수 $N$과 외울 단어의 길이 기준이 되는 $M$이 공백으로 구분되어 주어진다. ($1 \leq N \leq 100\,000$, $1 \leq M \leq 10$) 둘째 줄부터 $N+1$번째 줄까지 외울 단 www.acmicpc.net 영어 단어장에 N개의 단어가 적혀있다. 화은이는 단어장에있는 N개의 단어들중 K개의 길이 이상의 단어를 다음 순서에따라 정렬할려고한다. 1. 자주 나오는 단어순으로 정렬한다. 2. 단어의 길이가 길수록 앞으로 배치한다. 3. 알파벳 사전 순으로 앞에있는 단어일수록 앞에 배치한다. N과 K, N개의 단어가 주어졌을때,..

티스토리툴바