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

영벨롭 개발 일지

[백준 BOJ][C++]15650번 N과 M(2) 풀이: 브루트 포스 & DFS

https://www.acmicpc.net/problem/15650 15650번: N과 M (2) 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해 www.acmicpc.net 이 문제는 15649번 N과 M(1) 풀이와 매우 유사합니다. (풀이: https://iridescent-zeal.tistory.com/86) 하나만 바꾸어 주면 되는데요! dfs 함수에 현재 노드의 수를 나타내는 인자를 추가하여 해당 노드 보다 큰 수에 대해서만 자식 노드를 탐색하면 간단하게 풀립니다. #include #include #include #include #include #inclu..
알고리즘 문제 풀이/BOJ 2022. 3. 28. 16:43
[백준 BOJ][C++]15649번 N과 M(1) 풀이: 브루트 포스 & DFS

https://www.acmicpc.net/problem/15649 15649번: N과 M (1) 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해 www.acmicpc.net 이 문제는 브루트 포스 문제로 명시되어 있지만 DFS를 사용하여 해결할 수 있습니다. 작은 수부터 차례대로 수를 트리 형태로 나타낼 수 있는데요. DFS 를 쓰고 싶게 생기지 않았나요! ㅎㅎ 작은 수 부터 순차적으로 탐색하여 depth를 증가시켜 가며 탐색하면 됩니다. 이때 탐색 과정에서 visit을 true로 해주어 중복이 안되게 해야합니다. 다만 해당 노드의 자식 노드의 탐색이 끝나고 난 뒤..
알고리즘 문제 풀이/BOJ 2022. 3. 28. 16:37
[백준 BOJ][C++]13913번 숨바꼭질 4 풀이: BFS

https://www.acmicpc.net/problem/13913 13913번: 숨바꼭질 4 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 www.acmicpc.net 이 문제는 BFS를 사용하여 해결할 수 있습니다. 먼저 BFS 탐색을 하면서 queue에 push할 node 구조체를 정의하겠습니다. loc은 해당 노드의 위치, *parent는 부모 노드의 link입니다. generated[MAX] 배열은 탐색 과정에서 생성된 노드를 체크할 배열입니다. generated[n] = true 라면 n 위치 노드는 이미 생성되었다는 ..
알고리즘 문제 풀이/BOJ 2022. 3. 24. 20:54
[백준 BOJ][C++]1748번 수 이어 쓰기 1 풀이

https://www.acmicpc.net/problem/1748 1748번: 수 이어 쓰기 1 첫째 줄에 N(1 ≤ N ≤ 100,000,000)이 주어진다. www.acmicpc.net N - 1 + 1 : 1부터 N까지의 수 중, 1의 자리 수를 갖고 있는 수의 개수 N - 10 + 1 : 1부터 N까지의 수 중, 10의 자리 수를 갖고 있는 수의 개수 N - 100 + 1 : 1부터 N까지의 수 중, 100의 자리 수를 갖고 있는 수의 개수 ... #include using namespace std; int main(void) { int N; int cnt = 0; cin >> N; if (N < 10) { cout
알고리즘 문제 풀이/BOJ 2022. 3. 24. 18:18
[백준 BOJ][C++]6064번 카잉 달력 풀이: 브루트 포스

https://www.acmicpc.net/problem/6064 6064번: 카잉 달력 입력 데이터는 표준 입력을 사용한다. 입력은 T개의 테스트 데이터로 구성된다. 입력의 첫 번째 줄에는 입력 데이터의 수를 나타내는 정수 T가 주어진다. 각 테스트 데이터는 한 줄로 구성된다. www.acmicpc.net [풀이 과정] 1. 멸망년도인 m과 n의 최소공배수를 구한다. 2. 로 표현되는 해 i를 x값으로 초기화 한다. 3. (i - 1)%n + 1 == y를 만족하는지 검사한다. 4. 최소공배수에 도달하거나 위 조건을 만족할 때까지 i 에 m 값을 더해 3~4 과정을 반복한다. 5. i가 최소 공배수보다 크다면 유효하지 않은 해이고, 그렇지 않다면 i를 출력한다. #include #include usin..
알고리즘 문제 풀이/BOJ 2022. 3. 24. 17:05
[백준 BOJ][C++]1655번 가운데를 말해요 풀이: Heap

https://www.acmicpc.net/problem/1655 1655번: 가운데를 말해요 첫째 줄에는 백준이가 외치는 정수의 개수 N이 주어진다. N은 1보다 크거나 같고, 100,000보다 작거나 같은 자연수이다. 그 다음 N줄에 걸쳐서 백준이가 외치는 정수가 차례대로 주어진다. 정수는 -1 www.acmicpc.net 이 문제는 최대 힙, 최소 힙 두 개 모두를 사용하여 해결해야 합니다. 중앙값을 기준으로 중앙값 이하의 수들은 최대 힙에, 중앙값보다 큰 수들은 최소 힙에 저장하고 이때의 중앙값은 최대 힙의 top 원소가 됩니다. 힙에 원소를 삽입할 때, 최대 힙과 최소 힙의 원소 개수가 같다면 최대 힙에, 그렇지 않다면 최소 힙에 삽입합니다. 이때 최대 힙과 최소 힙은 중앙값을 기준으로 나누었기..
알고리즘 문제 풀이/BOJ 2022. 3. 23. 18:49
이전 Prev 1 ··· 3 4 5 6 7 8 9 ··· 13 Next 다음