CSE 전공노트

-개인적인 풀이일 뿐, 최적의 정답이 아님을 알려드립니다. 문제 www.acmicpc.net/problem/1463 1463번: 1로 만들기 첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 정수 N이 주어진다. www.acmicpc.net 난이도: 실버 3 사용언어: JAVA 풀이 문제의 시간제한을 봐도 알 수 있듯이, 이 문제는 다이나믹 프로그래밍을 이용해서 해결해야 합니다. 문제는 1을 만드는 것이지만, 구현은 반대로 1에서 N을 만드는 최소 연산 수를 구하는 식으로 했습니다. 배열을 하나 만들어, 반복문을 돌며 배열의 i 번째 칸에 i까지 오는데 걸리는 연산의 최소 횟수를 저장해주고, 마지막에 배열의 N번째 칸에 들어있는 값을 출력해주면 됩니다. i 번째 칸까지 오는데 필요한 연산의 최소 횟..

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