문제 https://school.programmers.co.kr/learn/courses/30/lessons/12980 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 풀이 문제를 처음봤을땐 DP인가 싶었다, 그러나 10억개의 배열을 선언하면 메모리가 터져버린다. 또 다르게는 1칸을 가거나 2배를 가거나 하는 완전탐색을 생각했는데 이건 시간초과를 벗어날 수 없었다. 곰곰히 생각해보다가 n에서부터 0을 찾아가면 쉽겠다고 생각이 들었다. 무조건 2배를 해주는게 좋으니 나눌수 있을땐 나누고, 그게 아니라면 -1을 해주고 카운트를 1늘려주면 된다. 이 과정을 n이..

문제 https://school.programmers.co.kr/learn/courses/30/lessons/12979# 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 풀이 이 문제의 핵심은 레이더가 닿지 않는 범위를 알아낸 다음, 레이더를 적절하게 설치하는 것이다. 위 케이스를 보면 레이더가 닿지 않는곳은 1~2 , 6 ~ 9 이다. 어떻게 구할 수 있을까? stations 배열에는 [4, 11]이 존재하고, w는 1이다. 6 ~ 9 부분을 생각해보자. 6을 생각해보면 4에서 w만큼 더하고, + 1을 더한 값이고, 9는 11에서 w만큼 빼고 - 1을 뺀..

문제 https://school.programmers.co.kr/learn/courses/30/lessons/92344 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 풀이 정확성만 본다면 단순히 브루트포스로 풀 수 있는 문제이나, 시간을 따졌을때 그렇게 풀 수 없는 문제이다. 이 문제의 핵심은 '누적합' 인데, 나도 전혀 감을 못잡아서 풀이를 보고 알게 되었다. 개인적으로는 이런 문제를 접해보지 않고, 관련 테크닉을 모른다면 못푸는 문제가 아닐까 생각했다. (구현보다는 스킬, 테크닉 의존적인 문제 아닐까..) 이 누적합 테크닉은 1차원 배열을 먼저 예시로..

문제 https://school.programmers.co.kr/learn/courses/30/lessons/72413 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 풀이 플로이드 알고리즘을 사용하면 금방 풀 수 있는 문제였다. 우선 fares를 활용하여 배열을 세팅하고, 플로이드 알고리즘을 수행한다. 그러면 노드간의 최단 경로를 얻을 수 있다. 이후 중요 포인트는 "택시를 어디까지 같이 타고 갈 것인가" 이다. 예시를 보면 5까지 같이 타고 간 다음에 각자 택시를 타고 이동한다. 이게 단순히 s에서 a로 가는거 + s에서 b로 가는 방식보다 훨씬 싸게 ..

문제 https://school.programmers.co.kr/learn/courses/30/lessons/67259 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 풀이 dfs 에 dp 테크닉을 조금 섞은 문제였다. 우선 경로에 따른 값 처리를 생각했다. 직선도로 같은 경우에는 방문한 칸 - 1 개였다. 만약 7칸을 방문한다면 코너와 상관없이 직선코너는 6개가 있다. 코너같은 경우에는 이전에 내가 어느 방향에서 왔는지를 기억하고, 그에 따라서 코너인지 아닌지 판단하기로 했다. 만약 왼쪽에서 오른쪽으로 왔는데 내가 갈려는 방향이 오른쪽이면 같은 방향이므로..