chamMal

https://school.programmers.co.kr/learn/courses/30/lessons/42748 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr import java.util.*; class Solution { public int[] solution(int[] array, int[][] commands) { int[] answer = new int[commands.length]; int idx = 0; for(int[] command : commands){ int[] com = new int[command[1]-command[0] + 1]..

최소신장트리(Minimum Spanning Tree, MST)는 연결 그래프에서 모든 노드를 연결하는 트리(Tree)를 만들 때, 간선의 가중치 합이 최소가 되도록 하는 사이클이 존재하지 않는 트리를 말합니다. 이는 그래프 이론에서 매우 중요한 문제 중 하나이며, 실제로 최소신장트리 알고리즘은 다양한 분야에서 활용되고 있습니다. 대표적인 최소신장트리 알고리즘으로는 Kruskal 알고리즘과 Prim 알고리즘이 있습니다. Kruskal 알고리즘은 그리디 알고리즘(Greedy Algorithm)을 기반으로 하며, 간선의 가중치가 작은 순서대로 간선을 선택하여 트리를 만들어 나가는 방식입니다. 반면, Prim 알고리즘은 시작점에서부터 출발하여 연결된 노드들 중에서 가장 가중치가 작은 간선을 선택하여 트리를 만들..

프로그래머스 : 예산 https://school.programmers.co.kr/learn/courses/30/lessons/12982 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 풀이 접근법 : 최대한 많은 부서가 지원을 받아야 하므로, sort한 처음부터 하나씩 예산에서 빼주면서 cnt를 올린다. import java.util.Arrays; class Solution { public int solution(int[] d, int budget) { int answer = 0; Arrays.sort(d); for(int dot : d){ if(dot >..

https://school.programmers.co.kr/learn/courses/30/lessons/12930# 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 풀이 접근법 : 1) input 값이 String으로 들어와 split() 함수를 사용하여 단어의 index가 홀수,짝수에 따라 대문자, 소문자로 나누려고 했으나 단어 사이에 공백이 여러개 있을 경우 문제가 풀리지 않아 Char Array 형태로 바꿈 2) Char Array로 바꾸어 foreach 문으로 char를 하나씩 가져와 공백이면 cnt를 0으로 초기화 하고 아닐 경우에 홀수, 짝수에 ..

최단 경로 알고리즘은 두 노드 사이의 최단 경로를 찾는 알고리즘입니다. 그래프 이론에서 자주 사용됩니다. 가장 기본적인 최단 경로 알고리즘은 다익스트라 알고리즘입니다. 다익스트라 알고리즘은 음의 가중치를 가지지 않는 그래프에서 사용할 수 있으며, 시작 노드로부터 모든 다른 노드까지의 최단 경로를 찾을 수 있습니다. 이 알고리즘은 매우 효율적인 알고리즘으로 알려져 있으며, 우선순위 큐를 사용하여 구현할 수 있습니다. 그러나 음의 가중치를 가진 그래프에서는 벨만-포드 알고리즘이 사용됩니다. 이 알고리즘은 다익스트라 알고리즘과 달리 음의 가중치를 가진 그래프에서도 사용할 수 있습니다. 그러나 다익스트라 알고리즘보다 더 느린 실행 속도를 가지며, 음수 가중치 사이클이 있는 경우에는 최단 경로를 찾을 수 없습니다..

다이나믹 프로그래밍(Dynamic Programming) : 큰 문제를 작은 문제로 나누어 푸는 방법으로 계산된 결과를 기록하고 재활용하며 문제의 답을 구할 수 있는 방식. 중간에 계산된 결과를 메모리에 저장하고 재활용 가능 분할 정복과의 차이 - 분할 정복은 부분 문제가 중복되지 않고, DP는 부분 문제가 중복되어 재활용을 한다 그리디 알고리즘과의 차이 - 그리디는 순간의 최선을 구하는 방식으로 근사치를 구할 수 있지만, DP는 모든 방법을 확인 후에 최적의 해를 구한다. 다이나믹 프로그래밍이 되기 위한 조건은 3가지가 있다고 한다. 1. Simple subproblems 큰 문제를 작은 문제로 나눌 수 있어야 합니다. 2. Optimal substructure 최적의 해를 찾는 구조를 만들 수 있어야..

1. 프로그래머스 : 짝수는 싫어요 https://school.programmers.co.kr/learn/courses/30/lessons/120813 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 풀이 접근법 : n 까지의 홀수를 출력하는 것이므로 짝수일 때는 배열의 크기를 n/2, 홀수일 때는 n/2+1로 잡고 1~n까지 나머지가 1인 수를 배열에 담아 출력한다. class Solution { public int[] solution(int n) { int[] answer; if( n % 2 == 0){ answer = new int[n/2]; }els..

https://www.acmicpc.net/problem/24174 24174번: 알고리즘 수업 - 힙 정렬 2 2 5 1 4 3(heapify(A, 2, 5)) -> 2 3 1 4 5(heapify(A, 1, 5)) -> 1 3 2 4 5(A[1] A[5]) -> 5 3 2 4 1(heapify(A, 1, 4)) -> 2 3 5 4 1(A[1] A[4]) -> 4 3 5 2 1(heapify(A, 1, 3)) -> 3 4 5 2 1(A[1] A[3]) -> 5 4 3 2 1(heapify(A, www.acmicpc.net 풀이 접근법 : 위 문제는 heapify( heap 구조로 증명) 하면서 최소값을 root로 옮긴 후 가장 뒤로 보내면서 정렬하는 슈도 코드를 가지고 있다. 값이 변경될 때에 cnt를..

https://school.programmers.co.kr/learn/courses/30/lessons/42627# 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 풀이 접근법 : 2번의 PriorityQueue를 만든 다음, 하나의 PriorityQueue pqStart에는 시작 시간 순, 하나의 PriorityQueue pqJob은 작업 시간 순으로 오름차순으로 정렬해 time을 증가시키면서 이전 작업 시간을 초과한 작업들을 하나씩 pqJob에서 뽑아 작업해 계산. 나의 코드 import java.util.*; class Solution { public..

https://school.programmers.co.kr/learn/courses/30/lessons/42587 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 풀이 접근법 : 과제 조건(LinkedList를 꼭 사용해야한다는 전제 조건)이 있어, LinkedList 안에 우선 순위와 위치를 넣어 가장 앞에 있는 프린트물이 List 내에서 우선 순위가 최대일 때 List 내에서 꺼내고, 꺼낸 값이 원하는 location 일때 list 내에 꺼낸 순서를 출력한다. import java.util.*; class Solution { public int solu..