꾸물꾸물 졔의 개발공부

[ 알고리즘 ] 1번 : 상 / 하 / 좌 / 우 중 한방향으로 쭉 ( 벽을 만나거나 경계만날때까지 ) 2번 : (상, 하) / (좌, 우 ) 3번 : (상,우) (우,하) (하,좌), (좌,상) 4번 : (좌,상,우) (상,우,하), (우,하,좌), (하,좌,상) 5번 : (상,하,좌,우) CCTV 의 위치를 모두 저장해두고, 가능한 모든 경우의 수를 완전탐색한다. dfs 를 통해 재귀 호출하며 탐색하고, 종료시 0의 갯수를 세서 매번 최소 사각지대 갯수를 갱신한다. + 간단해보이지만, 구현이 은근히 어려웠다. 한쪽으로 탐색하며 dfs 호출하는게 생각보다 쉽지 않았기 때문에, 상 / 하 / 좌 / 우 한방향을 경계만날때까지 탐색하는 함수를 따로 구현하였다. (goRight ~ goUp) → 다른 구현 ..

[ 알고리즘 ] 결국엔 목적 숫자에 도달하기 위한 최소횟수를 구하는 문제 → BFS 탐색을 위해 , 1000~9999의 수를 소수 판별하여 primary[] 일차원 배열에 소수인지 아닌지 T/F 값으로 저장하였다. 시작숫자에서 출발하여, i ) 첫번째 자릿수를 바꾼다 , 방문한적이 없고 소수라면 큐에 저장 ( visited 배열과 primary 배열 탐색 ) ii) 두번째 자릿수를 바꾼다. 방문한적이 없고 소수라면 큐에 저장 iii ) 세번째 자릿수를 바꾼다. 방문한 적이 없고 소수라면 큐에 저장 iiii) 네번째 자릿수를 바꾼다. 방문한 적이 없고 소수라면 큐에 저장 과 같은 과정으로 큐에 소수 값들을 저장하였다 . 최소 횟수를 도출해내야 하는 문제이기 때문에 , 네자리 정수를 저장하는 큐를 우선순위큐..

[ 알고리즘 ] 최단거리 구하기와 비슷한 맥락으로 생각하여 BFS 로 접근하기로 했다. 거울갯수를 오름차순 정렬하여 우선순위큐를 구현하였고, 거울갯수가 적은것이 우선적으로 실행되었다. 방문체크는 TRUE , FALSE 가 아닌 거울 갯수로 저장하였고, 다음 방문시 거울 갯수가 더 적다면 값을 갱신하였다. → 거울 갯수는 최소인 경우를 구하는 것이기 때문에, 처음 초기화시, 배열전체를 정수최댓값으로 채워두었다. 큐에 넣을 해당 좌표 정보를 class 로 구현하였다. x, y 좌표와 , 해당 좌표에 진입한 방향 , 해당 좌표에 도달하기 위해 필요한 거울 갯수를 변수로 가지고 있었고. compare 함수를 구현하여 `this . - o.` 로 오름차순 정렬하였다 . 사방탐색 ( 상 / 하 / 좌 / 우 ) 를..

[ 알고리즘 ] B → A 로 넘어가며 각 경우의 수를 나눈다 . 끝자리가 1인 경우 : 2로 나눌 수 없기 때문에 무조건 1을 수의 오른쪽에 추가한 경우 짝수인 경우 : 무조건 2를 곱한 경우 끝자리가 1인 아닌 홀수이거나, A > B 인 경우 : 연산불가능한 경우, -1 위의 경우의 수를 가지고 재귀를 돌다가, A==B 가 되는 시점에 count+1를 리턴 하였다. 1. 끝자리가 1인 경우 b%10 == 1 일 때로 판별하였고, 끝자리를 날리기 위해, b /= 10 ( ex) b=81일때, b/10 = 8 ) 2. 짝수인 경우 b%2 == 0 으로 판별하였고, 반대로 2를 나누어줌 . b/=2 (ex) b=42 일때, b/2 = 21 ) [ 코드 ] import java.util.*; public c..

[ 알고리즘 ] 재귀를 통해, 가능한 연산자의 모든 조합을 다 구해보았다. 각 연산자의 갯수를 cal 배열에 저장하여, cal 값이 0이 되기 전까지 재귀 반복 . 연산자의 종류는 switch 문을 사용하여 재귀를 호출하였고, 재귀 호출 이후에는 다음 탐색을 위해 다시 cal ++. 재귀 종료조건으로는 index 값이 숫자의 갯수와 같을 때, max 값과 min 값을 도출해내고, return [ 코드 ] import java.util.*; import java.io.*; public class Main { private static int[] num; //숫자 배열 private static int[] cal; //연산자 배열 private static int min = Integer.MAX_VALUE;..

[ 그리디 + 오름차순 정렬 ] 주어진 숫자는 해당 사원의 점수가 아닌 등수이다. 둘 중 하나를 기준으로 오름 차순 정렬하면 , 해당 등수에 대해 등수가 높은 순으로 정렬이 되어진다. 나는 서류등수를 기준으로 오름차순 정렬하였고 서류등수가 1등인 사람은 무조건 합격이므로 count++ . 이후부터는 방금 뽑힌 사람보다 면접등수가 높은 사람을 합격시켰다 . 서류등수는 등수가 정렬 되어있기 때문에, 면접등수가 높은 사람을 선택 해야한다. ex ) 서류등수 기준으로, 1등의 면접등수 > 2등 면접등수 이면, 탈락 ▶ 1등보다 면접, 서류 다 낮은 것이므로 . 1등의 면접 등수 < 3등의 면접 등수이면 ,합격 → 3등의 면접 등수와 4등의 면접 등수 비교하면서 반복 .. [ 코드 ] import java.uti..

[ 알고리즘 ] 만약 카드 갯수가 4개라고 주어졌을 땐, 1장팩 * 4 / 2장팩 *2 / 3장팩 + 1장팩 / 4장팩 중 최솟값을 구해야 한다. 그렇기 위해선 각 1장팩 ~ 4장팩이 항상 가질 수 있는 값 중 최솟값을 가지고 있어야 한다 . ▶ DP 를 사용 해서 해결하였다. → dp 배열에는 각 카드 갯수에 대해서, 필요한 최소 금액을 저장하였다 . ( memorization ) dp[1] = 1장 사는 최소금액, dp[2] = 2장 사는 최소금액 . .... dp[n] = n장 사는 최소금액 일단 , dp 값을 각 카드팩 가격으로 초기화 시킨다음, 반복문을 돌면서 나올 수 있는 카드 팩 조합에 대해 dp 합을 구했다. dp 보다 더 작은 값이 나오면 dp 값을 갱신 . [ 코드 ] import ja..

시간초과 - 부분집합 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 51 52 53 54 55 import java.io.*; import java.util.*; public class Main_시간초과 { public static int[] drink; //포도주 마셨으면 1 private static int n; private static ArrayList grape; private static int max; // 최댓값 public static void main(String[] args) thr..