CSE 전공노트

개인적인 풀이일 뿐, 최적의 정답이 아님을 알려드립니다. 문제 www.acmicpc.net/problem/2170 2170번: 선 긋기 첫째 줄에 선을 그은 횟수 N(1 ≤ N ≤ 1,000,000)이 주어진다. 다음 N개의 줄에는 선을 그을 때 선택한 두 점의 위치 x, y(-1,000,000,000 ≤ x < y ≤ 1,000,000,000)가 주어진다. www.acmicpc.net 난이도: 골드 5 사용언어: JAVA 풀이 시작점과 도착점에 대한 입력을 받아 시작점의 위치를 기준으로 오름차순 정렬만 할 수 있다면, 이미 문제를 푼 것이나 다름이 없습니다. 정렬을 해두었다면 그냥 선을 하나씩 확인하면서 현재 그려지고 있는 선과 분리된 것인지 또는 겹쳐지는 것인지를 판단하고, 그어진 선의 총 길이를 계..

개인적인 풀이일 뿐, 최적의 정답이 아님을 알려드립니다. 문제 www.acmicpc.net/problem/14442 14442번: 벽 부수고 이동하기 2 첫째 줄에 N(1 ≤ N ≤ 1,000), M(1 ≤ M ≤ 1,000), K(1 ≤ K ≤ 10)이 주어진다. 다음 N개의 줄에 M개의 숫자로 맵이 주어진다. (1, 1)과 (N, M)은 항상 0이라고 가정하자. www.acmicpc.net 난이도: 골드 3 사용언어: JAVA 풀이 기본적으로 BFS를 이용하는 문제이며, 벽을 K번 부술 수 있기 때문에 이를 감안해서 코드를 작성해 주어야 합니다. 메모리 초과를 막기 위해 가장 중요한 아이디어는, 만일 누가 이미 한 번 지나간 경로를 발견했을 때, 해당 경로가 자신보다 더 적거나 같은 수의 벽을 파괴하..

개인적인 풀이일 뿐, 최적의 정답이 아님을 알려드립니다. 문제 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/9465 9465번: 스티커 첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스의 첫째 줄에는 n (1 ≤ n ≤ 100,000)이 주어진다. 다음 두 줄에는 n개의 정수가 주어지며, 각 정수는 그 위치에 해당하는 스티커의 www.acmicpc.net 난이도: 실버 2 사용언어: JAVA 풀이 전형적으로 다이나믹 프로그래밍을 이용하여 해결하는 문제이고, 구현도 어렵지 않습니다. 왼쪽부터 다이나믹 프로그래밍을 위한 dp라는 배열을 채워나갈 텐데, 다음과 같은 규칙을 갖습니다. 바로 A칸에 들어갈 dp의 값은 1번 칸까지의 dp 값과, 2번 칸까지의 dp 값과, 3번 칸까지의 dp 값 중 ..

개인적인 풀이일 뿐, 최적의 정답이 아님을 알려드립니다. 문제 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/12852 12852번: 1로 만들기 2 첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 자연수 N이 주어진다. www.acmicpc.net 난이도: 실버 1 사용언어: JAVA 풀이 기본적인 문제의 풀이는 아래의 문제와 같습니다. jooona.tistory.com/104 [BOJ] 1463 - 1로 만들기 -개인적인 풀이일 뿐, 최적의 정답이 아님을 알려드립니다. 문제 www.acmicpc.net/problem/1463 1463번: 1로 만들기 첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 정수 N이 주어진다. www.acmicpc.net 난이.. jooona.tistory.com..

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

-개인적인 풀이일 뿐, 최적의 정답이 아님을 알려드립니다. 문제 www.acmicpc.net/problem/16953 16953번: A → B 첫째 줄에 A, B (1 ≤ A < B ≤ 109)가 주어진다. www.acmicpc.net 난이도: 실버 1 사용언어: JAVA 풀이 굉장히 전형적인 다이나믹 프로그래밍 문제처럼 보이지만, 다이나믹 프로그래밍으로 해당 문제를 구현 시 메모리 초과가 나는 것을 확인할 수 있었습니다. 이 문제는 다이나믹 프로그래밍이 아닌 그리디 알고리즘으로 접근을 해야 합니다. B에서부터 뒤에 1을 뗄 수 있으면 떼주고, 2로 나눌 수 있으면, 2로 나누어주면서 A까지 이동하는 것입니다. 물론 1을 떼는 것에 우선순위를 둡니다. 그리고 중간에 1을 뗄 수도, 2로 나눌 수도 없는 ..