algorithm
-
백준 8980 택배Algorithm/BOJ 2020. 7. 20. 16:10
출처: www.acmicpc.net/problem/8980 분류: 그리디 접근방식 출발 도시와 도착 도시, 용량이 적혀있는 택배 목록이 주어질 때 배달할 수 있는 최대 용량을 구하는 문제입니다. 단, 한번 지나온 마을은 다시 돌아갈 수 없습니다. 핵심 포인트는 다음 2가지 입니다. 문제의 핵심은 도착 도시를 기준으로 정렬 각 도시에서 적재 가능한 용량 체크 특히 도착 도시를 기준으로 정렬하는 것이 핵심인데요, 도착 도시를 기준으로 정렬했기 때문에 가장 먼저 내릴 수 있는 택배를 우선적으로 배달할 수 있습니다. 예를 들어, 3 60 3 1 3 50 1 2 30 2 3 60 이렇게 주어질 때 도착 기준으로 정렬합니다. 1 2 30 1 3 50 2 3 60 가장 먼저 도착하는 2번 마을에 배달해야 할 양 30..
-
백준 15683 감시Algorithm/BOJ 2020. 7. 16. 13:29
출처: www.acmicpc.net/problem/15683 분류: 완전탐색 접근방식 하.. 코드량이 너무 너무 너무 길었던 문제였습니다. 5개의 CCTV가 있고 각 CCTV는 90도로 회전이 가능합니다. 사각지대가 가장 최소가 되는 경우를 찾는 문제입니다. 각 CCTV 의 케이스는 1번 상하좌우 4개 2번 상하, 좌우 2개 3번 4개 4번 4개 5번 1개 입니다. 저는 CCTV를 먼저 찾아놓고 CCTV List를 다 탐색할 때 까지 DFS를 돌렸습니다. CCTV 에 케이스는 많지만 결국 지우는 건 방향에 따라 상하좌우 4가지 이므로 상하좌우 direction을 입력받는 함수를 만들어서 지우고 CCTV 타입별로 상 하 좌 우로 직접 입력해주는 방식을 사용했습니다. 더 스마트하게 풀 수도 있을 것 같은데 ..
-
백준 1107 리모컨Algorithm/BOJ 2020. 7. 16. 11:56
출처: www.acmicpc.net/problem/1107 분류: 완전 탐색 접근방식 돌고돌아 결국 순수한 완전탐색으로 해결한 문제입니다. 고장난 숫자 버튼이 주어질 때 원하는 채널을 만들기 위해 필요한 조작 횟수를 구하는 문제입니다. 조정할 수 있는 채널 중에서 원하는 채널과 가장 가까운 채널로 가서 + 혹은 - 로 조작하면 최소의 수를 구할 수 있... 을줄 알았으나, 생각보다 간단한 문제는 아니었습니다. 가장 가까운 채널을 어떻게 만들 것인가, "처음엔 수어진 숫자의 각 자리 마다 위, 아래로 가까운 수를 뽑으면 가장 가까운 수가 되겠구나." 라고 생각하고 접근했습니다. 5000 2 5 0 이렇게 주어지면, 5 와 0을 피해 가장 가까운 각 자리 수를 up, down으로 만들면, 밑으로 가장 가까운..
-
백준 14500 테트로미노Algorithm/BOJ 2020. 7. 15. 14:07
출처: www.acmicpc.net/problem/14500 분류: 완전 탐색 접근방식 주어진 5개의 테트로미노를 하나 놓을 때 테트로미노에 겹쳐지는 블록의 최대값이 얼마인지 구하는 문제입니다. 모든 경우를 다 체크하면 되겠지만 테트로미노는 회전 또는 대칭이 되기 때문에... 매우매우 귀찮습니다.. 😨 하지만 이 문제에는 귀찮음을 덜어줄 수 있는 법칙이 숨겨져 있습니다 :) 바로 ㅗ 모양을 제외한 테트로미노들은 한 점에서 dfs로 4개씩 탐색한 결과들입니다. 한 점에서 dfs로 4개의 블록을 고르면 4개의 테트로미노를 회전 대칭 시킨 모양안에 모두 포함됩니다! 대신 ㅗ 모양은 ㅗ ㅜ ㅏ ㅓ를 따로 찾아줘야 합니다. 해결방법 let nm = readLine()!.split(separator: " ").ma..
-
백준 6603 로또Algorithm/BOJ 2020. 7. 15. 12:26
출처: www.acmicpc.net/problem/6603 분류: 완전 탐색 접근방식 주어진 문제에서 로또번호 6개를 골라서 출력하는 문제입니다. 전형적인 순열문제였습니다. 제 순열 관련 글도 있습니다 :) 위 글에서 사용한 스왑방식 대신 select 를 체크할 배열을 만들어서 인덱스만 넘겨주는 방식으로 풀었습니다. 스왑해서 재귀호출하고 다시 스왑을 한 번 더 해서 원상태로 바꿔주듯이 인덱스를 선택해서 true로 바꿔주고 호출한 다음에 다시 false로 바꾸고 호출해주는 과정이 필요합니다 ! 해결방법 func select(index: Int, count: Int) { //print("index: \(index), count: \(count)") if count == lottoNumberCount { fo..
-
백준 15686 치킨 배달Algorithm/BOJ 2020. 7. 13. 18:42
출처: www.acmicpc.net/problem/15686 분류: 완전탐색 접근방식 집과 치킨집이 주어지고 집에서 제일 가까운 치킨집까지의 거리가 집의 치킨거리가 됩니다. 모든 집의 치킨 거리를 합친 값이 도시의 치킨거리가 됩니다. 치킨집을 M개 만큼 선택했을 때 최소가 되는 치킨거리를 구하는 문제입니다. 우선 집과 치킨집의 위치를 먼저 저장해두고 치킨집을 M개 골랐을 때의 치킨 거리들을 구하면 됩니다. 해결방법 let nm = readLine()!.split(separator: " ").map{Int($0)!} var board = [[Int]]() for _ in 0..
-
BOJ 14889 스타트와 링크Algorithm/BOJ 2020. 7. 8. 16:17
출처: www.acmicpc.net/problem/14889 분류: 완전탐색 접근방식 짝수의 사람과 두 사람이 같은 팀일 때 능력치가 주어지고, 사람들을 두 팀으로 나눌 때, 능력치의 차이를 구하는 문제입니다. 핵심 포인트는 크게 두 가지로 볼 수 있습니다. 1. 사람들을 두 팀으로 나누기 2. 각 팀의 능력치를 구하기 주의할 점은 각 팀의 능력치를 구할 때 팀원 두 쌍의 능력치를 각각 모두 더해줘야 합니다. 만약 1, 3, 6이 한 팀이고 두 사람이 팀일 때 능력치를 Sij 라고 한다면, S13 + S16 S31 + S36 S61 + S63 위 6가지 경우를 모두 더해줘야 합니다. 해결방법 팀을 나누는 건 3명을 뽑으면 나머지 팀은 자동으로 완성되므로 3명을 뽑을 때까지 재귀로 구현했습니다. func ..
-
백준 1041 주사위Algorithm/BOJ 2020. 6. 30. 15:37
출처: www.acmicpc.net/problem/1041 분류: Greedy 접근방식 주사위를 쌓아서 정육면체를 만들 때 각 주사위에서 서로 마주보는 면이 동시에 보일 수는 없습니다. 따라서 마주보는 면이 안 나오게 잘 계산해서 최소값을 구해줘야 합니다. 주어진 도면에서 각 주사위의 마주보는 면은 (0, 5), (1, 4), (2, 3) 입니다. (주사위 1개인 경우 제외) 만들어진 정육면체에서 각 주사위는 3가지 케이스 밖에 생기지 않고 각 케이스의 개수는 아래와 같습니다. 세 면이 보이는 경우 4개 ( 각 모서리 위쪽 ) 두 면이 보이는 경우 4(N-1) + 4(N-2) (옆면 모서리 + 위쪽 모서리) 한 면이 보이는 경우 4N(N-2) + (N-2)(N-2) (테두리를 제외한 옆면 + 테두리를 제..