코딩테스트

문제 https://school.programmers.co.kr/learn/courses/30/lessons/77486 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 풀이 딕셔너리를 활용하여 풀었다. 첫째로 자신을 추천해준 사람을 저장해주는 recommender 두번째로 판매원들마다 수익을 저장할 income 이다. enroll과 referral 을 활용하여 recommender 를 key는 추천받은 사람, value는 추천해준 사람으로 초기화 하고, 이 때 income도 판매원마다 0으로 초기화 해준다. 이후에 수익을 계산해준다. 우선 10프로가 1원 ..

문제 https://school.programmers.co.kr/learn/courses/30/lessons/12971 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 풀이 dp 문제이다. 1. dp 점화식 d라는 dp 배열이 있을때 d[n]은 n번째 티켓까지 고려했을 때 가장 높은 점수가 들어가 있다고 가정하자. 이후 점화식을 어떻게 세울지 고민해보면 된다. 만약 내가 n번째 티켓을 고른다고 생각해보자. 그러면 n-1번째 티켓 값은 사용하지 못할것이다. 그리고 d[n-2] 값에 현재 고른 티켓값을 합치면 될 것이다. n번째 티켓을 고르지 않는다면? d[n..

문제 https://school.programmers.co.kr/learn/courses/30/lessons/68646 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 풀이 작은 값은 '한번만' 터트릴 수 있는게 문제의 요점이다. 내가 선택한 풍선이 살아남기 위해서, 내가 가장 작은값이 아니라면 언젠가 가장 작은값을 터트려야한다. 결국 작은값을 터트리는 선택지는 가장 작은 풍선을 만났을때만 사용할 수 있는 것이다. (가장 작은 값을 가진 풍선은 무조건 살아남을 수 있다.) 만약 내가 가장 작은값 왼쪽에 존재한다고 해보자, 내 오른쪽은 가장 작은 값의 풍선이..

문제 https://school.programmers.co.kr/learn/courses/30/lessons/49993?language=python3# 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 풀이 tech라는 딕셔너리를 선언했고, 키는 스킬이고 밸류는 그 스킬을 배우기 위한 직전 스킬을 넣어주었다. 따라서 만약 A스킬이 skill에 있고, 그 스킬을 배우기 위해서 무엇을 배워야하는지 tech를 통해 알 수 있다. (1부터 넣은 이유는 첫 스킬은 선행스킬이 없기 때문에) 이후 skill_trees 를 순회한다. 한 스킬셋마다 가능한지 여부를 따져주기..

문제 https://school.programmers.co.kr/learn/courses/30/lessons/49994 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 풀이 이동한 길만 체크하는 문제이다. 이렇게 저렇게 삽질좀 해보다가, 두 지점의 좌표를 set에 넣고 검사해보면 되겠다 싶었다. (1, 0) => (1, 1) 이라면 set에 (1, 0, 1, 1)과 같이 넣는다. 단, (1, 1) => (1, 0) 도 같은 경로를 사용하기에 여기에 대한 검사를 해줘야한다. 따라서 (1, 0) => (1, 1) 을 갈때 (1, 0, 1, 1) 과 (1, 1,..

문제 https://school.programmers.co.kr/learn/courses/30/lessons/77885 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 풀이 처음에는 기준이 되는 수에서 +1, +2를 한 값과 xor를 하고, 1의 개수를 세는 방식으로 접근했다. 그러나 이 방법은 시간복잡도 면에서 통과할수가 없었다. 1의 개수를 세기위해 비트를 모두 체크해야하는데 범위가 너무 컸을뿐더러, +1 , +2 씩 하면 언제 비트가 2개 이하로 다른 숫자가 나올지도 모르기 때문이다. 한참을 고민해봤으나 이 접근방법은 틀렸다고만 생각이 들었지 뾰족한 ..

문제 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/76502 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 풀이 기본적으로 괄호의 짝이 맞는지 검사하는 문제이다. 스택의 기본문제로 나오는데 조금 추가된건 괄호의 종류가 3가지 인것과 문자열의 길이만큼 회전을 해야한다는 것이다. 문자열을 회전하기 위해서는 가장 앞의 요소를 제거한다음, 뒤에 붙여야한다. 다른 방법으로는 시작인덱스와 끝 인덱스를 갱신하는 방법도 있겠지만, 나는 전자가 편하다. 그래서 앞과 뒤에 추가 및 삭제가 O(1)인 덱을 활용하기로..

문제 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차원 배열을 먼저 예시로..