공부의 발자취를 남기는 블로그

문제분석: 특수조건을 유의하여 최소거리의 갯수 찾기 왜 이 문제는 최소거리의 갯수인가? 자동차는 오른쪽 또는 아래로만 갈수있기때문 위 또는 왼쪽으로 돌아가는 행위는 있을수 없기에, 길이 막히지만 않고 도달한다면 무조건 최소거리다. 특수조건: 0 : 자유로운 통행가능 1: 통행 금지 2: 커브 금지 0과 1인 경우는 간단하지만 2인 경우때문에 로직이 더 복잡해진다. 커브를 금지한다는뜻은, 이전에 온 방향이 왼쪽에서, 또는 위에서 온것인지 판별을 해야하기때문이다. 그래서 거리 방향 판별을 어떻게 할까?? 3차원 배열을 사용한다. 즉, dp[방향][X좌표][Y좌표] = dp[2][N][N] 거리가 0일땐, 모든 방향을 통과하니 (현재 세로방향DP+ 현재 가로방향DP)을 다음 지역에 더해준다. 거리가 1일땐, ..

문제 분석: 목표 : 모든 강철 부대원이 복귀하는 최단 복귀시간 roads는 지나갈수있는 길 sources는 강철부대원이 현재 있는 지역 destination은 복귀해야하는 지점 문제를 읽어보니 그래프 문제다. 그래프 문제도 수많은 푸는 기법이 있다. (최소 신장트리, 다익스트라, 플로이드 와샬..등등) 근데 이 문제는 다익스트라로 푸는게 바람직하다. 그 이유는 도착지가 동일하기 때문이다. "각 병사가 도착지를 향해 가는것"을 반대로 생각하여, "도착지에서 병사가 있는곳으로 간다"로 생각할수가 있기 때문입니다. 다익스트라는 그래프+DP 이기때문에, 써야하는 자료구조가 좀 많다. 문제 풀이: 먼저, 그래프를 표현 해줘야한다. 그래프를 표현해주는 방법은 다양하게 있지만, 필자는 Map으로 표현하였다. Key..

문제분석 연속 행렬의 연산수를 최소화 시키는 문제다. 계산을 할 수 없는 행렬은 입력으로 주어지지 않는게 특징이다. 즉, 연속된 행렬의 인접한 숫자는 무조건 같다. 1. 첫번째 접근 연속된 두 행렬을 merge , 계산하면 인접한 숫자는 사라진다. 즉, 인접한 숫자를 "먼저" 없애면 연산을 최적화 할수 있다고 생각했다. 즉, [5,3],[3,10],[10,6] 이면 인접한 숫자 10을 먼저 소거시키면 적은 연산을 이룰수 있을줄알았다. 1. 인접한 숫자와 위치를 먼저 뽑는다. 2. 인접한 숫자가 제일큰 순서대로 정리한뒤, 그 위치에있는 2개의 행렬을 merge한뒤에 삽입한다. 이 과정을 행렬이 한 개 남을때 까지 반복한다. => 틀림 이유는, 추측이 잘 안되지만.. 인접한 숫자가 가장 큰 순서대로 뽑아 연..

https://school.programmers.co.kr/learn/courses/30/lessons/72414 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 문제분석 시청자의 동영상 로그를 토대로, 최적의 광고타이밍을 선정해야한다. 동영상 상영시간은 최대 99:59:59 초, 광고의시간은 동영상시간보단 적다. 필자가 처음 접근한 전략 => 이분탐색 으로 최적의 광고타이밍을 구한다 => X 시청자의 동영상로그가 한쪽에 몰려있을수가 있다. 이런경우 이분탐색으로 탐지를못한다. 차선택: => 결국 시청자 동영상로그를 효율적으로 탐색해야한다. => 누적합 개념..

문제분석 수열이 주어지고, 이 수열에다 -1 , 1 이 반복한 수열을 곱하거나 1, -1을 반복한 수열을 곱한다. 그렇게 나온 수열중에 부분수열이 젤 높은값을 반환하는 문제다. DP , 부분합의 개념이없으면 풀기 힘든문제다. 윗개념을 사용하지않고 푼다면, 모든 부분수열을 구해야하는데, 비효율적이다. 첫 시작을 -1로 곱한것과 , 그대로 시작하는 결과는 매우 달라져서 둘의 경우를 분리하여 보셔야합니다. dp를 2개를 생성해야 한다는 말이죠. dp 작성 dp 기준을 잡는게 제일 중요한데, dp[n] = n까지 탐색한 모든 부분수열중 최댓값으로 잡습니다. 예시 {2,3,-6,1} dp[0] 를 음수로 시작을 해보자면, dp[0] = -2 입니다. dp[1]은 여기서 2가지 선택지가 있습니다. 0번째 숫자를 그..

문제분석 문제 이해는 매우쉽다. 요점은 한 지점을 골랏으면 양옆 지점을 못고른다. 이 규칙을 유지하면서 최대로 얻을수있는 스코어를 반환하면된다. 놀라운건 이 스티커문제와 도둑질문제 로직이 100%같다. (중복문제..) 이해는 쉽게했는데 막상 짜려고하면 참 막막할것이다. DP를 짜는건 늘 새롭고 어렵다.. 하나씩 생각해보자.. 1.첫번째를 고르면 마지막과 두번째를 못고른다. 2.두번째를 고르면 첫번째 와 세번째를 못고른다. 이 2가지 경우가 명백하게 다른 결과를 나타내는걸 푸는 사람 모두가 동의할것이다. 1번루트를 한번 타보자. 예시 {14,6,5,11} 첫번째를 고르면 첫번째는 14이다. 두번째를 고르는건 불가능하다. -> 현재 까지 최고값인 14로 저장해두자. 세번째를 고를수도 있고 안고를수도있다. -..

문제분석 timetable로 주어진 시간을 전부다 숫자로 변환한다. 그 후, 한번 대기열순대로 정렬한다. 버스는 n 개 손님은 m명 배차간격은 t분이다. 9시부터 시작하여 버스 도착시간까지 대기열이 있다면 입장을시켜 출발시킨다. 여기서 문제는 어떻게든 늦게출근하고싶은 주인공을 반환해줘야한다. 어떻게든 늦게출근하고싶으니, 막차시간을 유의하며 보면된다. 막차+ 자리가 남을땐, 막차시간에 탑승을하면된다. 막차 + 자리가 없을땐, 대기열을 유리하게 가져가야하므로, 버스에 마지막에타는사람보다 1분일찍오면된다. 문제풀이 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..

문제분석 문제설명이 상당히 긴 문제 근데 비교적 간단하다. 요점은, 스킬들이 Type으로 공격과 치유를 구분하고, 범위와 강도가 주어진다. 공격과 치유를 적용한뒤, 파괴되지않는 건물을 리턴하면된다. 이게끝? 맞다 이게끝이다. First Try: 2차반복문 사용 누구나 생각할 풀이방법이다. 스킬을 순회하며, 각 스킬마다 적용되는 범위에다 강도를 빼주거나 더한다. 그후, 마지막에 파괴된건물이 있는지 한번확인한다. 이렇게 하면 정확성은 100%다. 실제 카카오 테스트때도 50%응시자가 이와같은 코드를 짯다. 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 class Sol..

문제분석: 일단 문제부터 이해하는게 난관이다. 규칙: 1. 어떤 수가 있다면, 그걸 이진수로 바꾼다. 2. 표현된 이진수로 포화이진트리를 만든다. {1 이면 있는노드 , 0이면 비어있는노드} 3. 만약 2번으로 포화이진트리가 안된다면, 0을반환, 된다면 1을반환한다. 단기간에 풀기에 조금 벅찬 느낌의 문제다. 일단 먼저 1번 과정을한다. 이진수로 바꾸는 과정이 필요하다. 흔한 이진수 로직이다. 하지만, 우리는 포화이진트리를 만들어야하기 때문에 포화이진트리의 갯수만큼 이진수를 늘려줘야한다. {비어있는부분을 0으로} 문제에서 요구하는건 포화이진트리를 만들어서 되는지를 묻기때문이다. 2번스텝으로 넘어간다. 표현된 이진수를 포화이진트리가 가능하게 만든다. 포화 이진트리는 2^n -1 갯수이니 그만큼 더 늘려준다..

문제분석 목표: 완호의 인센티브 순위를 구하라 규칙 1. 누군가의 근무태도와 동료평가가 다른사람의 두 요소보다 낮으면 인센티브 제외 2. 1번의 경우가아니라면, 근무와 동료평가점수를 합산해 랭킹을 매김 첫생각 규칙 1번에 의하여 제일먼저 떠오르는 해결방법은사람 2명을골라 비교하는 방법이다. 하지만, 제한사항을 보면 인원수가 10만명이다.(와우.. 어떤 회사가 10만명의 사원을..?) 10만*10만 = 100억이라서 조합을사용하는건 안된다. {아 근데, 이 문제는 가지치기를 잘 만하면 2차반복문 써도 풀리는거같다..} 즉, 1차반복문으로 해결을해야한다. 규칙1번처럼 사람과 사람마다 두 요소가 모두낮은지 확인해야하며, 2차 반복문을 사용하지 않는 방법은 꽤나 찾기 힘들다. 방법은 근무태도순대로 정렬하는것이다..