꾸준함

문제 링크입니다: https://www.acmicpc.net/problem/6087 6087번: 레이저 통신 문제 크기가 1×1인 정사각형으로 나누어진 W×H 크기의 지도가 있다. 지도의 각 칸은 빈 칸이거나 벽이며, 두 칸은 'C'로 표시되어 있는 칸이다. 'C'로 표시되어 있는 두 칸을 레이저로 통신하기 위해서 설치해야 하는 거울 개수의 최솟값을 구하는 프로그램을 작성하시오. 레이저로 통신한다는 것은 두 칸을 레이저로 연결할 수 있음을 의미한다. 레이저는 C에서만 발사할 수 있고, 빈 칸에 거울('/', '\')을 설치해서 방향을 90도 회전시킬 수 있다. www.acmicpc.net 저는 처음에 거울을 하나하나 설치하는 방법으로 접근했고 이는 당연히 TLE가 발생했습니다. 이후에 문제에 대해 곰곰히..

문제 링크입니다: https://www.acmicpc.net/problem/1981 1981번: 배열에서 이동 문제 n×n짜리의 배열이 하나 있다. 이 배열의 (1, 1)에서 (n, n)까지 이동하려고 한다. 이동할 때는 상, 하, 좌, 우의 네 인접한 칸으로만 이동할 수 있다. 이와 같이 이동하다 보면, 배열에서 몇 개의 수를 거쳐서 이동하게 된다. 이동하기 위해 거쳐 간 수들 중 최댓값과 최솟값의 차이가 가장 작아지는 경우를 구하는 프로그램을 작성하시오. 입력 첫째 줄에 n(2≤n≤100)이 주어진다. 다음 n개의 줄에는 배열이 주어진다. 배열의 각 수는 0보 www.acmicpc.net 백준 2842번 집배원 한상덕(https://jaimemin.tistory.com/1279)과 유사하지만 조금 더..

문제 링크입니다: https://www.acmicpc.net/problem/2957 2957번: 이진 탐색 트리 문제 이진 탐색 트리는 모든 노드가 많아야 2개의 자식 노드를 가지고 있는 트리이고, 각 노드에는 수가 하나씩 쓰여있다. 만약 어떤 노드에 쓰여 있는 수가 X라면, 그 노드의 왼쪽 서브트리에는 X보다 작은 수, 오른쪽 서브트리에는 X보다 큰 수만 저장되어 있어야 한다. 1보다 크거나 같고, N보다 작거나 같은 수 N개가 한 번씩 등장하는 수열이 입력으로 주어진다. 이 수열을 이용해서 이진 탐색 트리를 만들려고 한다. 이제 배열의 첫 번째 수를 루트 노드로 www.acmicpc.net N은 최대 300,000이고 이진 탐색 트리를 구성할 때 최악의 경우 skewed binary tree가 되기 ..

문제 링크입니다: https://www.acmicpc.net/problem/2933 2933번: 미네랄 문제 창영과 상근은 한 동굴을 놓고 소유권을 주장하고 있다. 두 사람은 막대기를 서로에게 던지는 방법을 이용해 누구의 소유인지를 결정하기로 했다. 싸움은 동굴에서 벌어진다. 동굴에는 미네랄이 저장되어 있으며, 던진 막대기가 미네랄을 파괴할 수도 있다. 동굴은 R행 C열로 나타낼 수 있으며, R×C칸으로 이루어져 있다. 각 칸은 비어있거나 미네랄을 포함하고 있으며, 네 방향 중 하나로 인접한 미네랄이 포함된 두 칸은 같은 클러스터이다. 창영은 동굴의 왼쪽에 www.acmicpc.net 해당 문제는 새로 생긴 클러스터가 바닥에 닿을 때까지 클러스터들을 한칸씩 내리는 것이 핵심인 문제였습니다. 새로 생긴 클..

문제 링크입니다: https://www.acmicpc.net/problem/2186 2186번: 문자판 첫째 줄에 N(1 ≤ N ≤ 100), M(1 ≤ M ≤ 100), K(1 ≤ K ≤ 5)가 주어진다. 다음 N개의 줄에는 M개의 알파벳 대문자가 주어지는데, 이는 N×M 크기의 문자판을 나타낸다. 다음 줄에는 1자 이상 80자 이하의 영단어가 주어진다. 모든 문자들은 알파벳 대문자이며, 공백 없이 주어진다. www.acmicpc.net DFS + DP 문제였습니다. 처음에는 DFS 알고리즘만 적용했는데 시간초과가 발생했습니다. (최대 100 * 100 보드판에 최대 80 길이의 문자열을 찾아야하고 visited 배열을 사용할 수 없기 때문에 당연히 TLE가 발생합니다.) 따라서, 각 칸과 목표 문자열..

문제 링크입니다: https://www.acmicpc.net/problem/5635 5635번: 생일 문제 어떤 반에 있는 학생들의 생일이 주어졌을 때, 가장 나이가 어린 사람과 가장 많은 사람을 구하는 프로그램을 작성하시오. 입력 첫째 줄에 반에 있는 학생의 수 n이 주어진다. (1 ≤ n ≤ 100) 다음 n개 줄에는 각 학생의 이름과 생일이 "이름 dd mm yyyy"와 같은 형식으로 주어진다. 이름은 그 학생의 이름이며, 최대 15글자로 이루어져 있다. dd mm yyyy는 생일 일, 월, 연도이다. 이름이 같거나, 생일이 같은 사람은 없다. 출력 www.acmicpc.net 간단한 정렬 문제였습니다. pair의 속성을 잘 생각해보면 되는 문제였습니다. 개발환경:Visual Studio 2017 ..

문제 링크입니다: https://www.acmicpc.net/problem/6118 6118번: 숨바꼭질 문제 재서기는 수혀니와 교외 농장에서 숨바꼭질을 하고 있다. 농장에는 헛간이 많이 널려있고 재석이는 그 중에 하나에 숨어야 한다. 헛간의 개수는 N(2

문제 링크입니다: https://www.acmicpc.net/problem/1516 1516번: 게임 개발 첫째 줄에 건물의 종류 수 N(1 ≤ N ≤ 500)이 주어진다. 다음 N개의 줄에는 각 건물을 짓는데 걸리는 시간과 그 건물을 짓기 위해 먼저 지어져야 하는 건물들의 번호가 주어진다. 건물의 번호는 1부터 N까지로 하고, 각 줄은 -1로 끝난다고 하자. 각 건물을 짓는데 걸리는 시간은 100,000보다 작거나 같은 자연수이다. www.acmicpc.net 간단한 위상정렬 문제였습니다. 핵심은 max(result[nextNode], result[node] + duration[node]); 이 부분이였습니다. 개발환경:Visual Studio 2017 지적, 조언, 질문 환영입니다! 댓글 남겨주세요~

문제 링크입니다: https://www.acmicpc.net/problem/1766 1766번: 문제집 첫째 줄에 문제의 수 N(1 ≤ N ≤ 32,000)과 먼저 푸는 것이 좋은 문제에 대한 정보의 개수 M(1 ≤ M ≤ 100,000)이 주어진다. 둘째 줄부터 M개의 줄에 걸쳐 두 정수의 순서쌍 A,B가 빈칸을 사이에 두고 주어진다. 이는 A번 문제는 B번 문제보다 먼저 푸는 것이 좋다는 의미이다. 항상 문제를 모두 풀 수 있는 경우만 입력으로 주어진다. www.acmicpc.net 간단한 위상정렬 문제였습니다. 문제 번호 오름차순으로 쉬운 문제이므로 우선순위 큐를 통해 minHeap을 구성하는 것이 핵심이였습니다. 개발환경:Visual Studio 2017 지적, 조언, 질문 환영입니다! 댓글 남겨..

문제 링크입니다: https://www.acmicpc.net/problem/16674 16674번: 2018년을 되돌아보며 조그만 수학적 연관성에도 깊은 흥미를 두는 상헌이는 우연히 고려대학교 프로그래밍 경시대회가 열리는 날짜를 년도와 월일을 붙여 쓰면 20181208임을 알게 되었다. 2018년이 한 달도 남지 않음을 깨달은 상헌이는 수학적 감수성에 휩싸여, 이 수가 숫자 2, 0, 1, 8로만 이루어져 있는 사실에 심취하였다. 상헌이는 다사다난했던 2018년을 추억하기 위해 2, 0, 1, 8로만 이루어져 있는 정수를 생각하기 시작하였고, 그 결과 상헌이는 양의 정수를 다 www.acmicpc.net 간단한 문자열 처리 문제였습니다. 개발환경:Visual Studio 2017 지적, 조언, 질문 환영..