전체 글
-
[BOJ] 색종이 붙이기(JAVA)Algorithm/BOJ 2021. 1. 27. 15:37
[17136] 색종이 붙이기 www.acmicpc.net/problem/17136 Solution 색종이를 붙일 수 있는 칸에(findDot()) 대해서 1~5 사이즈의 색종이를 붙이고(isValid() & drawing()) 지워가며(removing()) count가 가장 작은 값을 answer에 저장했다. 처음에 접근했던 방식은 map[i][j] 값이 1인 dot들을 List에 넣고, 순서대로 뽑아서 색종이를 붙이는 식으로 구현했는데 이 경우에는 위 6, 7번 예제의 답이 제대로 나오지 않아서 findDot()으로 칸을 찾도록 만들었다. 소스코드 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 ..
-
[BOJ] 빵집(JAVA)Algorithm/BOJ 2021. 1. 25. 15:34
[3109] 빵집 www.acmicpc.net/problem/3109 Solution 간단한 백트래킹 문제인데, 처음에 문제를 보고 고려하지 않아도 될 부분에 대해서 오래 생각해서 시간이 걸렸다. 파이프는 우상향, 우, 우하향으로만 연결될 수 있기 때문에 dfs로 파이프를 연결하다 보면 자연스럽게 우상향으로 파이프는 그려진다. 처음에 잘못 생각했던 부분이 (0~i행에서 시작하는)위에 있는 파이프가 아래로 내려와 그려졌을 때 (i+1~r행)아래행에서 더많이 연결될 수 있음에도 불구하고 연결하지 못하는 경우가 있을거라고 생각했다. dfs 메서드가 다음 칸으로 연결될 수 있을 때만 true를 리턴하도록 만들어서 가장 처음 파이프가 연결된 경우를 제외하고는 map에 그려지지 않고 false를 리턴한다. 반복문 ..
-
[BOJ] 월드컵(JAVA)Algorithm/BOJ 2021. 1. 24. 17:18
[6987] 월드컵 www.acmicpc.net/problem/6987 Solution 국가별로 같은 조에 속한 나라들과 1번씩 총 5번의 경기를 치루기 때문에, matches 배열에 경기 순서를 미리 정의했다. matches 배열에 순서대로 접근하면서 backtracking(count+1) 메서드를 dfs로 호출하고, 옳은 결과를 유지하면서 count==15가 되었을 때 탐색을 종료한다. 총 15 번의 경기만 치루기 때문에 count==15까지 도달했다는 것은 모든 경기가 주어진 결과에 부합한다는 것을 의미한다. 소스코드 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 ..
-
[BOJ] 근손실Algorithm/BOJ 2021. 1. 20. 22:50
[18429] 근손실 www.acmicpc.net/problem/status/18429/3/1 Solution 가장 기본적인 백트래킹 유형이라고 할 수 있다. N은 물론 8이하이고, 모든 순열에 대해 문제의 조건을 충족하는 경우(근손실 없이 N개의 운동 장비를 사용할 수 있는지)만 카운트한다. 소스코드 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 import java.io.BufferedReader;..
-
[BOJ] 계란으로 계란치기Algorithm/BOJ 2021. 1. 20. 16:27
[16987] 계란으로 계란치기 www.acmicpc.net/problem/16987 Solution N개의 각각의 계란이 한 번씩만 다른 계란을 칠 수 있을 때 깨지는 계란의 최대 갯수를 구하는 문제 처음에는 문제를 제대로 이해하지 못해서 i번째 계란은 i+1 이상의 순서의 계란만 깰 수 있다고 생각했다. 백트래킹으로 계란의 내구도(durability)를 복구하면서 모든 경우를 탐색해 답을 구할 수 있었다. 소스코드 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 ..
-
[BOJ] 청소년 상어Algorithm/BOJ 2021. 1. 19. 20:20
[19236] 청소년 상어 www.acmicpc.net/problem/19236 Solution 백트래킹 문제인데 중간에 되돌려 놔야할 조건을 놓쳐서 또 엄청난 삽질을 했다.. 문제의 알고리즘의 큰 흐름은 다음과 같다 (1) 상어가 (sx, sy) 자리의 물고기를 먹는다 & 상어는 먹은 물고기의 방향을 가진다. (2) 각자 번호와 방향을 가진 물고기들이 작은 번호 부터 순서대로 자신의 방향으로 이동한다. (3) 상어는 자신의 방향으로 갈 수 있는 칸으로 한 번 이동할 수 있다. => dfs() 호출 (1) - (3) 과정이 반복되고, answer 변수에 상어가 먹을 수 있는 물고기 번호의 합의 최대값을 저장한다. 3번 과정에서 어떤 칸으로 가야 answer의 최댓값을 구할 수 있는지 알 수 없기 때문에 ..
-
[BOJ] 아기상어Algorithm/BOJ 2021. 1. 12. 19:09
[16236] 아기 상어 www.acmicpc.net/problem/16236 Solution 문제 조건 제대로 안 읽고 풀었다가 디버깅의 늪에 빠져벌임.. 문제 제대로 보자 1. 현재 상어 위치를 기준으로 BFS를 돌리고 상어가 먹을 수 있는 (=자신의 크기보다 작은) 물고기를 모두 fishes 리스트에 넣는다. 2. fishes 리스트를 문제 조건에 따라 가장 가까운 > x 좌표 > y좌표 기준으로 정렬하고 첫번째 물고기를 먹는다. 위 두 과정을 반복하다가 fishes 리스트의 길이가 0일 때, 즉 더이상 먹을 수 있는 물고기가 없을 때 while문을 종료한다. BFS 메서드에서 상어와 물고기 사이의 거리를 visited 배열에 저장한다. 소스코드 1 2 3 4 5 6 7 8 9 10 11 12 13..
-
[Programmers] 단체사진 찍기Algorithm/Programmers 2020. 12. 28. 23:46
[2017 카카오코드 본선] 단체사진 찍기 programmers.co.kr/learn/courses/30/lessons/1835# Solution permutation으로 모든 캐릭터의 순서를 구한다음 조건에 맞는지 체크하는 방식으로 풀었다. 캐릭터의 위치를 저장하기 위해 알파벳을 idx로 하는 배열을 만들어 위치를 저장했는데 그렇게 할 필요없이 map으로 위치를 저장하는 방법도 있었다. 소스코드 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 ..