본문 바로가기
반응형

Programming Solve/BOJ60

BOJ 1697 - 숨바꼭질 / C++ 문제 링크 : https://www.acmicpc.net/problem/1697 1697번: 숨바꼭질 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 www.acmicpc.net 문제 풀이 요약하면, 현재 위치 n에서 k까지 갈 때 x+1, x-1, 2*x 중 한 가지 과정을 거쳐서 갈 수 있으며 최소 시간(카운트)을 구하면 되는 문제이다. 잠시 DFS와 BFS의 개념을 살펴보면 DFS는 아래의 그림처럼 현재 branch를 최대한 깊이 탐색한 후 다음 branch를 탐색하는 방식이며 BFS는 아래의 그림처럼 인접 노드를 모두 탐색한.. 2022. 2. 12.
BOJ 1260 - DFS와 BFS / C++ 문제 링크 : https://www.acmicpc.net/problem/1260 1260번: DFS와 BFS 첫째 줄에 정점의 개수 N(1 ≤ N ≤ 1,000), 간선의 개수 M(1 ≤ M ≤ 10,000), 탐색을 시작할 정점의 번호 V가 주어진다. 다음 M개의 줄에는 간선이 연결하는 두 정점의 번호가 주어진다. 어떤 두 정점 사 www.acmicpc.net 문제 설명 주석으로 대체 소스 코드 #include #include #include using namespace std; const int MAX = 1001; int N, M, V; //정점, 간선, 탐색 시작 번호 int adjacent[MAX][MAX]; bool visited[MAX]; queue q; void DFS(int idx) {/.. 2022. 2. 10.
BOJ 1991 - 트리 순회 / C++ 문제 링크 : https://www.acmicpc.net/problem/1991 1991번: 트리 순회 첫째 줄에는 이진 트리의 노드의 개수 N(1 ≤ N ≤ 26)이 주어진다. 둘째 줄부터 N개의 줄에 걸쳐 각 노드와 그의 왼쪽 자식 노드, 오른쪽 자식 노드가 주어진다. 노드의 이름은 A부터 차례대로 알파 www.acmicpc.net 문제 풀이 저번 포스트에서 map을 이용하여 트리를 구현하는 법을 알아보았다. 트리 구조 - 개념 및 예제 트리 구조 트리 구조는 정보의 항목들이 가지(branch)로 연결될 수 있도록 하는 자료 구조이다. 트리를 이해하고 구현하려면 아래의 용어들을 이해해야 한다. 우선, A-C 노드의 관계를 보면 A를 부 appdevorsec.tistory.com 이를 이용하여 트리를 .. 2022. 2. 2.
C++ - 소수 판별 / 단순 브루트포스, 에라토스테네스의 체 문제 1 : https://www.acmicpc.net/problem/2581 2581번: 소수 M이상 N이하의 자연수 중 소수인 것을 모두 찾아 첫째 줄에 그 합을, 둘째 줄에 그 중 최솟값을 출력한다. 단, M이상 N이하의 자연수 중 소수가 없을 경우는 첫째 줄에 -1을 출력한다. www.acmicpc.net 해당 문제는 범위가 10,000 이하의 자연수이며 시작값과 끝값 중에 존재하는 소수를 모두 더한 값과 최솟값을 출력하면 된다. 따라서 단순 브루트포스로 isPrime 함수를 구현한다. 1과 n이 아닌 다른 값으로 나누어 떨어지면 false를 반환, 그렇지 않다면 소수이므로 true를 반환한다. 이렇게 소수를 판별할 수 있고, 소수로 판별된 값은 total에 모두 더하며 최솟값을 계속 갱신해준다... 2021. 10. 12.
반응형

티스토리툴바