전체 글

전체 글

    [java] 프로그래머스 (문자열 압축) Level 2
    Algorithm/Programmers

    [java] 프로그래머스 (문자열 압축) Level 2

    Problem : https://programmers.co.kr/learn/courses/30/lessons/60057 코딩테스트 연습 - 문자열 압축 데이터 처리 전문가가 되고 싶은 어피치는 문자열을 압축하는 방법에 대해 공부를 하고 있습니다. 최근에 대량의 데이터 처리를 위한 간단한 비손실 압축 방법에 대해 공부를 하고 있는데, 문자 programmers.co.kr Approach 2020 KAKAO BLIND RECRUITEMENT 문제로, 문자열을 처리하는 문제이다. 최대로 문자열을 압축하여, 그 길이를 반환하여야 한다. 압축 단위는 최대 원래 문자열 크기의 반이다. 알고리즘 자체는 쉽지만, 여러 테스트케이스들을 고민해 봐야한다. 예를 들어, x....x처럼 x가 100개인 경우의 최소길이는 4이..

    [java] 프로그래머스 (카카오프렌즈 컬러링) Level 2
    Algorithm/Programmers

    [java] 프로그래머스 (카카오프렌즈 컬러링) Level 2

    Problem : https://programmers.co.kr/learn/courses/30/lessons/1829 코딩테스트 연습 - 카카오프렌즈 컬러링북 6 4 [[1, 1, 1, 0], [1, 2, 2, 0], [1, 0, 0, 1], [0, 0, 0, 1], [0, 0, 0, 3], [0, 0, 0, 3]] [4, 5] programmers.co.kr Approach 2017 카카오코드 예선문제로, 간단한 BFS 문제이다. 일단 모든 점을 검사한다. 검사하면서 방문할 수 있으면 방문하면서 최대 영역의 넓이와 영역의 개수를 갱신하고 방문표시를 한다. Code import java.util.LinkedList; import java.util.Queue; public class KakaoFriends..

    [java] 백준 2293 (동전 1) Silver 1
    Algorithm/Baekjoon Online Judge

    [java] 백준 2293 (동전 1) Silver 1

    Problem : https://www.acmicpc.net/problem/2293 2293번: 동전 1 첫째 줄에 n, k가 주어진다. (1 ≤ n ≤ 100, 1 ≤ k ≤ 10,000) 다음 n개의 줄에는 각각의 동전의 가치가 주어진다. 동전의 가치는 100,000보다 작거나 같은 자연수이다. www.acmicpc.net Approach DP 문제이다. 입력되는 동전의 가치가 오름차순으로 주어진다는 말이 없어 동전의 가치를 저장한 배열을 오름차순으로 정렬시킨 후, 다음과 같은 규칙을 이용하여 문제를 풀어나가면 된다. 코인의 가치가 a, b, c 일 때, x를 만드는 방법의 수는 x - a원 에서 a원을 더하여 만드는 법(1), x - b원에서 b원을 더하여 만드는 법(2), x - c 원에서 c원을..

    [java] 백준 11049 (행렬 곱셈 순서) Gold 3
    Algorithm/Baekjoon Online Judge

    [java] 백준 11049 (행렬 곱셈 순서) Gold 3

    Problem : https://www.acmicpc.net/problem/11049 11049번: 행렬 곱셈 순서 첫째 줄에 입력으로 주어진 행렬을 곱하는데 필요한 곱셈 연산의 최솟값을 출력한다. 정답은 231-1 보다 작거나 같은 자연수이다. 또한, 최악의 순서로 연산해도 연산 횟수가 231-1보다 작거나 같 www.acmicpc.net Approach DP 문제로 행렬의 곱셈규칙을 알아야 한다. A x B 행렬, B X C 행렬을 곱한다고 하였을 떄, 필요한 곱셈연산 수는 A x B x C번이며, 곱셈으로 만들어진 행렬은 A x C 크기의 행렬이다. 그리고 이 행렬과 C x D 행렬을 곱한다고 하였을 때, 필요한 곱셈연산 수는 A x C x D 이다. 그리고 만들어진 행렬의 크기는 A x D 이다...

    [java] 백준 11066 (파일 합치기) Gold 3
    Algorithm/Baekjoon Online Judge

    [java] 백준 11066 (파일 합치기) Gold 3

    Problem : https://www.acmicpc.net/problem/11066 11066번: 파일 합치기 소설가인 김대전은 소설을 여러 장(chapter)으로 나누어 쓰는데, 각 장은 각각 다른 파일에 저장하곤 한다. 소설의 모든 장을 쓰고 나서는 각 장이 쓰여진 파일을 합쳐서 최종적으로 소설의 완성본 www.acmicpc.net Approach DP를 이용한 문제로, DP[i][j] = i ~ j까지의 파일을 합치는 최소 비용 이라고 정의하고 문제에 접근한다. 주어진 파일의 개수가 1개라면, 그 파일의 크기를 return 한다. 주어진 파일의 개수가 2개라면, 두 개의 파일 크기를 합친 값을 return 한다. 주어진 파일의 개수가 3개 이상이라면, DP[i][j] = DP[i][k] + DP[..

    [java] 백준 1655 (가운데를 말해요) Gold 2
    Algorithm/Baekjoon Online Judge

    [java] 백준 1655 (가운데를 말해요) Gold 2

    Problem : https://www.acmicpc.net/problem/1655 1655번: 가운데를 말해요 첫째 줄에는 수빈이가 외치는 정수의 개수 N이 주어진다. N은 1보다 크거나 같고, 100,000보다 작거나 같은 자연수이다. 그 다음 N줄에 걸쳐서 수빈이가 외치는 정수가 차례대로 주어진다. 정수는 -1 www.acmicpc.net Approach 최대 힙과 최소 힙 두개를 사용하여 문제를 풀 수 있다. 최대 힙은 최댓값이 우선으로 빠져나오는 큐이고, 최소 힙은 최솟값이 우선으로 빠져나오는 큐라고 할 때, 최대 힙과 최소 힙에 하나씩 숫자를 넣는다고 가정햇을 때, 최대 힙의 최댓값이 최소 힙의 최솟값보다 항상 작음을 유지한다면, 최대 힙의 최댓값이 항상 중간값을 가지게 된다. 그러기 위해선 ..

    [java] 프로그래머스 (삼각 달팽이) Level 2
    Algorithm/Programmers

    [java] 프로그래머스 (삼각 달팽이) Level 2

    Problem : https://programmers.co.kr/learn/courses/30/lessons/68645 코딩테스트 연습 - 삼각 달팽이 5 [1,2,12,3,13,11,4,14,15,10,5,6,7,8,9] 6 [1,2,15,3,16,14,4,17,21,13,5,18,19,20,12,6,7,8,9,10,11] programmers.co.kr Approach 월간 코드 챌린지 시즌1 에 수록된 문제이다. 정삼각형의 위쪽 꼭짓점부터 반시계방향으로 외곽부터 순회하면서(토네이도 식으로) 번호를 매기고, 그것을 1차원 배열로 변환하여 리턴하는 문제이다. 정삼각형의 한 변의 길이가 n이고, 번호를 1부터 매긴다고 하면, 마지막 번호는 n + (n - 1) + (n - 2) + ... + 1 = n(..

    [java] 백준 11286 (절댓값 힙) Silver 1
    Algorithm/Baekjoon Online Judge

    [java] 백준 11286 (절댓값 힙) Silver 1

    Problem : https://www.acmicpc.net/problem/11286 11286번: 절댓값 힙 첫째 줄에 연산의 개수 N(1≤N≤100,000)이 주어진다. 다음 N개의 줄에는 연산에 대한 정보를 나타내는 정수 x가 주어진다. 만약 x가 0이 아니라면 배열에 x라는 값을 넣는(추가하는) 연산이고, x가 0 www.acmicpc.net Approach PriorityQueue를 이용하여 풀 수 있는 문제이다. JAVA에서 기본적으로 PriorityQueue는 default값으로 오름차순, 즉 Integer큐일 경우 숫자가 작을수록 우선순위가 높다. 따라서 별다른 설정없이 우선순위 큐에 넣었다 뺀다면 자동적으로 가장 작은 값이 나온다. 절댓값이 가장 작은 값을 출력하려면 PriorityQue..

    [java] 백준 11279 (최대 힙) Silver 2
    Algorithm/Baekjoon Online Judge

    [java] 백준 11279 (최대 힙) Silver 2

    Problem : https://www.acmicpc.net/problem/11279 11279번: 최대 힙 첫째 줄에 연산의 개수 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 N개의 줄에는 연산에 대한 정보를 나타내는 정수 x가 주어진다. 만약 x가 자연수라면 배열에 x라는 값을 넣는(추가하는) 연산이고, x가 www.acmicpc.net Approach PriorityQueue를 이용하여 풀 수 있는 문제이다. JAVA에서 기본적으로 PriorityQueue는 default값으로 오름차순, 즉 Integer큐일 경우 숫자가 작을수록 우선순위가 높다. 따라서 별다른 설정없이 우선순위 큐에 넣었다 뺀다면 자동적으로 가장 작은 값이 나온다. 하지만 가장 큰 값이 나와야 하므로 별도의 설정이 필요하다..

    [java] 백준 1927 (최소 힙) Silver 1
    Algorithm/Baekjoon Online Judge

    [java] 백준 1927 (최소 힙) Silver 1

    Problem : https://www.acmicpc.net/problem/1927 1927번: 최소 힙 첫째 줄에 연산의 개수 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 N개의 줄에는 연산에 대한 정보를 나타내는 정수 x가 주어진다. 만약 x가 자연수라면 배열에 x라는 값을 넣는(추가하는) 연산이고, x가 0 www.acmicpc.net Approach 우선순위 큐(PriorityQueue)를 이용하여 풀 수 있는 문제이다. JAVA에서 기본적으로 PriorityQueue는 default값으로 오름차순, 즉 Integer큐일 경우 숫자가 작을수록 우선순위가 높다. 따라서 별다른 설정없이 우선순위 큐에 넣었다 뺀다면 자동적으로 가장 작은 값이 나온다. Code import java.io.*; i..

티스토리툴바