[java] 백준 12851 (숨바꼭질 2) Gold 5

문제 원문 링크 : https://www.acmicpc.net/problem/12851 12851번: 숨바꼭질 2 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 때 www.acmicpc.net Approach 대표적인 BFS 문제로, N to K의 최단시간과 최단시간으로 가는 방법을 구하는 문제이다. 현재 위치가 X 일 때, 1초 후에 X - 1 또는 X + 1 또는 2 * X 위치로 갈 수 있다. 처음 큐에 N을 넣은 후 하나씩 뺀다. 뺀 수에 +1, -1, *2를 하여 범위(0 ~ 100,000)를 넘지 않..

→2020.12.21

Algorithm/Baekjoon Online Judge

[java] 백준 1697 (숨바꼭질) Silver 1

문제 원문 링크 : https://www.acmicpc.net/problem/1697 1697번: 숨바꼭질 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 www.acmicpc.net Approach 대표적인 BFS 문제로 Queue와 visited[] 배열을 이용하여 풀이를 생각했다. 현재 위치가 X 일 때, 1초 후에 X - 1 또는 X + 1 또는 2 * X 위치로 갈 수 있다. 처음 큐에 N을 넣은 후 하나씩 뺀다. 뺀 수에 +1, -1, *2를 하여 범위(0 ~ 100,000)를 넘지 않는다면 큐에 넣는..

→2020.12.21

Algorithm/Baekjoon Online Judge

[java] 백준 14003 (가장 긴 증가하는 부분 수열 5) Gold 1

문제 원문 링크 : https://www.acmicpc.net/problem/14003 14003번: 가장 긴 증가하는 부분 수열 5 첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (-1,000,000,000 ≤ Ai ≤ 1,000,000,000) www.acmicpc.net Approach 이 문제는 백준 12015번 가장 긴 증가하는 부분 수열 2 과 백준 12738번 가장 긴 증가하는 부분 수열 3 의 문제에 LIS을 추가로 출력해야 하는 문제이다. 12015번: 가장 긴 증가하는 부분 수열 2 첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄에는 수열 A를 이루고 있는 Ai가..

→2020.12.20

Algorithm/Baekjoon Online Judge

[java] 백준 14002 (가장 긴 증가하는 부분 수열 4) Gold 4

문제 원문 링크 : https://www.acmicpc.net/problem/14002 14002번: 가장 긴 증가하는 부분 수열 4 수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이 www.acmicpc.net Approach 이 문제는 백준 11053번 가장 긴 증가하는 수열 의 문제에서 가장 긴 부분 수열을 추가로 출력하는 문제이다. 11053번: 가장 긴 증가하는 부분 수열 수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {10, 20,..

→2020.12.20

Algorithm/Baekjoon Online Judge

[java] 백준 12738 (가장 긴 증가하는 부분 수열 3) Gold 2

문제 원문 링크 : https://www.acmicpc.net/problem/12738 12738번: 가장 긴 증가하는 부분 수열 3 첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (-1,000,000,000 ≤ Ai ≤ 1,000,000,000) www.acmicpc.net Approach LIS(Longest Increasing Subsequence)는 Backtracking을 이용한 DP 방식과 이분탐색 방식이 가능하다. DP 방식은 O(N^2) 의 시간복잡도를 가지며, 이분 탐색은 O(NlogN)의 시간복잡도를 가진다. 이 문제에서는 입력의 크기가 최대 1,000,000 이므로 DP를 이용한 풀이는 시간이 너무 ..

→2020.12.19

Algorithm/Baekjoon Online Judge

[java] 백준 12015 (가장 긴 증가하는 부분 수열 2) Gold 2

문제 원문 링크 : 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 Approach LIS(Longest Increasing Subsequence)는 Backtracking을 이용한 DP 방식과 이분탐색 방식이 가능하다. DP 방식은 O(N^2) 의 시간복잡도를 가지며, 이분 탐색은 O(NlogN)의 시간복잡도를 가진다. 이 문제에서는 입력의 크기가 최대 1,000,000 이므로 DP를 이용한 풀이는 시간이 너무 오래걸리므로 이분탐색을 이용한 ..

→2020.12.19

Algorithm/Baekjoon Online Judge

[java] 백준 11053 (가장 긴 증가하는 부분 수열) Silver 2

문제 원문 링크 : https://www.acmicpc.net/problem/11053 11053번: 가장 긴 증가하는 부분 수열 수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이 www.acmicpc.net Approach LIS(Longest Increasing Subsequence)는 Backtracking을 이용한 DP 방식과 이분탐색 방식이 가능하다. DP 방식은 O(N^2) 의 시간복잡도를 가지며, 이분 탐색은 O(NlogN)의 시간복잡도를 가진다. 이 문제에서는 입력이 1000보다 작으므로 N..

→2020.12.19

Algorithm/Baekjoon Online Judge

[java] 백준 11779 (최소비용 구하기 2) Gold 3

문제 원문 링크 : https://www.acmicpc.net/problem/11779 11779번: 최소비용 구하기 2 첫째 줄에 도시의 개수 n(1≤n≤1,000)이 주어지고 둘째 줄에는 버스의 개수 m(1≤m≤100,000)이 주어진다. 그리고 셋째 줄부터 m+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 버스 www.acmicpc.net Approach 대표적인 Dijkstra 알고리즘을 활용한 문제이다. 문제에서 요구했듯이 최단거리 cost뿐만 아니라 경로 또한 구해야 하므로 최단거리 cost를 업데이트 할 때, 이전 도시가 무엇인지만 별도로 저장해두면 간단하게 구현된다. 이전 노드가 0이라면 그 때의 마을은 시작 마을이 된다. 경로 출력은 Stack 자료형을 이용하면 편하다...

→2020.12.15

Algorithm/Baekjoon Online Judge

[java] 백준 14226 (이모티콘) Gold 5

문제 원문 링크 : https://www.acmicpc.net/problem/14226 14226번: 이모티콘 영선이는 매우 기쁘기 때문에, 효빈이에게 스마일 이모티콘을 S개 보내려고 한다. 영선이는 이미 화면에 이모티콘 1개를 입력했다. 이제, 다음과 같은 3가지 연산만 사용해서 이모티콘을 S개 만 www.acmicpc.net Approach DFS 를 이용한 DP문제이다. 문제의 조건 화면에 있는 이모티콘을 모두 복사해서 클립보드에 저장한다. 클립보드에 있는 모든 이모티콘을 화면에 붙여넣기 한다. 화면에 있는 이모티콘 중 하나를 삭제한다. 이 문제를 풀려면 이모티콘의 길이가 X일 때, 현재 클립보드에 저장된 이모티콘의 길이가 몇인지를 저장해 놓아야 한다. 그래야 X보다 큰 길이Y의 이모티콘을 만들 때..

→2020.12.15

Algorithm/Baekjoon Online Judge

[java] 백준 1949 (우수 마을) Gold 1

문제 원문 링크 : https://www.acmicpc.net/problem/1949 1949번: 우수 마을 N개의 마을로 이루어진 나라가 있다. 편의상 마을에는 1부터 N까지 번호가 붙어 있다고 하자. 이 나라는 트리(Tree) 구조로 이루어져 있다. 즉 마을과 마을 사이를 직접 잇는 N-1개의 길이 있으며, www.acmicpc.net Approach(Wrong: TLE) 트리에서의 DP문제로, 2213번 트리의 독립집합과 유사한 문제이다. DFS를 이용하여 트리 끝까지 내려가면 함수가 차례차례 종료되는 것을 이용하여 값을 갱신했지만 시간초과(TLE)가 떴다. 질문 글을 올려 답변을 받자면 내 잘못된 코드는 DP를 수행하지 않고 그냥 탐색만 하는 것이므로 각 호출에서 구한 답을 메모이제이션 해보라는 ..

→2020.12.13

티스토리툴바