알고리즘

문제 https://school.programmers.co.kr/learn/courses/30/lessons/43162 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 풀이 나는 유니온 파인드를 활용하여 문제를 풀이하였다. 연결되어 있는 컴퓨터를 확인하고, union을 진행했다. union find알고리즘 그대로 사용하면 풀 수 있는 문젠데, 마지막에 parent의 원소값으로 판단하는게 아닌 "find_parent" 함수를 실행하여 루트값을 확인해야한다. 코드 import java.util.*; import java.util.stream.*; class S..

문제 https://school.programmers.co.kr/learn/courses/30/lessons/42628 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 풀이 대놓고 문제에 우선순위큐가 적혀있는만큼, 우선순위큐를 이용하여 풀 수 있다. 해당 문제는 최댓값이나 최솟값을 효율적으로 구해야한다. 따라서 우선순위큐를 사용하되, 최대힙과 최소힙 두개를 선언한다. 우선 값을 넣을땐 두 큐에 모두 넣어준다. 이후에 D -1 가 나오면 최소힙에서 값을 빼주면 되고, D 1이 나오면 최대힙에서 빼주면 된다. 여기서 발생하는 문제는, 최소힙에서 뺀 값을 최대힙..

문제 https://school.programmers.co.kr/learn/courses/30/lessons/87946 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 풀이 문제에서 주어지는 dungeons 의 최대 크기가 8인 것을 보고 완탐을 해도 되겠구나 라고 판단할 수 있었다. 해당 문제는 순열을 만들어서, 그 순서대로 방문을 해보고 가장 큰 값이 무엇인지 판단해주면 된다. dungeons의 크기가 3일 경우 순열을 구하면 0 1 2 0 2 1 1 0 2 1 2 0 2 0 1 2 1 0 과 같이 6개 값이 나오는데, 모두 시도해보면서 가장 많이 방문..

문제 https://school.programmers.co.kr/learn/courses/30/lessons/42587 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 풀이 location이라는 값을 간편히 처리하기 위해서는 실제로 큐처럼 데이터를 넣고 빼고하면 힘들것이라 생각했다. 따라서 priorities라는 배열은 가만히 두고, 배열을 순회하는 식으로 생각했다. 어차피 큐는 한 방향으로 추가 되니 이렇게 순회해도 큰 문제는 없었다. 배열을 넘어가면 다시 0으로 돌아가는 방식으로 말이다. 다음은 우선순위를 어떻게 계산하는가 였다. 나는 현재 배열에서 다..

문제 https://school.programmers.co.kr/learn/courses/30/lessons/42747 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 풀이 문제를 해석해보면, 배열내의 n이상의 값이 n개 있을때, 그 중 가장 최대 n을 구하라는 말이다. 따라서 d[n]이라는 배열을 하나 선언해서 d[n] => n개 이상의 숫자 개수로 정의했다. 이후에 citations에서 값을 하나씩 가져와서, 그 값이하의 d를 모두 채워줬다. citations은 최대 1,000이고, 논문 인용 횟수는 10,000이여서 시간 초과 걱정은 없다. 그리고 마..

문제 https://school.programmers.co.kr/learn/courses/30/lessons/131127# 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 풀이 map 자료구조를 활용하여 쉽게 풀 수 있었다. 우선 내가 원하는 값들을 [제품, 개수] 형식으로 초기화 해준다. 다음에는 할인 현황을 담을 map 을 계속 갱신해준다. 하루가 지남에 따라 가장 앞의 값을 제거해주고, 새로운 제품을 추가해준다. 그리고 할인중인 목록에 내 제품이 있으면서, 개수도 다 만족한다면 정답에 값을 추가해주면 된다. (단, 할인 현황 map에 개수가 10개가 ..

문제 https://school.programmers.co.kr/learn/courses/30/lessons/131701 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 풀이 이 문제의 핵심은, 수열합을 구할때 이미 구한 부분을 어떻게 다시 계산하지 않고 구할 수 있느냐이다. (만약 수열때마다 모든 합을 구하면 1000 (원소의 개수) * 1000 (수열의 최대 길이) * 1000 (수열합 구하기) 의 시간 복잡도가 나오게 될 것이다..) [1, 2, 3, 4] 배열이 있을때 수열 2인 값을 구할때 [1, 2] 의 합을 구하게 될 것이다. 그리고 수열3인 ..

문제 https://school.programmers.co.kr/learn/courses/30/lessons/12914 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 풀이 dp로 풀이했다. 1칸 또는 2칸만 움직일 수 있다는걸 반대로 생각하면 -> 내가 있는 현재 위치 - 1 에서 오는 방법, 내가 있는 현재 위치 -2 에서 오는 방법 두가지가 있다. 따라서 점화식은 d[i] = d[i-1] + d[i-2] 로 정의할 수 있다. 그리고 값 오버 플로우를 대비해서 dp 배열에 저장할때부터 % 연산하는걸 주의해야 한다. 마지막에 return할때 처리할려면 이..

문제 https://school.programmers.co.kr/learn/courses/30/lessons/12953 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 풀이 나무위키로 최소 공배수의 특징을 확인하였다. 세개 이상의 수의 최소 공배수를 구하기 위해서는, 두 수의 최소공배수와 새로운 수의 최소 공배수를 구하면 된다. 두 수의 최소 공배수 같은 경우에는 최대 공약수(gcd)를 통해서 구할 수 있는데, 최대공약수는 유명한 "유클리드 호제법" 으로 구할 수 있다. 따라서, 두 수의 최대 공약수를 구한 후에 이 값을 활용하여 최대 공배수를 구하는 과정..

문제 https://school.programmers.co.kr/learn/courses/30/lessons/42885 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 풀이 대놓고 그리디라고 적혀있어서 그리디 방식으로 접근했다. "인원은 최대 2명" "무게는 limit 초과 되면 안됨" 두가지의 조건을 가지고 풀어야 한다. 그리디 방식으로 보트를 최소한으로 띄울려면 한 보트안에 몸무게가 많이 나가는 사람1명 + 몸무게가 적게 나가는 사람1명 방식으로 태워야 한다. 따라서 우선 몸무게가 큰 순으로 정렬을 했다. 다음에는 포인터를 두개 두었다. 하나는 무거운 ..