Ikjo's Technology blog

문제 설명 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 접근 방법 해당 문제는 메모제이션을 통해 출발 지점인 (0, 0) 부터 도착 지점인 (m - 1, n - 1) 까지 도달할 수 있는 경로를 구하도록 했습니다. DFS를 이용하여 도달할 수 있는 경로를 일일이 카운팅하는 법도 있겠지만 m과 n이 최대 500까지 되므로 시간 초과 이슈로 인해 적용하기엔 다소 어렵습니다. 우선 파라미터로 입력받는 지도 데이터인 cityMap과 별도로 메모제이션을 위한 sum 배열을 선언해주었습니다. 이때 배열을 다음과 같이 3차원 배열로 선언해주었는데, 이에 대해선 좀 ..

문제 설명 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 접근 방법 해당 문제는 이분 탐색을 이용하여 해결할 수 있었습니다. n명의 입국자에 대해 최대한 빨리 심사를 마치려면, 심사관 중 심사하는데 걸리는 시간이 가장 적은 사람에 가장 많은 입국자를 배정해야합니다. 이를 위해(이후 이분 탐색을 위함이기도) 우선적으로 심사 시간 배열(times)를 오름차순으로 정렬해줍니다. class Solution { int[] times; public long solution(int n, int[] times) { this.times = times; Arrays.sor..

문제 설명 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 접근 방법 해당 문제는 우선순위 큐를 활용하여 해결할 수 있었습니다. 문제 조건 분석 문제에서는 각 작업별로 최초 요청 시간과 작업 시간이 주어졌을 때, 각 작업별로 요청되는 시간부터 작업이 종료되는 시간(이하 '처리 시간' = 대기 시간 + 실행 시간)의 '최소' 평균을 요구하고있습니다. 이때 각 작업별 처리 시간 동안 작업의 상태를 다음과 같이 나타내볼 수 있겠습니다. 여기서 실행 시간은 고정되어있는 값으로, 각 작업별 처리 시간의 최소 평균을 구하기 위해서는 대기 상태를 최대한 줄이는 노력이 ..

문제 설명 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 접근 방법 처음 해당 문제에 어떤 방법으로 접근해야할지 고민이 많았습니다. 그리디 → 백트래킹 → 메모이제이션 → 숫자 규칙 처음에는 그리디 알고리즘 느낌으로 순간 이동으로 최대한 많이 이동함으로써 배터리를 이용한 이동횟수를 최소화하고 나머지 이동 칸수에 대해서만 배터리를 이용하여 1칸씩 전진하는 방법을 취할려고 했었으나, 특정 경우의 수에선 순간 이동 중에 배터리를 사용하여 한 칸 전진한 후 다시 순간 이동하는 것이 최적의 해인 경우가 존재했기 때문에 그리디 알고리즘으로 구현하기는 다소 어렵겠다는..

문제 설명 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 접근 방법 해당 문제는 재귀 함수를 이용하여 해결할 수 있었습니다. 최초 정사각형 배열 arr이 주어질 때, 각 요소가 다음과 같다고 가정해보겠습니다. 현재의 배열에서는 1의 개수는 9개, 0의 개수는 7개로 압축이 불가능합니다. 따라서 행과 열을 절반씩 나눠서 4개의 영역으로 재탐색합니다. 1번, 3번, 4번 영역은 앞선 탐색과 마찬가지로 하나의 수로 일치하지 않아 압축이 불가능하여 다시 각 영역별로 행과 열을 절반씩 나눠서 4개의 영역으로 탐색해야합니다. 반면, 2번 영역은 0이라는 수로 일치하..