본문 바로가기

백준

BOJ 백준 14499번 주사위 굴리기 Java 14499번: 주사위 굴리기 첫째 줄에 지도의 세로 크기 N, 가로 크기 M (1 ≤ N, M ≤ 20), 주사위를 놓은 곳의 좌표 x, y(0 ≤ x ≤ N-1, 0 ≤ y ≤ M-1), 그리고 명령의 개수 K (1 ≤ K ≤ 1,000)가 주어진다. 둘째 줄부터 N개의 줄에 지 www.acmicpc.net 이 문제는 지도 위에서 주사위는 동(1), 서(2), 북(3), 남(4) 방향으로 굴릴 때 주사위의 윗면의 수를 출력해야 합니다 가장 중점적으로 봐야할 점은 주사위를 4방향으로 굴릴 때, 각 위치가 어떻게 변하는지입니다. 따라서 저는 0부터 5까지 바닥, 동, 서, 남, 북, 위를 설정하고, 4방향으로 굴릴 때의 위치 변화를 저장하는 배열을 만들었습니다. 가장 먼저 각 명령마다 지도의 범위를 벗어나.. 더보기
BOJ 백준 28069번 김밥천국의 계단 Java 28069번: 김밥천국의 계단 첫 번째 줄에 계단 개수에 해당하는 $N$, 계단을 오르는 횟수 $K$가 주어진다. $(1 \leq N, K \leq 1\,000\,000)$ www.acmicpc.net 김밥천국의 위치인 N와 도달 횟수 K가 주어집니다. 1. 계단 한 칸 올라가기 2. 지팡이를 사용해서 i번째 계단일 때 i + i/2째 계단으로 순간이동 이렇게 2가지 행동 중 하나를 선택해서 K번째 행동에서 N에 도달해야 합니다. 풀이 2번 행동의 특성을 파악하는 것이 중요하다고 생각해서, 42번째 계단까지 10번째에 도달할 수 있는지 파악해보았습니다. 1. 짝수, 3의 배수 i번째 계단에서 1번 혹은 2번 방법으로 도달할 수 있는 계단을 다 나열해보니, 3 이상일 때 규칙이 보였습니다. 2번째 방법을 .. 더보기
[BOJ 백준] 2531번 회전초밥 (Java) 주어진 회전 초밥 벨트에서 먹을 수 있는 초밥의 가짓수의 최댓값을 하나의 정수로 출력한다. 2531번: 회전 초밥 첫 번째 줄에는 회전 초밥 벨트에 놓인 접시의 수 N, 초밥의 가짓수 d, 연속해서 먹는 접시의 수 k, 쿠폰 번호 c가 각각 하나의 빈 칸을 사이에 두고 주어진다. 단, 2 ≤ N ≤ 30,000, 2 ≤ d ≤ 3,000, 2 ≤ www.acmicpc.net 처음에는 List와 Set을 사용해서 풀었지만, 매번 N이 최대 30,000, k가 최대 3,000이기 때문에 시간초과가 났습니다. 해결 방법 1. 슬라이딩 윈도우 크기가 d인 selected라는 정수 배열을 이용합니다. 현재 선택된 초밥의 번호를 인덱스로 하여 개수를 늘립니다. 초기 세팅을 한 후 0부터 N까지 탐색하면서, 윈도우에.. 더보기
[BOJ 백준] 2031번 가스관 (Java) 2931번: 가스관 www.acmicpc.net import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.LinkedList; import java.util.Queue; import java.util.StringTokenizer; public class Main { static class Position { int x; int y; Position(int x, int y) { this.x = x; this.y = y; } } static int R, C, blockCount; static int[] dx = { 1, 0, -1, 0 }, dy = { 0, -1, 0,.. 더보기
[백준] 1992번 - 쿼드트리(Quad Tree) (재귀) (Swift) 쿼드트리 문제 흑백 영상을 압축하여 표현하는 데이터 구조로 쿼드 트리(Quad Tree)라는 방법이 있다. 흰 점을 나타내는 0과 검은 점을 나타내는 1로만 이루어진 영상(2차원 배열)에서 같은 숫자의 점들이 한 곳에 많이 몰려있으면, 쿼드 트리에서는 이를 압축하여 간단히 표현할 수 있다. 주어진 영상이 모두 0으로만 되어 있으면 압축 결과는 "0"이 되고, 모두 1로만 되어 있으면 압축 결과는 "1"이 된다. 만약 0과 1이 섞여 있으면 전체를 한 번에 나타내지를 못하고, 왼쪽 위, 오른쪽 위, 왼쪽 아래, 오른쪽 아래, 이렇게 4개의 영상으로 나누어 압축하게 되며, 이 4개의 영역을 압축한 결과를 차례대로 괄호 안에 묶어서 표현한다 위 그림에서 왼쪽의 영상은 오른쪽의 배열과 같이 숫자로 주어지며, 이.. 더보기
[백준] 2630번 - 색종이 만들기 (재귀) (swift) 재귀란? 하나의 함수에서 자기 자신을 다시 호출해 작업을 수행하는 알고리즘이다. 절차지향적 사고 vs 귀납적 사고 → 과정을 하나하나 따라가는 대신 귀납적인 사고로 이해하기 재귀 함수의 조건 특정 입력에 대해서는 자기 자신을 호출하지 않고 종료되어야 함(Base condition) 모든 입력은 base condition을 수렴해야 함 → 이 두 조건 중 어느 하나라도 지켜지지 않는다면 재귀 함수는 결과를 내지 못하고 무한히 들어가다가 런타임 에러가 날 것 재귀에 대한 정보 1 함수의 정의를 명확하게: 함수의 인자로 어떤 것을 받고 어디까지 계산한 후 자기 자신에게 넘겨줄지 명확하게 정해야 함 모든 재귀 함수는 반복문만으로 동일한 동작을 하는 함수를 만들 수 있음. 재귀는 반복문으로 구현했을 때에 비해 코.. 더보기
반응형

티스토리툴바