2178번: 미로 탐색 첫째 줄에 두 정수 N, M(2 ≤ N, M ≤ 100)이 주어진다. 다음 N개의 줄에는 M개의 정수로 미로가 주어진다. 각각의 수들은 붙어서 입력으로 주어진다. www.acmicpc.net 문제 예제 풀이 해당 문제도 DFS와 BFS를 둘 다 사용해도 되지만 DFS로 풀게 되면 시간초과가 발생한다. 그렇기에 DFS보다 비교적 계산속도가 빠른 BFS를 통해서 문제를 해결해야한다. [백준] 1260번 : DFS와 BFS 1260번: DFS와 BFS 첫째 줄에 정점의 개수 N(1 ≤ N ≤ 1,000), 간선의 개수 M(1 ≤ M ≤ 10,000), 탐색을 시작할 정점의 번호 V가 주어진다. 다음 M개의 줄에는 간선이 연결하는 두 정점의 번호가 주어진다. pids.tistory.com..

1874번: 스택 수열 1부터 n까지에 수에 대해 차례로 [push, push, push, push, pop, pop, push, push, pop, push, push, pop, pop, pop, pop, pop] 연산을 수행하면 수열 [4, 3, 6, 8, 7, 5, 2, 1]을 얻을 수 있다. www.acmicpc.net 문제 예제 소스 코드 import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.Stack; public class Main { public static void main(String[] args) throws IOException { Buffe..

18111번: 마인크래프트 팀 레드시프트는 대회 준비를 하다가 지루해져서 샌드박스 게임인 ‘마인크래프트’를 켰다. 마인크래프트는 1 × 1 × 1(세로, 가로, 높이) 크기의 블록들로 이루어진 3차원 세계에서 자유롭게 www.acmicpc.net 문제 예제 풀이 이차원 배열 arr[N][M] 을 채워준다. 채워주는 동시에 층이 가장 낮은 값과, 가장 높은 값을 구해서 max, min 변수에 따로 담아둔다. 그리고 min 부터 max 까지 반복하는 반복문을 통해 시간이 가장 적게 드는 값과 층을 구한다. 코드를 확인하면 이해하기 쉽다. 소스 코드 import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReade..

4949번: 균형잡힌 세상 하나 또는 여러줄에 걸쳐서 문자열이 주어진다. 각 문자열은 영문 알파벳, 공백, 소괄호("( )") 대괄호("[ ]")등으로 이루어져 있으며, 길이는 100글자보다 작거나 같다. 각 줄은 마침표(".")로 끝난다 www.acmicpc.net 문제 예제 풀이 9012번 괄호 문제의 업그레이드 버전인 문제라고 할 수 있다. [백준] 9012번 : 괄호 9012번: 괄호 괄호 문자열(Parenthesis String, PS)은 두 개의 괄호 기호인 ‘(’ 와 ‘)’ 만으로 구성되어 있는 문자열이다. 그 중에서 괄호의 모양이 바르게 구성된 문자열을 올바른 괄호 문자열(Valid P pids.tistory.com 문자열 입력을 받고 해당 문자열이 .이면 종료하고 버퍼에 있는 걸 출력한다..

10773번: 제로 첫 번째 줄에 정수 K가 주어진다. (1 ≤ K ≤ 100,000) 이후 K개의 줄에 정수가 1개씩 주어진다. 정수는 0에서 1,000,000 사이의 값을 가지며, 정수가 "0" 일 경우에는 가장 최근에 쓴 수를 지우고, 아닐 경 www.acmicpc.net 문제 예제 풀이 스택의 구조(LIFO)를 잘 이해한다면 쉽게 해결이 가능한 문제이다. 입력되는 숫자가 0 이상이라면 스택에 push()하고, 0이라면 스택에 pop()을 하면 된다. 그러고 스택이 비어있을 때까지 변수에 스택의 값을 더해주고, 최종적으로 해당 변수를 출력하면 된다. 소스 코드 import java.io.BufferedReader; import java.io.IOException; import java.io.Inpu..

10845번: 큐 첫째 줄에 주어지는 명령의 수 N (1 ≤ N ≤ 10,000)이 주어진다. 둘째 줄부터 N개의 줄에는 명령이 하나씩 주어진다. 주어지는 정수는 1보다 크거나 같고, 100,000보다 작거나 같다. 문제에 나와있지 www.acmicpc.net 문제 풀이 [Java]컬렉션 프레임웍 (3) - Stack & Queue 스택과 큐 (Stack & Queue) ▶ 스택(Stack) : LIFO구조. 마지막에 저장된 것을 제일 먼저 꺼내게 된다. 스택은 밑이 막힌 상자이다. 상자에 0, 1, 2를 순서대로 넣게 되면 꺼낼 때는 마지막에 넣었던 2, 1, 0 pids.tistory.com 큐의 구조와 원리를 파악한다면 쉽게 해결이 가능한 문제이다. 큐를 사용하여 해결하는 방법과, 큐를 직접 구현하..

2606번: 바이러스 첫째 줄에는 컴퓨터의 수가 주어진다. 컴퓨터의 수는 100 이하이고 각 컴퓨터에는 1번 부터 차례대로 번호가 매겨진다. 둘째 줄에는 네트워크 상에서 직접 연결되어 있는 컴퓨터 쌍의 수가 주어 www.acmicpc.net 문제 예제 풀이 DFS(깊이 우선 탐색) 와 BFS(넓이 우선 탐색)을 활용한 대표적인 문제이다. [백준] 1260번 : DFS와 BFS 1260번: DFS와 BFS 첫째 줄에 정점의 개수 N(1 ≤ N ≤ 1,000), 간선의 개수 M(1 ≤ M ≤ 10,000), 탐색을 시작할 정점의 번호 V가 주어진다. 다음 M개의 줄에는 간선이 연결하는 두 정점의 번호가 주어진다. pids.tistory.com 1260번 문제를 통해서 DFS와 BFS의 구조와 방식을 이해했다..

11726번: 2×n 타일링 2×n 크기의 직사각형을 1×2, 2×1 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오. 아래 그림은 2×5 크기의 직사각형을 채운 한 가지 방법의 예이다. www.acmicpc.net 문제 풀이 2 * N 의 경우의 수는 2 * (N - 1)의 경우의 수와 2 * (N - 2)의 경우의 수의 합과 같다. 즉, 배열을 생성하여 2 * 1일때는 1개의 경우의 수와 2 * 2일때는 2개의 경우의 수가 있으니 배열에 넣어주고, 반복문을 통해서 i를 3부터 시작하여 i - 2와 i -1을 더한값을 arr[i]에 넣어주면 된다. 여기서 주의할 점은 연산할 때마다 mod 연산을 해주어야 한다. 계속 숫자를 더하고 마지막 출력시에만 mod연산을 해줄 경우 Integer.MAX_V..

2579번: 계단 오르기 계단 오르기 게임은 계단 아래 시작점부터 계단 꼭대기에 위치한 도착점까지 가는 게임이다. 과 같이 각각의 계단에는 일정한 점수가 쓰여 있는데 계단을 밟으면 그 계단에 쓰여 있는 점 www.acmicpc.net 문제 입출력 예제 소스 코드 import java.io.*; import java.util.*; public class Main { public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); int N = Integer.parseInt(br.readLine()); int[] DP = new int..

9093번: 단어 뒤집기 첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스는 한 줄로 이루어져 있으며, 문장이 하나 주어진다. 단어의 길이는 최대 20, 문장의 길이는 최대 1000이다. 단어와 단어 사이에는 www.acmicpc.net 문제 풀이 방법 1 : reverse() 메서드 직접 구현 입력되는 문자열을 뒤집어주는 메서드를 직접 구현하여 단어를 뒤집는다. 방법 2 : stack stack의 LIFO구조(마지막에 저장된 것을 제일 먼저 꺼냄)를 활용하여 단어를 뒤집는다. 소스코드 방법 1 : 직접 구현 import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import j..