Algorithm/BOJ
-
백준 1969 DNAAlgorithm/BOJ 2020. 6. 15. 14:07
출처: www.acmicpc.net/problem/1969 분류: 그리디 접근방식 주어진 DNA 들의 각 인덱스를 보면서 DNA 원소인 A T G C 중에 가장 많은 녀석을 골라 Hamming Distance가 가장 작은 DNA를 만들면 되는 문제입니다. 각 인덱스에서 Hamming Distance는 가장 많이 DNA들의 개수 - 선택한 원소의 개수 가 됩니다. 해결방법 let n = readLine()!.split(separator: " ").map {Int($0)!} var dnas = [[String.Element]]() for _ in 0..
-
백준 1543 문서 검색Algorithm/BOJ 2020. 6. 15. 13:31
출처: www.acmicpc.net/problem/1543 분류: 그리디 접근방식 문자열 매칭 문제 입니다. 겹치지 않게 문자열을 찾으면 됩니다. 문서 길이가 2500정도 밖에 안되서 단순 매칭으로도 해결할 수 있는 문제입니다. 문제는 탐색의 시작을 반드시 0번부터 할 필요는 없다는 것이죠. 첫번째부터 탐색한거보다 그 이후부터 탐색을 시작해서 더 경우가 많아지는 반례는 찾지 못했습니다... 앞에서 탐색한 것 때문에 뒤에 문자를 더 찾지 못해 한 개를 손해 보더라도 앞에서 탐색한거랑 쌤쌤으로 개수는 똑같을 것 같은데.... 한 개이상 손해볼 수가 있는지 반례를 잘 찾지 못하겠습니다 😭 실제로도 c++ 같은 다른 분들의 풀이를 보니 그냥 첫번째부터 탐색해서 통과하셨더라구요... 채점 방식이 예전과 달라진 것..
-
BOJ 백준 1449 수리공 항승Algorithm/BOJ 2020. 6. 13. 12:00
출처: www.acmicpc.net/problem/1449 분류: 그리디 접근방식 테이프의 좌 우로 0.5를 남겨둬야 한다고 했으니 테이프 길이 - 1 만큼의 구멍은 한 번에 막을 수 있습니다. 구멍을 막을 때마다 테이프의 길이는 줄어들겠죠. 테이프의 길이보다 구멍까지의 간격이 더 크다면 테이프를 새로 끊어야 합니다. 현재 남은 테이프로 남은 구멍을 메꿀 수 있는지 확인하고 아니면 테이프를 새로 끊어줍니다. 다른 분의 접근법을 보고 알았는데요. 더 쉽게 생각하면 현재 구멍의 위치 + 테이프길이-1 만큼까지 커버가 가능하다는 말이 됩니다. 테이프를 새로 끊을 때 현위치 + 테이프길이-1 까지를 커버 가능한 범위라고 생각하면, 다음 위치가 커버 가능한 범위를 벗어나면 테이프를 새로 끊어주면 됩니다. 해결방법..
-
백준 2437 저울Algorithm/BOJ 2020. 6. 13. 01:53
출처: www.acmicpc.net/problem/2437 분류: 그리디 접근방식 쉬워보였으나, 실제로도 방법만 알면 쉬우나, 쉽지 않았던 문제입니다 😭 추들이 주어질 때 측정할 수 없는 최소값을 구하는 문제입니다. 어떤 경우가 되면 더 이상 무게를 구할 수 없다고 판단할 수 있을까요? 추를 오름차순으로 정렬했을 때, 처음 추의 무게가 2라면, 절대 1은 만들 수가 없습니다. 1, 2 다음에 900이 나온다면? 최대로 3까지 만들 수가 있습니다. 1, 2, 3 다음에 900이 나온다면? 최대로 6까지 만들 수가 있습니다. 그렇다면 이제 다시 생각해볼까요? 저희는 직관적으로 알고 있습니다. 1, 2, 3 다음에 900이 나오면, 이미 900은 너무 큰 숫자니 제치고 그 전의 1, 2, 3가지고 최대를 찾아..
-
BOJ 2352 반도체 설계Algorithm/BOJ 2020. 6. 12. 16:10
출처: www.acmicpc.net/problem/2352 분류: Greedy, LIS 접근방식 포트에 선이 서로 꼬이지 않게 연결하려고 할 때 가장 많이 연결할 수 있는 개수를 찾는 문제입니다. 문제의 예처럼 이렇게 연결되어 있을 때, 왼쪽을 A포트 오른쪽을 B포트라고 생각해보겠습니다. A[1] -- B[4] 포트가 연결되어 있다면 왼쪽에서 A[1]을 제외한 나머지 포트들은 모두 1보다 크기 때문에 B에서 4보다 작은 포트들에는 연결할 수가 없습니다. 다시말해 A[i] 포트 --> B[j] 포트로 연결하려고 할 때 현재까지 B에 연결되어있는 포트 중 가장 큰 녀석보다 작은 경우에는 연결할 수가 없게 됩니다. 즉, 이 경우엔 B에 연결해야 하는 포트들 중에서 연속적으로 증가하는 수의 최대 길이가 몇이야?..
-
BOJ1080 행렬Algorithm/BOJ 2020. 6. 11. 17:31
출처: www.acmicpc.net/problem/1080 분류: Greedy 접근방식 두 형렬에서 한 행렬을 한번에 3x3 만큼씩 뒤집는 연산을 통해 같은 행렬을 만들 수 있는 최소 연산횟수를 구하는 문제입니다. 처음엔 dfs로 무식하게 모든 경우를 다 해봤는데 이럴 경우 엄청난 연산 횟수로 역시 시간초과가 납니다. 그리디 문제인 만큼 그리디하게 풀면 생각보다 쉽게 해결할 수 있습니다. 0,0 부터 시작해서 n-3까지 가면서 해당 지점이 타겟 행렬과 다르다면 뒤집어줍니다. 0,0부터 시작하기 때문에 해당 점에서 뒤집지 않으면 결코 같은 행렬을 만들 수 없습니다. 같다면 그냥 통과하면 되는거고 다를 경우 연산 횟수를 카운트하면서 넘어가주면 됩니다. 이때 몇 가지 경우를 더 생각해줘야 하는데 같은 행렬을 ..
-
백준 1049 기타줄Algorithm/BOJ 2020. 6. 8. 16:18
출처: www.acmicpc.net/problem/1049 분류: 그리디 접근방식 패키지와 낱개의 가격이 주어지고 고장난 기타줄 이상을 살 수 있는 최소가격을 구하는 문제입니다. 최소 가격을 구하는 문제이므로 패키지와 낱개 각각의 최소값에만 신경쓰면 됩니다. 동전나누기와 비슷하죠? 낱개 6개 가격이 패키지 가격보다 싸지만 않다면 패키지만큼 다 나눠주고 나머지랑 패키지랑 비교해서 풀면 됩니다. 해결방법 let n = readLine()!.split(separator: " ").map{Int($0)!} var minPackage = Int.max var minPiece = Int.max for _ in 0.. minPiece * 6 { print(n[0] * minPiece) } else { var tota..
-
백준 1946 신입 사원Algorithm/BOJ 2020. 6. 8. 15:54
출처: www.acmicpc.net/problem/1946 분류: 그리디 접근방식 다른 사람보다 서류와 면접 점수가 모두 낮은 경우엔 탈락, 합격한 사람의 수를 구하는 문제입니다. 서류 1등은 무조건 합격입니다. 1등보다 면접 등수마저 낮다면 그 사람은 탈락이 되겠죠. 이때 1등의 면접 등수가 서류 2등 ~ 나머지 사람의 합격을 가르는 기준점이 됩니다. 1등의 면접 점수보다 낮은 사람을 모두 거르고 나면 남아있는 사람 중 서류 1등이 다시 합격의 기준점이 되죠. 이를 반복해주면 합격자의 수를 구할 수 있습니다. 하지만 이렇게 해주면 시간 초과가 납니다. (Swift 기준) 매번 나머지를 다시 도는건 너무 비효율적인 방법이죠. 보다 효율적으로 해결할 수 있는 방법이 있습니다. 서류 1등의 면접 등수를 기준..