짱아의 개발 기록장

완벽한 백트래킹(dfs)문제이다. dfs 함수에서 모든 상태를 새로운 배열과 벡터에 담아두고 물고기를 움직이고, 상어를 움직인 후 재귀함수를 통해 계속 반복한다. 그 후 재귀에서 돌아오면 다시 담아두었던 새로운 배열과 벡터의 값들을 원래 배열과 벡터에 넣어주면 된다. 즉, 계속 백트래킹을 하면서 원래대로 돌려놓는 작업이 중요하다! 코드첨부 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 ..

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

URL shortening 이란? URL 단축(URL shortening)은 월드 와이드 웹 상의 긴 URL을 짧게 만들어 주는 기술이다. URL 단축 기능을 제공하는 서버는 HTTP 넘겨주기를 이용해 클라이언트(client)를 긴 URL로 넘겨준다. DB table 저는 DB table 구성을 다음과 같이 했습니다. 이름(속성) 내용 index(Auto Increment) 인덱스 url 접속하고자하는 Url의 주소 Short URL 생성 원리 Short URL은 해당 URL을 직접적으로 encoding하는 방식이 아니라, URL을 삽입하고 해당 Index를 encoding하는 방식이다. encoding방식은 base 62를 사용했다. 여기서 잠깐! base64가 아닌 base62 방식을 사용하는 이유는..

이 문제는 처음에 딱 읽었을 때 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..