모항이코딩한다

풀이방법 및 문제점 2022.02.05 (1) 예제 입력에 대한 출력값은 올바르게 나오지만 채점 결과는 틀렸다고 나오는 상황이 또 발생했다. 큰일이다... 문제점이 무엇인지 모르겠다. 채점 시 6%에서 틀렸습니다 가 나온다. 잠이 부족한 상태에서 풀다 보니 놓친 반례가 생긴 것일까? 단계별로 다시 차근차근 검토해보아야겠다. 사용한 풀이방법은 다음과 같다. 가장 위 한 줄을 잘라내면, 이번 차례에 비교대상이 되는 단어들은 모두 앞전에 비교대상이었던 단어들의 가장 앞 한 글자만 떼어낸 접미사이다. Polynomial Hashing 기법을 사용하면 접미사를 빠르게 해싱할 수 있으므로, Polynomial Hashing으로 모든 접미사들의 해싱을 미리 끝내둔 뒤, 그 해시값을 비교하며 count 값을 구하였다...

풀이방법 사용된 것: 그리디 알고리즘 정렬 2022.01.28 (1) 빨대들을 모두 큰 것부터 정렬한다. 가장 긴 빨대를 1번, 가장 짧은 빨대를 N번이라 부르겠다. 일단 1번 빨대와 2번 빨대가 무조건 쓰일 것이라고 가정한다. 3번부터 N번까지 차례차례 살피면서, (2번빨대의 길이) + (j번째 빨대의 길이) > (1번 빨대의 길이) 인 j를 찾는다. 찾아지면 1번, 2번, j번 빨대 세 개로 만드는 삼각형의 변의 합이 정답이다. 위의 과정에서 N번 빨대까지 모두 살폈는데 조건에 부합하는 빨대가 없었다면, 2번 빨대와 3번 빨대가 무조건 쓰일 것이라고 가정하고 4번부터 살펴 합당한 j를 찾는다. 또 없었다면, 3번 빨대와 4번 빨대가 무조건 쓰일 것이라고 가정하고 5번부터 살핀다. 이렇게 N-2번 빨대..

풀이방법 사용된 것: HashMap StringTokenizer StringBuilder 2022.01.28 오답노트 #18870 : 좌표 압축 풀이방법 및 문제점 2022.01.28 (1) 입력 수열의 값을 복사한 temp 배열을 크기순으로 정렬하면 각 좌표의 압축 결과를 쉽게 구할 수 있다. 그 다음 temp값과 기존 입력 수열의 값을 비교하여 본래 순서 blowupmomo.tistory.com 주어진 정수들에 순위를 매겨 그 순위를 출력하는 문제이다. 값이 같은 정수끼리는 순위도 같다. 가장 작은 정수가 0위이며 클수록 순위는 1씩 증가한다. 수들을 입력된 순서대로 저장하는 배열, 수들을 정렬하여 오름차순으로 정렬할 배열, 각 수마다의 순위를 저장할 HashMap이 필요하다. 오름차순으로 정렬한 배..

풀이방법 및 문제점 2022.01.28 (1) 입력 수열의 값을 복사한 temp 배열을 크기순으로 정렬하면 각 좌표의 압축 결과를 쉽게 구할 수 있다. 그 다음 temp값과 기존 입력 수열의 값을 비교하여 본래 순서에 맞게 결과값을 화면에 출력하였다. 문제점: 시간초과. 데이터의 개수 N이 최대 100만 개이고 제한시간은 2초이다. 그런데 압축 결과값을 구하는 부분, 값을 출력할 순서를 알아내기 위해 기존 입력 수열을 조회하는 부분 모두 $N^2$의 시간복잡도를 가져서 시간을 많이 초과하였다. 2022.01.28 (2) HashMap을 사용하여 코드를 짜보았다. HashMap의 key에는 정수 값을, value에는 순위를 저장한 뒤 조회하는 방식이다. 그런데 또 시간이 초과된다. 얼마나 더 빨라져야 하는..

풀이방법 2022.01.26 입력값으로 n개의 정수 배열이 주어진다. 이 정수 배열을 nums라 부르자. 길이가 n인 정수 배열 dp를 만든다. dp[i] 는 nums[i]를 마지막 순서로 갖는 가장 긴 증가하는 배열의 길이이다. 예를 들어, 아래의 표를 보자. nums 10 20 10 30 20 50 dp 1 2 1 3 2 4 nums[0]의 값은 10이다. 10으로 끝나는 가장 긴 증가하는 배열은 {10}이다. {10}의 길이는 1이다. 따라서 dp[0]은 1이다. nums[3]의 값은 30이다. 30으로 끝나는 가장 긴 증가하는 배열은 {10, 20, 30}이다. {10, 20, 30}의 길이는 3이다. 따라서 dp[3]은 3이다. 이를 코드로 구현한 뒤에 dp 배열의 요소 중 가장 큰 것을 화면에..

풀이방법 사용된 것: 그리디 알고리즘 2022.01.24 가지고 있는 동전을 액수가 큰 것부터 차례대로 살핀다. 현재 살피는 중인 동전의 액수 값을 t라 한다. 만들어내야 하는 금액을 k라 한다. 출력할 답은 ans에 저장한다. ans의 초기값은 0이다. 만약 t=0; i--) { coins[i] = sc.nextInt(); } for(int i = 0; i

풀이방법 2022.01.22 재귀함수로 구현하면 제한시간 1초 내에 해결할 수 없는 문제이다. 반복문을 사용해 정수 배열에 피보나치 수들을 미리 저장해놓고 꺼내쓰면 빠르게 해결할 수 있다. n

풀이방법 사용된 것: DP 알고리즘 더보기 도움이 된 블로그 글 2022.01.22 (i, j)에서 (i+1, j+1)까지 대각선으로 이동할 경우, (i+1, j)를 거쳐 'ㄴ'자로 이동한 경우와 (i, j+1)을 거쳐 'ㄱ'자로 이동한 경우보다 사탕을 더 많이 모으는 것이 불가능하다. 그러므로 대각선으로 이동하는 경우는 배제한다. 따라서, (i, j)까지 이동하면서 모을 수 있는 사탕의 최대 개수는 (i-1, j)까지 이동하면서 모을 수 있는 사탕의 최대 개수에 (i, j)에 있는 사탕의 개수를 더한 것 (i, j-1)까지 이동하면서 모을 수 있는 사탕의 최대 개수에 (i, j)에 있는 사탕의 개수를 더한 것 위의 두 값 중 더 큰 쪽이다. 이 아이디어를 이용하면 (N, M)까지 이동하면서 모을 수 있..

풀이방법 사용된 것: HashSet 집합 안에 특정 요소가 존재하는지 여부를 빠르게 파악하기 위해 사용하였다. TreeSet 요소 추가가 편리하고 자동으로 요소들을 정렬해주기 때문에 사용하였다. 2022.01.21 듣도 못한 사람들의 이름을 HashSet set1에 저장한다. 보도 못한 사람들의 이름을 하나씩 읽어오면서, set1에 포함되어있는 이름일 경우에만 TreeSet set2에 저장한다. set2의 크기를 화면에 출력한다. set2의 크기가 0이 아닐 경우, set2의 요소들을 forEach를 사용하여 화면에 순서대로 출력한다. 코드 Java(2022.01.21) import java.io.*; import java.util.HashSet; import java.util.TreeSet; publi..

풀이방법 사용된 것: ArrayList 아스키코드 2022.01.21 26개의 요소를 가지고 있으며 모든 요소의 값이 0인 ArrayList list를 생성한다. a를 1번째 알파벳, b를 2번째 알파벳, ... z를 26번째 알파벳이라 부르자. 입력된 문장을 앞에서부터 한 글자씩 살피며, 해당 글자가 n번째 알파벳일 경우 list의 n번째 요소의 값을 1로 설정한다. 만약 입력된 문장이 팬그램이라면 list의 모든 요소의 값이 1로 바뀌고, 팬그램이 아니라면 list의 요소 중 하나 이상의 값이 0인 채로 남아있게 된다. 이를 이용해 팬그램 여부 및 문장에 등장하지 않은 알파벳이 무엇인지를 파악한다. 코드 Java(2022.01.21) import java.io.*; import java.util.Ar..