Algorithm/Programmers93

• 

  [2020 카카오 기출] 외벽 점검 programmers.co.kr/learn/courses/30/lessons/60062 문제 해설(tech.kakao.com/2019/10/02/kakao-blind-recruitment-2020-round1/)을 보고 해결했습니다. 가장 중요한 건 원형으로 되어 있는 곳을 어떻게 탐색할 지 방법을 찾는 거 같습니다. 해설에 나와 있는 대로 인덱스를 하나씩 밀면서 뒤로 있는 인덱스값에는 + N만큼 더해줘서 아래처럼 원형으로 되어 있는 효과를 만드는 게 중요합니다. N = 12 [1, 5, 6, 10] [5, 6, 10, 13] [6, 10, 13, 17] [10, 13, 17, 18] 그리고 나서는 dist의 크기 제한을 보면 8로 크기가 작습니다. 그래서 비트 바스킹을 통해 (예시 5명) 00000 ~.. Algorithm/Programmers 2020. 9. 10.

• 

  [코딩테스트 연습] 땅따먹기 programmers.co.kr/learn/courses/30/lessons/12913 dp + 슬라이딩 윈도우로 해결할 수 있습니다. 현재 칸에서 어떤 칸을 밟을지 결정할 때는 오직 '이전 칸'의 정보만 가지고 있으면 되므로 dp테이블은 dp[2][N] 크기만 가져도 됩니다. dp 점화식은 dp[i+1][N] = max(dp[i][0], dp[i][1], dp[i][2], ... , dp[i][N-1]) + score[i+1][N] 입니다. 즉, N열이 아닌 이전 칸 중에 최댓값 + 이번 칸의 값을 더하면 점화식이 됩니다. 코드: github.com/cottory/algorithm/blob/master/PROGRAMMERS/PG12913.cc Algorithm/Programmers 2020. 9. 10.

• 

  [2018 카카오 기출] 추석 트래픽 programmers.co.kr/learn/courses/30/lessons/17676 Dltkddud님의 풀이(medium.com/@dltkddud4403/2018-%EC%B9%B4%EC%B9%B4%EC%98%A4-%EB%B8%94%EB%9D%BC%EC%9D%B8%EB%93%9C-%EC%BD%94%EB%94%A9%ED%85%8C%EC%8A%A4%ED%8A%B8-%EC%B6%94%EC%84%9D-%ED%8A%B8%EB%9E%98%ED%94%BD-450067ce84a8)를 참고하여 해결했습니다. 중요한 것은 아래 두 가지입니다. 1. 파싱 2. 무엇을 기준으로 골라야 최대 요청량을 알 수 있는가? 파싱은 코드를 참고하시면 될 듯 합니다. 1. 저는 시간 * 1000을 하여 Double을 Int로 취급하여 .. Algorithm/Programmers 2020. 9. 9.

• 

  [코딩테스트 연습] 게임 맵 최단거리 programmers.co.kr/learn/courses/30/lessons/1844 BFS 문제입니다. 시작점 (1,1) 부터, (N,M)까지 최단거리로 도착할 수 있는 1인 칸의 갯수를 세주면 됩니다. 코드: github.com/cottory/algorithm/blob/master/PROGRAMMERS/PG1844.cc Algorithm/Programmers 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.. Algorithm/Programmers 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(알파벳 크기)^(남은 문자.. Algorithm/Programmers 2020. 8. 12.