chamMal

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으로 초기화 하고 아닐 경우에 홀수, 짝수에 ..

https://school.programmers.co.kr/learn/courses/30/lessons/82612 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 풀이 접근법 예시) price = 3 , money = 20 , count = 4 일 때 result = 10이다 이용금액이 3인 놀이기구를 4번 타고 싶은 고객이 현재 가진 금액이 20이라면, 총 필요한 놀이기구의 이용 금액은 30 (= 3+6+9+12) 이 되어 10만큼 부족하므로 10을 return 합니다. N배수로 값이 증가하므로 3 * (1 + 2 + 3 + 4) 이므로 1~n의 값에 대..

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

다이나믹 프로그래밍(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..

Heap 자료구조는 완전이진트리 구조로 최고 depth-1까지의 이진트리가 꽉 채워진 이진트리형태이다. Min heap과 Max heap으로 구현할 수 있으며, 중복값을 허용하고, 반 정렬상태(형제 node끼리는 정렬 순서를 보장하지 않음)이다. 최소값/최대값을 빠르게 찾아내는 유용한 자료구조이다. 데이터 삽입 1. 트리의 가장 끝 위치에 데이터를 삽입 2. 부모 노드의 키와 비교한 후 부모 자리와 교체(반복) 데이터 삭제 1. root 노드를 반환 및 삭제 2. 가장 마지막 위치의 node를 root로 변경 3. 자식 노드 중 비교하여 부모 노드와 자리 교체(반복) Java 내에서 minheap와 maxheap의 구현은 PriorityQueue : java.util.PriorityQueue 로 쉽게 할..

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..

https://www.acmicpc.net/problem/1158 1158번: 요세푸스 문제 첫째 줄에 N과 K가 빈 칸을 사이에 두고 순서대로 주어진다. (1 ≤ K ≤ N ≤ 5,000) www.acmicpc.net 풀이 접근법: LinkedList()에 1~N만큼 넣고, list size가 0이 될 떄까지 인덱스 값을 특정하여 값을 지우면서 출력함 인덱스 계산하는게 마음대로 되지 않아, 생각보다 오래 걸림.. import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.*; public class Main { public static void main(String[..