Archive: 2018

2018
0
computer sciencealgorithms

백준[1963] - 소수 경로

문제백준 1963 문제 보기 접근 방법에라토스테네스의 채를 이용해서 1000에서 10000까지의 모든 소수를 구해 놓고 문제를 접근했다. 그 이후 입력된 숫자를 각 자리별로 배열에 담아 bfs로 자릿수를 바꿔 소수인지 아닌지를 판별했다. 코드#include <iostream> #include <cstring> #include <string

0
computer sciencealgorithms

백준[10971] - 외판원 순회 2

문제백준 10971 문제 보기 접근 방법각 점마다 모든 점을 순회하고 다시 출발했던 점으로 돌아오는 것으로 종료 시점을 잡으면 dfs로 문제를 풀 수 있다. 코드#include <iostream> #include <cstring> using namespace std; int N; int arr[15][15]; int visited[15];

0
computer sciencealgorithms

백준[1697] - 숨바꼭질

문제백준 1697 문제 보기 접근 방법숨박꼭질 문제는 좌표 값이 10만까지 있어 이를 dfs를 활용해 문제를 풀 경우 시간초과가 날수 있다. 따라서 최소값을 구하는데 편리한 bfs를 활용하면 문제를 쉽게 풀 수 있다. -1을 한 경우. +1을 한 경우. *2를 한 경우. 다음과 같이 모든 경우를 나누어 큐에 넣어주면 된다. 코드#include <io

0
computer sciencealgorithms

백준[1107] - 리모컨

문제백준 1107 문제 보기 접근 방법완전 탐색 방법을 활용해 문제를 풀었다. 모든 키의 조합을 활용해 최소한의 버튼 클릭을 구하는 방법이다. +, -로 이동하는 경우. 숫자 키로만 이동하는 경우. 위 두가지를 조합하여 이동하는 경우. 다음과 같은 조합을 적절히 활용해 정답을 구할 수 있다. 일단 +와 -로만 이동이 가능 한 경우는 단순한 계산으로 처리

0
computer sciencealgorithms

백준[1722] - 순열의 순서

문제백준 1722 문제 보기 접근 방법순열의 길이가 큰 관계로 최대 20!의 값을 가진다. 즉, 모든 경우를 해보면서 답을 출력하기는 적절하지 않다. 따라서 약간의 수학적 접근으로 문제를 해결한다.순열의 길이가 10이라고 가정을 한다면 {1, 2, 3, …}, {1, 3, 2, …}, {1, 4, 2, …} 이런식으로 올 수 있는 경우의 수가 9!이다. 따

0
computer sciencealgorithms

백준[10974] - 모든 순열

문제백준 10974 문제 보기 접근 방법n이 작은 관계로 next_permutation을 이용해서 모든 순열을 구할 수 있다. 코드#include <iostream> #include <algorithm> #include <vector> using namespace std; int n; vector<int> a(n); int