boj
BOJ_14864_줄서기
BOJ_14864_줄서기
2021.05.30시작 줄서기 문제는 Ad-hoc 으로 문제 분류가 되어있습니다. 이 알고리즘을 찾아보니, 창의력 문제 정도로 찾아볼 수 있었습니다. 규칙? 문제를 읽고 손으로 끄적이다가 대강 넣어보니 이렇게 들어가는 구나 이해를 했습니다. 아래는 그 손으로 끄적인것을 그림으로 도식화 한것입니다. 근데 막상 규칙을 찾아보려 하니 규칙이 눈에 띄진 않았지만 괄호안에서 왼쪽, 오른쪽 사이에는 대소 비교관계가 있고 왼쪽이 오른쪽보다 크기 때문에 묶어 생각해보면 학생1이 가진 숫자는 최소 2개의 숫자보다 크게 됩니다. 그렇기 때문에 +2 라는 표시를 했고 학생5의 경우에는 최소 3개의 숫자보다 작게 됩니다. 마찬가지로 -3라는 표시를 했습니다. 그렇게 보니, 초기 값 N=5라면 Array 각 인덱스에 1,2,3,4,5 가 순서대..
BOJ 5719 거의 최단 경로
BOJ 5719 거의 최단 경로
2021.05.27시작 https://lotuslee.tistory.com/137 본문을 참고하였습니다. 문제를 읽어보면 한가지 좋은 아이디어를 생각해볼 수 있었는데 구현이 쉽지 않았습니다. 아이디어는 비교적 간단합니다. 1. 다익스트라로 최단 경로를 구합니다. 2. 최단 경로들을 모두 제외 합니다. 3. 다익스트라로 다음 최단 경로를 구합니다. 그림으로 보면 다음과 같습니다. 각 순서는 그림에서 왼쪽부터 1, 2, 3으로 확인해 볼 수 있습니다. 소스코드를 우선 살펴보겠습니다. 코드 중에 preNodeCollections, ArrayList 를 선언해 두었습니다. 최소 비용을 가진 경로를 담아두기 위한 목적인데, 거리 값이 갱신 되면 왼쪽에 보이는 1번 경로가 clear 되고 2번 경로가 preNodeCollection..
다익스트라 X BOJ_4485_녹색옷입은애가 젤다지?
다익스트라 X BOJ_4485_녹색옷입은애가 젤다지?
2021.05.26시작 다익스트라 개념에 대해 정리한것을 포스팅 합니다. 다익스트라는 기본적으로 최단 경로로 많이들 알고 있지만, 최단 경로는 BFS 로도 접근할 수 있기 때문에 여기서 최소 비용 개념을 추가해주어야 합니다. 즉, 다이스트라는 최단 거리 + 최소 비용의 문제입니다. 조건 보통의 다익스트라의 문제 경우 아래 조건들을 만족합니다. 1. 방향 그래프 입니다. 2. 0 이상의 가중치 값을 가지고 있습니다 3. 사이클이 존재하지 않아야 합니다. 구현 (코드X) 다익스트라의 경우 BFS 개념에 그리디 알고리즘을 적용합니다. 덧붙이면, 최단 거리를 구하게 되지만 매 순간 가장 좋은 가중치 값을 선택하게 됩니다. 거리, 방문 여부 변수를 두어 다익스트라 알고리즘이 어떻게 동작하는지 살펴보겠습니다. 그림 처음 워크플로우는..
BOJ 17612 쇼핑몰
BOJ 17612 쇼핑몰
2021.05.25개요 이 문제는 우선순위 큐를 사용하는 문제지만, 정렬 방법에 대해 이해하고 있어야 하고 무엇보다 문제에서 주어진 요구사항을 동적으로 처리하는것보다 사전에 전처리하여 값을 모두 저장 한뒤 문제 요구사항에 맞게 풀어야 했었습니다. 처음에는 while 문으로 계속 돌면서 입력 받는대로 동적으로 값을 처리 해주었습니다. 결과적으로 꼬였습니다. 그래서, k개 즉 카운터라고 볼 수 있는 k개에 쇼핑 카트를 모두 대기하는 값을 pq에 담게 되었습니다. 그림 그림을 보게 되면 어쨋든, 상품들이 1초에 하나씩 계산이 될텐데 더 적은 상품에 대해서 카운터에 배정되게 됩니다. 상품의 개수가 같다면 카운트가 더 적은 애한테 우선 할당하게 되는데 그게 인입하는 과정에서 수행하게 됩니다. 반대로, 나갈때도 마찬가지로 기본적인 ..
BOJ_1781_컵라면
BOJ_1781_컵라면
2021.05.23시작하면서 해당 문제는 pq 외에도 그리디한 방법으로 해결해 볼 수 있는데, 포스팅에서는 pq로 푸는 방법에 대해 고민해봤습니다. 여러 알고리즘 로직을 세워서 문제를 접근했는데, 9%에서 "틀렸습니다." 가 나와서 참으로 힘들게 했던 문제입니다. 문제 접근 시 데드라인과 컵라면 수를 잘 고려해봐야 하는데 데드라인은 우선순위를 높게, 같다면 컵라면 수는 더 큰것을 정해서 큐에 담아주어야 합니다. 처음 생각한 점 우선순위 큐를 지정했을 때 정렬 순서를 1. 데드라인은 우선순위를 높게 2. 컵라면 수는 더 큰것을 지정 3. 우선순위 큐에 Max-heap 구성 (데드라인 기준으로 push 할 경우 더 높은 숫자의 데드라인이 pop되는 것을 고려) ex) pq에 {1,7} 이 있다고 고려 하면, 새롭게 {2,6}..
BOJ 1619, 최소비용구하기
BOJ 1619, 최소비용구하기
2020.11.08문제유형 다익스트라 문제풀이 다익스트라 기본 문제, 원리를 이해하고 풀면 좋습니다. 이차원 a 배열을 생성, a값을 모두 inf(1000000000) 로 초기화 x,y,z 값을 입력으로 받는다. 그리고 a[x][y] 가 z보다 큰경우 값을 업데이트 한다. (작은값을 찾아야 하므로) start, end를 입력으로 받는다. d를 배열로 생성한다. n+1 만큼 /마찬가지로 방문여부를 확인할 수 있는 c를 n+1만큼 선언 및 초기화 n만큼 d에 inf 를 업데이트, n만큼 c를 false 로 업데이트 d[start] = 0 으로 초기화 시작지점, d의 역할은 비용 이라고 보면됀다. 반복문을 n-1 만큼 순회한다. 노드의 최솟지점을 찾아야 하므로 min과 x를 선언합니다. (min은 최댓값으로 x는 -1), x는..
숨바꼭질4
숨바꼭질4
2020.11.07문제유형 BFS, 단순구현 문제풀이 모듈 2가지 1. BFS -. x+1, x-1, x*2 방문체크 -. 방문하지 않았다면 큐에 대입 -. 역추적을 위해 from[now] = next 형태로 저장, 재귀함수를 통해 마지막에 추적하기 위함 e.g) 1->2->3->4 면 from[4] = 3, from[3] = 2, from[2] =1 이런식 2. 역추적 -. 재귀함수로 역추적 코드 package backjun; import java.io.*; import java.util.*; public class BOJ_13913_숨바꼭질4 { static void print(int n, int m, int[] from) { if(n!=m) { print(n, from[m], from); } System.out.pr..
특정거리의 도시찾기
특정거리의 도시찾기
2020.11.07이 문제는 최단거리를 찾아내는 과정을 BFS알고리즘을 통해 해결할 수 있습니다. 알고리즘 개략적인 부분은 아래와 같습니다. pq에 시작위치와 depth를 저장 ans를 위한 pq선언 BFS depth가 우리가 찾는 depth라면 ans 에 node번호를 넣기(2의 pq에서 첫번째 요소) 그리고 continue 그게 아니라면 2의 pq 전체를 돌면서 현재 node의 사이즈만큼 돈다. next를 선언 방문하지 않았다면 방문체크해주고 pq에 넣어준다. next, cost+1 로 ans 의 사이즈가 0 이면 -1 그렇지않으면 ans 가 empty가 아닐때까지 poll 해서 정답을 유추한다. package programmers; import java.util.*; import java.io.*; public cl..
BOJ :: 1182(부분 수열의 합)
BOJ :: 1182(부분 수열의 합)
2020.10.261 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 51 52 53 54 55 package backjun; import java.io.BufferedReader; import java.io.InputStreamReader; import java.util.StringTokenizer; import java.util.*; public class BOJ_1182_부분수열의합_백트래킹 { static int aim=0; static int[] arr; static int answer = 0; public stat..
알고리즘104 :: BOJ_1766_문제집
알고리즘104 :: BOJ_1766_문제집
2020.09.26import java.util.*; public class Main { static class Empty implements Comparator{ public int compare(int a, int b) { return Integer.compare(a, b); } @Override public int compare(Integer o1, Integer o2) { // TODO Auto-generated method stub return o1-o2; } } public static void main(String[] args) { // TODO Auto-generated method stub Scanner sc = new Scanner(System.in); int n = sc.nextInt(); int m ..
알고리즘79 :: BOJ_2503_숫자야구
알고리즘79 :: BOJ_2503_숫자야구
2020.04.111234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768697071727374757677787980818283848586import java.io.BufferedReader;import java.io.InputStreamReader;import java.util.ArrayList;import java.util.StringTokenizer; public class backjun_2503_숫자야구 { static int totalGame ; static int ans = 0; static numberInfo[] gogo; static cl..
알고리즘77 :: 이분탐색이란? BOJ_13702에 적용
알고리즘77 :: 이분탐색이란? BOJ_13702에 적용
2020.03.18이분탐색이란? 데이터를 반씩 탐색하여 O(logN) 으로 찾아갈 수 있다. 단, 이분탐색은 정렬된 상태에서 쓸 수 있다. 이분탐색원리 low, high 가 있어서 low