알고리즘,PS/프로그래머스

문제 https://programmers.co.kr/learn/courses/30/lessons/87946 코딩테스트 연습 - 12주차 XX게임에는 피로도 시스템(0 이상의 정수로 표현합니다)이 있으며, 일정 피로도를 사용해서 던전을 탐험할 수 있습니다. 이때, 각 던전마다 탐험을 시작하기 위해 필요한 "최소 필요 피로도"와 던 programmers.co.kr 풀이 입장 피로도와 소모피로도 두 가지가 있는데 만약 입장컷이 큰 순서대로 간다면 .. ? => 예제에서 3번째 던전을 못 돌기때문에 fail 그렇다고 작은 순서대로 간다면 .. ? => 입장컷이 큰 것이 나중에 나오면 못 돌기때문에 fail 결론 => 완전탐색 던전의 방문여부를 visit , 던전을 통과한 시점으로 남은 피로도를 tired , 던..

https://programmers.co.kr/learn/courses/30/lessons/42839 코딩테스트 연습 - 소수 찾기 한자리 숫자가 적힌 종이 조각이 흩어져있습니다. 흩어진 종이 조각을 붙여 소수를 몇 개 만들 수 있는지 알아내려 합니다. 각 종이 조각에 적힌 숫자가 적힌 문자열 numbers가 주어졌을 때, 종이 programmers.co.kr 문제 풀이 완전탐색 + 백트래킹 문제이다 주어진 numbers 로 모든 순열을 만들어서 소수인지아닌지 판별하여 카운트를 리턴하면된다. String -> int 형으로 바꿀 때 , "01234" 이런것도 1234 로 변환할 수 있는 메서드가 Integer 라이브러리에 있다. Integer.valueOf 라는 메서드로 변환을 한 다음, 중복을 허용하지..

문제 https://programmers.co.kr/learn/courses/30/lessons/87694 코딩테스트 연습 - 11주차 [[1,1,7,4],[3,2,5,5],[4,3,6,9],[2,6,8,8]] 1 3 7 8 17 [[1,1,8,4],[2,2,4,9],[3,6,9,8],[6,3,7,7]] 9 7 6 1 11 [[2,2,5,5],[1,3,6,4],[3,1,4,6]] 1 4 6 3 10 programmers.co.kr 풀이 좌표평면 위에 여러 사각형이 겹쳐지는데 , 이들을 겉 돌면서 최종목표까지 탐색하는 방법이다. 사각형이 그려지는 면적을 allowed로 체크해주고 겉 둘레만 돌기위해 visit 배열로 사각형 내부만 true 로 준다. (외부는 false 그대로 놔둠) 여기서 중요한데 , 만..

https://www.acmicpc.net/problem/9466 9466번: 텀 프로젝트 이번 가을학기에 '문제 해결' 강의를 신청한 학생들은 텀 프로젝트를 수행해야 한다. 프로젝트 팀원 수에는 제한이 없다. 심지어 모든 학생들이 동일한 팀의 팀원인 경우와 같이 한 팀만 있을 www.acmicpc.net 문제 풀이 총 2가지 풀이 방법으로 접근할 수 있다. 1. SCC 로 강한 결합요소를 전부 찾아서 (요소가2이상 혹은 셀프 사이클인 부분) 전체N에서 빼는방법 2. dfs 사이클 탐지 방법 1. SCC 풀이 방법 SCC는 scc집합들을 담은 ArrayList라고 할때 , SCC를 반복문으로 돌려서 scc의 크기가 2이상이거나 , 1이지만 셀프참조를 할 경우에 전체 N에서 그 만큼 갯수를빼주면 팀에 속하..

풀이 스케쥴링 방법 중 하나인 SJF 방식이다. 1. 처리해야 할 작업 중 현재 기준으로 처리할 수 있는 작업을 선택 2. 선택한 작업을 가장 시간이 덜 걸리는 순으로 처리 1. 입력받은 jobs를 가장 먼저 도착하는 순서로 정렬을 수행한다. 2. 정렬된 jobs배열 중 처리 가능 한 Task를 우선순위 큐에 전부 삽입 3. 만약 큐가 비어있다면 => 현재까지 경과된 시간을 jobs배열의 다음 대상의 도착시간까지 당겨오고 , 2번으로 4. 큐에서 하나씩 빼면서 처리하면서 시간들 계산 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 import j..

문제 https://programmers.co.kr/learn/courses/30/lessons/86971 코딩테스트 연습 - 9주차 9 [[1,3],[2,3],[3,4],[4,5],[4,6],[4,7],[7,8],[7,9]] 3 7 [[1,2],[2,7],[3,7],[3,4],[4,5],[6,7]] 1 programmers.co.kr 풀이 다음과 같은 예시인 경우 , 6:3 으로 나누면 차이가 최소가 된다. 즉 , 차이가 최소이기 위해선 한쪽편에 해당되는 노드의 자식수를 a 라고하고 전체 노드의 수n-a 를 다른 한쪽편의 노드들이라고 했을때 구해야 하는 최소값을 min 이라고 하자. min(n-2a , min) 이 답이다. 1. 1번 노드를 root 로 기준을 잡고 시작하여 2. 해당 노드의 자식수를 ..

문제 풀이 전형적인 크루스칼 알고리즘 풀이다. 1. Edge의 weight크기가 작은 순으로 정렬 2. Edge를 집합에 포함 시키기위해 find(x) 함수를 호출해서 parent가 같은지 확인 3. Parent가 같지 않은 Edge 한에서 Union을 호출하여 집합에 포함시킨 후 가중치 합을 반환 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 import java.util.*; import java.io.*; class Solution{ static int[] parent; static ArrayLi..