모항이코딩한다

1회차에는 시간 복잡도의 개념 등 기본적인 이야기가 많아 정리를 생략하였다. 2회차에서는 문자열 비교 시에 해싱을 사용하는 방법을 알려주었다. 아직까지 학교 수업에서는 해싱을 개념적으로 배우고 수학적인 예시를 풀어보았을 뿐, 코드에 적용한 적은 없었다. 실제로 구현해보니 굉장히 흥미로웠다.이번 강의에서는 비교적 쉽고 사용하기 편한 Polynimial Rolling Hash 기법을 배웠다. 새로 알게 된 표기문자열의 길이는 절대값기호로 표기. 문자열 해싱을 통한 비교란?문자열을 한 글자씩 일일이 비교하는 대신,문자열마다의 고유 값을 도출하여 그 값을 비교하는 방식이다. 서로 다른 문자열끼리 해시값이 겹치는 경우가 발생하면, 다중 해시를 사용하여 해결할 수 있다.(하나의 대상에게 다른 기준으로 만들어진 여러..

줄바꿈을 나타내는 문자를 개행문자라 한다. 개행문자에는 두 가지가 있다. \n 커서를 한 칸 아래로 이동하여 새로운 라인을 추가한다. \r 커서를 맨 왼쪽으로 이동한다. 그런데 운영체제마다 개행문자가 다르다. 윈도우: \n\r MAC: \r UNIX: \n 이로 인한 문제를 예방하기 위해 코드에 개행문자 자체를 적는 대신, 코드가 실행되는 환경의 운영체제에 맞는 개행문자를 알아서 취하도록 할 수 있다. 다음과 같이 쓰면 된다. System.getProperty("line.separator"); //혹은 System.lineSeparator(); StringBuilder에서 사용하는 예시는 다음과 같다. StringBuilder sb = new StringBuilder(); sb.append("abc");..

풀이방법 사용된 것: 그리디 알고리즘 정렬 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이 필요하다. 오름차순으로 정렬한 배..

HashSet은 Set 인터페이스의 구현 클래스이다. HashMap은 Map 인터페이스의 구현 클래스이다. 즉, HashSet은 일반적인 요소를 저장하고, HashMap은 키와 값을 한 쌍으로 묶어 저장한다. HashSet은 중복되는 요소를 허용하지 않는다. HashMap은 중복되는 키를 허용하지 않는다. 값은 중복되어도 괜찮다. 이 두 자료구조는 이름에서 알 수 있듯이 해싱(Hashing)기법으로 데이터를 관리한다. 따라서 다음의 특징을 가진다. 데이터를 탐색할 때 성능이 뛰어나다. 각 데이터의 저장 위치가 저장 순서와 관련이 없다. (데이터가 연속적으로 저장되는 배열과 다르다) 쓰임새 1. HashSet 특정 데이터 집합 중 어떠한 값이 존재하는지 여부를 판단할 때 쓰기 좋다. 2. 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)까지 이동하면서 모을 수 있..