짱아의 개발 기록장

전형적인 kmp문제이다. 하지만 더 추가해야할 포인트가 있다. 입력받은 문자열에 대한 failure function을 작성해서 돌리되, kmp Algorithm은 맨 처음 문자부터 시작하기 때문에 접미사를 하나씩 지우면서 최대값을 찾아나갔다. 일단, kmp Algorithm에 대한 개념이 생소하신 분은 아래 링크를 참고해서 공부하시면 될 것 같습니다. https://jason9319.tistory.com/130 KMP(Knuth–Morris–Pratt) 알고리즘 KMP 알고리즘은 문자열 A와 문자열 B가 있을 때, 문자열 A에서 문자열 B를 찾아주는 알고리즘 입니다. KMP는 KMP를 만든 사람의 이름인 Knuth, Morris, Prett 세 사람의 앞 글자를 따서 KMP 알고리즘이라고 � jason9..

생각보다 까다로웠던 문제? 시간초과와 틀렸습니다 늪에 빠져 푸는 데에 오래걸렸다.... sliding window문제!! 그냥 해독하려는 문자열을 기준으로 찾고자 하는 단어의 크기만큼 (g만큼) 길이를 잡아서 w문자열과 종류가 같고 개수도 같은지 확인하면 된다. 나는 map을 사용하여 종류와 개수를 판단했다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 //..

이 문제는 처음에 딱 읽었을 때 bfs로 풀면 간단하겠다라고 생각했지만, 통신탑과 간선의 개수가 각각 최대 100,000 인것을 보고 bfs로 풀다가는 백퍼 시간초과가 나겠구나 싶었다. 그리고 다른 방법을 고민하다가 도저히 아이디어가 생각나지 않아, 문제 유형을 검색해보니 바로 "유니온파인드"를 이용하는 문제였다. 끊을 간선을 제외한 모든 간선을 먼저 연결해주고 끊을 간선들을 역순으로 하나씩 연결해주며 값을 계산해나가면 된다. 예를 들어, a->b a를 b와 연결해준다면 a의 부모 노드를 찾고 b의 부모노드를 찾아서 연결해주고 b의 부모노드의 값에 a의 부모노드의 값을 더해주면 된다. (cost[b] += cost[a] 이런식으로 구현했다.) 코드 첨부 1 2 3 4 5 6 7 8 9 10 11 12 1..

DP를 활용한 문제이다. 문제를 보자마자 DP를 이용하면 쉽게 풀 수 있겠다는 생각을 했다. dp라는 2차원배열을 선언하고 -1로 초기화 시켰다. 이렇게 하면 visited배열을 선언하지 않아도 -1값을 가지면 처음 방문한 좌표라는 것을 알 수 있다. 그리고 (1, 1)좌표에서 시작해서 top-down방식으로 구현했다. 또한, 문제에서 "경로의 개수는 263-1보다 작거나 같다."라는 조건이 있기 때문에 dp배열을 long long으로 선언했다. 코드 첨부(c++) 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 ..

투포인터를 활용해 푸는 문제이다. 2020카카오인턴 기출 문제 3번인 보석쇼핑과 매우 유사한 문제이다. 유사 문제 https://programmers.co.kr/learn/courses/30/lessons/67258 코딩테스트 연습 - 보석 쇼핑 ["DIA", "RUBY", "RUBY", "DIA", "DIA", "EMERALD", "SAPPHIRE", "DIA"] [3, 7] programmers.co.kr 위 문제에 대한 코드도 블로그에 정리해 두었다. https://jungahshin.tistory.com/10?category=830724 2020 카카오 인턴 코딩 테스트 - 3번. 보석쇼핑(c++) 이 문제는 투포인터를 이용하면 쉽게 풀 수 있는 문제이다. 문제에서 gems 배열의 크기가 100,..

실제 LIS 알고리즘을 통해 생성된 백터는 실제 LIS를 나타내지 않습니다. 그렇기 때문에 LIS를 이루는 원소들을 알아내기 위해서는 추가 과정이 필요합니다. 아래 문제가 LIS 요소 역추적을 연습하기에 가장 좋은 문제입니다. https://www.acmicpc.net/problem/2568 2568번: 전깃줄 - 2 첫째 줄에는 두 전봇대 사이의 전깃줄의 개수가 주어진다. 전깃줄의 개수는 100,000 이하의 자연수이다. 둘째 줄부터 한 줄에 하나씩 전깃줄이 A전봇대와 연결되는 위치의 번호와 B전봇대와 연결�� www.acmicpc.net 일단, 전깃줄-2번 문제의 코드 설명에 앞서 https://yhwan.tistory.com/21님의 블로그 사진을 참고하여 정확하게 이해할 수 있었습니다. [백준] ..