Algorithm/Baekjoon Online Judge

    [Java] 백준 13397 (구간 나누기 2) Gold 4
    Algorithm/Baekjoon Online Judge

    [Java] 백준 13397 (구간 나누기 2) Gold 4

    Problem : https://www.acmicpc.net/problem/13397 13397번: 구간 나누기 2 첫째 줄에 배열의 크기 N과 M이 주어진다. (1 ≤ N ≤ 5,000, 1 ≤ M ≤ N) 둘째 줄에 배열에 들어있는 수가 순서대로 주어진다. 배열에 들어있는 수는 1보다 크거나 같고, 10,000보다 작거나 같은 자연수 www.acmicpc.net Approach 이분탐색을 이용한 문제이다. 문제에서 말한 점수의 최솟값은 구간의 크기가 1일 때, 0이다. 점수의 최댓값은 최대 요소값 - 최소 요소값이지만, 편의상 최대 요소값 - 1로 이분탐색의 left와 right를 정해도 상관없다. 이분탐색을 진행하면서 해당 값을 만족시키는 구간의 개수가 m개 초과인지 아닌지 판단한다. 초과라면, 해..

    [Java] 백준 1939 (중량제한) Gold 4
    Algorithm/Baekjoon Online Judge

    [Java] 백준 1939 (중량제한) Gold 4

    Problem : https://www.acmicpc.net/problem/1939 1939번: 중량제한 첫째 줄에 N, M(1≤M≤100,000)이 주어진다. 다음 M개의 줄에는 다리에 대한 정보를 나타내는 세 정수 A, B(1≤A, B≤N), C(1≤C≤1,000,000,000)가 주어진다. 이는 A번 섬과 B번 섬 사이에 중량제한이 C인 다리 www.acmicpc.net Approach 이분탐색과 DFS/BFS를 사용하는 문제이다. 먼저 입력을 받으면서 그래프를 구성한다. 와중에 중량제한의 최솟값과 최댓값 또한 같이 구한다. 이 두 값이 이분탐색에 쓰일 left와 right가 될 것이다. 이 중량제한 값을 이용하여 BFS를 수행한다. 시작 섬을 출발하여 도착 섬에 도달할 수 있다면, ans를 갱신하..

    [Java] 백준 1377 (버블 소트) Gold 3
    Algorithm/Baekjoon Online Judge

    [Java] 백준 1377 (버블 소트) Gold 3

    Problem : https://www.acmicpc.net/problem/1377 1377번: 버블 소트 첫째 줄에 N이 주어진다. N은 500,000보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에 A[1]부터 A[N]까지 하나씩 주어진다. A에 들어있는 수는 1,000,000보다 작거나 같은 자연수 또는 0이다. www.acmicpc.net Approach 정렬을 활용한 문제이다. 문제에서 소개한 버블정렬 알고리즘은 해당 리스트를 맨 뒤부터 채우는 정렬 방법이다. 문제에서 물어보는 것은 완전히 정렬될 때까지, 외부 for문이 몇번 돌아가는지를 물어보는 것이다. 한 번의 외부 for문을 돌릴 때, 리스트의 한 요소 a는 오른쪽으로는 최대 리스트의 끝까지 움직일 수 있고, 왼쪽으로는 1칸 움직일 ..

    [Java] 백준 1933 (스카이라인) Gold 2
    Algorithm/Baekjoon Online Judge

    [Java] 백준 1933 (스카이라인) Gold 2

    Problem : https://www.acmicpc.net/problem/1933 1933번: 스카이라인 첫째 줄에 건물의 개수 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 N개의 줄에는 N개의 건물에 대한 정보가 주어진다. 건물에 대한 정보는 세 정수 L, H, R로 나타나는데, 각각 건물의 왼쪽 x좌표, 높이, 오 www.acmicpc.net Approach 우선순위 큐(PriorityQueue)와 TreeMap 자료구조를 활용하는 문제이다. 문제에서 원하는 것은 높이가 변하는 부분의 x좌표와 그 때의 최대높이이다. 이를 위해 우선순위 큐와 TreeMap을 사용한다. 우선순위 큐는 x좌표 기준 오름차순(같을 경우, 높이 기준 내림차순)으로, 트리맵은 높이 기준 내림차순의 정렬 기준을 규정한다..

    [Java] 백준 21776 (가희와 읽기 쓰기 놀이) Gold 4
    Algorithm/Baekjoon Online Judge

    [Java] 백준 21776 (가희와 읽기 쓰기 놀이) Gold 4

    Problem : https://www.acmicpc.net/problem/21776 21776번: 가희와 읽기 쓰기 놀이 1번째 줄에 N, C가 공백으로 구분되어 주어집니다. 2번째 줄 부터 N+1번째 줄까지 1번 사람부터 N번 사람까지 낸 카드의 갯수와 카드를 낸 순서가 주어집니다. 예를 들어 3번째 줄에 3 2 4 5 가 있다면 www.acmicpc.net Approach 중복된 요소로 만드는 순열 알고리즘과 문자열 처리가 필요한 문제이다. 주어진 카드 개수로 순열을 만들되, 특정 카드 집합의 순서가 유지되어야 한다. 만약 1번 사람이 3,2,1 순으로 카드를 사용하고 2번 사람이 4,5 순으로 카드를 사용한다면 (1번, 1번, 1번, 2번, 2번)으로 만드는 수열과 같은 개수가 된다. (1번,2번..

    [Java] 백준 21775 (가희와 자원 놀이) Gold 5
    Algorithm/Baekjoon Online Judge

    [Java] 백준 21775 (가희와 자원 놀이) Gold 5

    Problem : https://www.acmicpc.net/problem/21775 21775번: 가희와 자원 놀이 T턴에 걸쳐서, 각 턴에 수행된 연산 카드의 id를 한 줄에 하나씩 출력해 주세요. www.acmicpc.net Approach 간단한 구현 문제이다. (본인은 간단하지 않았다.) 먼저 사용할 자료구조들을 생각해 보았다. 구현 문제에선 어떤 자료구조를 사용할 것인가가 중요한 포인트같다. 턴을 수행하는 사람의 번호 -> sequence 배열 주어진 연산카드 -> 배열 or 큐 개인공간 -> 사람마다 공간 할당(메모리 초과) -> Map 사용 (key, value) == (자원카드 번호, 소지한 사람 번호) 공용공간 -> 불필요 (Map에 없으면 다 공용공간에 있는 것) 번호가 n인 사람이 ..

    [Java] 백준 21774 (가희와 로그 파일) Gold 3
    Algorithm/Baekjoon Online Judge

    [Java] 백준 21774 (가희와 로그 파일) Gold 3

    Problem : https://www.acmicpc.net/problem/21774 21774번: 가희와 로그 파일 2000년부터 2020년까지 연도 중에, 윤년인 것은 2000, 2004, 2008, 2012, 2016, 2020년 입니다. www.acmicpc.net Approach 문자열을 파싱하여 DP를 구성하고, 이분 탐색의 lowerbound, upperbound를 활용해야 하는 문제이다. 문제 풀이의 로직은 다음과 같다. 먼저 문자열을 파싱한다. 주어진 시각 문자열이 YYYY-MM-DD hh:mm:ss 형식이고 순서대로 주어지므로, -:와 공백문자를 없애면 자연스럽게 정렬이 된 상태가 된다. (본인은 Long 타입으로 형변환을 하였지만, String 타입이어도 자연스럽게 사전순으로 정렬 상..

    [Java] 백준 21773 (가희와 프로세스 1) Gold 5
    Algorithm/Baekjoon Online Judge

    [Java] 백준 21773 (가희와 프로세스 1) Gold 5

    Problem : https://www.acmicpc.net/problem/21773 21773번: 가희와 프로세스 1 1초일 때 부터 4초일 때 상황을 그림으로 나타내면 아래와 같습니다. 아래 그림에서 주황색은 특정 시점에 스케쥴러가 선택한 프로세스를 의미합니다. www.acmicpc.net Approach 우선순위 큐(PriorityQueue) 를 이용한 문제이다. 문제의 로직은 다음과 같다. 레디 큐에서 가장 우선순위가 높은 프로세스를 꺼내 1초동안 실행시킨다. 꺼낸 프로세스를 제외한 레디 큐에 있는 모든 프로세스의 우선순위는 1증가한다. 위 로직을 구현하려면, 먼저 우선순위 큐의 정렬 기준을 확립해야 한다. 프로세스의 우선순위 기준 내림차순이 필요할 것이다. 이제 우선순위큐에서 프로세스를 하나 뽑..

    [Java] 백준 1891 (사분면) Gold 4
    Algorithm/Baekjoon Online Judge

    [Java] 백준 1891 (사분면) Gold 4

    Problem : https://www.acmicpc.net/problem/1891 1891번: 사분면 첫 줄에 이동시키려는 사분면 조각 번호의 자릿수를 나타내는 정수 d와, 그 사분면 조각의 번호가 주어진다. (1≤d≤50) 둘째 줄에는 이동의 내용을 나타내는 두 정수가 x, y가 주어진다. (|x|, |y|≤2 www.acmicpc.net Approach 분할 정복(Divide & Conquer)을 구현한 문제이다. 아래와 같이 두 가지 기능을 구현하여야 한다. 그리고 순서대로 수행하면서 답을 도출한다. 주어진 사분면 숫자의 위치 (x, y)를 찾는다. 그리고 그 위치에 주어진 이동 횟수를 더한 위치를 찾는다. 구한 위치의 사분면 숫자를 구한다. 1번 기능의 경우, 주어진 사분면 숫자를 앞에서부터 한..

    [Java] 백준 1201 (NMK) Platinum 3
    Algorithm/Baekjoon Online Judge

    [Java] 백준 1201 (NMK) Platinum 3

    Problem : https://www.acmicpc.net/problem/1201 1201번: NMK 첫째 줄에 세 정수 N, M, K가 주어진다. www.acmicpc.net Approach 알고 보면 쉬운데 그걸 알기까지가 어려웠던 Greedy 문제이다. 먼저 유효하지 않은 n, m, k를 찾아보자. (m + k) - 1 > n: 1 ~ n 까지의 숫자가 모두 증가하는 수열 혹은 감소하는 수열에 속한다고 가정할 때, 두 수열을 더했을 때의 길이 m + k = n + 1이다. (두 수열은 적어도 하나의 숫자를 공유하기 때문이다.) 그렇기 때문에 (m + k) - 1 > n 라면 길이 m의 증가수열 + 길이 k의 감소수열은 만들 수 없다. 각 수열을 구하는 방법은 다음과 같다. 길이 m의 증가수열을 만..

티스토리툴바