문제 https://school.programmers.co.kr/learn/courses/30/lessons/77886 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 풀이 해당 문제는 "110" 을 찾아서, 어떻게 옮길지가 관건인 문제다. 우선 "사전순으로 앞서는" 숫자의 개념을 생각해보자. 10과 01이 있을경우 사전순으로 앞서는 숫자는 01이다. 10은 10진수로 2이고, 01은 1이다. 이 말은 2진수로 나타낸 숫자를 10진수로 바꾸었을때, 작은 숫자가 사전순으로 앞선다는 뜻이다. 동시에 2진수는 왼쪽일수록 가중치가 높아지기 때문에 작은 숫자를 만들..

문제 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/60058 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 풀이 사실 이 문제는 하라는대로 구현만 하면 슉슉 풀리는 문제이다. 단 지문이.. 이해하기 조금 난해하다는게 문제다. 슈도 코드를 작성하면 조금 더 쉽지 않을까 생각한다. 1. 입력이 빈 문자열인 경우, 빈 문자열을 반환합니다. 2. 문자열 w를 두 "균형잡힌 괄호 문자열" u, v로 분리합니다. 단, u는 "균형잡힌 괄호 문자열"로 더 이상 분리할 수 없어야 하며, v는 빈 문자열이 될 수..

문제 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/87390?language=python3 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 풀이 만약 n*n배열을 모두 만들어서 값을 추출하려하면 메모리 초과 + 시간초과가 걸릴것이다. (n은 최대 1000만인데, n*n은 답도 없다.) 따라서 문제의 핵심은 left부터 right 값만 구하는 것이다. right - left는 최대 10만으로 명시되어 있기에 시간이나 메모리에 걸릴일이 없다. 2차원적으로 생각해서 시작하는 행과, 끝나는 행을 구할필요가..

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