본문 바로가기

Algorithm

2019 KAKAO 실패율 Java 2019. 8. 26. 2. 실패율 정답률: 55.57% 문제 풀러 가기 슈퍼 게임 개발자 오렐리는 큰 고민에 빠졌다. 그녀가 만든 프랜즈 오천성이 대성공을 거뒀지만, 요즘 신규 사용자의 수가 급감한 것이다. 원인은 신규 사용자와 기존 사용자 사이에 스테이지 차이가 너무 큰 것이 문제였다. 이 문제를 어떻게 할까 고민 한 그녀는 동적으로 게임 시간을 늘려서 난이도를 조절하기로 했다. 역시 슈퍼 개발자라 대부분의 로직은 쉽게 구현했지만, 실패율을 구하는 부분에서 위기에 빠지고 말았다. 오렐리를 위해 실패율을 구하는 코드를 완성하라. 실패율은 다음과 같이 정의한다. 스테이지에 도달했으나 아직 클리어하지 못한 플레이어의 수 / 스테이지에 도달한 플레이어 수 전체 스테이지의 개수 N, 게임을 이용하는 사용자가 현재 멈춰있는 스테이지의..
백준 17136 색종이 붙이기 Java 2019. 8. 23. 삼성 기출문제인 색종이 붙이기 문제이다. 삼성 기출 문제는 거의 대부분 완전 탐색을 해야 하는구나 하고 느꼈다. 이 문제는 색종이 크기가 큰 순부터 붙이는 그리디적인 요소와 DFS + 백트래킹을 활용해서 풀어야 한다. 꽤 오랜시간 못 맞추고 여러 번 틀렸었는데 해답을 보고 나서야 순서가 틀렸구나 하고 깨달았다. 나는 색종이 크기가 큰 순서대로해서 색종이 크기를 기준으로 배열을 돌면서 색종이를 붙이는 방식으로 구현했다. 이 방식이 안돼서 색종이의 크기를 1, 2->1, 3->2->1... 이런 식으로도 구현했었다. 하지만 이렇게하면 색종이를 붙일 수 있는 모든 경우의 수를 탐색할 수 없다. 색종이를 붙이는 모든 경우를 탐색하기 위해선 배열을 기준으로 색종이 크기를 큰 순서대로 돌면서 색종이를 붙이는 방식으..
백준 1300 K번째 수 Java 2019. 8. 22. 이분 탐색으로 분류되어 있는 K번째 수이다. N제한이 100,000에 배열은 N*N인 10,000,000,000으로 굉장히 크다. 그러므로 직접 배열을 만들어서 수를 구한다든지 하는 방법들은 전부 정답이 될 수 없다. 이 문제에서 가장 중요한 부분은 배열에 들어가는 수가 A[i][j] = i * j 이기 때문에 i번째 행이나 i번째 열은 i의 배수이라는 점이다. N이 2일 때의 배열을 보자. 1 2 3 4 2 4 6 8 3 6 9 12 4 8 12 16 x라는 수가 있을 때 x가 몇번째로 큰 수 인지 찾기 위해서는 cnt 변수를 두고 i번째 행이나 열이 i의 배수이기 때문에 x / i를 했을 때 N을 넘는다면 N번째 행이나 열보다 전부 큰 것이기 때문에 N을 더해주고 N이 넘지않는다면 x / i를 더해주..
백준 1520 내리막 길 Java 2019. 8. 20. 단계별로 풀어 보기 -> 동적 프로그래밍에 있는 내리막 길 문제이다. 이 문제를 풀 때 내가 실수한 점이 몇가지 있다. 첫 번째로는 Queue를 사용한 BFS로 풀려고 했다는 점이다. 문제의 내용이 BFS를 사용한 탐색으로 풀어왔던 문제들과 비슷해서 BFS로 풀려고 시도했으나 메모리 초과가 나왔다. 아무래도 Queue를 사용함으로써 메모리 초과가 나온 것 같았다. BFS는 대게 최소 횟수 등 최소 값을 구할 때 사용하는데 이 문제에 최소라는 단어는 없다. 그럼 굳이 BFS를 사용할 필요 없이 DFS로 탐색하면 되는 것이었다. 두 번째로 중복 방문을 허용했다는 점이다. 내가 중복 방문을 허용한 이유는 예제의 3가지 경우 중 2가지 경우를 보면 1, 3 좌표의 20을 두 번 방문한다. 그렇기 때문에 나는 중..
SWEA 1859 백만 장자 프로젝트 Java 2019. 8. 20. https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV5LrsUaDxcDFAXc SW Expert Academy SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요! swexpertacademy.com SWEA의 D2문제인 백만 장자 프로젝트이다. 문제를 간단히 설명하자면 N일 만큼의 매매가가 주어지고 하루에 최대 1개만 살 수 있다. 판매는 개수 제한없이 팔 수 있다. 예를 들어 N = 3 1 2 3 이 주어지면 첫째 날 1원을 주고 1개를 사고 둘째 날 2원을 주고 1개를 사고 셋째 날 3원에 2개를 팔면 6-3 = 3원의 이득이 생긴다. 이처럼 테스트 케이스의 개수, N, 매매가가 주어지면 ..
백준 1038 감소하는 수 Java 2019. 8. 19. 알고리즘 분류 브루트 포스, 다이나믹 프로그래밍으로 분류되어있는 감소하는 수 문제이다. 브루트 포스로 짜봐도 시간 초과가 나오고 jump 변수를 사용해서 필요없는 수는 건너뛰는 다른분들의 코드를 봐도 제대로 이해하기가 쉽지 않았다. dp는 더더욱... 그렇다. 그래서 이 문제는 Queue를 활용하여 푸는 방법이 제일 간단하고 쉬운 것 같다. 문제를 읽어보면 N이 0부터 9까지 인 경우에는 그냥 N을 출력해주면 된다. 그리고 감소하는 수가 없다면 -1 출력인데 여기서 수는 무한한데 어떻게 감소하는 수가 없을 수 있을까 하는 의문이 들 수 있다. N은 백만까지이지만 이것도 함정이다.. 생각해보면 감소하는 수는 9876543210보다 큰 수가 있을 수 없다. 그리고 9876543210은 1022번째 감소하는 ..
백준 12865 평범한 배낭 Java 2019. 8. 16. 대표적인 dp문제 중 하나인 냅색 문제이다. 냅색 문제는 무게 K가 주어졌을 때 무게에 맞게 물건들을 최대 가치로 넣는 문제이다. 다른 냅색 문제들은 모르겠지만 이 문제는 한 번 넣은 물건은 또 못 넣는다는 점에 주의해야 한다. dp배열을 2차원 배열로 사용하는 방법과 1차원 배열로 사용하는 방법이 있다. 2차원 배열은 dp[i][j] = 무게가 i일 때 j번째 물건까지 넣었을 때의 최대 가치이다. 이를 통해 점화식을 짜면 1 2 3 4 5 if(i >= w[j]) { dp[i][j] = Math.max(dp[i][j-1], dp[i-w[j]][j-1]+v[j]); } else { dp[i][j] = dp[i][j-1]; } 이렇게 점화식이 나올 수 있다. 여기서 dp[i-w[j]] [j-1] + v[j..
백준 17298 오큰수 Java 2019. 8. 15. 단계별로 풀어보기 -> 스택에 있는 오큰수 문제이다. 오큰수는 말 그대로 오른쪽에서 가장 첫 번째로 큰 수이다. 1번부터 N번까지의 오큰수를 출력하면 되는 문제이다. N의 최대 크기는 백만이니까 당연히 O(N^2)으로 탐색하는 방법은 안된다. 스택을 사용해야 한다는 걸 알고 문제를 접했기 때문에 스택으로 어떻게 O(N)만에 처리할지 고민해야 한다. 내가 푼 방식은 N개의 값들을 N크기의 배열에 넣고 for문을 n-1부터 0까지 돌린다. 1. 스택의 top부분보다 배열[i]가 크다면 배열[i]가 더 작을 때까지 pop 해준다. 2. 스택이 비어있다면 배열[i]보다 더 큰 수가 없는 것 = 오큰수가 없는 것, i번째 오큰수는 -1 3. 스택의 top이 배열[i]보다 크다면 i번째 오큰수는 스택의 top 4...

티스토리툴바