BOJ

    [Java] 백준 1865 (웜홀) Gold 4
    Algorithm/Baekjoon Online Judge

    [Java] 백준 1865 (웜홀) Gold 4

    Problem : https://www.acmicpc.net/problem/1865 1865번: 웜홀 첫 번째 줄에는 테스트케이스의 개수 TC(1 ≤ TC ≤ 5)가 주어진다. 그리고 두 번째 줄부터 TC개의 테스트케이스가 차례로 주어지는데 각 테스트케이스의 첫 번째 줄에는 지점의 수 N(1 ≤ N ≤ 500), www.acmicpc.net Approach 문제에서 음수 사이클이 있는지를 물어보기에, 당연스럽게 벨만-포드 알고리즘을 시도해봤다. 벨만-포드 알고리즘은 시간복잡도가 O(VE) 인데, 간선의 개수가 V^2에 근사할 수 있으므로 최대 O(V^3)의 시간복잡도를 가진다. 이는 다익스트라 알고리즘의 시간복잡도인 O(V^2)보다 크지만, 음수 사이클을 판별해야 하는 문제에서는 다익스트라를 사용할 수 ..

    [Java] 백준 1799 (비숍) Gold 2
    Algorithm/Baekjoon Online Judge

    [Java] 백준 1799 (비숍) Gold 2

    Problem : https://www.acmicpc.net/problem/1799 1799번: 비숍 첫째 줄에 체스판의 크기가 주어진다. 체스판의 크기는 10이하의 자연수이다. 둘째 줄부터 아래의 예와 같이 체스판의 각 칸에 비숍을 놓을 수 있는지 없는지에 대한 정보가 체스판 한 줄 단위로 www.acmicpc.net Approach 백트랙킹(Backtracking) 문제이다. 시간제한 10초이고, 체스판의 크기가 n x n 이라고 하여, N-Queens 문제와 같이 백트랙킹을 시도하면 시간초과가 날 것이다. N-Queens 에서는 임의의 행에 퀸을 하나 놓았다면, 그 행의 다른 열에 대해서는 검사를 하지 않았기에 가능하였다. 하지만, 여기서는 체스판의 요소가 모두 1이고(모든 곳에 비숍을 놓을 수 있..

    [Java] 백준 1202 (보석 도둑) Gold 2
    Algorithm/Baekjoon Online Judge

    [Java] 백준 1202 (보석 도둑) Gold 2

    Problem : https://www.acmicpc.net/problem/1202 1202번: 보석 도둑 첫째 줄에 N과 K가 주어진다. (1 ≤ N, K ≤ 300,000) 다음 N개 줄에는 각 보석의 정보 Mi와 Vi가 주어진다. (0 ≤ Mi, Vi ≤ 1,000,000) 다음 K개 줄에는 가방에 담을 수 있는 최대 무게 Ci가 주어진다. (1 ≤ Ci www.acmicpc.net Approach 우선순위 큐를 활용한 Greedy 문제이다. 접근법을 떠올렸다면 쉽게 구현할 수 있다. (PriorityQueue 이용하여) 먼저 보석과 가방을 각각 무게 기준 오름차순으로 정렬한다. 각 가방에 대하여 가방의 무게보다 작은 보석들을 pq에 넣는다. (pq는 보석의 가치 기준 내림차순의 우선순위를 가진다...

    [Java] 백준 2098 (외판원 순회) Gold 1
    Algorithm/Baekjoon Online Judge

    [Java] 백준 2098 (외판원 순회) Gold 1

    Problem : https://www.acmicpc.net/problem/2098 2098번: 외판원 순회 첫째 줄에 도시의 수 N이 주어진다. (2 ≤ N ≤ 16) 다음 N개의 줄에는 비용 행렬이 주어진다. 각 행렬의 성분은 1,000,000 이하의 양의 정수이며, 갈 수 없는 경우는 0이 주어진다. W[i][j]는 도시 i에서 j www.acmicpc.net Approach 대표적인 외판원 문제 (TSP: Traveling Salesman Problem) 이다. 어떤 지점 A에서 모든 지점을 돌아 다시 A로 오는 최소 비용 경로를 찾으면 된다. (완전탐색) 시작 지점은 아무 곳에서 시작해도 된다. 어디서 시작하든 최소 비용 사이클은 동일하기 때문이다. 코드의 주석처럼 도시가 4개일 때, 1001이..

    [Java] 백준 1509 (팰린드롬 분할) Gold 1
    Algorithm/Baekjoon Online Judge

    [Java] 백준 1509 (팰린드롬 분할) Gold 1

    Problem : https://www.acmicpc.net/problem/1509 1509번: 팰린드롬 분할 세준이는 어떤 문자열을 팰린드롬으로 분할하려고 한다. 예를 들어, ABACABA를 팰린드롬으로 분할하면, {A, B, A, C, A, B, A}, {A, BACAB, A}, {ABA, C, ABA}, {ABACABA}등이 있다. 분할의 개수의 최솟값을 출력하 www.acmicpc.net Approach 주어진 문자열이 최소 몇 개의 팰린드롬 문자열로 구성되어 있는지를 구하는 문제이다. 팰린드롬 문자열 자체를 구하는 로직은 O(n^2) 의 시간복잡도를 가진다. 팰린드롬 문자열을 구하는 방법은 투포인터를 사용하였다. DP[i] 는 0 ~ i인덱스의 문자열이 몇 개의 최소 팰린드롬 문자열로 구성되는지..

    [Java] 백준 2568 (전깃줄 - 2) Gold 1
    Algorithm/Baekjoon Online Judge

    [Java] 백준 2568 (전깃줄 - 2) Gold 1

    Problem : https://www.acmicpc.net/problem/2568 2568번: 전깃줄 - 2 첫째 줄에는 두 전봇대 사이의 전깃줄의 개수가 주어진다. 전깃줄의 개수는 100,000 이하의 자연수이다. 둘째 줄부터 한 줄에 하나씩 전깃줄이 A전봇대와 연결되는 위치의 번호와 B전봇대와 연결 www.acmicpc.net Approach 겉으로는 그렇게 보이지 않을지도 모르지만 LIS (Longest Increase Subsequence) 문제이다. 한 쪽 전봇대를 오름차순으로 정렬한 뒤, 최대 LIS의 요소가 아닌 전깃줄들을 제거하면 된다. LIS 는 시간제한에 따라(입력데이터의 범위에 따라) DP 혹은 이분탐색으로 풀이가 가능한데, 여기서는 이분탐색으로 풀이를 해야한다. 이분 탐색을 이용하..

    [Java] 백준 1562 (계단 수) Gold 1
    Algorithm/Baekjoon Online Judge

    [Java] 백준 1562 (계단 수) Gold 1

    Problem : https://www.acmicpc.net/problem/1562 1562번: 계단 수 첫째 줄에 정답을 1,000,000,000으로 나눈 나머지를 출력한다. www.acmicpc.net Approach Bitmasking을 이용한 DP문제였다. 그냥 계단수를 구하는 문제를 풀어본 기억이 있어 일단 DP를 떠올렸다. 그리고 보통 사용한 숫자를 체크할 때에는 Bitmasking을 사용했기에 이 문제도 그렇게 접근해 보았다. i자리 계단수를 구하는 방법은 i-1자리 계단수의 끝자리에 +1 한 숫자와 -1 한 숫자를 붙인 계단수의 합이다. 하지만 끝자리가 0과 9인 경우에는 각각 +1한 숫자, -1한 숫자만 고려해야한다. 34가 계단수임을 알고 있으면 343도(-1한 숫자를 붙인 것) 계단수..

    [Java] 백준 16946 (벽 부수고 이동하기 4) Gold 2
    Algorithm/Baekjoon Online Judge

    [Java] 백준 16946 (벽 부수고 이동하기 4) Gold 2

    Problem : https://www.acmicpc.net/problem/16946 16946번: 벽 부수고 이동하기 4 N×M의 행렬로 표현되는 맵이 있다. 맵에서 0은 이동할 수 있는 곳을 나타내고, 1은 이동할 수 없는 벽이 있는 곳을 나타낸다. 한 칸에서 다른 칸으로 이동하려면, 두 칸이 인접해야 한다. 두 칸이 www.acmicpc.net Approach BFS/DFS 문제이다. 하지만 각 점마다 탐색을 한다면 TLE 를 면치 못할 것이다. 각 벽에서 도달할 수 있는 칸이 몇개인지 판단하기 전에 한번의 탐색이 선행되어야 한다. 바로 각 칸이 속하는 그룹의 종류와 그 그룹의 크기를 구해놔야 한다. 따라서 나는 다음과 같은 변수를 사용했다. int[][] group: (i, j) 점이 무슨 그룹인..

    [Java] 백준 17143 (낚시왕) Gold 2
    Algorithm/Baekjoon Online Judge

    [Java] 백준 17143 (낚시왕) Gold 2

    Problem : https://www.acmicpc.net/problem/17143 17143번: 낚시왕 낚시왕이 상어 낚시를 하는 곳은 크기가 R×C인 격자판으로 나타낼 수 있다. 격자판의 각 칸은 (r, c)로 나타낼 수 있다. r은 행, c는 열이고, (R, C)는 아래 그림에서 가장 오른쪽 아래에 있는 칸이다. www.acmicpc.net Approach 삼성 역량 테스트 문제이다. 역시 구현 시뮬레이션 문제. 크게 아래 두가지를 구현하여야 한다. 구현하는게 좀 어렵다. 상어 잡기 상어 이동 1번 과정인 상어 잡기는 쉽다. 그냥 j 열에서 가장 가까운 i 행에 있는 상어를 잡으면 된다. 까다로운 부분은 2번 과정인 상어 이동이다. 나는 다음과 같은 변수를 사용하였다. int[][] map: 상어..

    [Java] 백준 16724 (피리 부는 사나이) Gold 2
    Algorithm/Baekjoon Online Judge

    [Java] 백준 16724 (피리 부는 사나이) Gold 2

    Problem : https://www.acmicpc.net/problem/16724 16724번: 피리 부는 사나이 첫 번째 줄에 지도의 행의 수를 나타내는 N(1 ≤ N ≤ 1,000)과 지도의 열의 수를 나타내는 M(1 ≤ M ≤ 1,000)이 주어진다. 두 번째 줄부터 N개의 줄에 지도의 정보를 나타내는 길이가 M인 문자열이 주 www.acmicpc.net First Approach 처음 문제를 보고 단순 BFS 인 줄 알았다. 하지만 시작점에 따라 집합의 개수가 달라진다. // ex 2 4 DLDL RLRL // 단순 BFS로 (0,0)부터 시작하면 4를 뱉는다. 정답은 2이다. Approach 집합(사이클)의 개수가 몇 개인지를 찾는 문제이다. Union-Find 알고리즘을 사용하였다. 범위를..

티스토리툴바