Algorithm/Programmers93 [코딩테스트 연습] 가장 긴 팰린드롬 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. [2020 카카오 기출] 기둥과 보 설치 문제: https://programmers.co.kr/learn/courses/30/lessons/60061 sooooooyn님의 솔루션으로 해결하였습니다. (https://sooooooyn.tistory.com/32) 기둥과 보를 설치/삭제 시에 어떻게 따져주는 지에 따라 난이도가 달라지는 문제입니다. 서치했던 솔루션 중에 굉장히 심플한 솔루션이라고 생각합니다. 간단하게 두 가지로 모든 경우를 처리합니다. 1. stick[N][N], paper[N][N] 으로 기둥과 보를 표현 2. 삭제 입력이 들어오면 일단 삭제 시켜본 후에, 삭제 시킨 좌표와 연관이 있는 기둥이나 보가 설치 불가능하다고 판정이 나는 경우 롤백시킵니다. 코드: https://github.com/cottory/algorithm/blob.. 2020. 8. 11. 이전 1 ··· 8 9 10 11 12 13 14 ··· 24 다음
