본문 바로가기

알고리즘

 (179)
[BOJ 1072] 게임(C++) https://www.acmicpc.net/problem/1072 1072번: 게임 각 줄에 X와 Y가 주어진다. X는 1,000,000,000보다 작거나 같은 자연수이고, Y는 0보다 크거나 같고, X보다 작거나 같은 자연수이다. www.acmicpc.net 게임 기록은 다음과 같이 생겼다. 게임 횟수 : X 이긴 게임 : Y (Z %) Z는 형택이의 승률이다. 소수점은 버린다. 예를 들어, X=53, Y=47이라면, Z = 88이다. X와 Y가 주어졌을 때, 형택이가 게임을 몇 판 더해야 Z가 변하는지 구하는 프로그램을 작성하시오. 몇 판을 더하는 횟수를 a라고 하면, (X + a) / (Y + a) >= (X / Y) + (1 / 100) 을 구하기 위해선, 양변에 Y를 곱해야 하는데, Y의 최댓값..
[BOJ 1080] 행렬(C++) https://www.acmicpc.net/problem/1080 1080번: 행렬 첫째 줄에 행렬의 크기 N M이 주어진다. N과 M은 50보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에는 행렬 A가 주어지고, 그 다음줄부터 N개의 줄에는 행렬 B가 주어진다. www.acmicpc.net "0과 1로만 이루어진 행렬 A와 행렬 B가 있다. 이때, 행렬 A를 행렬 B로 바꾸는데 필요한 연산의 횟수의 최솟값을 구하는 프로그램을 작성하시오." A 행렬을 B 행렬로 만든다는 것은, 값이 다른 행렬의 원소들을 모두 바꿔야하는 것을 의미한다. 이중 For문을 이용해 순차적으로 값이 다른 행렬의 원소들을 바꾸면서 정답을 찾을 수 있을까? 값이 다른 원소들을 임의의 순서로 골라서 바꿔야지 연산 횟수의 최솟값을..
[BOJ 1049] 기타줄 https://www.acmicpc.net/problem/1049 1049번: 기타줄 첫째 줄에 N과 M이 주어진다. N은 100보다 작거나 같은 자연수이고, M은 50보다 작거나 같은 자연수이다. 둘째 줄부터 M개의 줄에는 각 브랜드의 패키지 가격과 낱개의 가격이 공백으로 구분하여 주 www.acmicpc.net "끊어진 기타줄의 개수 N과 기타줄 브랜드 M개가 주어지고, 각각의 브랜드에서 파는 기타줄 6개가 들어있는 패키지의 가격, 낱개로 살 때의 가격이 주어질 때, 적어도 N개를 사기 위해 필요한 돈의 수를 최소로 하는 프로그램을 작성하시오." 가장 최소의 금액으로, 끊어진 기타줄을 고칠 수 있는 방법을 찾아야 한다. 그러기 위해서 필요한 것은, 가장 싼 패키지 가격, 가장 싼 낱개 가격을 이용해야..
[BOJ 1213] 팰린드롬 만들기(브루트 포스 접근이 필요한가?) 팰린드롬은 알고리즘의 단골 소재이다. 이번 문제는, 팰린드롬을 만들어야 하는 문제이다. 팰린드롬은, 문자열를 뒤집어도 같은 문자열이 되어야 한다. 주어진 문자열을 통해서, 각 대문자 알파벳의 개수를 파악하고 짝수냐 홀수에 따라서 문자열을 처리해주면 된다. 팰린드롬이 불가능한 경우는, 홀수인 알파벳이 1개 초과되면 팰린드롬이 불가능하게 된다. 위의 말들을 바탕으로 코드를 구현하면 아래와 같다. 해설코드(C++). 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 #include #include using namespace std; int arr[26] = { ..
[BOJ 1946] 신입사원 이 문제는 브루트포스로 비교하게 되면, 시간 초과가 발생한다. 그리고, 이 문제의 분류도 그리디 알고리즘이므로 더더욱 브루트포스는 아닐 것이다. 문제에서 원하는 것은, "그래서 진영 주식회사는, 다른 모든 지원자와 비교했을 때 서류심사 성적과 면접시험 성적 중 적어도 하나가 다른 지원자보다 떨어지지 않는 자만 선발한다는 원칙을 세웠다. 즉, 어떤 지원자 A의 성적이 다른 어떤 지원자 B의 성적에 비해 서류 심사 결과와 면접 성적이 모두 떨어진다면 A는 결코 선발되지 않는다." 을 만족하는, 신입사원의 수이다. 서류심사를 기준으로 지원자들을 정렬하면, 특정 지원자가 합격하기 위해서는, 자기의 서류심사점수보다 높은 지원자들을 대상으로 면접 시험 성적이 높아야 한다. 정렬을 하고, 브루트 포스로 비교를 하면 ..
[BOJ 7453] 합이 0인 네 정수 4개의 배열을 가지고, 합이 0이 되도록 구성해야 한다. 이 문제를 브루트포스로 풀게 되면, 배열의 크기는 최대 4000이므로, 4000의 4승이 된다. 시간복잡도가 너무 크므로, 분명히 시간초과가 발생한다. 시간초과가 발생하지 않기 위해서는, 두 개의 배열의 합의 모든 값을 vector 자료구조에 넣는다. 자료구조에 넣은 다음에 정렬을 시킨다. 그리고, 남은 두 개의 배열의 합과 vector의 원소를 합쳤을 때, 0이 되는 값을 찾으면 된다. vector에 값을 넣은 이유는 0이 되는 값을 찾을 때, 이분탐색(logN)을 하기 위해서이다. 이렇게 하면, 시간 복잡도는 4000 * 4000 * log(4000 * 4000)으로 줄어드므로 시간초과가 발생하지 않는다. 해설코드(C++). 1 2 3 4 5 ..
유용한 내장 함수 추천(C++, 알고리즘, 백준) vector와 관련해서 내장 함수들을 매우 많다. 일반적으로, sort 함수는 대부분 사용한다. 하지만, sort 함수이외에도 훌륭한 내장함수들이 많다. - std::binary_search - std::upper_bound - std::lower_bound - std:equal_range 위의 4가지 함수들은 매우 유용하게 사용될 것이다. 시간복잡도와 예제를 아래에서 설명하도록 하겠다. 1. std::binary_search 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 // binary_search example #include // std::cout #include // std::binary_search, std::s..
[BOJ 2875] 대회 or 인턴(반복문없는 if문 풀이, 시간복잡도 최소화) 이 문제는 그리디 알고리즘으로 분류되어 있다. 그리디는, 매순간 최선의 선택을 하는 알고리즘인데 이 문제에서 어떤 의도로 사용하라고 했는지는 잘 모르겠다. 문제를 풀기 위해서 다음의 과정을 거쳤다. 1. 최대 만들 수 있는 팀의 수를 구하기 2. 최대 만들 수 있는 팀 이외의 인원들을 K에 사용하기('-' 연산) 3. 2를 실시한 후에, K에 해당되는 인원이 아직도 남아있다면 팀을 해체시키기 위의 세 과정을 코드로 작성하였다. 구글링을 해보면 대부분 While문을 이용한 코드를 작성했다. While문을 이용한 코드는 N과 M이 크다면, 시간복잡도가 증가해서 효율성이 떨어지기 때문에, 아래의 코드가 더 효율적이라고 볼 수 있다. 해설코드(C++). 1 2 3 4 5 6 7 8 9 10 11 12 13 14..

티스토리툴바