본문 바로가기

전체보기272

[백준 2251] 물통 물통의 갯수는 세개이고 물통의 크기는 1부터 200까지이다. 이때 물통의 갯수가 세개이기 때문에 모든 경우를 고려한 BFS 알고리즘을 사용하여 A 물통이 비어있을 때, C의 물통에 담겨 있는 물의 양을 출력하면 된다. 모든 경우라고 해봤자. 총 6가지이다1. A -> B 2. A -> C3. B -> A4. B -> C5. C -> A6. C -> B ( 각각의 모든 경우는, 옮기려는 물들이 옮기려는 곳의 최대 용량보다 많은지 검사를 해야한다.)음수가 나오므로 불 필요한 연산을 하지 않기 위해서 1. 임의로 만든 water 구조를 사용하여, 저장 및 사용이 편리하도록 Queue을 사용하였다. 2. 방문 여부를 확인 하기 위해서 bool visit[][][]를 작성하였다. 출처 : https://www.a.. 2019. 4. 25.
[백준 9019] DSLR 시간 초과를 넘기지 않도록 주의하여 구현해야 하는 BFS 문제이다. 주어진 시간이 짧지는 않지만 (6초) queue 식으로 구현을 하면, 문제 특성상 string이 복사가 일어난다. 따라서 어마어마한 시간이 지연이 될 수 있다. (저는 그랬어요 ㅠ) 시간을 줄이기 위해서, 가급적 if문과 배열을 사용하였고, vector 컨테이너를 사용하여 탐색을 진행 하였다. 주의해야 할 점은, 시작 루트(from)에서 도착 루트(to)로 향할 때 순서대로 필요한 명령어를 출력해야 하기 때문에 시간 복잡도 상, 시작 -> 도착 순으로 하나씩 검색을 하면 Big-O 표기법으로 제곱 혹은 그 이상이다. ( 애초에 BFS 접근을 하기 때문에 도착하기 전에는 어디가 최단거리인지 알 수가 없다) ( 즉, 미리 저장이 불가능하다 .. 2019. 4. 24.
[백준1963] 소수 경로 정답률이 높았지만, 다른 정답률이 높은 문제들에 비해서 긴 소스코드를 작성해야 하는 문제였습니다. BFS와 에라토스테네스의 체의 개념을 확실하게 알고 있어야 풀 수 있는 문제입니다. ( BFS로 푸는 이유 => 모든 간선의 비용이 1이다 )저 같은 경우는, 하나의 큐와 1부터 10000까지 배열을 2개 만들어 queue q는 BFS 접근을 하기 위하여 사용하였고 int visit [10000] 배열은 방문 여부를 확인하는 배열이며, 값은 소수 변환에 필요한 횟수를 가지게 구현하고 bool c [10000] 배열은 소수인지 아닌지 확인하는 배열을 구현하였습니다. 추가적으로는 배열이 아닌 struct { int a, bool b} 혹은 vector c 컨테이너를 사용하여 충분히 풀 수 있는 문제입니다. 출처.. 2019. 4. 23.
[C++] 소수 구하기 (에라토스테네스의 체) 보통 소수라 하면, 1과 자기자신을 제외하고는 나누어 떨어지지 않는 수라고 불린다.이를 구하기 위해서 하나 하나씩 나누어 떨어지는 지 검사를 하고는 했는데 더 빠르게 구할 수 있는 방법이 있다. 바로'에라토스테네스의 체' 라는 알고리즘을 사용하는 것이다. 에라토스테네스의 체는, 미리 범위를 정하여 소수인지 아닌지 구하여배열에 저장을 한 뒤에, 일반적으로 사용이 된다. 로직은 다음과 같다. 1은 소수가 아니다. 2는 소수이다. -> 2의 배수는 소수가 아니다.3은 소수이다. -> 3의 배수는 소수가 아니다.4는 소수가 이미 아니다.5는 소수이다. -> 5의 배수가 소수가 아니다.... (반복) 식으로 구현이 가능하며, boolean 값을 가지는 check 배열을 사용하여반복문을 돌려준다. 1. 1의 소수가.. 2019. 4. 22.
[백준 1697] 숨바꼭질 Queue를 사용한 BFS의 개념을 알고 있다면쉽게 풀 수 있는 문제이다. 수빈이가 동생을 찾기 위해서 몇 번을 이동하는지 구하는 문제인데,이동 할 수 있는 경로가 오직 세 가지 경우( now = 현재위치)1. now - 12. now + 13. now * 2밖에 없어서 배열을 사용하여 간단하게 구현이 가능하다. (이때 수빈이와 동생의 위치가 같을 경우 '0'을 출력하는 경우를 예외로 처리해야한다) 출처 : https://www.acmicpc.net/problem/1697 문제 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 때 걷.. 2019. 4. 22.
[C++] next_permutation을 사용한 조합 만들기 순열을 사용하여 조합을 만들어내는 방법입니다. 로직을 설명하면 vector 를 2개를 선언하고 하나는 원소를 삽입하는 vector list를 또 다른 하나는 순서 제어를 위해서 next_permutation을 사용할 vector idx를 만듭니다. 이어서 몇 개의 원소를 뽑을지 결정하는 변수 r 만큼 idx에 1을 list의 크기 (n이라고 하겠습니다) - r 만큼 idx에 0을 넣습니다. 그 뒤로 idx를 next_permutation을 사용하여 반복하여 idx의 원소가 1일 때마다 list의 원소를 출력해주면 됩니다. 저는 내림차순으로 출력하기 위해서 desc라는 함수를 따로 작성하였습니다. 소스코드 12345678910111213141516171819202122232425262728293031323.. 2019. 4. 21.

티스토리툴바