programemrs. 위장 많은 사람들이 풀었던 문제인 만큼 난이도는 높지 않았습니다. 종류별로 의상을 나눠야 한다는 필요성은 문제를 풀면서 느꼈을 것입니다. 그리고 해시를 이용하면 깔끔하게 분류할 수 있겠다는 생각도 했을 것입니다. 그리고 나서 드는 생각은 이것이죠. 의상 종류 중 하나도 고를수도 있고, 두개를 고를수도 있고, 또 여러개를 고를 수 있는데 이 조합을 어떻게 구할 수 있을까? 그렇습니다. 조합을 찾아야 합니다. 조합이라는 단어만 들어도 뭔가 경우의 수를 많이 만들어야할 것만 같습니다. 하지만 다행이게도 여기서의 조합은 쉽게 구할 수 있습니다. 각 의상 종류별로 다음 의상을 하나 더 추가시키면 되거든요. 상의 - 티셔츠, 후드, 선택 안하는 경우 하의 - 청바지, 면바지, 쫄바지, 선택 ..
programmers. 등굣길 지도 문제 그리고 최단거리를 보니 저도 모르게 bfs를 생각하게 되었습니다. 이러한 고정관념이 문제를 다양한 방식으로 생각하는 것을 막았던 것 같습니다. 그렇기 때문에 전형적인 bfs를 푸는 방식으로 큐를 이용하여 풀었습니다. 하지만 bfs는 최단거리를 찾는 것에 최적화된 것이지 '최단거리를 갈 수 있는 개수'에 대해서는 최적화되진 않았기 때문에 bfs코드에서 추가적인 조건이 붙었습니다. 그래서 목적지의 위와 옆에 왔을 때는 visit표시를 하지않고(만약 해버리면 다른 경우의 수가 무시되기 때문입니다) 그 개수를 세아렸습니다. 하지만 역시 어설픈 저의 조건인지 몇 개의 경우 오류가 났고 결정적으로 런타임 오류가 발생하였습니다. class Solution { p..
programmers. 정수 삼각형 동적 계획법의 대표적인 문제였던 것 같습니다. 처음에 재귀적으로만 접근했다가 '시간 초과'를 경험하고 다른 코드들을 참고하다가 Memorization을 사용할 수 있다는 것을 다시 깨닫게 되었습니다. Memorization은 이전의 값을 기록해둠으로써 이후에 불필요한 계산을 줄일 수 있게 해줍니다. 그렇기 때문에 앞의 결과에 따라서 뒤에서 처리해주는 것이 동적으로 달라지죠. 그럼 앞서 재귀로 풀면서 시간초과했던 코드부터 보겠습니다. class Solution { private int maxSum; public int solution(int[][] triangle) { search(triangle, 0, 0, 0); return maxSum; } publi..
programmers. 타일 장식물 문제 자체는 어렵지 않았습니다. 원소가 4개 이상이면 answer은 제일 마지막에서 앞으로 순서대로 3배, 2배, 2배, 1배 한 값들을 더해주면 구할 수 있거든요. 다만 효율성 테스트에서 실패가 발생했었는데요. 그래서 코드를 조금씩 수정해봤는데 결국은 해결방법은 형변환이었습니다 위 과정을 다 정수(Integer)타입으로 계산을 했었는데 실제 반환값이 long이었거든요. 형변환 과정에서 좀 더 시간이 걸렸던 것 같아요. 실제로 답을 제출할 때 2ms에서 실패가 떴었는데 계산과정 내에서 long타입으로 하면 1ms로 시간이 줄어들 수 있었거든요. 반환값 타입이 제가 계산한 것과 다를 때는 형변환이 필요한지 유무도 고려해야할 것 같네요. class Solution { pu..
programmers. 구명보트 남들은 다 쉽게 푸는것 같은데 저는 왜 이렇게 그리디 문제가 감이 안올까요.. 처음엔 우선순위큐를 사용하여 가장 작은 몸무게를 찾은 다음 남은 사람들 중 무게제한을 초과하지 않는 사람들 중 가장 무거운 사람을 골랐습니다. 아무래도 남은 사람들 중 가장 무거운 사람을 찾는 과정에서 복잡도가 증가하였고 여러 테스트케이스에서 통과하지 못하였습니다. 이렇게 제일 큰 것 찾고 가장 작은 것도 동시에 찾기 위해선 우선순위큐 대신 리스트를 사용하고 포인터를 2개를 사용하면 됩니다(다 풀고나서 다른 사람들의 풀이를 보니 Deque도 많이 사용했더라구요. 어차피 똑같은 맥락이죠). 리스트를 오름차순 정렬하고 가장 작은(왼쪽) 수의 인덱스를 왼쪽(left), 가장 큰(오른쪽) 수의 인덱스를..
programmers. 큰 수 만들기 그리디(탐욕법) 문제라 그랬을까요. 무조건 큰 수를 먼저 골라내거나, 가장 작은 수를 빼내려고만 생각했던 것 같습니다. 탐욕법이 가장 유리해보이는 것을 가장 먼저 고려하는거잖아요. 그렇게 여러 가설을 세우고 이렇게 하면 모든 경우에 대해 적용이 될 수 있는지 탐험해보았습니다. 첫번째 가정 가장 작은수부터 지워나갑니다. 지울 수 있는 대상이 여러 개이고, 지울 수 있는 대상이 그 보다 작다면 앞의 수부터 지웁니다. 문제점 : "4177252841"와 같은 케이스를 걸러내지 못합니다. 두번째 가정 제일 큰 수부터 순서는 지키면서 앞의 순서대로 가져옵니다. 문제점 : 여전히 "4177252841"와 같은 케이스에서 문제이며 이때는 마지막 수 1이 문제입니다. 큰 수부터 가..
