Algorithm

    [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] 프로그래머스 (스킬트리) Level 2
    Algorithm/Programmers

    [java] 프로그래머스 (스킬트리) Level 2

    문제 원문 링크 : https://programmers.co.kr/learn/courses/30/lessons/49993 코딩테스트 연습 - 스킬트리 programmers.co.kr Approach String skill = "CBD"; String[] skill_trees = {"BACDE", "CBADF", "AECB", "BDA"}; skill_trees 에 있는 각각의 문자들이 skill.contains() 메소드를 활용하여 skill 에 들어있는지를 검사한다. 만약 들어있지 않다면 빈 문자열("")로 replace 한다. 위의 과정을 거치면 "BCD", "CBD", "CB", "BD" 가 된다. 그리고 위의 문자열들을 skill 의 0번째에서 찾을 수 있다면 문제에서 순서대로만 스킬을 배울 수 ..

    [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) 자신이 얼리어답터인지, 아닌지 일때..

    [java] 백준 15681 (트리와 쿼리) Gold 5
    Algorithm/Baekjoon Online Judge

    [java] 백준 15681 (트리와 쿼리) Gold 5

    문제 원문 링크 : https://www.acmicpc.net/problem/15681 15681번: 트리와 쿼리 트리의 정점의 수 N과 루트의 번호 R, 쿼리의 수 Q가 주어진다. (2 ≤ N ≤ 105, 1 ≤ R ≤ N, 1 ≤ Q ≤ 105) 이어 N-1줄에 걸쳐, U V의 형태로 트리에 속한 간선의 정보가 주어진다. (1 ≤ U, V ≤ N, U ≠ V) www.acmicpc.net Approach 트리에서의 DP문제다. 트리를 만들 때는 루트를 지정하고 시작하는 것이 편하다. 이 문제의 경우에는, 트리를 만들면서 배열에 자신의 서브노드 개수를 기록하면 된다. 함수를 재귀적으로 호출하면 Terminal Node부터 함수가 종료되기 때문에 쉽게 구현할 수 있다. Code import java.io..

    [java] 백준 17070 (파이프 옮기기 1) Gold 5
    Algorithm/Baekjoon Online Judge

    [java] 백준 17070 (파이프 옮기기 1) Gold 5

    문제 원문 링크 : https://www.acmicpc.net/problem/17070 17070번: 파이프 옮기기 1 유현이가 새 집으로 이사했다. 새 집의 크기는 N×N의 격자판으로 나타낼 수 있고, 1×1크기의 정사각형 칸으로 나누어져 있다. 각각의 칸은 (r, c)로 나타낼 수 있다. 여기서 r은 행의 번호, c는 열의 www.acmicpc.net Approach DP문제이다. 위 그림과 같이 파이프를 놓을 수 있고, 첫 파이프가 (1, 1) 과 (1, 2)를 차지할 수 있으므로 처음 놓을 수 있는 파이프는 3열부터 놓을수 있다. DP[i][j][1] = 파이프의 끝이 가로방향으로 (i, j) 에 놓여 있는 경우, DP[i][j][1] = DP[i][j - ..

티스토리툴바