프로그래머스69 [코딩테스트 연습] 게임 맵 최단거리 programmers.co.kr/learn/courses/30/lessons/1844 BFS 문제입니다. 시작점 (1,1) 부터, (N,M)까지 최단거리로 도착할 수 있는 1인 칸의 갯수를 세주면 됩니다. 코드: github.com/cottory/algorithm/blob/master/PROGRAMMERS/PG1844.cc 2020. 9. 7. [코딩테스트 연습] 가장 긴 팰린드롬 https://programmers.co.kr/learn/courses/30/lessons/12904 hyozkim님의 풀이를 보고 해결하였습니다. (https://velog.io/@sa833591/%EA%B0%80%EC%9E%A5-%EA%B8%B4-%ED%8C%B0%EB%A6%B0%EB%93%9C%EB%A1%AC-%ED%94%84%EB%A1%9C%EA%B7%B8%EB%9E%98%EB%A8%B8%EC%8A%A4-Lv.3) 팰린드롬을 위한 dp 점화식은 간단합니다. D[i][j] == 1 : i번째 문자부터 ~ j번째 문자가 팰린드롬이면 1 D[i][j] == 0 : i번째 문자부터 ~ j번째 문자가 팰린드롬이 아니면 0 기저 사례는 아래와 같습니다. DP[i][i] = 1 DP[i][i+1] = (str.. 2020. 9. 1. [2020 카카오 기출] 가사 검색 문제: https://programmers.co.kr/learn/courses/30/lessons/60060 참고 링크: https://shjz.tistory.com/99 shjz님의 블로그 글을 참고해서 해결했습니다. 중요한 점은 3가지 입니다. 1. 트라이 사용 문제 2. 정방향 트라이와 역방향 트라이를 사용 3. 문자열 길이만큼 트라이배열을 만들어서 사용 1. 트라이 사용 문제 각 문자열에 대한 판단을 O(M) (M: 문자열의 길이)에 끝내기 위해 트라이를 사용합니다. 2. 정방향 트라이와 역방향 트라이를 사용 '?'(와일드 카드 식별자)가 중간에 나오지 않는다는 뜻은 '?'가 나온 시점에는 나머지 탐색에 대한 처리가 상수 시간에 끝나야 합니다. 그렇게 처리하지 않고 26(알파벳 크기)^(남은 문자.. 2020. 8. 12. [2020 카카오 기출] 블록 이동하기 문제: https://programmers.co.kr/learn/courses/30/lessons/60063 시뮬레이션 문제입니다. 따져줄 게 참 많아보이는 문제입니다만 아래 두 가지에 대해서만 잘 정하고 풀면 됩니다. 1. 상태를 어떻게 저장할 지 2. 다음 좌표 탐색을 어떻게 할 지 우선 편의를 위해 블록의 2칸 중 한 칸을 HEAD, 다른 한 칸을 TAIL이라고 하겠습니다. 우리는 (HEAD_Y, HEAD_X, TAIl_Y, TAIL_X)로 4개의 정보가 필요하지만 이는 (HEAD_Y, HEAD_X, HEAD가 TAIL과 연결되어 있는 방향) 3개 정보로 똑같이 표현할 수 있습니다. 그래서 상태를 어떻게 저장하느냐에 대해서는 (HEAD_Y, HEAD_X, Direction)으로 표현하겠습니다. (b.. 2020. 8. 11. 이전 1 ··· 6 7 8 9 10 11 12 ··· 18 다음
