programmers. 도둑질 동적계획법 문제는 정말 동적계획법답게 풀지 않으면 시간 초과나 메모리 초과가 발생하는데 이 때문에 많은 고생을 했습니다. 처음엔 머리에 떠오르는대로 재귀로 풀었는데요. 모든 경우의 수를 다 돌다보니 역시나 시간초과부터 발생하더라구요. 그리고 이후엔 학교에서 배운대로 배낭문제나 최소 잔돈개수 문제처럼 표를 떠올리며 구현하였습니다. 여기서 정확성 테스트에서 시간 초과는 극복할 수 있었지만 효율성 테스트에서 시간 초과 및 메모리 초과가 발생하여 이 또한 통과하지 못하였습니다. 우선 메모리초과가 발생한 이유는 array[length][length] 로 만들었기 때문인데요. 다른 사람의 코드를 참고하면서 굳이 저렇게 배열을 모두 만들지 않더라도 해결할 수 있음을 알게되었습니다. 두 ..
programmers. 단속카메라 또 탐욕법이라 생각하니 자연스럽게 큰 것을 먼저 처리해야 한다는 생각이 들었고 이번 문제의 경우 길이가 가장 크거나 작은 순으로 하여 각각의 경우 체크하도록 문제를 풀었습니다. 구체적으로 먼저 길이로 정렬을 하였고, 해당 길이 내에서 for문을 돌면서 어느 지점에 단속카메라를 설치하였을 때 가장 겹치는 지점을 찾았고, 그 겹치는 지점에 속하는 구간을 빼내면서 결국 카메라가 몇 개가 필요한 것인지 찾아나갔습니다. 이렇게 하였을 때 정확성에는 문제가 없었지만 역시나 복잡도 때문에 시간초과가 발생하였습니다. 결국 다른 방법을 찾아야했습니다. 결국 길이가 중요한 것이 아니었습니다. 진입점과 진출점만 알면 위와 같은 복잡도 없이 쉽게 풀 수 있거든요. 우선 객체를 하나 만들었는데..
programmers. 숫자 야구 코드스쿼트라는 교육기관에 들어오기 전에 레벨 테스트로 숫자 야구를 구현했었는데요. 그렇다보니 이 문제가 참 낮설지 않았습니다. 이 문제에서 제가 생각하는 포인트는 2가지 입니다. 비교대상 숫자를 선정하는 방법 비교대상 숫자와 비교하여 스트라이크, 볼 판별 우선 '비교대상 숫자를 선정하는 방법'은 3자리 수를 만들기 위해 for문 3번을 쓸 수도 있겠지만 저는 그렇게는 하기 싫더라구요. 그래서 111~999까지 돌리는 방법을 정했는데요. 그렇게 하다보면 의도하지 않은 수(중복된 수가 존재하는 수, 0이 포함되는 수)가 나오게 됩니다. 그 경우는 Set 를 사용하여 0이 포함되지 않으면서도 중복된 수를 걸려낼 수 있었습니다. 그리고 비교를 하는 경우는 뭐 다를..
Today's Algorithm(2019-01-13) programmers. 카펫 처음에 문제를 읽었을 때는 똑같은 격자 문양 패턴이 여러번 나타날 수도 있을 것이라 생각하고 다양한 경우의 수를 고려해야겠다는 생각이 들었습니다. 하지만 입출력 예를 보면서 격자 문양 패턴이 1개가 있고 그 안의 red의 모양만 바뀐다고 생각했을 때 고려해야 하는 경우의 수는 확 줄었습니다. 일단 red의 width와 height가 결정이 되었다고 한다면 brown의 개수는 red의 width와 height를 이용하면 (width * 2 + (height + 2) * 2) 라는 사실은 충분히 납득할 수 있을거라 생각합니다. 그렇다면 red의 width와 height만 구한다면 문제를 거의 다 푼 것인데요. 그건 문제의 조건..
programmers. 소수 찾기 언젠가, 그리고 조만간 '조합'을 이용한 알고리즘 문제를 풀 날이 올 거라 생각을 했습니다. 그리고 오늘이 그런 날인 것 같더라구요. 수들이 주어졌을 때 이 수로 만들 수 있는 수의 조합들 중에서 소수가 나오는 개수를 구하는 문제입니다. 별 생각이 안 들었습니다. 만들 수 있는 수들의 조합을 구하고(자리수가 다른 수가 만들어질 수 있기 때문) 각각의 조합에 대해 순열로 구성해서 그 수가 소수인지 찾도록 하였습니다. 그게 다였습니다. 조합은 인터넷에 있는 일반적인 조합을 가져다 썼고, 순열은 지난번에 만들어둔 순열 코드를 사용하였고, 소수는 가장 보편적인 방법 인 자기 수까지 수를 나누면서 1과 자신이외에 나누어지는 수가 있으면 소수가 아닌 것으로 판별하도록..
programmers. H-Index 이 문제는 문제풀이 자체는 문제 자체를 이해하는데 힘들었던 문제였습니다. 그 놈의 h가 뭔지.. h번 이상 인용된 논문의 수가 h이고, 나머지 논문들이 h이하 인용이 되었다면 그 h를 구하라는 문제인데요. h h h h h 정말 헷갈렸습니다. 어느 순간 제가 h를 구하고 있는건지, 무엇을 구하고 있는건지 길을 잃기도 했습니다. 말로 설명하기 힘드니 코드로 살펴볼게요 class Solution { public int solution(int[] citations) { int answer = 0; List list = new ArrayList(); for (int citation : citations) { list.add(citation); } Collections.sor..
