CSE 전공노트

개인적인 풀이일 뿐, 최적의 정답이 아님을 알려드립니다. 문제 www.acmicpc.net/problem/5014 5014번: 스타트링크 첫째 줄에 F, S, G, U, D가 주어진다. (1 ≤ S, G ≤ F ≤ 1000000, 0 ≤ U, D ≤ 1000000) 건물은 1층부터 시작하고, 가장 높은 층은 F층이다. www.acmicpc.net 난이도: 골드 5 사용언어: JAVA 풀이 이 문제는 BFS를 사용하여 해결하는 대표적인 유형의 문제입니다. 출발층에서 BFS를 시작하여 스타트링크가 있는 G 층에 도달할 때까지 BFS를 반복해주기만 하면 됩니다. 물론 가장 빨리 도착하는 한 가지 경로만 찾으면 되므로 한 번 도착한 층은 마킹을 해주어 다시 검사하지 않도록 합니다. 1 2 3 4 5 6 7 8 ..

개인적인 풀이일 뿐, 최적의 정답이 아님을 알려드립니다. 문제 www.acmicpc.net/problem/14503 14503번: 로봇 청소기 로봇 청소기가 주어졌을 때, 청소하는 영역의 개수를 구하는 프로그램을 작성하시오. 로봇 청소기가 있는 장소는 N×M 크기의 직사각형으로 나타낼 수 있으며, 1×1크기의 정사각형 칸으로 나누어 www.acmicpc.net 난이도: 골드 5 사용언어: JAVA 풀이 사실 어떤 알고리즘 문제가 아니라 구현 문제라서, 문제의 조건대로 쭉 구현해주시면 됩니다. 그리고 주의해야 할 점은 청소는 북-서-남-동으로 이루어지지만, 입력을 받을 때 d 값은 0이 북쪽, 1이 동쪽, 2가 남쪽, 3이 서쪽으로 방향이 반대라는 점입니다. 저는 3차원 배열을 이용해 현재의 방향과 이동할..

개인적인 풀이일 뿐, 최적의 정답이 아님을 알려드립니다. 문제 www.acmicpc.net/problem/1937 1937번: 욕심쟁이 판다 n*n의 크기의 대나무 숲이 있다. 욕심쟁이 판다는 어떤 지역에서 대나무를 먹기 시작한다. 그리고 그 곳의 대나무를 다 먹어 치우면 상, 하, 좌, 우 중 한 곳으로 이동을 한다. 그리고 또 그곳에서 www.acmicpc.net 난이도: 골드 3 사용언어: JAVA 풀이 이 문제는 DFS와 다이나믹 프로그래밍을 함께 이용하여 해결할 수 있습니다. dfs에 관한 기본적인 내용은 아래 문제의 풀이에서 볼 수 있습니다. jooona.tistory.com/65 [BOJ] 1303 - 전쟁 - 전투 -개인적인 풀이일 뿐, 최적의 정답이 아님을 알려드립니다. 문제 설명 www..

-개인적인 풀이일 뿐, 최적의 정답이 아님을 알려드립니다. 문제 www.acmicpc.net/problem/1662 1662번: 압축 압축되지 않은 문자열 S가 주어졌을 때, 이 문자열중 어떤 부분 문자열은 K(Q)와 같이 압축 할 수 있다. K는 한자리 정수이고, Q는 0자리 이상의 문자열이다. 이 Q라는 문자열이 K번 반복된다는 뜻이 www.acmicpc.net 난이도: 골드 5 사용언어: JAVA 풀이 이 문제는 스택을 이용할 수도 있지만, 저는 재귀를 이용해 문제를 해결했습니다. 문자열에서 '('를 만나면 재귀 함수를 시작하고 ')'를 만나면 재귀를 탈출하는 형식으로 코드를 작성했습니다. 재귀 함수의 동작은 아래와 같습니다. 1. '('를 만나면 재귀 함수 시작 2. 또 다른 '(' 또는 ')'를..

개인적인 풀이일 뿐, 최적의 정답이 아님을 알려드립니다. 문제 www.acmicpc.net/problem/3055 3055번: 탈출 사악한 암흑의 군주 이민혁은 드디어 마법 구슬을 손에 넣었고, 그 능력을 실험해보기 위해 근처의 티떱숲에 홍수를 일으키려고 한다. 이 숲에는 고슴도치가 한 마리 살고 있다. 고슴도치는 제 www.acmicpc.net 난이도: 골드 5 사용언어: JAVA 풀이 기본적으로는 BFS를 이용해 문제를 해결할 수 있습니다. 단지 고슴도치와 물의 위치를 모두 탐색해 주어야 하므로, 큐와 BFS 함수를 따로따로 만들어주었습니다. BFS에 관한 설명은 아래 문제의 풀이에서 확인하실 수 있습니다. jooona.tistory.com/63 [BOJ] 2178 - 미로 탐색 -개인적인 풀이일 뿐..

-개인적인 풀이일 뿐, 최적의 정답이 아님을 알려드립니다. 문제 www.acmicpc.net/problem/16172 16172번: 나는 친구가 적다 (Large) 첫 번째 줄에는 알파벳 소문자, 대문자, 숫자로 이루어진 문자열 S가 주어진다. (1 ≤ |S| ≤ 200,000) 두 번째 줄에는 성민이가 찾고자 하는 알파벳 소문자, 대문자로만 이루어진 키워드 문자열 K가 www.acmicpc.net 난이도: 골드 4 사용언어: JAVA 풀이 문제의 의도는 KMP 알고리즘을 이용하여 문자열 비교를 수행하는 것입니다. KMP 알고리즘에 대해서는 아래의 글을 참고하시면 좋을 것 같습니다. jooona.tistory.com/102 [알고리즘] KMP Algorithm KMP(Knuth-Morris-Pratt) ..

-개인적인 풀이일 뿐, 최적의 정답이 아님을 알려드립니다. 문제 www.acmicpc.net/problem/2096 2096번: 내려가기 첫째 줄에 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 N개의 줄에는 숫자가 세 개씩 주어진다. 숫자는 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 중의 하나가 된다. www.acmicpc.net 난이도: 골드 4 사용언어: JAVA 풀이 이 문제는 [1149번 - RGB거리]와 굉장히 유사한 문제입니다. 기본적인 풀이는 아래의 RGB거리에 대한 풀이에서 확인하실 수 있습니다. jooona.tistory.com/64 [BOJ] 1149 - RGB거리 -개인적인 풀이일 뿐, 최적의 정답이 아님을 알려드립니다. 문제 설명 www.acmicpc.net/prob..

개인적인 풀이일 뿐, 최적의 정답이 아님을 알려드립니다. 문제 www.acmicpc.net/problem/1987 1987번: 알파벳 세로 R칸, 가로 C칸으로 된 표 모양의 보드가 있다. 보드의 각 칸에는 대문자 알파벳이 하나씩 적혀 있고, 좌측 상단 칸 (1행 1열) 에는 말이 놓여 있다. 말은 상하좌우로 인접한 네 칸 중의 한 칸으 www.acmicpc.net 난이도: 골드 4 사용언어: JAVA 풀이 이 문제는 재귀를 이용한 dfs를 이용하여 해결할 수 있습니다. dfs에 관한 기본적인 내용은 아래 문제의 풀이에서 볼 수 있습니다. jooona.tistory.com/65 [BOJ] 1303 - 전쟁 - 전투 -개인적인 풀이일 뿐, 최적의 정답이 아님을 알려드립니다. 문제 설명 www.acmicpc..

개인적인 풀이일 뿐, 최적의 정답이 아님을 알려드립니다. 문제 www.acmicpc.net/problem/13549 13549번: 숨바꼭질 3 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 www.acmicpc.net 난이도: 골드 5 사용언어: JAVA 풀이 비록 이차원이 아닌 일차원 배열에 입력이 들어가지만, 이 문제는 BFS를 사용하여 접근하는 것이 가장 이해하기 쉽습니다. 기존에 이차원 배열에서 상하좌우로 이동하던 것을, 좌우로 한 칸씩, 또는 2배씩 이동시키는 것으로 변형한다고 생각하면 됩니다. BFS에 관한 설명은 아래..

개인적인 풀이일 뿐, 최적의 정답이 아님을 알려드립니다. 문제 www.acmicpc.net/problem/2206 2206번: 벽 부수고 이동하기 N×M의 행렬로 표현되는 맵이 있다. 맵에서 0은 이동할 수 있는 곳을 나타내고, 1은 이동할 수 없는 벽이 있는 곳을 나타낸다. 당신은 (1, 1)에서 (N, M)의 위치까지 이동하려 하는데, 이때 최단 경로 www.acmicpc.net 난이도: 골드 4 사용언어: JAVA 풀이 기본적으로는 BFS를 이용하여 해결하는 문제이며, 거기에 한 번 벽을 뚫을 수 있는 옵션을 추가한 형태입니다. BFS에 관한 설명은 아래 문제의 풀이에서 확인하실 수 있습니다. jooona.tistory.com/63 [BOJ] 2178 - 미로 탐색 -개인적인 풀이일 뿐, 최적의 정..