문제 https://school.programmers.co.kr/learn/courses/30/lessons/12913 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 풀이 단순한(?) dp(?)문제다. 위에서 아래로 내려오고, 같은 열의 값은 밞을 수 없다는 조건을 생각해서 dp 2차원 배열을 갱신해주면 된다. dp배열의 값은 "현재 칸에 올 경우 가장 큰 값" 을 정의한다. 따라서 점화식은 dp[행][열] = (land[행][열]) + dp(이전 행 중 가장 큰 값) 위처럼 구성되고, dp(이전 행 중 가장 큰 값)

문제 https://school.programmers.co.kr/learn/courses/30/lessons/154539# 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 풀이 스택을 활용하여 풀 수 있는 문제였다. 처음에는 값 그 자체를 스택에 넣고, 큰 값이 오면 갱신해줘야했나? 했는데 이럴 경우 정답배열의 어떤 위치에 값을 업데이트 해줘야할 지 애매모호했다. 관점을 조금 바꿔서 인덱스를 넣는 방식으로 구현하면 풀 수 있었다. (스택에는 배열의 인덱스를 넣고, 값을 찾을땐 numbers[idx] 이런 방식으로 접근했다.) 문제 같은 경우에는 number..

문제 https://school.programmers.co.kr/learn/courses/30/lessons/43163 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 풀이 단순한 dfs 문제이다. 방문 여부를 따지면서 모든 경우의 수를 체크해보면 된다. 단 문자열에서 문자 하나만 다를경우 해당 문자열로 바꿀 수 있기에 그 부분만 잘 체크하면 무난하게 풀 수 있다. 코드 import java.util.*; class Solution { public boolean[] visited; public int answer = Integer.MAX_VALUE; pub..

문제 https://school.programmers.co.kr/learn/courses/30/lessons/12938# 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 풀이 우선, 어떤 상황에 -1이 나올까? n이 3인데 s가 2라고 해보자. 각 원소는 1이상의 값을 가지는데, 최소 형태인 [1, 1, 1] 로 만들면 이미 s를 넘기 때문에 답을 낼 수 없다. 따라서 이때 우선 -1을 담은 배열을 return 하면 된다. 그게 아닐경우에는 어떻게 할까? 예시를 보면 n=2, s=9 => [4, 5] n=2, s=8 => [4, 4] 와 같이 나타난다. 이..

문제 https://school.programmers.co.kr/learn/courses/30/lessons/12927 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 풀이 문제를 보고서 제곱이라는 행위에 대해 생각해보았다. 단순히 3의 제곱과 4의 제곱을 살펴만 봐도 9와 16, 약7의 차이가 나는것을 알 수 있다. 따라서 작은값을 0에 가깝게 만드는 행위보다, 큰 값들부터 줄여서 평균을 낮추는 방식으로 문제를 풀이해야 한다. 남은 일 중에 가장 큰 값을 꺼내서 일을 수행하고, 다시 넣어준다. 이 과정을 일이 없거나, 퇴근할 때 까지 반복하면 된다. 최대..

문제 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이여서 시간 초과 걱정은 없다. 그리고 마..