자바(Java) 백준 9019 DSLR 풀이
2022. 7. 26. 23:45
알고리즘 풀이/백준
문제 https://www.acmicpc.net/problem/9019 9019번: DSLR 네 개의 명령어 D, S, L, R 을 이용하는 간단한 계산기가 있다. 이 계산기에는 레지스터가 하나 있는데, 이 레지스터에는 0 이상 10,000 미만의 십진수를 저장할 수 있다. 각 명령어는 이 레지스터에 www.acmicpc.net 풀이 bfs로 문제를 풀어주면 됩니다. 숫자들을 계산할 때 이미 중간 계산결과로 나온 값은 방문체크를 해주고 큐에 넣지 않아야 시간초과를 면할 수 있습니다. 큐에 중간 계산 값과 현재까지 사용된 명령어들을 저장하기 위해 Info클래스를 생성해줍니다. 중간 계산 값이 이미 나온적이 있다면 넘어갑니다. 각 계산과정인 D, S, L, R값을 계산해주고 큐에 넣어주면 됩니다. 중간 값은..
자바(Java) 백준 16948 데스 나이트 풀이
2022. 7. 26. 21:45
알고리즘 풀이/백준
문제 https://www.acmicpc.net/problem/16948 16948번: 데스 나이트 게임을 좋아하는 큐브러버는 체스에서 사용할 새로운 말 "데스 나이트"를 만들었다. 데스 나이트가 있는 곳이 (r, c)라면, (r-2, c-1), (r-2, c+1), (r, c-2), (r, c+2), (r+2, c-1), (r+2, c+1)로 이동할 수 있다. 크 www.acmicpc.net 풀이 해당 문제는 bfs로 풀었습니다. 체스말의 위치와 움직인 횟수를 저장하는 Night클래스를 만들어줍니다. bfs를 통해서 큐에 넣은 값을 꺼내서 체스말을 움직여줍니다. 6가지 방향은 dx, dy배열을 통해서 for문으로 6가지 방향을 선택하도록 구현하였습니다. visited배열에 움직인 위치를 방문했다는 것을..
자바(Java) 백준 16928 뱀과 사다리 게임 풀이
2022. 7. 26. 21:13
알고리즘 풀이/백준
문제 https://www.acmicpc.net/problem/16928 [16928번: 뱀과 사다리 게임 첫째 줄에 게임판에 있는 사다리의 수 N(1 ≤ N ≤ 15)과 뱀의 수 M(1 ≤ M ≤ 15)이 주어진다. 둘째 줄부터 N개의 줄에는 사다리의 정보를 의미하는 x, y (x < y)가 주어진다. x번 칸에 도착하면, y번 칸으 www.acmicpc.net](https://www.acmicpc.net/problem/16928) 풀이 bfs를 통하여 문제를 풀었습니다. 처음에 방문체크를 하지 않고 했더니 메모리 초과가 뜨네요. 한 번 방문한 지점은 다시 방문했을 때 큐에 들어가지 않도록 해주는 과정이 중요합니다. map에 사다리와 뱀 값을 넣어줍니다. 큐에 현재 위치와 움직인 횟수 정보를 담은 In..
자바(Java) 백준 2048(easy) 풀이
2022. 7. 26. 20:17
알고리즘 풀이/백준
문제 https://www.acmicpc.net/problem/12100 [12100번: 2048 (Easy) 첫째 줄에 보드의 크기 N (1 ≤ N ≤ 20)이 주어진다. 둘째 줄부터 N개의 줄에는 게임판의 초기 상태가 주어진다. 0은 빈 칸을 나타내며, 이외의 값은 모두 블록을 나타낸다. 블록에 쓰여 있는 수는 2 www.acmicpc.net](https://www.acmicpc.net/problem/12100) 풀이 이 문제는 dfs를 사용하여 접근하였습니다. 경우의 수는 상, 하, 좌, 우 4가지 경우의 수가 있습니다. 따라서 for 문으로 4가지 방향에 대해서 블록을 이동시켜줍니다. 기존 board 배열에서 copy 라는 새로운 배열을 만들어줘서 한줄씩 이동시켜줍니다. 값이 0이 아닌 경우에 값..
자바(Java) 백준 13460 구슬 탈출 2 풀이
2022. 7. 26. 00:54
알고리즘 풀이/백준
문제 https://www.acmicpc.net/problem/13460 13460번: 구슬 탈출 2 첫 번째 줄에는 보드의 세로, 가로 크기를 의미하는 두 정수 N, M (3 ≤ N, M ≤ 10)이 주어진다. 다음 N개의 줄에 보드의 모양을 나타내는 길이 M의 문자열이 주어진다. 이 문자열은 '.', '#', 'O', 'R', 'B' www.acmicpc.net 풀이 이 문제는 Bfs를 사용하여 풀었습니다. 생각해줄 조건이 조금 까다롭습니다. 두 구슬을 동시에 움직이므로 생각해줘야 할게 많아진 것 같습니다. 먼저 빨간 구슬과 파란 구슬의 초기 위치를 저장합니다. 큐에 정보를 넣기 위해 빨간 구슬의 위치, 파란 구슬의 위치, 움직인 횟수 정보를 가지고 있는 PairBeads 클래스를 만듭니다. bfs는..
자바(Java) 백준 1062 가르침 풀이
2022. 7. 25. 15:06
알고리즘 풀이/백준
문제 https://www.acmicpc.net/problem/1062 1062번: 가르침 첫째 줄에 단어의 개수 N과 K가 주어진다. N은 50보다 작거나 같은 자연수이고, K는 26보다 작거나 같은 자연수 또는 0이다. 둘째 줄부터 N개의 줄에 남극 언어의 단어가 주어진다. 단어는 영어 소문 www.acmicpc.net 풀이 저는 dfs와 조합으로 문제를 풀었습니다. 학생들이 어떤 알파벳을 배웠는지 알 수 있는 aplhaArr라는 boolean 배열을 만들어줍니다. 문제에서 anta, tica 두개의 접두사와 접미사가 단어 안에 무조건 들어가야합니다. 따라서 a, n, t, i, c 5개의 알파벳은 학생들이 배우지 않는다면 어떤 단어도 읽을 수가 없습니다. 따라서 k가 5개 미만이라면 어떤 단어도 읽..
자바(Java) 백준 14501 퇴사 풀이
2022. 7. 18. 18:12
알고리즘 풀이/백준
문제 https://www.acmicpc.net/problem/14501 14501번: 퇴사 첫째 줄에 백준이가 얻을 수 있는 최대 이익을 출력한다. www.acmicpc.net 풀이 저는 dfs를 사용하여 풀었지만 해당 문제를 dp로 푸신 분들이 많네요. 이 문제의 의도 자체도 dp를 생각하고 만든 문제같긴합니다. 백트래킹을 조합해서 푸니까 시간 초과는 나지 않네요 130ms정도 걸렸습니다. dp로 풀고 싶은 분들은 다른 블로그를 참고해주세요. 제가 문제를 푼 방식은 다음과 같습니다. visited[i]에 i 날에 스케줄을 등록했는지 안했는지 체크해줍니다. dfs를 통해 1일부터 n 일까지 해당하는 날짜에 스케줄을 잡는 경우와 안 잡는 경우 2가지로 나눠서 탐색합니다. 해당하는 날짜에 스케줄을 잡으려면..
자바(Java) 백준 1987 알파벳 풀이
2022. 7. 18. 17:31
알고리즘 풀이/백준
문제 https://www.acmicpc.net/problem/1987 1987번: 알파벳 세로 R칸, 가로 C칸으로 된 표 모양의 보드가 있다. 보드의 각 칸에는 대문자 알파벳이 하나씩 적혀 있고, 좌측 상단 칸 (1행 1열) 에는 말이 놓여 있다. 말은 상하좌우로 인접한 네 칸 중의 한 칸으 www.acmicpc.net 풀이 dfs로 탐색해서 풀 수 있는 문제입니다. 제가 풀이한 방식은 다음과 같습니다. 각 알파벳을 한 번만 사용할 수 있으므로 방문했는지 확인하는 배열이 필요합니다. 방문 체크는 아스키코드를 활용하여 각 알바펫의 아스키 코드를 인덱스로 하여 체크합니다. (0, 0) 점에 있는 알파벳을 먼저 방문 체크한뒤에 dfs로 탐색합니다. 상하좌우 4방향으로 이동하면서 조건들을 만족하는지 확인한 ..