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/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를 사용하여 각각의 칸 마다 해당 숫자 만큼 점프를 해주되, 테이블을 벗어나는 범위만 체크해주면 쉽게 해결 할 수 있습니다. 저는 처음에 이동 방향이 오른쪽과 아래쪽 밖에 없기 때문에 굳이 방문 체크를 하지 않고 풀었었지만, 이렇게 풀면 메..

개인적인 풀이일 뿐, 최적의 정답이 아님을 알려드립니다. 문제 www.acmicpc.net/problem/1261 1261번: 알고스팟 첫째 줄에 미로의 크기를 나타내는 가로 크기 M, 세로 크기 N (1 ≤ N, M ≤ 100)이 주어진다. 다음 N개의 줄에는 미로의 상태를 나타내는 숫자 0과 1이 주어진다. 0은 빈 방을 의미하고, 1은 벽을 의미 www.acmicpc.net 난이도: 골드 4 사용언어: JAVA 풀이 이 문제는 BFS와 우선순위 큐를 이용해 해결할 수 있습니다. BFS를 이용해 경로를 찾되, 벽을 최소로 부수는 경우를 찾아야 하기 때문에 우선순위 큐를 통해 현 시점에서 가장 적게 벽을 부순 경로부터 체크를 해주면 됩니다. 그리고 이미 검사를 한 구역이더라도, 현재의 경로가 벽을 더 ..

개인적인 풀이일 뿐, 최적의 정답이 아님을 알려드립니다. 문제 www.acmicpc.net/problem/1584 1584번: 게임 첫째 줄에 위험한 구역의 수 N이 주어진다. 다음 줄부터 N개의 줄에는 X1 Y1 X2 Y2와 같은 형식으로 위험한 구역의 정보가 주어진다. (X1, Y1)은 위험한 구역의 한 모서리이고, (X2, Y2)는 위험한 구역의 www.acmicpc.net 난이도: 골드 5 사용언어: JAVA 풀이 기본적으로 bfs를 이용하여 문제를 해결할 수 있습니다. 하지만 최대한 위험한 지역을 통과하지 않고 목적지에 도착하는 것이 목적이기 때문에 한 번 검사한 지역도 생명의 개수에 따라 중복해서 검사해야 하는 문제가 생깁니다. 다시 말해 이미 검사한 칸이라도 현재 도착한 경로가 원래 지나간 ..