전체 글

전체 글

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

    [java] 프로그래머스 (프린터) Level 2

    문제 원문 링크 : https://programmers.co.kr/learn/courses/30/lessons/42587 코딩테스트 연습 - 프린터 일반적인 프린터는 인쇄 요청이 들어온 순서대로 인쇄합니다. 그렇기 때문에 중요한 문서가 나중에 인쇄될 수 있습니다. 이런 문제를 보완하기 위해 중요도가 높은 문서를 먼저 인쇄하는 프린 programmers.co.kr Approach Baekjoon Online Judge 사이트에 비슷한 문제(프린터 큐 Silver 3)가 있으니 같이 풀어보면 좋을 것이다. 문제의 조건은 이렇다. 1. 인쇄 대기목록의 가장 앞에 있는 문서(J)를 대기목록에서 꺼냅니다. 2. 나머지 인쇄 대기목록에서 J보다 중요도가 높은 문서가 한 개라도 존재하면 J를 대기목록의 가장 마지막에..

    [Java] int[] 배열을 Integer[] 배열로, Integer[] 배열을 int[] 배열로
    Language/Java

    [Java] int[] 배열을 Integer[] 배열로, Integer[] 배열을 int[] 배열로

    자바 int[] 배열을 Integer[] 배열로 변환 int a[] = {1,2,3,4}; Integer b[] = Arrays.stream(a).boxed().toArray(Integer[]::new); 자바 Integer[] 배열을 int[] 배열로 변환 Integer a[] = {1,2,3,4}; int b[] = Arrays.stream(a).mapToInt(Integer::intValue).toArray(); or int b[] = Arrays.stream(a).mapToInt(i->i).toArray(); Refer to http://www.techiedelight.com/convert-int-array-list-integer/

    [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 자료형을 이용하면 편하다...

티스토리툴바