BOJ

    [java] 백준 1697 (숨바꼭질) Silver 1
    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)를 넘지 않는다면 큐에 넣는..

    [java] 백준 14003 (가장 긴 증가하는 부분 수열 5) Gold 1
    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가..

    [java] 백준 14002 (가장 긴 증가하는 부분 수열 4) Gold 4
    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,..

    [java] 백준 12738 (가장 긴 증가하는 부분 수열 3) Gold 2
    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를 이용한 풀이는 시간이 너무 ..

    [java] 백준 12015 (가장 긴 증가하는 부분 수열 2) Gold 2
    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를 이용한 풀이는 시간이 너무 오래걸리므로 이분탐색을 이용한 ..

    [java] 백준 11053 (가장 긴 증가하는 부분 수열) Silver 2
    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..

    [java] 백준 11779 (최소비용 구하기 2) Gold 3
    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 자료형을 이용하면 편하다...

    [java] 백준 14226 (이모티콘) Gold 5
    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의 이모티콘을 만들 때..

    [java] 백준 1949 (우수 마을) Gold 1
    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를 수행하지 않고 그냥 탐색만 하는 것이므로 각 호출에서 구한 답을 메모이제이션 해보라는 ..

    [java] 백준 2533 (사회망 서비스(SNS)) Gold 3
    Algorithm/Baekjoon Online Judge

    [java] 백준 2533 (사회망 서비스(SNS)) Gold 3

    문제 원문 링크 : https://www.acmicpc.net/problem/2533 2533번: 사회망 서비스(SNS) 페이스북, 트위터, 카카오톡과 같은 사회망 서비스(SNS)가 널리 사용됨에 따라, 사회망을 통하여 사람들이 어떻게 새로운 아이디어를 받아들이게 되는가를 이해하는 문제가 중요해졌다. 사회망 www.acmicpc.net Approach (Wrong) 내가 처음 생각했던 잘못된 접근법 처음에는 아무 노드나 루트로 잡고 level을 매겨서 min(홀수레벨 총 노드개수, 짝수레벨 총 노드개수)로 구현하면 될 줄 알았다. 질문 게시판에 있는 대부분의 반례 또한 통과되어 맞는 풀이법이라고 생각했으나, 다음과 같은 반례가 있었다. Approach (Correct) 자신이 얼리어답터인지, 아닌지 일때..

티스토리툴바