본문 바로가기

전체보기272

[백준 6603] 로또 처음에 순열문제라서 간단하게 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에서 수를 고.. 2019. 4. 21.
[백준 10971] 외판원 순회2 정답률이 높지는 않았지만, 그렇다고 어렵지는 않았던 문제입니다. 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 분야에서 가장 중요하게 취급되는 문.. 2019. 4. 17.
[백준 10819] 차이를 최대로 n의 제한이 3 n; vector a; // 오름차순 정렬 for(int i = 0; i > tmp; a.push_back(tmp); } sort(a.begin(),a.end()); do{ int tmp = 0; for(int i = 0; i 2019. 4. 16.
[백준 2261] 가장 가까운 두 점 https://www.acmicpc.net/problem/2261 2261번: 가장 가까운 두 점 첫째 줄에 자연수 n(2 ≤ n ≤ 100,000)이 주어진다. 다음 n개의 줄에는 차례로 각 점의 x, y좌표가 주어진다. 각각의 좌표는 절댓값이 10,000을 넘지 않는 정수이다. 같은 점이 여러 번 주어질 수도 있다. www.acmicpc.net 문제도 어렵고, 정답률도 끔찍하게 낮았던 문제이다. 현재 mergeSort를 사용하여, 왼쪽 오른쪽의 최소 거리를 구했지만. 왼쪽과 오른쪽을 거치는 최소거리를 구하는데 실패 머리가 아파, 다음에 풀어야겠다. 2019. 4. 2.
[C++] 삽입 정렬 (Insertion Sort) 삽입 정렬은 배열을 그룹을 두 개로 나누어 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] = .. 2019. 4. 1.
[C++] 버블 정렬(Bubble Sort) 버블 정렬은 인접한 원소들을 교환하며, 이 모습이 흡사 거품들이 뾰로록 일어나는 것과 같다고 하여, 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, .. 2019. 4. 1.

티스토리툴바