boj
-
백준 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) 백준 1931 - 회의실배정Algorithm/BOJ 2019. 6. 18. 19:00
문제보러가기 1. 초기접근 문제 조건 해석 어떻게 회의실을 최적으로 배정할 수 있을까? 배정하는 방법은 여러가지가 있다. 1. 시작 시간이 가장 빠른 회의부터 배정 가장 빨리 시작해서 가장 늦게 끝난다면..? 삐빅 2. 회의 시간이 가장 적은 회의부터 배정 그 사이에 앞뒤로 겹치는 회의가 많다면 효율적이지 못할 수 있다. 3. 끝나는 시간이 가장 빠른 회의부터 배정 이렇게 하면 배정했을 때 뒤에 남은 시간을 가장 최적으로 사용할 수 있게 된다. 알고리즘 끝나는 시간을 기준으로 정렬하고 배정한 뒤 끝나는 시간을 현재 시간으로 생각하고 다음 회의가 배정 가능한지 확인한다. 2. 회고 회의 시간이 가장 짧은 회의부터 배정하는게 최선인가 싶어 삽질을 많이 했었다. 이런 문제는 어떠한 상황이 가장 최적의 상황인지..
-
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..
-
Algorithm) BOJ) 백준 1406 - 에디터Algorithm/BOJ 2019. 5. 21. 18:16
문제보러가기 1406번: 에디터 문제 한 줄로 된 간단한 에디터를 구현하려고 한다. 이 편집기는 영어 소문자만을 기록할 수 있는 편집기로, 최대 600,000글자까지 입력할 수 있다. 이 편집기에는 '커서'라는 것이 있는데, 커서는 문장의 맨 앞(첫 번째 문자의 왼쪽), 문장의 맨 뒤(마지막 문자의 오른쪽), 또는 문장 중간 임의의 곳(모든 연속된 두 문자 사이)에 위치할 수 있다. 즉 길이가 L인 문자열이 현재 편집기에 입력되어 있으면, 커서가 위치할 수 있는 곳은 L+1가지 경우가 www.acmicpc.net 문제를 보고 가장 먼저 한 생각은 배열로 만들어 풀면 되겠다 라고 생각했었지만 그렇게 하면 삽입, 삭제를 할 때 커서 뒤의 모든 원소를 옮겨야 하기 때문에 시간 제한에 걸리게 됩니다! 커서를 기..
-
Algorithm) BOJ) 백준 1676 - 팩토리얼 0의 개수Algorithm/BOJ 2019. 5. 17. 16:06
문제보러가기 1676번: 팩토리얼 0의 개수 N!에서 뒤에서부터 처음 0이 아닌 숫자가 나올 때까지 0의 개수를 구하는 프로그램을 작성하시오. www.acmicpc.net 팩토리얼을 구하는 방법은 다들 아실텐데요, 문제는 수가 조금만 커져도 그 값이 어마어마하게 커진다는게 문제에요ㅠㅠ / 뒤에 숫자 0이 붙는다는 건 무슨 의미일까요? / 2라는 숫자를 20으로 만들려면 어떻게 해야할까를 생각하면 이해가 쉬울 것 같습니다. 한 마디로 10이 곱해진다는 뜻이죠 ! 즉 우리는 팩토리얼에서 10이 몇 개가 있는지를 확인하면 된답니다! 10 = 5 x 2 이므로 5의 개수와 2의 개수를 확인하면 되겠죠? / 그렇다면 2의 개수와 5의 개수는 어떻게 확인할까요? / 먼저 15! 을 한번 예로 들어볼게요, 1 x 2..
-
Algorithm) BOJ) 백준 6588 - 골드바흐의 추측Algorithm/BOJ 2019. 5. 15. 11:44
문제 보러 기기 6588번: 골드바흐의 추측 문제 1742년, 독일의 아마추어 수학가 크리스티안 골드바흐는 레온하르트 오일러에게 다음과 같은 추측을 제안하는 편지를 보냈다. 4보다 큰 모든 짝수는 두 홀수 소수의 합으로 나타낼 수 있다. 예를 들어 8은 3 + 5로 나타낼 수 있고, 3과 5는 모두 홀수인 소수이다. 또, 20 = 3 + 17 = 7 + 13, 42 = 5 + 37 = 11 + 31 = 13 + 29 = 19 + 23 이다. 이 추측은 아직도 해결되지 않은 문제이다. 백만 이하의 모 www.acmicpc.net 주어진 짝수를 두 소수 홀수의 합으로 나타내는 문제이다. 문제는 두 홀 수를 a, b라 할 때, b-a가 가장 적어야 한다는 것이다. 한마디로 주어진 수 N - a(홀수 소수) =..