[백준 알고리즘]
-
백준 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..
-
백준 2583 영역 구하기 | BFS | C++[백준 알고리즘]/[C++] 2021. 3. 11. 13:30
이번 포스팅은 백준 2583번 영역 구하기입니다. 아래 url를 클릭하시면 백준 사이트에서 문제를 볼 수 있습니다. www.acmicpc.net/problem/2583 2583번: 영역 구하기 첫째 줄에 M과 N, 그리고 K가 빈칸을 사이에 두고 차례로 주어진다. M, N, K는 모두 100 이하의 자연수이다. 둘째 줄부터 K개의 줄에는 한 줄에 하나씩 직사각형의 왼쪽 아래 꼭짓점의 x, y좌표값과 오 www.acmicpc.net 기본 알고리즘 BFS (너비 우선 탐색) 전체 코드 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 41 42 43 44 45 ..
-
1987번 알파벳 | DFS | 백준 5014 C++ 코드[백준 알고리즘]/[C++] 2021. 3. 9. 10:32
이번 포스팅은 백준 1987번 알파벳입니다. 아래 url를 클릭하시면 백준 사이트에서 문제를 볼 수 있습니다. www.acmicpc.net/problem/1987 1987번: 알파벳 세로 R칸, 가로 C칸으로 된 표 모양의 보드가 있다. 보드의 각 칸에는 대문자 알파벳이 하나씩 적혀 있고, 좌측 상단 칸 (1행 1열) 에는 말이 놓여 있다. 말은 상하좌우로 인접한 네 칸 중의 한 칸으 www.acmicpc.net 기본 알고리즘 DFS 깊이 우선 탐색 백트래킹 전체 코드 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 41 42 43 44 45 46 47 4..
-
5014번 스타트링크 | BFS | 백준 5014 C++ 코드[백준 알고리즘]/[C++] 2021. 3. 3. 11:18
이번 포스팅은 백준 5014번 스타트링크입니다. 아래 url를 클릭하시면 백준 사이트에서 문제를 볼 수 있습니다. www.acmicpc.net/problem/5014 5014번: 스타트링크 첫째 줄에 F, S, G, U, D가 주어진다. (1 ≤ S, G ≤ F ≤ 1000000, 0 ≤ U, D ≤ 1000000) 건물은 1층부터 시작하고, 가장 높은 층은 F층이다. www.acmicpc.net 기본 알고리즘 최단 거리 = BFS (너비 우선 탐색) 전체 코드 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 41 42 43 44 45 46 47 48 49..