CSE 전공노트

-개인적인 풀이일 뿐, 최적의 정답이 아님을 알려드립니다. 문제 www.acmicpc.net/problem/3986 3986번: 좋은 단어 이번 계절학기에 심리학 개론을 수강 중인 평석이는 오늘 자정까지 보고서를 제출해야 한다. 보고서 작성이 너무 지루했던 평석이는 노트북에 엎드려서 꾸벅꾸벅 졸다가 제출 마감 1시간 전에 www.acmicpc.net 난이도: 실버 4 사용언어: JAVA 풀이 이 문제는 스택을 이용하는 전형적인 문제입니다. 다른 고려사항도 없어 쉽게 해결할 수 있습니다. 문자열에서 문자를 받아서 1. 스택이 비었으면 스택에 push 한다. 2. 스택이 비어있지 않다면, 스택의 top에 있는 문자를 확인한다. 3. 만약 top에 있는 문자와 자신이 같다면, 해당 문자를 스택에서 pop 해준..

-개인적인 풀이일 뿐, 최적의 정답이 아님을 알려드립니다. 문제 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/11399 11399번: ATM 첫째 줄에 사람의 수 N(1 ≤ N ≤ 1,000)이 주어진다. 둘째 줄에는 각 사람이 돈을 인출하는데 걸리는 시간 Pi가 주어진다. (1 ≤ Pi ≤ 1,000) www.acmicpc.net 난이도: 실버 3 사용언어: JAVA 풀이 필요한 시간의 합을 최소화하기 위해서는 당연히 짧게 걸리는 순서대로 연산을 수행하면 됩니다. 즉 입력을 한 배열에 담고 해당 배열을 오름차순으로 소팅하여 총시간을 계산해주면 됩니다. 예를 들어, 1 2 3 4 ... 순서로 줄을 서 있다면, 1이 인출을 하기 위해 기다려야 하는 시간은 1초 2가 인출을 하기 위해 기다려야 하는 시간은 1..

개인적인 풀이일 뿐, 최적의 정답이 아님을 알려드립니다. 문제 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 - 미로 탐색 -개인적인 풀이일 뿐, 최적의 정..

개인적인 풀이일 뿐, 최적의 정답이 아님을 알려드립니다. 문제 www.acmicpc.net/problem/2352 2352번: 반도체 설계 첫째 줄에 정수 n(1 ≤ n ≤ 40,000)이 주어진다. 다음 줄에는 차례로 1번 포트와 연결되어야 하는 포트 번호, 2번 포트와 연결되어야 하는 포트 번호, …, n번 포트와 연결되어야 하는 포트 번호가 주 www.acmicpc.net 난이도: 골드 3 사용언어: JAVA 풀이 겹쳐지지 않는 최대의 경우의 수를 묻는 문제이기 때문에, i 번째까지의 포트들을 겹쳐지지 않게 연결하는 최대 개수는 i보다 낮은 번호의 포트들을 겹쳐지지 않게 연결하는 최대 개수에 자기 자신을 포함하여 +1을 해주는 것입니다. 하지만 아무리 최대 개수라도 자신과 겹쳐지는 경우는 배제를 해..

개인적인 풀이일 뿐, 최적의 정답이 아님을 알려드립니다. 문제 www.acmicpc.net/problem/5427 5427번: 불 상근이는 빈 공간과 벽으로 이루어진 건물에 갇혀있다. 건물의 일부에는 불이 났고, 상근이는 출구를 향해 뛰고 있다. 매 초마다, 불은 동서남북 방향으로 인접한 빈 공간으로 퍼져나간다. 벽에 www.acmicpc.net 난이도: 골드 4 사용언어: JAVA 풀이 기본적으로는 BFS를 이용해 문제를 해결할 수 있습니다. 단지 불과 상근이의 위치를 모두 탐색해 주어야 하므로, 큐와 BFS 함수를 따로따로 만들어주었습니다. BFS에 관한 설명은 아래 문제의 풀이에서 확인하실 수 있습니다. jooona.tistory.com/63 [BOJ] 2178 - 미로 탐색 -개인적인 풀이일 뿐,..

개인적인 풀이일 뿐, 최적의 정답이 아님을 알려드립니다. 문제 www.acmicpc.net/problem/1806 1806번: 부분합 첫째 줄에 N (10 ≤ N < 100,000)과 S (0 < S ≤ 100,000,000)가 주어진다. 둘째 줄에는 수열이 주어진다. 수열의 각 원소는 공백으로 구분되어져 있으며, 10,000이하의 자연수이다. www.acmicpc.net 난이도: 골드 4 사용언어: JAVA 풀이 이 문제는 두 개의 포인터를 이용하여 해결할 수 있습니다. 수열에서 연속된 수들의 부분합 중에 그 합이 S를 넘는 것 중, 가장 짧은 것을 찾는 것이 문제이기 때문에, 연속된 수들의 첫 부분과 마지막 부분을 포인터로 가리키고, 이 두 포인터를 적절히 증가시키며 최소 길이를 구할 수 있습니다. ..

개인적인 풀이일 뿐, 최적의 정답이 아님을 알려드립니다. 문제 www.acmicpc.net/problem/2056 2056번: 작업 수행해야 할 작업 N개 (3 ≤ N ≤ 10000)가 있다. 각각의 작업마다 걸리는 시간(1 ≤ 시간 ≤ 100)이 정수로 주어진다. 몇몇 작업들 사이에는 선행 관계라는 게 있어서, 어떤 작업을 수행하기 위해 www.acmicpc.net 난이도: 골드 4 사용언어: JAVA 풀이 이 문제는 다이나믹 프로그래밍을 이용하면 비교적 어렵지 않게 해결할 수 있습니다. 한 작업이 시작되기 전에 완수되어야 할 여러 작업들을 입력으로 받아서, 해당 작업들이 완료되는데 걸리는 시간들을 확인하여 가장 늦게 끝나는 작업의 시간에 자신의 작업 시간을 더해서 dp 배열에 추가해주면 됩니다. t라..