전체 글
-
[백준 1697] 숨바꼭질알고리즘/백준 2019. 4. 22. 02:29
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일 때 걷..
-
[C++] next_permutation을 사용한 조합 만들기C_C++ 프로그래밍/C_C++ 프로그래밍 2019. 4. 21. 21:28
순열을 사용하여 조합을 만들어내는 방법입니다. 로직을 설명하면 vector 를 2개를 선언하고 하나는 원소를 삽입하는 vector list를 또 다른 하나는 순서 제어를 위해서 next_permutation을 사용할 vector idx를 만듭니다. 이어서 몇 개의 원소를 뽑을지 결정하는 변수 r 만큼 idx에 1을 list의 크기 (n이라고 하겠습니다) - r 만큼 idx에 0을 넣습니다. 그 뒤로 idx를 next_permutation을 사용하여 반복하여 idx의 원소가 1일 때마다 list의 원소를 출력해주면 됩니다. 저는 내림차순으로 출력하기 위해서 desc라는 함수를 따로 작성하였습니다. 소스코드 12345678910111213141516171819202122232425262728293031323..
-
[백준 6603] 로또알고리즘/백준 2019. 4. 21. 20:57
처음에 순열문제라서 간단하게 STL의 next_permutation을 사용하면 되는 줄 알았지만, (수정. 사용할 수 있습니다) DFS나 재귀 혹은 반복을 사용하면 되는 문제였다. 간단하게 반복문을 사용하여, 풀은 문제이다. (수정)문제풀이 1. (재귀호출)문제풀이 2. (next_permutation을 사용한 조합) 출처 : https://www.acmicpc.net/problem/6603 문제 독일 로또는 {1, 2, ..., 49}에서 수 6개를 고른다.로또 번호를 선택하는데 사용되는 가장 유명한 전략은 49가지 수 중 k(k>6)개의 수를 골라 집합 S를 만든 다음 그 수만 가지고 번호를 선택하는 것이다.예를 들어, k=8, S={1,2,3,5,8,13,21,34}인 경우 이 집합 S에서 수를 고..
-
[백준 10971] 외판원 순회2알고리즘/백준 2019. 4. 17. 21:53
정답률이 높지는 않았지만, 그렇다고 어렵지는 않았던 문제입니다. C++에서는 next_permutation을 사용하면 쉽게 구현할 수 있는 문제입니다. 4 0 10 15 20 5 0 9 10 6 13 0 12 8 8 9 0 인 경우 크기가 n= 4인 임시 벡터를 사용하여 모든 경우의 수를 비교하게 하였습니다. 마지막 노드에서 시작 노드로 돌아올 때는 시작 노드 start와 마지막 n-1 인덱스의 가중치를 더하여 가장 작은 비용을 출력하도록 구현하였습니다. 출처 : https://www.acmicpc.net/problem/10971 문제 외판원 순회 문제는 영어로 Traveling Salesman problem (TSP) 라고 불리는 문제로 computer science 분야에서 가장 중요하게 취급되는 문..
-
[백준 2261] 가장 가까운 두 점알고리즘/백준[분발!] 2019. 4. 2. 01:05
https://www.acmicpc.net/problem/2261 2261번: 가장 가까운 두 점 첫째 줄에 자연수 n(2 ≤ n ≤ 100,000)이 주어진다. 다음 n개의 줄에는 차례로 각 점의 x, y좌표가 주어진다. 각각의 좌표는 절댓값이 10,000을 넘지 않는 정수이다. 같은 점이 여러 번 주어질 수도 있다. www.acmicpc.net 문제도 어렵고, 정답률도 끔찍하게 낮았던 문제이다. 현재 mergeSort를 사용하여, 왼쪽 오른쪽의 최소 거리를 구했지만. 왼쪽과 오른쪽을 거치는 최소거리를 구하는데 실패 머리가 아파, 다음에 풀어야겠다.
-
[C++] 삽입 정렬 (Insertion Sort)C_C++ 프로그래밍/C_C++ 프로그래밍 2019. 4. 1. 23:20
삽입 정렬은 배열을 그룹을 두 개로 나누어 E = {5,4,3,2,1} 이 있다고 하면 {5}를 key로 두고, 이보다 작은 index을 확인하여, 삽입하는 정렬 방법이다. 그 다음의 key는 4... 3.. 2 .. 1 순이다. 아래 소스에서는 j를 유심히 잘 봐야 한다. #include using namespace std; int main(){ int size,i,j; cin >> size; int *arr = new int[size]; for(i = 0; i > arr[i]; for(i = 0; i = 0; j--){ if(key >= arr[j]) break; arr[j+1] = ..
-
[C++] 버블 정렬(Bubble Sort)C_C++ 프로그래밍/C_C++ 프로그래밍 2019. 4. 1. 22:49
버블 정렬은 인접한 원소들을 교환하며, 이 모습이 흡사 거품들이 뾰로록 일어나는 것과 같다고 하여, Bubble Sort라고 불립니다. (교환 정렬이라고도 불립니다. Exchange Sort) ...더보기 이해 E[5] = {95, 75, 85, 100, 75}이며 이를 오름차순으로 정렬한다면. (95, 75), 85, 100, 50 => 75, 95, 85, 100, 50 75, (95, 85), 100, 50 => 75, 85, 95, 100, 50 75, 85, (95, 100), 50 => 75, 85, 95, 100, 50 75, 85, 95, (100, 50) => 75, 85, 95, 50, 100 자, 여기에서 마지막 요소가 배열의 최댓값으로 들어갔습니다. (75, 85), 95, 50, ..