BOJ

    [java] 백준 7576 (토마토1) Silver 1
    Algorithm/Baekjoon Online Judge

    [java] 백준 7576 (토마토1) Silver 1

    Problem : https://www.acmicpc.net/problem/7576 7576번: 토마토 첫 줄에는 상자의 크기를 나타내는 두 정수 M,N이 주어진다. M은 상자의 가로 칸의 수, N은 상자의 세로 칸의 수를 나타낸다. 단, 2 ≤ M,N ≤ 1,000 이다. 둘째 줄부터는 하나의 상자에 저장된 토마토 www.acmicpc.net Approach 시작점이 여러개인 최단경로 문제이다. 문제에서 배열의 요소가 1인 모든 곳이 시작점이다. (따라서 요소가 1인 모든 좌표를 큐에 넣고 BFS를 수행한다.) 벽이 -1 로 막혀있지 않고, 범위를 벗어나지 않으며, 방문하지 않았다면, 방문하면서 직전 위치의 값 + 1을 방문하는 곳에 저장한다. BFS가 완전히 모두 수행된 후, 최단경로 배열을 검사하여..

    [java] 백준 2178 (미로 탐색) Silver 1
    Algorithm/Baekjoon Online Judge

    [java] 백준 2178 (미로 탐색) Silver 1

    Problem : https://www.acmicpc.net/problem/2178 2178번: 미로 탐색 첫째 줄에 두 정수 N, M(2 ≤ N, M ≤ 100)이 주어진다. 다음 N개의 줄에는 M개의 정수로 미로가 주어진다. 각각의 수들은 붙어서 입력으로 주어진다. www.acmicpc.net Approach (1, 1)에서 (n, n)까지의 최소 이동거리를 구하는 문제이다. BFS를 사용하여, 범위를 벗어나지 않고, 요소가 1이며, 방문하지 않았다면, 큐에 집어넣는 식으로 진행하였다. 방문할 곳에 직전 곳에 있는 값+1 을 저장해주면 (n, n)에 최소 비용이 저장될 것이다. BFS를 구현만 할줄 안다면, 쉬운 문제가 될 것이다. Code import java.io.*; import java.uti..

    [java] 백준 2667 (단지번호붙이기) Silver 1
    Algorithm/Baekjoon Online Judge

    [java] 백준 2667 (단지번호붙이기) Silver 1

    Problem : https://www.acmicpc.net/problem/2667 2667번: 단지번호붙이기 과 같이 정사각형 모양의 지도가 있다. 1은 집이 있는 곳을, 0은 집이 없는 곳을 나타낸다. 철수는 이 지도를 가지고 연결된 집의 모임인 단지를 정의하고, 단지에 번호를 붙이려 한다. 여 www.acmicpc.net Approach 보통 지도 형식의 배열이 나오면 BFS로 푸는게 더 나은 것 같다...(필자 생각) BFS, DFS 모두 풀이가 가능해도 더 좋은 풀이가 있는 문제처럼, 지도를 통한 탐색의 경우 필자는 BFS를 더 선호한다. (더 간단하기 때문 ㅎㅎ) 이 문제는 감을 익히기 위해서 두 방법 모두로 풀어봤다. 또한 이 문제는 프로그래머스에도 유사한 문제가 있다. 밑의 링크는 그 문제..

    [java] 백준 2606 (바이러스) Silver 3
    Algorithm/Baekjoon Online Judge

    [java] 백준 2606 (바이러스) Silver 3

    Problem : https://www.acmicpc.net/problem/2606 2606번: 바이러스 첫째 줄에는 컴퓨터의 수가 주어진다. 컴퓨터의 수는 100 이하이고 각 컴퓨터에는 1번 부터 차례대로 번호가 매겨진다. 둘째 줄에는 네트워크 상에서 직접 연결되어 있는 컴퓨터 쌍의 수가 주어 www.acmicpc.net Approach 여러 노드가 있을 때, X 라는 노드와 연결된 모든 노드의 개수를 구하면 되는 문제이다. -> 따라서 순회 문제라는 것을 빠르게 알아내어, 접근해야한다. DFS, BFS 중 아무거나 사용해도 되지만, 필자는 인접리슽으를 이용한 DFS 재귀 방식으로 풀이하였다. Code import java.io.*; import java.util.*; /** * no.2606: 바이러..

    [java] 백준 1260 (DFS와 BFS) Silver 2
    Algorithm/Baekjoon Online Judge

    [java] 백준 1260 (DFS와 BFS) Silver 2

    Problem : https://www.acmicpc.net/problem/1260 1260번: DFS와 BFS 첫째 줄에 정점의 개수 N(1 ≤ N ≤ 1,000), 간선의 개수 M(1 ≤ M ≤ 10,000), 탐색을 시작할 정점의 번호 V가 주어진다. 다음 M개의 줄에는 간선이 연결하는 두 정점의 번호가 주어진다. 어떤 두 정점 사 www.acmicpc.net Approach BFS(Breadth-First Search), DFS(Depth-First Search) 의 기본 문제이다. 일단 BFS, DFS 가 어떤 방식으로 돌아가는지를 알아야 한다. 사전적 정의는 DFS는 한 노드를 시작으로 인접한 다른 노드를 재귀적으로 탐색해가고 끝까지 탐색하면 다시 위로 와서 다음을 탐색하여 검색한다는 방식이고..

    [java] 백준 10942 (팰린드롬) Gold 2
    Algorithm/Baekjoon Online Judge

    [java] 백준 10942 (팰린드롬) Gold 2

    Problem : https://www.acmicpc.net/problem/10942 10942번: 팰린드롬? 총 M개의 줄에 걸쳐 홍준이의 질문에 대한 명우의 답을 입력으로 주어진 순서에 따라서 출력한다. 팰린드롬인 경우에는 1, 아닌 경우에는 0을 출력한다. www.acmicpc.net Approach 팰린드롬은 주어진 문자열을 거꾸로해도 원래의 문자열과 같은 경우를 말한다. 일반적으로 팰린드롬은 DP 문제가 아니지만, 하나의 문자열으로 범위를 나누어 팰린드롬인지를 검사할 때에는 DP를 써서 상태를 저장한다면 시간을 조금 단축시킬 수 있다. 일단 범위 (s, e) 가 팰린드롬이라면, 시작인덱스와 끝인덱스에 같은 수를 더하고 뺀 범위는 항상 팰린드롬이다. 예를 들어, (s, e) 가 팰린드롬이면, (s..

    [java] 백준 7579 (앱) Gold 3
    Algorithm/Baekjoon Online Judge

    [java] 백준 7579 (앱) Gold 3

    Problem : https://www.acmicpc.net/problem/7579 7579번: 앱 입력은 3줄로 이루어져 있다. 첫 줄에는 정수 N과 M이 공백문자로 구분되어 주어지며, 둘째 줄과 셋째 줄에는 각각 N개의 정수가 공백문자로 구분되어 주어진다. 둘째 줄의 N개의 정수는 현재 활 www.acmicpc.net Approach DP 문제로 냅색(KnapSack) 문제와 유사하다. N cost로 최대 몇 M size를 비활성화 할 수 있는지를 고민해서 풀어야 한다. DP[i][j] = i개의 앱이 있을 때, j cost로 비활성화 할 수 있는 최대 사이즈이다. 그런 후, X개 앱이 있을 때, Y size를 처음으로 넘기는 cost를 찾으면 된다. Code import java.io.*; impo..

    [java] 백준 1520 (내리막 길) Gold 4
    Algorithm/Baekjoon Online Judge

    [java] 백준 1520 (내리막 길) Gold 4

    Problem : https://www.acmicpc.net/problem/1520 1520번: 내리막 길 여행을 떠난 세준이는 지도를 하나 구하였다. 이 지도는 아래 그림과 같이 직사각형 모양이며 여러 칸으로 나뉘어져 있다. 한 칸은 한 지점을 나타내는데 각 칸에는 그 지점의 높이가 쓰여 있으 www.acmicpc.net Approach 최단거리 문제가 아니므로 미로문제 처럼 갈 수 있는 모든 곳을 방문해 봐야 한다. DP[i][j] = (i, j) 위치에서 최종 목적지까지 갈 수 있는 방법의 수라고 정의한다. DP[i][j] == 0 은 방문했음을 표시한 것이고, -1은 도달할 수 없는 곳이다. 현재 위치를 방문 했음을 표시하고, 상하좌우로 갈 수있는지 검사하여 갈 수 있다면 재귀를 돌리면서 리턴 값..

    [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 이다...

티스토리툴바