모항이코딩한다

풀이방법 및 문제점 2023.01.17 (1) 시간초과가 발생했다. 논리적 풀이 방식이 틀리지는 않은 것 같다. 모든 예제가 올바르게 해결되고, 하나하나 짚어보았을 때 논리적으로 오류가 있는 부분이 없어보인다. 시간초과가 발생한 것은 출력 수 하나마다 새 스택을 하나씩 만들어 푸는 방법을 택해서인 것 같다. 사용하는 스택의 개수를 줄이고, 무엇보다도 add()와 pop()의 수행 횟수를 최대한 줄여야 할 것 같다. 하나의 스택만 사용해서 푸는 방법이 있을까? 사용한 풀이방법은 다음과 같다. 1. 입력값은 1차원 정수 배열 original에 순서대로 저장한다. 2. 반복문에서, 0부터 N-1까지의 i에 대하여 다음과 같은 과정을 수행한다. stack을 새로 하나 만든다. boolean 값 check를 선언..

풀이방법 및 문제점 2022.11.23 이번 문제도 작은 실수로 인해 틀렸던 문제이다. 백트래킹 문제를 풀 때 절대 잊으면 안 되는 부분이기 때문에 오답노트에 적어두려 한다. 재귀를 통해 각 도시를 방문하다가, 모든 도시를 빠짐없이 방문한 것이 확인되면 출발지로 다시 돌아가는 비용을 현재까지 쌓인 비용에 더한 뒤 이번 여정의 최종 비용으로 결정하기로 하였다. 단, 마지막으로 방문한 도시에서 출발지로 돌아가는 길이 없다면 이번 여정은 무효로 처리하고 정답에 반영하지 않는다. 그 다음 모든 최종 비용 값 중 최솟값을 화면에 출력하여 문제를 해결한다. 이러한 풀이 방식은 잘 짠 것이었다. 단, 백트래킹 문제를 풀 때 꼭 기억해야 하는 사항 하나를 깜빡하여 틀렸었다. 백트래킹이란, 갔던 길을 되돌아오기를 반복하..

풀이방법 및 문제점 2022.11.22 사용한 방법은 다음과 같다. 0부터 9까지의 숫자가 담겨있는 해시셋을 선언한다. 수열에 특정 숫자가 나타날 때마다 그 숫자를 해시셋에서 remove()한다. 해시셋이 텅 비게 되면 그 시점의 k를 출력한다. 형변환의 번거로움을 줄이기 위해 각 숫자는 int나 long이 아닌 Character형으로 하였다. 완벽한 풀이법이라고 생각했는데 33퍼센트에서 자꾸 틀렸습니다를 받는다. 무엇이 문제지...? 친구가 한 것처럼 boolean 배열이 모두 true가 되었을 때 정답을 확정하는 코드도 짜보았는데, 똑같이 33퍼센트에서 틀렸습니다를 받았다. 이걸 보니 풀이법 자체가 문제가 아닌 것 같다. 친구가 했을 때 정답 처리를 받은 코드를 내 식으로 짜보니 오답 처리가 되었기 ..

풀이방법 및 문제점 2022.11.09 어이 없는 이유로 계속 실패하다가 오늘 해결에 성공한 문제이다. 이 문제를 풀 수 있는 완벽한 로직은 9달 전부터 알고 있었다. 그러나 그 때에는 Comparator를 아직 알지 못해, 매우 비효율적인 방식으로 값들을 정렬하였다. 그래서 시간초과를 받았다. 그리고 오늘 다시 도전하였다. 오늘은 Comparator를 아는 상태이기 때문에 시간초과는 받지 않았다. 그러나 for문에 break를 넣어서 틀렸다. 넣을 이유가 없는데 왜 넣었는지 모르겠다. 정말 멍청한 실수였다! break를 지우니 정답 처리가 되었다. 정답 게시글 바로가기 코드 Java(2022.01.22) 시간초과를 받은 코드 import java.util.Scanner; import java.util...

풀이방법 및 문제점 2022.06.10 전체적인 알고리즘은 완성되었다. 그런데 check 함수의 시간복잡도가 문제이다. 여기 때문에 시간초과가 발생한다. check만 상수시간이 걸리도록 바꾸면 해결될 것 같다. ... 구글링을 하다가 아래의 블로그 글을 발견했다. 백준 (BOJ) 16564 히오스 프로게이머 java https://www.acmicpc.net/problem/16564 16564번: 히오스 프로게이머 첫째 줄에는 캐릭터의 개수 N, 올릴 수 있는 레벨 총합 K가 주어진다. (1 ≤ N ≤1,000,000, 1 ≤ K ≤ 1,000,000,000) 다음 N개의 줄에는.. verycrazy.tistory.com 분명히 내 코드랑 똑같은 아이디어로 짠 코드인데 이 코드를 백준에 돌려보면 순식간에..

풀이방법 및 문제점 2022.06.08 (1) 이분탐색을 쓰지 않고 그냥 좌표압축을 시도해보았다. 해시맵을 사용하였다. 역시 시간초과가 발생한다. 답의 값 자체는 맞게 도출되는 것 같다. 2022.06.08 (2) 이분탐색을 이용하여 좌표압축을 하니 해결되었다. 정답 게시글 바로가기 코드 Java(2022.06.08(1)) import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.HashMap; import java.util.StringTokenizer; public class Main { public static void main(String[] args) thro..

풀이방법 및 문제점 2022.05.28 자바로 시간초과를 안 내기가 매우 매우 어려운 문제다. 난 최선을 다했다...따흐흑 다른 언어로 시도한 사람들은 나와 똑같은 알고리즘으로도 성공했다. 자바로 시도한 다른 사람들은 동일한 코드를 여러 번 제출했더니 한 번은 시간초과, 한 번은 통과가 된다고 한다ㅋㅋㅋㅋㅋㅋㅋㅋ굉장히 빡빡한가 보다. 시간을 줄일 기발한 알고리즘이 떠오르지 않는 한, C++ 또는 Python으로 나중에 도전하는 것이 낫겠다. 코드 Java(2022.05.28) import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.ArrayList; import j..

풀이방법 및 문제점 2022.05.27 지금까지 몇 개의 노드를 방문해왔는지 저장하는 변수 num을 전역변수로 설정하지 않고 재귀 시마다 넘겨주는 변수로 선언하였더니 틀린 답이 도출되었다. 이 점을 기억하기 위해 오답노트에 적는다. 틀렸던 이유는, 새로 방문하는 노드를 만날 때 dfs 함수 내에서 1 증가시켜주었던 num의 값이, 재귀가 끝나 이전 노드로 거슬러올라갈 때 다시 1씩 줄어든다는 데 있었다. 이것을 알아채는 것에는 백준의 질문 게시판에 있던 다음의 테스트케이스가 도움이 되었다. 6 7 1 1 6 1 2 2 6 2 3 2 4 3 5 4 5 1 -> 2 -> 3 -> 4 -> 5 -> 6 위 소스는 아래와 같이 나오네요. 1 2 3 5 4 3 내 코드에서도 똑같은 오답이 나와서 왜 그럴까를 고민..

풀이방법 및 문제점 2022.05.07 문제 없이 알고리즘을 잘 짰다고 생각했는데 50%에서 계속 막힌다. 정답이 2의 31제곱 미만이라는 것을 보고 화끈하게 BigInteger로 다루어보았는데 그래도 똑같이 50%에서 틀린다. 흠... 내가 놓친 분기 또는 반례가 있는 것 같다. 모든 가능한 분기를 하나하나 적어가며 빈틈없이 만들어봐야 하나? 거의 다 왔다는 생각이 들어 구글링하기가 아깝다. 알고리즘은 다음과 같다. 음수와 양수를 따로 다룬다. 음수의 경우 다음과 같이 다룬다. 가장 작은 수 즉 절댓값이 큰 것들부터, 모든 음수를 짝짓는다. 주어진 수들 중 음수가 -1, -5, -2, -7 이렇게 네 개라면 (-7, -5), (-2, -1) 이런 식으로 짝짓는 것이다. 만약 음수가 홀수 개라면 가장 절..

풀이방법 및 문제점 2022.04.30 예제에 대해서는 모두 올바른 값이 출력되지만, 시간 초과가 발생하여 실패하였다. 내가 짠 알고리즘의 시간복잡도가 O(NK)이기 때문이다. 알고리즘은 다음과 같다. 보석을 가치 기준으로 내림차순 정렬하되, 가치가 같은 보석끼리는 무게를 기준으로 오름차순 정렬한다. 가방의 용량은 오름차순 정렬한다. 가벼운 가방부터 순서대로 살핀다. 가장 앞에 있는 보석부터 살피며, 이 가방에 들어갈 만큼 가벼운지 확인한다. 들어갈 수 있으면 그 보석을 가방에 집어넣으면 된다. 아까 가치 기준으로 내림차순 정렬을 해뒀기 때문이다. 이렇게 모든 가방을 살피면 된다. 그러나 보석들 중 가장 가치가 낮은 보석만이 가방에 들어갈 수 있을 정도로 가볍다면 최악의 시간복잡도에 해당하게 된다... ..