CSE 전공노트

개인적인 풀이일 뿐, 최적의 정답이 아님을 알려드립니다. 문제 https://www.acmicpc.net/problem/2412 2412번: 암벽 등반 어떤 암벽에 n(1 ≤ n ≤ 50,000)개의 홈이 파져 있다. 각각의 홈의 좌표는 (x, y)와 같이 표현되는데, |a - x| ≤ 2이고 |b - y| ≤ 2이면 (x, y)에서 (a, b)로 이동할 수 있다. 이와 같이 홈들을 이용하여 이동 www.acmicpc.net 난이도: 골드 3 사용언어: JAVA 풀이 기본적인 BFS를 사용하면 쉽게 해결할 수 있는 문제입니다. 단, 다음의 문장만 유의해서 풀이를 하시면 됩니다. 각각의 홈의 좌표는 (x, y)와 같이 표현되는데, |a - x| ≤ 2이고 |b - y| ≤ 2이면 (x, y)에서 (a, b..

개인적인 풀이일 뿐, 최적의 정답이 아님을 알려드립니다. 문제 https://www.acmicpc.net/problem/16437 16437번: 양 구출 작전 2, 3, 5번에 사는 모든 양들은 1번 섬으로 갈 수 있지만 7번 섬에 사는 양들은 1번 섬으로 가기 위하여 6번 섬을 거쳐야 하는데 6번 섬에 사는 늑대들의 수가 7번 섬에 사는 양들의 수보다 많으므로 www.acmicpc.net 난이도: 골드 3 사용언어: JAVA 풀이 이 문제는 트리 형태의 데이터 구조를 가진다는 점만 잘 이용하면 쉽게 해결할 수 있습니다. 트리의 순회 방법 중 후위 순회를 사용하면 트리의 Leaf Node부터 Root Node까지 차례로 올라오면서 남아있는 늑대의 수와 올라올 수 있는 양의 수를 쉽게 계산할 수 있습니다...

개인적인 풀이일 뿐, 최적의 정답이 아님을 알려드립니다. 문제 https://www.acmicpc.net/problem/5430 5430번: AC 각 테스트 케이스에 대해서, 입력으로 주어진 정수 배열에 함수를 수행한 결과를 출력한다. 만약, 에러가 발생한 경우에는 error를 출력한다. www.acmicpc.net 난이도: 골드 5 사용언어: JAVA 풀이 우선 문제 자체는 덱을 사용하면 쉽게 풀 수 있습니다. 덱은 큐의 발전된 형태로, 양쪽 끝 모두로 입, 출력을 할 수 있는 자료구조입니다. 편의상 덱의 앞쪽 출입구를 머리 부분, 뒤쪽 출입구를 꼬리 부분이라고 하겠습니다. 덱은 다음과 같이 선언하여 사용할 수 있습니다. Deque dq_name = new ArrayDeque(); 덱의 주요 함수는 다..

개인적인 풀이일 뿐, 최적의 정답이 아님을 알려드립니다. 문제 https://www.acmicpc.net/problem/3078 3078번: 좋은 친구 첫째 줄에 N과 K가 주어진다. (3 ≤ N ≤ 300,000, 1 ≤ K ≤ N) 다음 N개 줄에는 상근이네 반 학생의 이름이 성적순으로 주어진다. 이름은 알파벳 대문자로 이루어져 있고, 2글자 ~ 20글자이다. www.acmicpc.net 난이도: 골드 3 사용언어: JAVA 풀이 문제를 해결하는 여러 방법이 있겠지만, 저는 큐를 이용하여 문제를 풀었습니다. 문제 해결 방법은 다음과 같습니다. 1. 한 명씩 입력을 받으며 큐에 삽입한다. 2. 등수의 차이가 K를 벗어나면 큐에서 삭제한다. (큐 내부에는 등수가 K 이내인 친구만 존재한다) 3. 입력을 ..

개인적인 풀이일 뿐, 최적의 정답이 아님을 알려드립니다. 문제 https://www.acmicpc.net/problem/2116 2116번: 주사위 쌓기 첫줄에는 주사위의 개수가 입력된다. 그 다음 줄부터는 한 줄에 하나씩 주사위의 종류가 1번 주사위부터 주사위 번호 순서대로 입력된다. 주사위의 종류는 각 면에 적혀진 숫자가 그림1에 있는 www.acmicpc.net 난이도: 골드 4 사용언어: JAVA 풀이 주사위를 이용한 구현문제이자 모든 경우의 수를 테스트 해보아야하는 브루트포스 문제입니다. 구현 로직은 다음과 같습니다. 1. 가장 아랫쪽 주사위는 마음대로 둘 수 있으므로 6면을 모두 테스트한다. 2. 두 번째 주사위부터는 아랫쪽 주사위의 윗면과 현재 주사위의 아랫면을 같은 수로 맞춰준다. 3. 아..

개인적인 풀이일 뿐, 최적의 정답이 아님을 알려드립니다. 문제 https://www.acmicpc.net/problem/4196 4196번: 도미노 도미노는 재밌다. 도미노 블록을 일렬로 길게 늘어세운 뒤 블록 하나를 넘어뜨리면 그 블록이 넘어지며 다음 블록을 넘어뜨리는 일이 반복되어 일렬로 늘어선 블록들을 연쇄적으로 모두 쓰러 www.acmicpc.net 난이도: 플래티넘 4 사용언어: JAVA 풀이 SCC와 위상 정렬을 함께 고려해야 하는 문제입니다. 언뜻보면 SCC 문제가 아닌것 같지만, 도미노들의 SCC를 구하고 구해진 SCC들간에 위상 정렬을 해서 다른 SCC로 부터 영향을 받지 않는 SCC들을 골라내면 정답을 도출 할 수 있습니다. SCC의 풀이 중 코사라주 알고리즘을 이용했고, 코사라주 알고..

개인적인 풀이일 뿐, 최적의 정답이 아님을 알려드립니다. 문제 https://www.acmicpc.net/problem/2150 2150번: Strongly Connected Component 첫째 줄에 두 정수 V(1 ≤ V ≤ 10,000), E(1 ≤ E ≤ 100,000)가 주어진다. 이는 그래프가 V개의 정점과 E개의 간선으로 이루어져 있다는 의미이다. 다음 E개의 줄에는 간선에 대한 정보를 나타내는 두 정 www.acmicpc.net 난이도: 플래티넘 5 사용언어: JAVA 풀이 이름 그대로 Strongly Connected Component(SCC) 문제의 가장 기본적인 유형입니다. 저는 코사라주 알고리즘을 이용하여 문제를 해결하였습니다. 코사라주 알고리즘은 아래의 링크에서 더 자세하게 확인..

개인적인 풀이일 뿐, 최적의 정답이 아님을 알려드립니다. 문제 https://www.acmicpc.net/problem/10423 10423번: 전기가 부족해 첫째 줄에는 도시의 개수 N(1 ≤ N ≤ 1,000)과 설치 가능한 케이블의 수 M(1 ≤ M ≤ 100,000)개, 발전소의 개수 K(1 ≤ K ≤ N)개가 주어진다. 둘째 줄에는 발전소가 설치된 도시의 번호가 주어진다. 셋째 www.acmicpc.net 난이도: 골드 2 사용언어: JAVA 풀이 크루스칼 알고리즘을 사용하는 최소 스패닝 트리 문제입니다. 전형적인 최소 스패닝 트리 문제에 각각의 발전소와의 연결 여부만 추가적으로 확인해 주면 정답을 받을 수 있습니다. 각 발전소와의 연결 여부는 각 발전소의 부모와 해당 도시의 부모를 비교해보면 ..

개인적인 풀이일 뿐, 최적의 정답이 아님을 알려드립니다. 문제 https://www.acmicpc.net/problem/20058 20058번: 마법사 상어와 파이어스톰 마법사 상어는 파이어볼과 토네이도를 조합해 파이어스톰을 시전할 수 있다. 오늘은 파이어스톰을 크기가 2N × 2N인 격자로 나누어진 얼음판에서 연습하려고 한다. 위치 (r, c)는 격자의 r행 c www.acmicpc.net 난이도: 골드 4 사용언어: JAVA 풀이 구현 문제는 하라는 대로 다 해주면 되죠? 제가 처음 구현할 때 간과했던 부분만 짚고 넘어가겠습니다. 1. 얼음을 삭제할 때 Queue에 담아서 삭제해 줄 것. 그렇지 않으면 이전에 삭제한 얼음이 다음 얼음에 영향을 미칠 수 있다. 2. 얼음을 0 이하의 정수로 감소시키지 ..

개인적인 풀이일 뿐, 최적의 정답이 아님을 알려드립니다. 문제 www.acmicpc.net/problem/16174 16174번: 점프왕 쩰리 (Large) 쩰리는 맨 왼쪽 위의 칸에서 출발해 (행, 열)로 나타낸 좌표계로, (1, 1) -> (2, 1) -> (3, 1) -> (3, 3)으로 이동해 게임에서 승리할 수 있다. www.acmicpc.net 난이도: 골드 5 사용언어: JAVA 풀이 이 문제는 BFS를 사용하여 간단하게 해결할 수 있는 문제입니다. BFS를 사용하여 각각의 칸 마다 해당 숫자 만큼 점프를 해주되, 테이블을 벗어나는 범위만 체크해주면 쉽게 해결 할 수 있습니다. 저는 처음에 이동 방향이 오른쪽과 아래쪽 밖에 없기 때문에 굳이 방문 체크를 하지 않고 풀었었지만, 이렇게 풀면 메..