전체 글

문제 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가 되는 경우를 찾아 그 깊이를 구하면 된다. 이때 포인트는 불필요한 탐색을 하지 않도록 하는 것이다. 불필요한 탐..

문제 https://school.programmers.co.kr/learn/courses/30/lessons/42883 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 리뷰 그리디(탐욕법) 문제이다. 풀이 주어진 수의 일정 범위에서 가장 큰 수를 각 자리의 값으로 만들면 된다. 이때 그 범위를 지정하는 것이 관건이다. 현재 자리에 들어갈 수를 구하는 범위를 정하기 위해서는 다음과 같은 조건을 고려해야 한다. 범위의 시작 인덱스(start)는 이전 자리에 들어간 수의 바로 다음 자리이다. 범위의 마지막 인덱스(end)의 뒤에는 아직 값이 정해지지 않은 자리의..

문제 https://school.programmers.co.kr/learn/courses/30/lessons/155651 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 배열 book_time에 저장된 각 예약 건의 입실 시간과 퇴실 시간을 바탕으로 최소 몇 개의 객실이 필요한지 구하는 문제이다. 퇴실 시간 이후 청소 시간 10분 동안은 다른 예약자가 같은 방을 사용할 수 없다는 점을 고려해야 한다. 리뷰 풀이 먼저 편하게 시간을 계산하기 위해 입실 시간과 퇴실 시간을 필드로 갖는 클래스 BookTime을 만들었다. 그리고 book_time의 각 원소들을 ..