룰루랄라 알고리즘

여태 실버문제는 풀지 않았지만 코테문제는 실버에서 골드 수준으로 나온다는 걸 알게 되고 앞으로는 적극 실버를 풀 생각이다. 마침 대학교 알고리즘 시간에 분할정복, DP의 차이점과 상황에 따른 우수성을 배운지 얼마 지나지 않았어서 해당 문제를 보고 바로 DP로 풀어야 한다는 생각이 났다. 감사합니다 프로페서 조. https://www.acmicpc.net/problem/9184 9184번: 신나는 함수 실행 입력은 세 정수 a, b, c로 이루어져 있으며, 한 줄에 하나씩 주어진다. 입력의 마지막은 -1 -1 -1로 나타내며, 세 정수가 모두 -1인 경우는 입력의 마지막을 제외하면 없다. www.acmicpc.net 해당 문제는 이미 재귀 분할정복으로 구현되어 있는 식을 DP로 바꾸는게 풀이였다. 해당 식..

https://www.acmicpc.net/problem/20125 20125번: 쿠키의 신체 측정 쿠키런은 데브시스터즈에서 제작한 모바일 러닝 액션 게임이다. 마녀의 오븐에서 탈출한 쿠키들과 함께 모험을 떠나는 게임으로, 점프와 슬라이드 2가지 버튼만으로 손쉽게 플레이할 수 있는 www.acmicpc.net 이 전까지 문자열을 입력으로 받아올 때 항상 String 배열을 사용했다. 문자열 2차원 배열을 받아온다 하면 묻지도 따지지도 않고 String [][]을 사용했는데 이 비용이 크다는 걸 깨달았다. char [][]를 사용해서 한 줄로 들어온 String을 저장할 수 있었던 것이다! public class Main { public static void main(String[] args) throws..

https://www.acmicpc.net/problem/19941 19941번: 햄버거 분배 기다란 벤치 모양의 식탁에 사람들과 햄버거가 아래와 같이 단위 간격으로 놓여 있다. 사람들은 자신의 위치에서 거리가 $K$ 이하인 햄버거를 먹을 수 있다. 햄버거 사람 햄버거 사람 햄버거 사 www.acmicpc.net 햄버거 하니까 군 시절에 동기가 행보관님을 햄버거한입으로 저장해 놓은 거 걸려서 엄청 털렸던 기억이 나네요. 전형적인 그리디 문제. 가능한 왼쪽부터 먹는 방법으로 O(N*K)로 풀 수 있다. String 배열 array에 입력을 저장하고 반복문을 돌려 해당 위치에 사람이 있다면 그다음 반복문을 실행한다. 2차 반복문의 범위는 해당 위치에서 +-K 로 제한. OutOfIndex 오류가 날 수 있기..

https://www.acmicpc.net/problem/15989 15989번: 1, 2, 3 더하기 4 정수 4를 1, 2, 3의 합으로 나타내는 방법은 총 4가지가 있다. 합을 나타낼 때는 수를 1개 이상 사용해야 한다. 합을 이루고 있는 수의 순서만 다른 것은 같은 것으로 친다. 1+1+1+1 2+1+1 (1+1+2, 1+2+1) 2+2 www.acmicpc.net 다이나믹 프로그래밍으로 점화식을 구해서 풀어야 하는 문제. 1차원 적으로 생각했다가 도저히 답이 안 나왔는데 dp 테이블을 2차원 배열로 나누어 풀어야지 풀 수 있었다. dp[i][0] : i를 만들 때 1이 가장 앞에 오는 경우 ex) i=4 1+1+1+1 dp[i][1] : i를 만들 때 2가 가장 앞에 오는 경우 ex) 2+1, ..

https://www.acmicpc.net/problem/2304 2304번: 창고 다각형 첫 줄에는 기둥의 개수를 나타내는 정수 N이 주어진다. N은 1 이상 1,000 이하이다. 그 다음 N 개의 줄에는 각 줄에 각 기둥의 왼쪽 면의 위치를 나타내는 정수 L과 높이를 나타내는 정수 H가 한 개의 www.acmicpc.net 받아온 x, y 좌표를 클래스 Point로 ArrayList에 저장 후 x좌표를 기준으로 오름차순 정렬한 후에 가장 큰 y 좌표 max_y를 기준으로 왼쪽의 넓이 + 오른쪽의 넓이 + max_y로 풀었다. 처음에 반례 가장 큰 y좌표가 여러 개인 경우를 생각 못해서 7번이나 틀렸음. -> 만약 좌표가 (1,3) (2,3) (3,2) (4,3) 이런 식으로 온다면 틀린 답을 도출했다..

https://www.acmicpc.net/problem/1138 1138번: 한 줄로 서기 첫째 줄에 사람의 수 N이 주어진다. N은 10보다 작거나 같은 자연수이다. 둘째 줄에는 키가 1인 사람부터 차례대로 자기보다 키가 큰 사람이 왼쪽에 몇 명이 있었는지 주어진다. i번째 수는 0보다 www.acmicpc.net N이 10 이하로 매우 작기 때문에 아이디어로만 풀 수 있는 문제 자신의 왼쪽에 자기보다 큰 수를 저장해 놓은 배열 left_tall 순서를 저장하고 -1로 초기화해 놓은 배열 order 생성 left_tall의 순서가 오름차순으로 이미 정렬되어 있기 때문에 앞에서부터 차례대로 채워 넣기만 하면 된다. public class Main { public static int N, count; p..

https://www.acmicpc.net/problem/17485 17485번: 진우의 달 여행 (Large) 첫줄에 지구와 달 사이 공간을 나타내는 행렬의 크기를 나타내는 N, M (2 ≤ N, M ≤ 1000)이 주어진다. 다음 N줄 동안 각 행렬의 원소 값이 주어진다. 각 행렬의 원소값은 100 이하의 자연수이다. www.acmicpc.net 3차원 배열을 통해 dp 테이블을 구성하고 (N+1) X M X 3으로 출발지를 의미하는 행을 한층 더 쌓았다. 좌표 dfs 처럼 dx, dy의 범위를 제한하면서 dp 테이블을 업데이트. 아래 알고리즘의 기본 점화식 dp[nx][ny][중앙] = min( dp[x][y][왼쪽 위], dp[x][y][오른쪽 위] ) + graph[nx][ny] public c..

https://www.acmicpc.net/problem/3758 3758번: KCPC 입력 데이터는 표준 입력을 사용한다. 입력은 T개의 테스트 데이터로 구성된다. 입력의 첫 번째 줄에는 테스트 데이터의 수를 나타내는 정수 T가 주어진다. 각 테스트 데이터의 첫 번째 줄에는 www.acmicpc.net 스터디 카페 가서 민폐로 푼 문제. 키스킨 끼면 소리 안 들릴 줄 알았는데 생각보다 너무 조용해서 내 타자속도로 치면 다들리더라. 스터디 카페는 전공 이론 공부나 문제 고민할 때만 가야 할 듯. 우선순위가 있는 정렬 문제. 우선순위가 있어서 예전에 학부 자료구조 과제였던 스케줄링 알고리즘에서 사용한 min heap 구조를 사용해야 하나 생각했었는데 풀다 보니 더 복잡해져서 중간에 풀이를 바꿨다. 문제에서..

https://www.acmicpc.net/problem/2164 2164번: 카드2 N장의 카드가 있다. 각각의 카드는 차례로 1부터 N까지의 번호가 붙어 있으며, 1번 카드가 제일 위에, N번 카드가 제일 아래인 상태로 순서대로 카드가 놓여 있다. 이제 다음과 같은 동작을 카드가 www.acmicpc.net 아주 기본적인 선입선출 queue 문제. 학부 자료구조 수업을 열심히 들어 놓길 잘했다. 자바로 구현하는 queue 사용법을 익혀두자. 삽입 add(e) : 삽입 성공 시 true 반환, 하지만 사용 가능한 공간이 없어 삽입 실패 시 IllegalStateException 발생 offer(e) : 삽입 성공 시 true 반환, 하지만 사용 가능한 공간이 없어 삽입 실패 시 false 반환 제거 r..

https://www.acmicpc.net/problem/11501 11501번: 주식 입력의 첫 줄에는 테스트케이스 수를 나타내는 자연수 T가 주어진다. 각 테스트케이스 별로 첫 줄에는 날의 수를 나타내는 자연수 N(2 ≤ N ≤ 1,000,000)이 주어지고, 둘째 줄에는 날 별 주가를 나타 www.acmicpc.net 시간 초과에 걸리지 않도록 탐색하는 게 목표인 문제다. 단순하게 생각해서 마구잡이로 for 문을 돌린다면 N의 최댓값 1,000,000인 O(N*N*T)의 말도 안 되는 Time Complexity 때문에 for문 한 번으로 문제를 푸는 방법을 찾아야 한다. 내가 생각한 방법은 객체 배열 ArrayList를 만드는 것이다. 1. ArrayList에 주식의 값과 날짜를 받아와 내림차순으..