Algorithm/BOJ
-
백준 1120 문자열Algorithm/BOJ 2020. 6. 8. 14:58
출처: www.acmicpc.net/problem/1120 분류: Greedy 접근방식 앞뒤로 아무 문자나 붙여서 길이를 같이 만들 때 차이가 가장 적은 경우를 찾는 문제입니다. 앞뒤로 아무 문자나 붙일 수 있으므로 현재 문자열과 비교할 문자열만 가지고 비교하면 나머지는 길이를 맞춰버릴 수 있습니다. 예제 케이스처럼 adaabc aababbc 를 보면, 0번 인덱스부터 adaabc와 adaabc의 길이만큼인 aababb 와 비교해보면 다른 개수는 3개입니다. 나머지는 adaabc 뒤에 c를 붙여버리면 길이를 똑같이 만들 수 있겠죠 1번 인덱스부터 adaabc와 adaabc의 길이만큼인 ababbc 와 비교해보면 다른 개수는 2개입니다. 마찬가지로 앞에 a를 붙여서 길이를 똑같이 만들 수 있겠죠 해결방법 ..
-
백준 1541 잃어버린 괄호Algorithm/BOJ 2020. 6. 7. 15:18
출처: www.acmicpc.net/problem/1541 1541번: 잃어버린 괄호 첫째 줄에 식이 주어진다. 식은 ‘0’~‘9’, ‘+’, 그리고 ‘-’만으로 이루어져 있고, 가장 처음과 마지막 문자는 숫자이다. 그리고 연속해서 두 개 이상의 연산자가 나타나지 않고, 5자리보다 www.acmicpc.net 분류: Greedy +와 -만으로 이루어진 연산이 들어올 때 괄호를 묶어서 최소인 수를 만드는 문제입니다. + 연산부터 해주고 - 연산을 해주면 최소의 값을 구할 수 있습니다. - 로 우선 다 잘라준 다음에 각각을 다 더해주고 마지막에 빼주는 방식으로 해결했습니다. import Foundation var str = readLine()! var plusOpers = str.components(sepa..
-
Algorithm) BOJ) 백준 1744 - 수묶기Algorithm/BOJ 2019. 6. 26. 23:18
Algorithm) BOJ) 백준 1744 - 수묶기 문제보러가기 1. 초기접근 문제 조건 해석 두 개의 수를 묶어서 곱해서 더해나가 가장 큰 수가 되게 묶는 문제다. 문제를 보고 가장 먼저 떠올린 생각은 큰 수끼리 곱하면 큰 수가 된다는 것. 따라서 정렬해서 묶어 나가면 되겠다. 음수는? 어쩔 수 없으니다 더하자. 라고 생각 하셨다면.. 저와 같이 좀 더 힘내자구요 우리..ㅠㅠ 음수와 음수를 곱하면 양수가 된다. 여기서 끝이 아니고 몇 가지 경우를 더 생각해야 한다. 1은 곱하는 것보다 더하는 것이 더 크다. 음수가 하나 남았고 0도 남아있다면 둘을 곱해서 없애버리는게 더 크다. 이렇게 3가지를 기억하면 이 문제를 풀 수 있다. 알고리즘 양수, 음수와 0 으로 나눠서 배열을 만든다. 양수는 오름차순, ..
-
Algorithm) BOJ) 백준 1931 - 회의실배정Algorithm/BOJ 2019. 6. 18. 19:00
문제보러가기 1. 초기접근 문제 조건 해석 어떻게 회의실을 최적으로 배정할 수 있을까? 배정하는 방법은 여러가지가 있다. 1. 시작 시간이 가장 빠른 회의부터 배정 가장 빨리 시작해서 가장 늦게 끝난다면..? 삐빅 2. 회의 시간이 가장 적은 회의부터 배정 그 사이에 앞뒤로 겹치는 회의가 많다면 효율적이지 못할 수 있다. 3. 끝나는 시간이 가장 빠른 회의부터 배정 이렇게 하면 배정했을 때 뒤에 남은 시간을 가장 최적으로 사용할 수 있게 된다. 알고리즘 끝나는 시간을 기준으로 정렬하고 배정한 뒤 끝나는 시간을 현재 시간으로 생각하고 다음 회의가 배정 가능한지 확인한다. 2. 회고 회의 시간이 가장 짧은 회의부터 배정하는게 최선인가 싶어 삽질을 많이 했었다. 이런 문제는 어떠한 상황이 가장 최적의 상황인지..
-
Algorithm) BOJ) 백준 1783 - 병든 나이트Algorithm/BOJ 2019. 6. 17. 20:46
문제보러가기 1. 초기접근 문제 조건 해석 나이트가 움직일 수 있는 4개의 방식이 주어지는데, 이동 횟수가 4번 이상인 경우에는 각각 한 번 이상은 사용해야 한다. 이 말을 잘 이해해야 한다. 4번 이상까지 이동 방식을 한 번씩 모두 사용했다면 그 다음 부터는 한 가지 방식만 계속 사용해도 된다. 알고리즘 N이 1이라면, 움직일 수 없으므로 현재 자신의 위치인 1이 된다. N이 2라면, n 은 (3번까지 이동한) 4가 최대이고 이후로는 M이 아무리 커도 4를 넘을 수 없다. n이 2밖에 안되서 오른쪽 두 칸씩 밖에 움직일 수 없으므로 (m+1) / 2 와 4 중에서 작은 수를 고른다. N이 3이상이라면, 4번 이동 전까지 각 방식을 모두 사용하고 그 다음부터 1번과 4번 방법을 번갈아 사용하면서 오른쪽 ..
-
Algorithm) BOJ) 백준 2875 - 대회 or 인턴Algorithm/BOJ 2019. 6. 10. 21:00
문제보러가기 1. 초기접근 문제 조건 해석 여자 > 남자x2 이면, 남자의 수 = 팀 아니면, 여자/2 = 팀 이후에 남자든 여자든 어느 한쪽은 모두 팀을 이뤘기 때문에 k에서 나머지 인원만큼을 뺀다. 아직 k가 남아 있다면 3명 단위로 빼줘서 구해나갈 수 있다. 알고리즘 총 3가지 방법이 있다. 1. 팀을 이룰 수 있는 3가지 경우 문제 해석에서 봤던 남자의 수, 여자/2의 수 + (전체인원 - 인턴의 수)/3 3개 중에 가장 적은 수가 가능한 팀이 된다. 2. 남자가 모두 팀을 이루거나, 여자/2가 모두 팀을 이루거나 문제 해석까지 생각한 다음, k가 남아 있다면 팀에서 k/3을 빼고, 아직도 팀이 남아있다면 1을 한번 더 빼준다. (3명을 넘지 않을 것이기 때문에) 3. 인턴을 남자에서 시킬지, 여..
-
Algorithm) BOJ) 백준 7576 - 섬의 개수Algorithm/BOJ 2019. 6. 6. 11:13
문제보러가기 1. 초기접근 문제 조건 해석 전형적인 dfs 문제로 단지번호붙이기 문제와 유사하다. 단, 이번에는 동서남북 + 대각선 까지 구해야 한다. 알고리즘 w, h 크기의 섬을 돌면서 dfs탐색을 한다. 섬의 개수만 구하면 되므로 처음 dfs를 시작할 때마다 count를 늘려준다. 2. 회고 전형적인 dfs문제였다. 머리속에 그려지는 문제는 빠르고 정확하게 풀 수 있도록 노력하자. 3. 코드 while let testCase = readLine()?.split(separator: " ") { let w = Int(testCase[0])! let h = Int(testCase[1])! if w == 0 && h == 0 { break } var map = [[String]](repeating: [St..
-
Algorithm) BOJ) 백준 2667 - 단지번호붙이기Algorithm/BOJ 2019. 6. 6. 00:42
문제보러가기 2667번: 단지번호붙이기 과 같이 정사각형 모양의 지도가 있다. 1은 집이 있는 곳을, 0은 집이 없는 곳을 나타낸다. 철수는 이 지도를 가지고 연결된 집들의 모임인 단지를 정의하고, 단지에 번호를 붙이려 한다. 여기서 연결되었다는 것은 어떤 집이 좌우, 혹은 아래위로 다른 집이 있는 경우를 말한다. 대각선상에 집이 있는 경우는 연결된 것이 아니다. 는 을 단지별로 번호를 붙인 것이다. 지도를 입력하여 단지수를 출력하고, 각 단지에 속하는 집의 수 www.acmicpc.net 1. 초기접근 문제 조건 해석 전형적인 DFS 문제이다. (0,0) ~ (n, n) 까지 돌면서 방문하지 않은 곳은 단지를 이룬다. 알고리즘 (0,0) ~ (n,n) 까지 돌면서 아직 방문하지 않았고, 1인 곳에서 d..