쿠쿠의 개발일지

문제 https://www.acmicpc.net/problem/2343 2343번: 기타 레슨 강토는 자신의 기타 강의 동영상을 블루레이로 만들어 판매하려고 한다. 블루레이에는 총 N개의 강의가 들어가는데, 블루레이를 녹화할 때, 강의의 순서가 바뀌면 안 된다. 순서가 뒤바뀌는 경 www.acmicpc.net 문제풀이 *접근방법 문제의 제한 조건이 강의의 수는 100,000 과 각 강의의 길이는 10,000분이 넘지 않는다고 주어졌다. 여기서 가능한 블루레이의 크기 중 최소를 구하는 프로그램을 만들어야 하는데 최대치를 두고 생각을 했을 때는 너무 터무니 없이 큰 제한이라 블루레이의 크기를 기준으로 이분탐색을 하면 찾을 수 있겠다 라고 생각이 들었다. 그런데 보통 이분탐색은 정렬된 곳에서 찾는게 보통인데 ..

문제 https://www.acmicpc.net/problem/2615 2615번: 오목 오목은 바둑판에 검은 바둑알과 흰 바둑알을 교대로 놓아서 겨루는 게임이다. 바둑판에는 19개의 가로줄과 19개의 세로줄이 그려져 있는데 가로줄은 위에서부터 아래로 1번, 2번, ... ,19번의 번호 www.acmicpc.net 문제풀이 문제의 제한조건이 생각보다 까따로웠다. 연속적 5알이 되는 색이 이기는 구조인데, 검은색과 흰색이 동시에 이기는 경우도 없고, 두 곳 이상에서 이기는 경우도 없다. 제일 중요한 제한조건인 여섯알이 연속적으로 놓은 경우 이긴 것이 아니다. 라는 말이 있습니다. 여섯알이 될 경우 승부가 결정이 안나 0을 출력해야한다는 것으로 착각했지만 다른 곳에 오목이 되면 그 색이 이기는 문제였습니다..

[문제] https://www.acmicpc.net/problem/2304 2304번: 창고 다각형 첫 줄에는 기둥의 개수를 나타내는 정수 N이 주어진다. N은 1 이상 1,000 이하이다. 그 다음 N 개의 줄에는 각 줄에 각 기둥의 왼쪽 면의 위치를 나타내는 정수 L과 높이를 나타내는 정수 H가 한 개의 www.acmicpc.net [문제풀이 전] 기둥들의 위치와 높이가 주어질 때, 가장 작은 창고 다각형의 면적을 구하면 되는 문제입니다. 힌트에서는 문제 분류가 브루트포스로 되어있지만 x축 (기둥의 왼쪽 면의 위치) 기준으로 정렬을 하여 구하여 항상 작은 면적이 나오게 구현을 했기 때문에 그리디 방법이 아닌가 생각이 들기도 합니다. 브루트포스는 가능한 모든 경우의 수를 탐색하는데 그런 경우를 따져 풀..

[문제] https://www.acmicpc.net/problem/2688 2688번: 줄어들지 않아 첫째 줄에 테스트 케이스의 개수 T(1 이전 자리수의 9 ~ 9 까지의 개수의 합 dp[i][j] = dp[i-1][j] + dp[i-1][j+1] ... + dp[i-1][8] + dp[i-1][9] 라는 식을 구할 수 있습니다. [ i = 자리수(1 ~ 64) , j = 숫자( 0 ~ 9)] 한자리수는 모두 1로 구성되어있어 미리 초기화를 시켜주며, 이 문제는 참고로 테스트 케이스가 있는데 매번 테스트 케이스마다 이 값들을 구할 필요없이 미리 dp테이블을 완성시켜, 테스트케이스안에서는 단순 원하는 자리수의 값만 구하여 출력하게 만들면 된다. 그리고 더하는 값이 너무 커져 오버플로우가 일어날 수 있으니..

ㄷhttps://www.acmicpc.net/problem/14938 14938번: 서강그라운드 예은이는 요즘 가장 인기가 있는 게임 서강그라운드를 즐기고 있다. 서강그라운드는 여러 지역중 하나의 지역에 낙하산을 타고 낙하하여, 그 지역에 떨어져 있는 아이템들을 이용해 서바이벌을 www.acmicpc.net [문제풀이 전] 다익스트라 알고리즘을 알아야 이 문제를 해결할 수 있습니다. 해당 알고리즘 개념을 모르면 쉬운 개념의 문제부터 익히고 오거나, 검색하셔서 해당 개념을 익히면 금방 풀 수 있는 정도의 난이도입니다. [문제풀이] 다익스트라를 활용한 문제로 수색할 수 있는 거리가 한정되어 있어, 한 정점에서 다른 정점으로 이동하는 최소거리를 전부 구하여 dist배열에 담아주고, 움직일 수 있는 범위이면 해..

[문제] https://www.acmicpc.net/problem/1946 1946번: 신입 사원 첫째 줄에는 테스트 케이스의 개수 T(1 ≤ T ≤ 20)가 주어진다. 각 테스트 케이스의 첫째 줄에 지원자의 숫자 N(1 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 N개 줄에는 각각의 지원자의 서류심사 성 www.acmicpc.net [문제풀이 전] 예전에 풀어봤던 문제를 다시 풀어봤는데 그때에 비해 시간을 덜 쓰게 됐는데 차이를 보니 Arrays.sort 와 Collections.sort 의 정렬의 속도 차이가 있다는 사실을 알았다. Arrays.sort() 는 Dual-Pivot Quict sort 를 활용하는데 시간복잡도가 O(nlongn) ~ O(n^2) 의 속도를 낸다. Collectio..

[문제] https://www.acmicpc.net/problem/2667 2667번: 단지번호붙이기 과 같이 정사각형 모양의 지도가 있다. 1은 집이 있는 곳을, 0은 집이 없는 곳을 나타낸다. 철수는 이 지도를 가지고 연결된 집의 모임인 단지를 정의하고, 단지에 번호를 붙이려 한다. 여 www.acmicpc.net [문제풀이 전] 처음 문제 풀때 생각없이 방문처리를 boolean 으로 하려해서 낭패를 보았다. 문제에 그림2를 보면 힌트가 주어졌다. 새로운 BFS가 시작되면 단지번호를 증가하여 결국 그림2 처럼 만들어 해당 개수만 세어주면 되는데 문제를 천천히 꼼꼼히 읽어야 겠다.. [문제풀이] BFS를 활용한 문제로 상하좌위 연결된 집의 모임을 단지라고 지정을 하여 번호를 붙여 단지수를 출력하고, 각..

출처 - https://www.acmicpc.net/problem/10825 10825번: 국영수 첫째 줄에 도현이네 반의 학생의 수 N (1 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 한 줄에 하나씩 각 학생의 이름, 국어, 영어, 수학 점수가 공백으로 구분해 주어진다. 점수는 1보다 크거나 같고, 1 www.acmicpc.net [문제] [문제풀이 전] 이코테 정렬파트에 나온 문제입니다. 문제를 봤을 때 학생 클래스 만들어서 요구한대로 정렬을 해주니 간단히 풀린 문제여서 크게 어렵지는 않았습니다. Comparator에 익숙치 않았다면 힘들었을지도..? [문제풀이] 문제의 요구번호대로 따라가서 정렬기준을 오버라이드 해주면 쉽게 풀리는 문제입니다. 만약 Comparator 를 모르신다면 http..

출처 - https://www.acmicpc.net/problem/18428 18428번: 감시 피하기 NxN 크기의 복도가 있다. 복도는 1x1 크기의 칸으로 나누어지며, 특정한 위치에는 선생님, 학생, 혹은 장애물이 위치할 수 있다. 현재 몇 명의 학생들은 수업시간에 몰래 복도로 빠져나왔는데, 복 www.acmicpc.net [문제풀이 전] 이코테 DFS&BFS 20번 문제이기도 합니다. 연구소 문제를 먼저 풀어봐서인지 쉽게 해결했습니다. 똑같이 3개의 장애물을 모든 경우에 세우고 감시의 여부를 구해야하는데 여기서 신경써야 할 점인게 선생님끼리 감시가 겹쳤을 때 처리만 잘 해준다면 될 것 같습니다. [문제풀이] N제한이 작아 모든 배열에 기둥을 3개씩 설치하는 경우는 36 C 3 으로 10,000 이..

[문제] https://www.acmicpc.net/problem/18405 18405번: 경쟁적 전염 첫째 줄에 자연수 N, K가 공백을 기준으로 구분되어 주어진다. (1 ≤ N ≤ 200, 1 ≤ K ≤ 1,000) 둘째 줄부터 N개의 줄에 걸쳐서 시험관의 정보가 주어진다. 각 행은 N개의 원소로 구성되며, 해당 위치 www.acmicpc.net [문제풀이 전] 이코테 책뒤에 DFS&BFS 17번 문제로 나온 문제이기도 하다. 백준에서 정답률 28%로 낮은 정답률을 보유하고 있는데 요즘 스터디의 효과를 보는지 한번에 통과해서 기분이 좋았다. 아마 이 문제에서 접근하기 어려운점이 모든 바이러스는 1초마다 상, 하, 좌. 우 방향으로 증식하는데 바이러스는 매 초마다 낮은 종류의 바이러스가 증식하고 그 시..