Problem Solving

문제 https://school.programmers.co.kr/learn/courses/30/lessons/142085 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 리뷰 그동안 여러 코딩 테스트에 많이 나왔을 법한 문제였다. 이번 기회로 확실히 풀이를 기억해 두어야겠다. 풀이 아이디어가 떠오르지 않아서 일단 재귀를 통한 완전탐색을 해봤다. 문제의 제한사항이 아래와 같으니 당연하게도 시간 초과가 발생했다. 1 ≤ n ≤ 1,000,000,000 1 ≤ k ≤ 500,000 1 ≤ enemy의 길이 ≤ 1,000,000 1 ≤ enemy[i] ≤ 1,00..

문제 https://school.programmers.co.kr/learn/courses/30/lessons/152996 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 리뷰 정확성을 맞히기는 어렵지 않고, 효율성을 더 고려해야 하는 문제이다. 2023 카카오 겨울 인턴십 3번 문제였던 주사위 고르기를 풀 때 효율성을 개선했던 방법으로 해결했다. 풀이 포인트는 몸무게가 중복인 사람들이 있기 때문에 같은 값에 대해 중복으로 계산하지 않도록 해서 연산 횟수를 줄이는 것이다. 주어진 weights를 순회해서 몸무게 각 값에 해당하는 사람이 몇 명인지 counts..

문제 https://school.programmers.co.kr/learn/courses/30/lessons/43105 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 리뷰 DP(동적계획법) 문제이다. 직전 단계까지의 계산을 따로 저장해놓고 현 단계를 계산할 때 이를 사용해야 한다. 풀이 주어진 triangle과 똑같은 형태의 이차원배열 memo를 생성했다. 그리고 맨 위 숫자부터 차례로 내려왔을 때 triangle의 각 값에 도달하기까지 만들어지는 최대값을 memo에 기록한다. 이때 맨 왼쪽 값들과 맨 오른쪽 값들은 바로 위에 있는 값을 계속 누적해서 합..

문제 https://school.programmers.co.kr/learn/courses/30/lessons/154538 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 리뷰 프로그래머스 알고리즘 고득점 Kit에서 DFS/BFS 문제로 분류되는 타겟넘버와 비슷하다고 생각해서 아이디어를 얻었다. 풀이 문제에 따라 x에서 n을 더한 경우, 2를 곱한 경우, 3을 곱한 경우를 모두 찾으면 위와 같은 그래프를 그릴 수 있을 것이다. 이를 탐색하면서 y가 되는 경우를 찾아 그 깊이를 구하면 된다. 이때 포인트는 불필요한 탐색을 하지 않도록 하는 것이다. 불필요한 탐..