문제 https://programmers.co.kr/learn/courses/30/lessons/43105 코딩테스트 연습 - 정수 삼각형 [[7], [3, 8], [8, 1, 0], [2, 7, 4, 4], [4, 5, 2, 6, 5]] 30 programmers.co.kr 풀이 DP를 통해 해결할 수 있었다. DP[i][j]가 i,j의 좌표가 가질 수 있는 거쳐간 숫자의 최댓값이라고 가정했을 때 이 문제는 점화식은 3개로 나뉘는데 i) 삼각형의 왼쪽 끝일 때 - dp[i][j] = dp[i - 1][j] + triangle[i][j] ii) 삼각형의 오른쪽 끝일 때 - dp[i][j] = dp[i - 1][j - 1] + triangle[i][j]; ii) 삼각형의 왼쪽 끝, 오른쪽 끝이 모두 아닐 ..
문제 https://programmers.co.kr/learn/courses/30/lessons/12980 코딩테스트 연습 - 점프와 순간 이동 OO 연구소는 한 번에 K 칸을 앞으로 점프하거나, (현재까지 온 거리) x 2 에 해당하는 위치로 순간이동을 할 수 있는 특수한 기능을 가진 아이언 슈트를 개발하여 판매하고 있습니다. 이 아이언 슈 programmers.co.kr 풀이 문제를 처음보자마자 BFS거나 DP라고 생각하고 DP로 풀었는데 전혀 아니었다. 그냥 그리디 비슷한 구현 문제였다. DP로 점화식 세워서 효율성까지 줄여가며 풀었는데 정확성은 만점이었지만 효율성이 0점이 나와서 그냥 단순 구현으로 문제를 풀어 100점을 얻을 수 있었다. 풀이과정을 보자면 예를들어 n = 2인 상태에서 순간 이동..
문제 https://programmers.co.kr/learn/courses/30/lessons/72410 코딩테스트 연습 - 신규 아이디 추천 카카오에 입사한 신입 개발자 네오는 "카카오계정개발팀"에 배치되어, 카카오 서비스에 가입하는 유저들의 아이디를 생성하는 업무를 담당하게 되었습니다. "네오"에게 주어진 첫 업무는 새로 programmers.co.kr 풀이 따로 문제를 풀기위한 알고리즘을 요구하는 문제는 아니고 문자열 + 시뮬레이션(빡구현) 문제이다. 문제의 의도대로 스텝 하나하나 잘 따라가면 크게 어렵지는 않을 것이다. 풀면서 몇가지 주의할 점은 스텝을 밟으면서 문자열의 빈번한 삭제가 일어나는데 문자열이 비었는데 문자열을 참조하려는 경우가 종종 있어서 이 부분에 대해서 항상 문자열이 비었는지 체..
문제 https://programmers.co.kr/learn/courses/30/lessons/49994 코딩테스트 연습 - 방문 길이 programmers.co.kr 풀이 빡구현 문제이다. 흔히 시뮬레이션이라고 하는데 몇 가지 예외에 대해 생각을 못 해서 힘들었다. 일단 움직일 수 있는 보드를 만들었다. 4차원 배열로 만들었는데 앞에 2칸은 현재 위치를 저장해줬고, 뒤에 두칸은 어느 위치에서 왔는지 저장해주었다. 이렇게 설계한 이유는 예를들어 현재 위치만 저장하는 2차원 배열을 통해 'U' -> 'D'로 움직여 0,0이라는 위치에 도달하여 0,0을 방문처리해버리면 나중에 다른 방향에서 0,0에 방문했을 때 따라온 길은 다른데 0,0이 이미 방문했다는 이유로 새로운 길이 아니라는 판단을 해버릴 수 있어..
