BOJ

    [java] 백준 1305 (광고) Platinum 5
    Algorithm/Baekjoon Online Judge

    [java] 백준 1305 (광고) Platinum 5

    Problem : https://www.acmicpc.net/problem/1305 1305번: 광고 세준이는 길 한가운데에서 전광판을 쳐다보고 있었다. 전광판에는 광고가 흘러나오고 있었다. 한참을 전광판을 쳐다본 세준이는 이 광고가 의미하는 것이 무엇인지 궁금해지기 시작했다. 전광 www.acmicpc.net Approach KMP 알고리즘의 실패함수(Failure Function)를 연습할 수 있는 문제이다. KMP 알고리즘의 자세한 내용은 다음 링크를 참조하면 좋을것이다. https://bowbowbow.tistory.com/6#comment5168448 여기서 사용할 내용은 실패함수(Failure Function) pi를 활용한다. 실패함수 pi는 간단히 말하면, i길이의 문자열 p 에서 접두사와..

    [java] 백준 4354 (문자열 제곱) Platinum 5
    Algorithm/Baekjoon Online Judge

    [java] 백준 4354 (문자열 제곱) Platinum 5

    Problem : https://www.acmicpc.net/problem/4354 4354번: 문자열 제곱 알파벳 소문자로 이루어진 두 문자열 a와 b가 주어졌을 때, a*b는 두 문자열을 이어붙이는 것을 뜻한다. 예를 들어, a="abc", b="def"일 때, a*b="abcdef"이다. 이러한 이어 붙이는 것을 곱셈으로 생각한다 www.acmicpc.net Approach KMP 알고리즘의 실패함수(Failure Function)를 연습할 수 있는 문제이다. KMP 알고리즘의 자세한 내용은 다음 링크를 참조하면 좋을것이다. https://bowbowbow.tistory.com/6#comment5168448 여기서 사용할 내용은 실패함수(Failure Function) pi를 활용한다. 실패함수 p..

    [java] 백준 1786 (찾기) Gold 1
    Algorithm/Baekjoon Online Judge

    [java] 백준 1786 (찾기) Gold 1

    Problem : https://www.acmicpc.net/problem/1786 1786번: 찾기 첫째 줄에, T 중간에 P가 몇 번 나타나는지를 나타내는 음이 아닌 정수를 출력한다. 둘째 줄에는 P가 나타나는 위치를 차례대로 공백으로 구분해 출력한다. 예컨대, T의 i～i+m-1번 문자와 P의 1～m www.acmicpc.net Approach KMP 알고리즘을 활용한 연습문제이다. KMP 알고리즘에 대한 내용은 여기서 다루지 않고 다음 링크를 참고하면 좋을 것이다. 설명이 정말 명쾌하다. https://bowbowbow.tistory.com/6#comment5168448 KMP : 문자열 검색 알고리즘 문자열 검색이 뭐지? 워드프로세서를 사용할 때 찾기 기능을 사용한적 있을 겁니다. 브라우저에서도..

    [java] 백준 17472 (다리 만들기 2) Gold 3
    Algorithm/Baekjoon Online Judge

    [java] 백준 17472 (다리 만들기 2) Gold 3

    Problem : https://www.acmicpc.net/problem/17472 17472번: 다리 만들기 2 첫째 줄에 지도의 세로 크기 N과 가로 크기 M이 주어진다. 둘째 줄부터 N개의 줄에 지도의 정보가 주어진다. 각 줄은 M개의 수로 이루어져 있으며, 수는 0 또는 1이다. 0은 바다, 1은 땅을 의미한다. www.acmicpc.net Approach 삼성 A형 기출문제라고 한다. 만만치 않았다. 푸는 도중에도 풀이가 길어져서 이렇게 풀어도 되는지에 대해 계속 생각하게 만들었다. 문제 풀이에 앞서 크게 3가지의 알고리즘이 사용된다. 주어진 섬들의 numbering -> BFS/DFS numbering된 섬들끼리의 거리 계산 -> BruteForce(행렬로 주어졌으므로 다른 방법은 제한적이다..

    [java] 백준 20040 (사이클 게임) Gold 4
    Algorithm/Baekjoon Online Judge

    [java] 백준 20040 (사이클 게임) Gold 4

    Problem : https://www.acmicpc.net/problem/20040 20040번: 사이클 게임 사이클 게임은 두 명의 플레이어가 차례대로 돌아가며 진행하는 게임으로, 선 플레이어가 홀수 번째 차례를, 후 플레이어가 짝수 번째 차례를 진행한다. 게임 시작 시 0 부터 n − 1 까지 고유한 www.acmicpc.net Approach Union-Find 알고리즘을 활용하여 풀 수 있는 문제이다. 주어진 그래프가 사이클을 이루지 않는다면, m개의 간선을 처리할 동안 두 노드의 부모가 항상 달라야한다. 만약 간선을 처리하는 중, 두 노드의 부모가 같은 것이 나온다면, 두 노드는 이미 하나의 집합으로 묶여있는 상태이고, 같은 집합에 간선을 추가한다는 것은 곧 사이클을 만든다는 뜻이 된다. 따라..

    [java] 백준 4803 (트리) Gold 4
    Algorithm/Baekjoon Online Judge

    [java] 백준 4803 (트리) Gold 4

    Problem : https://www.acmicpc.net/problem/4803 4803번: 트리 입력으로 주어진 그래프에 트리가 없다면 "No trees."를, 한 개라면 "There is one tree."를, T개(T > 1)라면 "A forest of T trees."를 테스트 케이스 번호와 함께 출력한다. www.acmicpc.net Approach 트리의 기본성질을 이용한 문제이다. 트리의 경우 노드개수는 (간선의 개수 + 1)이다. 문제에서 각 테스트케이스마다 노드의 개수 n과 간선의 개수m이 주어진다. 노드가 연결되지 않은 경우도 있기 때문에, 모든 노드를 방문해 보아야한다. 또한, 양방향 간선으로 구성했기 때문에 주어진 그래프가 트리를 이룬다면 (간선의 개수 / 2 + 1)이 노드의 ..

    [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] 백준 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] 백준 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로 정한 후,범위를 좁혀나가며 용액의 특성값들을 ..

티스토리툴바