분류 전체보기

    [java] 백준 1450 (냅색문제) Gold 1
    Algorithm/Baekjoon Online Judge

    [java] 백준 1450 (냅색문제) Gold 1

    Problem : https://www.acmicpc.net/problem/1450 1450번: 냅색문제 첫째 줄에 N과 C가 주어진다. N은 30보다 작거나 같은 자연수이고, C는 10^9보다 작거나 같은 음이아닌 정수이고. 둘째 줄에 물건의 무게가 주어진다. 무게도 10^9보다 작거나 같은 자연수이다. www.acmicpc.net Approach meet in the middle 알고리즘을 적용하여 각각을 완전탐색 후 이진탐색을 수행하는 문제이다. meet in the middle 알고리즘을 간단하게 말하면 주어진 범위를 반으로 나누어 각각 처리하는 알고리즘이다. 문제에서 주어진 N이 최대 30이므로 완전탐색을 수행하려면 2^30번의 연산이 필요하다. 2^30은 대략 10억이지만, 절반인 2^15은 ..

    [java] 프로그래머스 (네트워크) Level 3
    Algorithm/Programmers

    [java] 프로그래머스 (네트워크) Level 3

    Problem : https://programmers.co.kr/learn/courses/30/lessons/43162 코딩테스트 연습 - 네트워크 네트워크란 컴퓨터 상호 간에 정보를 교환할 수 있도록 연결된 형태를 의미합니다. 예를 들어, 컴퓨터 A와 컴퓨터 B가 직접적으로 연결되어있고, 컴퓨터 B와 컴퓨터 C가 직접적으로 연결되어 있 programmers.co.kr Approach 간단하게 BFS/DFS 를 활용하여 풀 수 있는 문제이다. 나는 BFS 를 사용하였다. 모든 노드에 대하여 BFS 를 수행한 후, 집합의 개수가 몇개인지를 판별해주면 된다. Code import org.junit.jupiter.api.Assertions; import org.junit.jupiter.api.Test; imp..

    [java] 프로그래머스 (자물쇠와 열쇠) Level 3
    Algorithm/Programmers

    [java] 프로그래머스 (자물쇠와 열쇠) Level 3

    Problem : https://programmers.co.kr/learn/courses/30/lessons/60059 코딩테스트 연습 - 자물쇠와 열쇠 [[0, 0, 0], [1, 0, 0], [0, 1, 1]] [[1, 1, 1], [1, 1, 0], [1, 0, 1]] true programmers.co.kr Approach 2020 KAKAO BLIND RECRUITMENT 문제였다. 문제풀이의 핵심은 배열을 확장시키고, 흘러가듯 밀면서 비교한다는 점이다. 완전탐색으로도 통과는 가능하다고 한다.(?) TC에서 100ms 정도 걸린다는 글을 보았다. 원본 lock 배열에 홈의 크기 hole를 구한다. 원본 lock 배열에 상하좌우에 (key배열 사이즈 - 1) 만큼씩 padding을 주어 확장된 e..

    [java] 백준 1644 (소수의 연속합) Gold 3
    Algorithm/Baekjoon Online Judge

    [java] 백준 1644 (소수의 연속합) Gold 3

    Problem : https://www.acmicpc.net/problem/1644 1644번: 소수의 연속합 첫째 줄에 자연수 N이 주어진다. (1 ≤ N ≤ 4,000,000) www.acmicpc.net Approach 한쪽에서 시작하는 투포인터를 활용한 문제였다. 주어진 수 N을 연속된 소수의 합으로 만드는 방법의 가짓수를 찾는 문제이다. 따라서, 일단 연속된 소수 수열을 구해야한다. 주어진 수 N이 소수라면 그 또한 방법 가짓수에 포함되기 때문에, 1 ~ N까지의 수들 중에서 소수를 모두 찾아야한다. 소수를 구하는 방법은 에라토스테네스의 체 방법을 사용하였다. 여기서는 해당 방법을 설명하진 않는다. start = 0, end = 0으로 시작한다. 에라토스테네스의 체를 활용하여 소수 수열을 구한다..

    [java] 백준 1806 (부분합) Gold 4
    Algorithm/Baekjoon Online Judge

    [java] 백준 1806 (부분합) Gold 4

    Problem : https://www.acmicpc.net/problem/1806 1806번: 부분합 첫째 줄에 N (10 ≤ N < 100,000)과 S (0 < S ≤ 100,000,000)가 주어진다. 둘째 줄에는 수열이 주어진다. 수열의 각 원소는 공백으로 구분되어져 있으며, 10,000이하의 자연수이다. www.acmicpc.net Approach 한쪽에서 시작하는 투포인터 문제이다. 연속된 수의 합이 S이상이 되는 것 중, 가장 짧은 길이를 찾는 문제이다. start와 end를 모두 배열의 처음부터 시작한다.(start = 0, end = 0) 나는 Index 처리 때문에 배열의 크기를 n+1로 지정해주었다. start와 end가 같다면, sum이 S이상이라면, 최소 길이는 1이다. 1보다 ..

    [java] 프로그래머스 (풍선 터트리기) Level 3
    Algorithm/Programmers

    [java] 프로그래머스 (풍선 터트리기) Level 3

    Problem : https://programmers.co.kr/learn/courses/30/lessons/68646 코딩테스트 연습 - 풍선 터트리기 [-16,27,65,-2,58,-92,-71,-68,-61,-33] 6 programmers.co.kr Approach 월간 코드 챌린지 시즌1 문제였다. 문제의 조건은 다음과 같다. 임의의 인접한 두 풍선을 고른 뒤, 두 풍선 중 하나를 터트립니다. 터진 풍선으로 인해 풍선들 사이에 빈 공간이 생겼다면, 빈 공간이 없도록 풍선들을 중앙으로 밀착시킵니다. 인접한 두 풍선 중에서 번호가 더 작은 풍선을 터트리는 행위는 최대 1번만 할 수 있습니다. 즉, 어떤 시점에서 인접한 두 풍선 중 번호가 더 작은 풍선을 터트렸다면, 그 이후에는 인접한 두 풍선을 고..

    [java] 프로그래머스 (브라이언의 고민) Level 3
    Algorithm/Programmers

    [java] 프로그래머스 (브라이언의 고민) Level 3

    Problem : https://programmers.co.kr/learn/courses/30/lessons/1830 코딩테스트 연습 - 브라이언의 고민 programmers.co.kr Approach 2017 카카오코드 예선문제였다. 결과적으로 문제를 통과하진 못했다. 문제의 조건은 다음과 같다. 광고글은 원래 문구에 다음 규칙을 적용하여 만들 수 있다. (규칙 1) 특정 단어를 선택하여 글자 사이마다 같은 기호를 넣는다. ex) HELLO -> HaEaLaLaO (규칙 2) 특정 단어를 선택하여 단어 앞뒤에 같은 기호를 넣는다. ex) WORLD -> bWORLDb 위의 두 가지 규칙은 한 단어에 모두 적용될 수 있지만 같은 규칙은 두 번 적용될 수 없다. 한 번 쓰인 소문자(특수기호)는 다시 쓰일 ..

    [java] 백준 2470 (두 용액) Gold 5
    Algorithm/Baekjoon Online Judge

    [java] 백준 2470 (두 용액) Gold 5

    Problem : https://www.acmicpc.net/problem/2470 2470번: 두 용액 첫째 줄에는 전체 용액의 수 N이 입력된다. N은 2 이상 100,000 이하이다. 둘째 줄에는 용액의 특성값을 나타내는 N개의 정수가 빈칸을 사이에 두고 주어진다. 이 수들은 모두 -1,000,000,000 이상 1,000,00 www.acmicpc.net Approach 투포인터를 활용하여 풀었다. 주어진 용액들 중 두 용액을 합쳐 특성값이 0에 가장 가까운 혼합 용액을 만드는 문제이다. 주어진 용액들의 특성값은 중복값이 없다. 따라서 나는 우선 주어진 용액들의 특성값을 오름차순으로 정렬했다. 그런후 start = 0, end = length - 1로 정한 후,범위를 좁혀나가며 용액의 특성값들을 ..

    [java] 프로그래머스 (추석 트래픽) Level 3
    Algorithm/Programmers

    [java] 프로그래머스 (추석 트래픽) Level 3

    Problem : https://programmers.co.kr/learn/courses/30/lessons/17676 코딩테스트 연습 - [1차] 추석 트래픽 입력: [ 2016-09-15 20:59:57.421 0.351s, 2016-09-15 20:59:58.233 1.181s, 2016-09-15 20:59:58.299 0.8s, 2016-09-15 20:59:58.688 1.041s, 2016-09-15 20:59:59.591 1.412s, 2016-09-15 21:00:00.464 1.466s, 2016-09-15 21:00:00.741 1.581s, 2016-09-15 21:00:00.748 programmers.co.kr Approach 2018 KAKAO BLIND RECRUITMENT ..

    [java] 프로그래머스 (n진수 게임) Level 2
    Algorithm/Programmers

    [java] 프로그래머스 (n진수 게임) Level 2

    Problem : https://programmers.co.kr/learn/courses/30/lessons/17687 코딩테스트 연습 - [3차] n진수 게임 N진수 게임 튜브가 활동하는 코딩 동아리에서는 전통적으로 해오는 게임이 있다. 이 게임은 여러 사람이 둥글게 앉아서 숫자를 하나씩 차례대로 말하는 게임인데, 규칙은 다음과 같다. 숫자를 0 programmers.co.kr Approach 2018 KAKAO BLIND RECRUITMENT 문제였다. 일단 0부터 숫자를 1씩 늘린 숫자를 N진법으로 바꾼 후, 문자열 s에 붙인다. 10진수 A를 N진법으로 바꾸는 방법은 아래와 같다. A를 N으로 나눈 나머지를 리스트의 끝에 저장한다. A를 N으로 나눈 몫을 다시 A에 저장한다. 1번 2번과정을 A가..

티스토리툴바