[백준 알고리즘]/[C++]
-
백준 2230 수 고르기 | C++[백준 알고리즘]/[C++] 2021. 3. 24. 10:41
이번 포스팅은 백준 2230번 수 고르기입니다. 아래 url를 클릭하시면 백준 사이트에서 문제를 볼 수 있습니다. www.acmicpc.net/problem/2230 2230번: 수 고르기 첫째 줄에 두 정수 N, M(0≤M≤2,000,000,000)이 주어진다. 다음 N개의 줄에는 차례로 A[1], A[2], …, A[N]이 주어진다. 각각의 A[i]는 0 ≤ |A[i]| ≤ 1,000,000,000을 만족한다. www.acmicpc.net 기본 알고리즘 투 포인터 셸 정렬 사용함 벡터와 sort 함수를 사용하면 코드의 길이와 실행 시간을 단축할 수 있다. 전체 코드 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 2..
-
백준 14567 선수과목 (Prerequisite) | C++[백준 알고리즘]/[C++] 2021. 3. 23. 10:20
이번 포스팅은 백준 14567번 선수과목 (Prerequisite)입니다. 아래 url를 클릭하시면 백준 사이트에서 문제를 볼 수 있습니다. www.acmicpc.net/problem/14567 14567번: 선수과목 (Prerequisite) 3개의 과목이 있고, 2번 과목을 이수하기 위해서는 1번 과목을 이수해야 하고, 3번 과목을 이수하기 위해서는 2번 과목을 이수해야 한다. www.acmicpc.net 기본 알고리즘 위상 정렬 (Topological Sort) 풀이 위상 정렬하면서 출력 배열(과목 번호가 인덱스)에 수강 학기 수를 저장한다. 1학기 부터 시작하므로 result 배열을 1로 초기화 한다. q 1 4 6 result[i] 1 1 1 cur = 1 q 1 4 6 2 3 result[i]..
-
백준 2109 순회강연 | C++[백준 알고리즘]/[C++] 2021. 3. 18. 13:17
이번 포스팅은 백준 2109번 순회강연입니다. 아래 url를 클릭하시면 백준 사이트에서 문제를 볼 수 있습니다. www.acmicpc.net/problem/2109 2109번: 순회강연 한 저명한 학자에게 n(0 ≤ n ≤ 10,000)개의 대학에서 강연 요청을 해 왔다. 각 대학에서는 d(1 ≤ d ≤ 10,000)일 안에 와서 강연을 해 주면 p(1 ≤ p ≤ 10,000)만큼의 강연료를 지불하겠다고 알려왔다. www.acmicpc.net 기본 알고리즘 우선순위 큐 priority queue 풀이 한 대학의 강연은 한 번만 간다. 입력 p | 20 2 10 100 8 5 50 d | 1 1 3 2 2 20 10 입력 값을 pair로 묶어 벡터에 저장 후 d를 기준으로 오름차순 정렬 {1, 10} {1..
-
백준 1744 수 묶기 | C++[백준 알고리즘]/[C++] 2021. 3. 17. 10:50
이번 포스팅은 백준 1744번 수 묶기입니다. 아래 url를 클릭하시면 백준 사이트에서 문제를 볼 수 있습니다. www.acmicpc.net/problem/1744 1744번: 수 묶기 길이가 N인 수열이 주어졌을 때, 그 수열의 합을 구하려고 한다. 하지만, 그냥 그 수열의 합을 모두 더해서 구하는 것이 아니라, 수열의 두 수를 묶으려고 한다. 어떤 수를 묶으려고 할 때, 위치에 www.acmicpc.net 기본 알고리즘 vector sort() 풀이 2개씩 묶어 곱한 합의 최댓값 구하기 곱셈의 값이 커지려면 ▷양수, 음수는 서로 곱한다 ▷ 1은 곱하는 것이 무의미함 = 개별로 더하는 것이 합의 최댓값 유도 ▷0은 더하는 것이 무의미함 = 0은 음수의 개수가 홀수일 때 절댓값이 가장 작은 음수와 곱하는..
-
백준 1377 버블 소트 | C++[백준 알고리즘]/[C++] 2021. 3. 15. 15:51
이번 포스팅은 백준 1477번 버블 소트입니다. 아래 url를 클릭하시면 백준 사이트에서 문제를 볼 수 있습니다. www.acmicpc.net/problem/1377 1377번: 버블 소트 첫째 줄에 N이 주어진다. N은 500,000보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에 A[1]부터 A[N]까지 하나씩 주어진다. A에 들어있는 수는 1,000,000보다 작거나 같은 자연수 또는 0이다. www.acmicpc.net 기본 알고리즘 버블 소트 풀이 문제에 주어진 코드를 사용하면 시간 초과 판정이 나므로 문제에서 요구하는 출력값이 무엇인지 파악해야 한다. 출력 값 i는 버블 정렬을 몇 번째 수행에서 버블 정렬이 완성되는지 출력하는 값이다. i=1 10 1 5 2 3 1 10 5 2 3 1 5..
-
백준 11478 서로 다른 부분 문자열의 개수 | C++[백준 알고리즘]/[C++] 2021. 3. 15. 12:55
이번 포스팅은 백준 11478번 서로 다른 부분 문자열의 개수입니다. 아래 url를 클릭하시면 백준 사이트에서 문제를 볼 수 있습니다. www.acmicpc.net/problem/11478 11478번: 서로 다른 부분 문자열의 개수 첫째 줄에 문자열 S가 주어진다. S는 알파벳 소문자로만 이루어져 있고, 길이는 1,000 이하이다. www.acmicpc.net 기본 알고리즘 부분 문자열 추출 전체 코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 //백준11478 서로 다른 부분 문자열의 개수 #include #include using namespace std; int main() { string s; cin >> s; set set; st..
-
백준 2210 숫자판 점프 | DFS | C++[백준 알고리즘]/[C++] 2021. 3. 12. 10:14
이번 포스팅은 백준 2210번 숫자판 점프입니다. 아래 url를 클릭하시면 백준 사이트에서 문제를 볼 수 있습니다. www.acmicpc.net/problem/2210 2210번: 숫자판 점프 111111, 111112, 111121, 111211, 111212, 112111, 112121, 121111, 121112, 121211, 121212, 211111, 211121, 212111, 212121 이 가능한 경우들이다. www.acmicpc.net 기본 알고리즘 DFS (깊이 우선 탐색) 참고 line 46-47 벡터의 중복 원소 제거 C++ vector 중복 원소 삭제 1. unique 함수 unique 함수는 vector에서 중복되지 않는 원소들을 앞에서부터 채워나가는 함수 (algorithm ..
-
백준 1620 나는야 포켓몬 마스터 이다솜 | C++[백준 알고리즘]/[C++] 2021. 3. 11. 13:41
이번 포스팅은 백준 1620번 나는야 포켓몬 마스터 이다솜입니다. 아래 url를 클릭하시면 백준 사이트에서 문제를 볼 수 있습니다. www.acmicpc.net/problem/1620 1620번: 나는야 포켓몬 마스터 이다솜 첫째 줄에는 도감에 수록되어 있는 포켓몬의 개수 N이랑 내가 맞춰야 하는 문제의 개수 M이 주어져. N과 M은 1보다 크거나 같고, 100,000보다 작거나 같은 자연수인데, 자연수가 뭔지는 알지? 모르면 www.acmicpc.net 기본 알고리즘 unordered_map (hash_map) 참고 백준에서 hash_map 사용시 컴파일 에러가 발생한다. hash_map → unordered_map 으로 변경하면 해결된다. 전체 코드 1 2 3 4 5 6 7 8 9 10 11 12 1..