본문 바로가기

알고리즘 공부 및 문제 풀이

 (317)
[pro] 프로그래머스 level2 148653 마법의 엘리베이터 (Java) - 시뮬레이션 [문제] https://school.programmers.co.kr/learn/courses/30/lessons/148653 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr [풀이] 각 자릿수마다 엘리베이터를 올리는게 최소인지, 내리는게 최소인지 판단해야 한다. 먼저 6, 7, 8, 9일 때 엘리베이터를 올린다면 각각 4, 3, 2, 1 만큼 올리고 내릴 때보다 1만큼 더 소요되므로 5, 4, 3, 2 만큼이 들 것이다. 이는 엘리베이터를 내리는 경우 6, 7, 8, 9 가 걸리는 것보다 작다. 단순히 생각해보아도 엘리베이터를 무조건 올려야 최소가 될 것이..
[pro] 프로그래머스 level2 152996 시소 짝꿍 (Java) - 구현 [문제] https://school.programmers.co.kr/learn/courses/30/lessons/152996 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr [풀이] 오름차순 정렬을 했기 때문에 무게가 같은 경우와 (*4,*3), (*3, *2), (*4, *2) 경우에 대해서만 체크해준다. 또한 같은 무게인 경우 앞서 구한 count에서 1을 뺀 값을 그대로 활용할 수 있다. 시간초과가 나지 않기 위해서 필수적인 부분! [코드] import java.util.*; class Solution { public long solution(int[..
[pro] 프로그래머스 level2 154538 숫자 변환하기 (Java) - DP [문제] https://school.programmers.co.kr/learn/courses/30/lessons/154538 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr [풀이] dfs&bfs 풀이로 먼저 생각이 되었는데 dfs 로 풀었다가 시간초과가 났다. 그래서 완전탐색말고 더 효율적인 코드를 찾아서 dp로 풀이하게 되었다. (bfs 로 푼 정답 코드는 찾아보니 많다..) dp 풀이도 단순하게 3가지 경우만 고려해주면 된다. dp[i] = x를 i로 변환하기 위해 필요한 최소 연산 수를 저장한다. 따라서 dp[x] = 0으로 두고 시작한다. 1. d..
[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..

티스토리툴바