짱아의 개발 기록장

전형적인 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,..

bfs로 한 번에 풀 수 있는 문제였다. 다만, visited배열을 4차원 배열로 선언해서 x, y, dir, dir_num(지금까지 방향 전환한 수) 이렇게 4가지 값을 저장햇다. 코드 첨부(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 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 //2020 카카오인턴 #4번(bfs) //경주로 건설 #include #include #include #include #include #include using na..

이 문제는 투포인터를 이용하면 쉽게 풀 수 있는 문제이다. 문제에서 gems 배열의 크기가 100,000이하라는 것을 보자마자 이중 for문을 돌렸다가는 터지겠다는 생각이 들었다. 따라서, 시간복잡도를 고려하여 투포인터로 풀면 된다. 처음 이 문제를 카카오인턴 코테가 끝나고 바로 올라오자마자 풀어보았는데,,,, 지금 다시 똑같이 풀어보니 틀렸다!!!!!! 첫 번째 오류 문제는 End, Start가 모두 다음에 연산할 것을 미리 가르키다보니 End=kind일 경우에는 End

이 문제는 한 번에 맞을 수 있었다. 최단 거리의 사람을 판별하는 것이 핵심 포인트! 나는 벡터에 를 넣어주었고 sort해주어서 가장 앞에 있는 원소들 중 거리가 똑같다면 또 다른 벡터에 값을 넣고 sort해주어 0번째 있는 customer를 최단 거리에 있는 사람으로 판별했다. 주저리 설명을 너무 못한다.... 코드에 주석을 달아 놓았으니 참고하시길... 코드 첨부 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..