프로그래민👨‍💻

시뮬레이션 문제이다. 문제에 주어진 조건 그대로를 사용하면 된다. 문제처럼 bridge배열을 하나 선언하여 맨처음에 온 트럭을 bridge에 태운채로 시작하였다. 그 후 현재 bridge 무게를 확인하며 다음 트럭이 올라올수 있는 경우 다음 트럭을 태우는 과정 및 움직임을 반복하며 마지막 트럭까지 확인을 하는 과정을 거쳐 문제를 해결하였다. 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 56 57 58 59 60 61 62 63 64 65 package selfStudy.ch..

문제에 주어진 그대로를 구현하는 시뮬레이션 문제이다. 이 문제에서 관건은 주사위를 굴리면서 위치마다 주어진 값들을 스왑하는 과정이 중요하다. 주사위를 0 1 2 3 4 5 위와 같은식으로 인덱싱을 하였고, 2번 인덱스를 top, 5번 인덱스를 bottom으로 생각하고 문제를 접근하였다. 그리고 각 각 방향마다 함수를 두어 스왑하는 과정을 통해 문제를 해결하였다. 그리고 문제를 읽는 과정에서 위쪽과 아래쪽을 헷갈리지 않고 방향을 주어야하는 점도 중요하다. 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 5..

BFS를 활용하는 문제이다. 이 문제의 경우 불(*)의 경우와 사람(@)의 경우가 있으므로 visit배열을 2차원 두개를 이용하기위해 3차원으로 선언하여 각 각 구분하여 문제를 접근하였다. 또한, 불길이 사람보다 먼저 번지기 때문에 일반적인 queue보단 deque를 이용하여 불길이 deque앞쪽에 들어가 있게 했다. 위의 두가지 포인트가 기본적인 BFS 문제와 차이점을 보였던 문제이다. 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 56 57 58 59 60 61 62 63..

기본적인 부분수열의 합문제이다. 두가지 방법으로 풀어보았다. 첫번째로는 비트마스킹을 이용하여 모든 부분수열을 구하는 방식으로 구현하였다. 두번째로는 재귀적인 DFS 방식으로 현재항을 더해주는 경우, 현재항을 더해주지 않는 경우로 나누어 2번씩 호출해주는 방식으로 풀었다. 이때 기저조건으로는 마지막인덱스에 도달하였을 경우 종료시키게 해주었다. 시간은 비트마스킹을 사용하는 첫번째 코드보다 두번째 재귀적인 DFS를 사용한 코드가 빨랐다. 1. 비트마스킹 사용 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 package ch..

그래프를 구현하는 문제였다. 그래프를 구현하기 위해 메모리측면을 고려하여 배열보단 리스트를 사용하였다. 리스트로 그래프를 구성한 후 재귀를 이용한 DFS를 이용하여 모든 정점을 방문하도록 하였다. 방문하는 과정에서 flag를 인자로 주어 두팀으로 나눌 수있도록하였다. 모든 DFS끝난 후 바로 이어서 다시 방문하여서 만일 같은 flag를 가지고 있다면 조건을 만족하지 않는 식으로 구성하였다. 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 56 57 58 59 60 61 62 6..

백트래킹의 전형적인 문제인 N-Queen 문제이다. 체스판에 서로 공격할 수 없도록 N개의 Queen을 배치하는 문제인데, Queen의 움직임 특성상 한 행에 한 개의 Queen 만을 가질수 있게 됨으로 한행을 depth로 보고 dfs를 실행하였다. 보통의 백트래킹은 visit함수로만 방문 여부를 결정하였는데 이 문제에선 대각선이랑 같은 열에 Queen이 존재해야하는지 봐야함으로 check함수를 이용하여 방문 가능여부를 한번더 확인해주는 과정을 거쳐 문제를 해결하였다. 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 4..

주어진 구슬 N의 최대 크기가 4, 너비 W가 12이므로 모든 경우의 수를 구할 때 순열을 사용하여도 복잡도가 넘어 갈 것 같지 않아서 바로 순열을 사용하였다. 순열을 선택한 후 다음과 같은 과정을 계획하였다. 1. W에서 N개를 선택하는 모든 수열을 구한다. 2-1. 구한 순열의 경우의 수마다 위에서 부터 폭파하는 과정을 BFS를 통하여 계산한다. 2-2. 폭파된 후 중간에 공백을 아래로 당겨준다. 그 후 2-1 반복한다. 3. 모든 폭파가 종료된 후 살아있는 블럭을 카운팅해준다. 또한, 중간에 최적화를 시키기 위해, 만일 2-1 과정에서 선택한 열의 블록이 하나도 없는 경우, 그 순열의 경우는 바로 종료 시키게 해주었다. 문제를 읽고 있는 그대로 차분하게 구현하여서 답을 얻을 수 있었다. 1 2 3 ..

조합을 사용하는 문제이다. 백트래킹을 사용하는 comb함수를 구현하여 N개중에서 N/2개를 뽑는 조합의 경우를 구하고, 그 경우 마다 check함수를 적용시켜 서로 다른 두 집합의 시너지 합이 최소가 되는 경우를 찾았다. check함수에서는 visit배열을 기준으로 방문의 유무를 이용하여 두개의 그룹으로 나누었다. 그리고 이 check함수에서도 2개씩 뽑아내야 하는 조합이 있는데 이것은 단순 이중for문으로 구현하였다. 문제를 이해하는데 꽤 많은 시간이 걸려서 다른 블로그를 참고하였다. 문제의 의도를 파악하는 연습이 필요한 것 같다. 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 ..

BFS를 사용하는 문제이다. 해당 칸의 값이 0이면 8칸의 값을 무조건 방문해줘야하기에 전체 배열을 돌면서 0인 곳을 찾아서 방문해주는 BFS 로직을 우선 사용하였다. 그리고 모든 방문이 끝난후 아직 방문하지 않고, 빈칸인 경우들의 대해서 count를 추가해주는 과정을 거쳐 답을 구하였다. 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 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 8..

재귀를 사용하는 기본적인 문제이다. 기저조건으로 size가 1이되는 경우 맨왼쪽 위 기준으로 9칸씩 채우도록 해주었다. 또한, flag를 이용하여 현재위치에서 공백을 출력해야할지 *을 출력해야할지를 결정하였다. 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 package chap06; import java.io.BufferedReader; import java.io.InputStreamReader; public class Main_bj_2447_별찍기10 { static char[][] map; public static void..