알고리즘 공부 및 문제 풀이/프로그래머스(PRO) (81) 썸네일형 리스트형 [pro] 프로그래머스 level2 154539 뒤에 있는 큰 수 찾기 (Java) - 스택 [문제] https://school.programmers.co.kr/learn/courses/30/lessons/154539 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr [풀이] 스택을 이용해 풀 수 있다. 예시2의 [9, 1, 5, 3, 6, 2] 에 대해서 하강곡선일 때는 스택에 해당 인덱스를 넣어준다. 9, 1의 인덱스 0,1을 스택에 넣으면, 그 다음 수인 5에 대해서는 1 5 로 상승곡선을 보인다. 이는 1보다 뒤에 있는 큰 수 중 가장 가까운 수가 5라는 것이므로 하강곡선에 한해서 stack.pop() 인덱스에 대한 정답 배열을 채워준다. 다.. [pro] 프로그래머스 level2 154540 무인도 여행 (Java) - BFS [문제] https://school.programmers.co.kr/learn/courses/30/lessons/154540 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr [풀이] 단순 bfs 풀이. [코드] import java.util.*; class Solution { boolean[][] visited; int[] dr = {0, 0, -1, 1}; int[] dc = {-1, 1, 0, 0}; Queue q = new LinkedList(); int w, h; public int[] solution(String[] maps) { int[] ans.. [pro] 프로그래머스 level2 155651 호텔 대실 (Java) - 누적합 [문제] https://school.programmers.co.kr/learn/courses/30/lessons/155651 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr [풀이] 배열 누적합 문제. 입실시간과 퇴실시간을 분으로 환산한 후 배열에 기록하여 누적합을 하면 특정 시간대에 사람들이 얼마나 겹치는 지를 알 수 있다. 가장 많이 겹치는 만큼 방이 필요하므로 이를 갱신해주면 된다. 배열 누적합에 대해서는 따로 알고리즘 정리글을 쓸 생각이지만, 간단하게 정리해보면 다음과 같다. [2, 6], [4, 8] 두 배열에 대해서 공간을 채운다고 하면 for문.. [pro] 프로그래머스 level2 택배 배달과 수거하기 (Java) - 그리디 [문제] https://school.programmers.co.kr/learn/courses/30/lessons/150369 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr [풀이] 전혀 level2 같지 않은 문제...(◞‸◟；) 트럭 하나로 배달/수거를 마치고 물류창고까지 돌아올 수 있는 최소 이동거리를 구해야 한다. 이동거리가 최소가 되기 위해서는 가장 멀리 있는 집부터 배달/수거를 완료해서 다시 그 집을 가지 않도록 만들어야 한다. 가장 멀리 있는 집에서 배달/수거를 했을 때 트럭의 용량이 남았다면 돌아오면서 다른 집의 배달/수거도 할 수 있을 것이.. [pro] 프로그래머스 level3 133500 등대 (Java) - dp, dfs [문제] https://school.programmers.co.kr/learn/courses/30/lessons/133500 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr [풀이] 두 연결된 등대 중 어느 한쪽이 꼭 켜져있어야 할 때, 켜 두어야 하는 등대 개수의 최솟값을 구해야 한다. 2가지 경우를 나눠서 생각할 수 있다. 1. 부모 등대가 켜져있다면 자식 등대는 켜둘 수도 있고, 안 켜둘 수도 있다. 켜두는 등대 개수를 줄이기 위해 min 값을 취한다. 2. 부모 등대가 꺼져있다면 자식 등대는 무조건 켜야 한다. 비슷한 풀이 방식의 문제: 백준 252.. [pro] 프로그래머스 level3 131129 카운트 다운 (Java) - dp [문제] https://school.programmers.co.kr/learn/courses/30/lessons/131129 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr [풀이] dp 문제이다. 최선의 경우 던질 다트의 수와 그 때의 싱글/불을 맞춘 횟수의 합을 반환해야 한다. 두 가지 정보를 기록해 주기 위해 dp[i][0]에는 i 점을 맞출 때 던질 수 있는 최소한의 다트 수를, dp[i][1]에는 그때의 싱글/불을 맞춘 횟수를 저장해주도록 했다. 그 다음 for문 반복을 통해 1~target 점수까지, 1~20점의 다트 점수마다 불/싱글/더블/트리.. [pro] 프로그래머스 level3 12920 선입 선출 스케줄링 (Java) - 이분탐색 [문제] https://school.programmers.co.kr/learn/courses/30/lessons/12920 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr [풀이] for문 반복으로 초를 증가시켜가며 n의 개수를 감소시키거나 우선순위 큐를 이용하는 방법도 있지만 시간초과가 발생하므로 효율적으로 풀기위한 방법을 찾아야 하는 문제. 이분탐색으로 풀 수 있다. 이분탐색을 하기 위해서는 이분탐색의 기준이 되는 값을 무엇으로 정할 지가 중요하다. cores[0]=1 cores[1]=2 cores[2]=3 누적값 0H o o o 3개 1H o x x .. [pro] 프로그래머스 level3 87391 공 이동 시뮬레이션 (Java) - 시뮬레이션 [문제] https://school.programmers.co.kr/learn/courses/30/lessons/87391 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr [풀이] n, m의 범위가 둘 다 매우 크기 때문에 모든 지점에 대해 탐색을 하면 시간초과가 발생할 것이다. 따라서 효율적으로 문제를 해결할 방법을 생각해봐야 한다. 행과 열의 이동을 분리해서 생각하면 조금 더 쉽게 문제를 이해할 수 있다. n=4, m=3, (x,y) = (0,0)는 queries는 ↑ ← → ← ↑ 순서대로 이동한다고 가정해보자. 행 방향 이동인 ↑ ↑ 에 대해서만 생.. 이전 1 2 3 4 5 6 7 8 ··· 11 다음