목록알고리즘 문제 풀이/BOJ (77)

영벨롭 개발 일지

[백준 BOJ][C++]10971번 원판원 순회2 풀이: DFS or next_permutation()

https://www.acmicpc.net/problem/10971 10971번: 외판원 순회 2 첫째 줄에 도시의 수 N이 주어진다. (2 ≤ N ≤ 10) 다음 N개의 줄에는 비용 행렬이 주어진다. 각 행렬의 성분은 1,000,000 이하의 양의 정수이며, 갈 수 없는 경우는 0이 주어진다. W[i][j]는 도시 i에서 j www.acmicpc.net 이 문제는 DFS 또는 next_permutation() 함수를 사용해서 해결할 수 있습니다. dfs로 아직 방문하지 않은 도시를 방문하는 과정은 순열을 만드는 과정과 동일한데요! 때문에 dfs를 직접 구현해도 되지만 next_permutation() 함수로 좀 더 쉽게 해결할 수 있습니다. [풀이 과정] 1. 도시 0번부터 n-1번까지 dfs를 호출 ..
알고리즘 문제 풀이/BOJ 2022. 4. 1. 13:11
[백준 BOJ][C++]9375번 패션왕 신해빈 풀이: hash

https://www.acmicpc.net/problem/9375 9375번: 패션왕 신해빈 첫 번째 테스트 케이스는 headgear에 해당하는 의상이 hat, turban이며 eyewear에 해당하는 의상이 sunglasses이므로 (hat), (turban), (sunglasses), (hat,sunglasses), (turban,sunglasses)로 총 5가지 이다. www.acmicpc.net 이 문제는 c++ STL map 컨테이너로 쉽게 해결할 수 있지만, 저는 해시 맵을 직접 구현해서 해결해보았습니다! size는 hashing의 원소의 개수, 즉 카테고리의 수 입니다. hashing은 의상의 종류 category를 저장하는 string 배열입니다. data는 hashing에서 categor..
알고리즘 문제 풀이/BOJ 2022. 3. 31. 17:27
[백준 BOJ][C++]10819번 차이를 최대로 풀이: std::next_permutation()

https://www.acmicpc.net/problem/10819 10819번: 차이를 최대로 첫째 줄에 N (3 ≤ N ≤ 8)이 주어진다. 둘째 줄에는 배열 A에 들어있는 정수가 주어진다. 배열에 들어있는 정수는 -100보다 크거나 같고, 100보다 작거나 같다. www.acmicpc.net https://iridescent-zeal.tistory.com/97 [C++]순열 next_permutation STL 사용하기 순열(permutation)은 서로 다른 n개의 원소에서 r개를 뽑아 한 줄로 세우는 경우의 수를 표현할 수 있습니다. C++ STL을 사용하여 순열을 쉽게 표현할 수 있습니다. 헤더파일 #include 기본형 bool next_ iridescent-zeal.tistory.com #..
알고리즘 문제 풀이/BOJ 2022. 3. 31. 16:09
[백준 BOJ][C++]10972번 다음 순열 풀이: std::next_permutation()

https://www.acmicpc.net/problem/10972 10972번: 다음 순열 첫째 줄에 입력으로 주어진 순열의 다음에 오는 순열을 출력한다. 만약, 사전순으로 마지막에 오는 순열인 경우에는 -1을 출력한다. www.acmicpc.net 이 문제는 c++ STL next_permutation을 사용하면 쉽게 해결할 수 있습니다. next_permutation 사용법 -> https://iridescent-zeal.tistory.com/97 #include #include #include using namespace std; int main(void) { vector arr; int N; cin >> N; for (int i = 0; i > x; a..
알고리즘 문제 풀이/BOJ 2022. 3. 31. 15:43
[백준 BOJ][C++]15663번 N과 M(9) 풀이: 브루트 포스 & DFS

https://www.acmicpc.net/problem/15663 15663번: N과 M (9) 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해 www.acmicpc.net 이 문제는 기존 N과 M 문제와 크게 다르지 않습니다. 다만 입력으로 주어지는 N개의 수에 중복되는 수가 있다는 것 인데요. 변수 하나만 추가하면 해결할 수 있습니다. 입력으로 주어지는 수열을 sort() 함수를 통해 오름차순 정렬하면 작은 수 부터 차례대로 DFS를 수행하겠죠? 이때 동일한 수열이 나오지 않게 하기 위해선 해당 노드에서 동일한 자식 노드를 두 번 이상 생성하면 안 됩니다. 예시..
알고리즘 문제 풀이/BOJ 2022. 3. 29. 16:23
[백준 BOJ][C++]13023번 ABCDE 풀이: 그래프 & DFS

https://www.acmicpc.net/problem/13023 13023번: ABCDE 문제의 조건에 맞는 A, B, C, D, E가 존재하면 1을 없으면 0을 출력한다. www.acmicpc.net 이 문제는 그래프 문제로, DFS 로 해결할 수 있습니다. 그래프 생성 후, depth가 5인 경로를 찾기만 하면 되는데요! 처음엔 인접 행렬로 그래프를 구현하였는데 시간 초과가 떴습니다 ㅠㅠ 아마 인접 행렬은 검사하지 않아도 될 녀석들도 검사해서 그런 것 같아요. 때문에 인접 리스트로 그래프를 구현한 결과 시간초과가 뜨지 않고 성공했습니다! 추가로 depth가 5인 경로를 찾기만 하면 그 즉시 탐색을 끝내고 1을 출력하면 되기 때문에 depth가 5인 경로를 찾았음을 나타내는 변수 flag를 선언하여..
알고리즘 문제 풀이/BOJ 2022. 3. 28. 18:18
이전 Prev 1 2 3 4 5 6 7 8 ··· 13 Next 다음