목록Algorithm (35)
지나공 : 지식을 나누는 공간
백준 점 모으기 문제링크 www.acmicpc.net/problem/7571 7571번: 점 모으기 첫 줄에는 격자공간의 크기와 점들의 개수를 나타내는 두 정수 N과 M이 하나의 공백을 사이에 두고 주어진다. 다음의 M줄에는 각 줄마다 격자공간내의 점의 위치를 나타내는 두 개의 정수가 하나 www.acmicpc.net 완전탐색으로 빠르게 풀면서도 뭔가 의심스러웠다... 이렇게 간단하다고..? 역시나ㅎ 시간초과였다. 찾아보니 중간값으로 해결해야 한다는데 그 이유를 기록하고자 한다, 먼저, 완전탐색으로 푼 시간 초과 코드는 아래와 같다. #include #include using namespace std; int n, m, ans; vectorv; void init() { cin >> n >> m; for ..
문제링크 : www.acmicpc.net/problem/4796 4796번: 캠핑 입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스는 한 줄로 이루어져 있고, L, P, V를 순서대로 포함하고 있다. 모든 입력 정수는 int범위이다. 마지막 줄에는 0이 3개 주어진다. www.acmicpc.net 주석 없는 코드 #include using namespace std; int l, p, v,i; int main() { do { i++; cin >> l >> p >> v; if (l == 0 && p == 0 && v == 0) break; int ans = (v / p) * l + min(v % p, l); cout
www.acmicpc.net/problem/1759 1759번: 암호 만들기 첫째 줄에 두 정수 L, C가 주어진다. (3 ≤ L ≤ C ≤ 15) 다음 줄에는 C개의 문자들이 공백으로 구분되어 주어진다. 주어지는 문자들은 알파벳 소문자이며, 중복되는 것은 없다. www.acmicpc.net next_permutation으로 조합을 구현했다. 주석 없는 코드 #include #include #include #include using namespace std; int main() { vector v; vectorpick; int l, c; cin >> l >> c; for (int i = 0; i > x; v.push_back(x); pick.push_back(..
오늘 알아볼 내용은, 순차 탐색 이진 탐색 트리 자료구조 이진 탐색 트리 실전문제 - 부품 찾기 실전문제 - 떡볶이 떡 만들기 순차 탐색 [개념] 가장 기본 탐색 방법으로, 배열 안에 있는 특정한 데이터를 찾기 위해 앞에서부터 데이터를 하나씩 차례대로 확인하는 탐색 알고리즘이다. 이름처럼, 순차로 데이터를 탐색한다. [사용예] - 배열에 특정 값의 원소가 있는지 체크할 때 - 배열 자료형에서 특정한 값을 가지는 원소의 개수를 셀 때 [코드] #include #include #include using namespace std; int sequantialSearch(int n, string target, vector arr) { //모든 원소 하나씩 확인 for (int i = 0; i < n; i++) {..
띄어쓰기를 포함해서 원하는 글자 수 만큼 한줄로 한번에 입력받기 cin의 getline이나 fgets를 사용할 수 있는데 fgets가 좀 더 빠르다. 1. cin.getLine(저장할 문자열, 글자 수) #include #include using namespace std; int main() { char chars[10]; cin.getline(chars, 10); cout
알아볼 내용은, sort 기본 함수 알아보기 내림차순 정렬하기 특정 변수 기준으로 정렬하기 compare 함수 구현 연산자 오버로딩으로 구현 특정 변수 기준 내림차순 정렬하기 연산자 오버로딩 + compare 함수로 구현 compare 함수만 구현 정렬 방식은 퀵 정렬이다. 시간복잡도는 O(NlogN)이라고 레퍼런스에도 적혀 있다. www.cplusplus.com/reference/algorithm/sort/ sort 기본 함수 알아보기 sort의 인자로는 [배열의 시작주소]와 [배열의 마지막주소 + 1]이 들어간다. #include #include using namespace std; int main(void){ int a[10] = {9, 1, 4, 5, 8, 2, 7, 3, 6, 10}; sort(..
정렬이란? 데이터를 특정한 기준에 따라서 순서대로 나열하는 것 정렬이 되면 이진 탐색이 가능해진다. 선택정렬, 삽입정렬, 퀵정렬, 계수 정렬에 대하여 선택 정렬 [소개] 가장 원시적인 방법으로 매번 '가장 작은 것을 '선택'하는 정렬 [방법] 데이터가 무작위로 여러 개 있을 때, 이 중에서 가장 작은 데이터를 선택해 맨 앞에 있는 데이터와 바꾸고, 그 다음 작은 데이터를 선택해 앞에서 두 번째 데이터와 바꾸는 과정을 반복한다. [그림] [코드] #include using namespace std; int n = 5; //정렬할 개수 int arr[10] = { 7, 4, 5, 9. 8, 2, 1 }; int main(void) { for (int i = 0; i < n; i++) { int min_ind..
탐색(Search)? DFS/BFS? -> 많은 양의 데이터 중에서 원하는 데이터를 찾는 과정이 탐색 -> 탐색의 대표적인 예로 그래프 탐색 알고리즘은 DFS와 BFS가 있다. 이번 포스팅에서 알아볼 것 스택의 자료구조와 구현 큐의 자료구조와 구현 재귀함수(의미, 구현, 팩토리얼 구현으로 알아보는 재귀함수) 유클리드 호제법 with 재귀함수 DFS 동작과 구현 BFS 동작과 구현 스택(Stack) -> 마지막에 들어간 데이터가 먼저 빠져나오는 구조 -> LIFO (Last In First Out) 스택코드 구현 삽입(5) -> 삽입(2) -> 삽입(3) -> 삽입(7) -> 삭제() -> 삽입(1) -> 삽입(4) -> 삭제() 큐(Queue) -> 처음에 들어간 데이터가 먼저 빠져나오는 구조 -> FI..
이것이 코딩테스트다. chapter 4 구현 실전 문제 풀이 구현 문제는 어떤 문제? 머릿 속에 있는 알고리즘을 소스코드로 바꾸는 과정으로, 어떤 문제든 간에 해당이 될 수 있는 매우 넓은 범위의 유형이다. 구현 문제를 풀 때 생각할 점들 - 파이썬 기준 1초에 2000만 번의 연산 수행을 가정할 때 크게 무리가 없음 - 시간제한이 1초이고, 데이터 개수가 100만 개인 문제에서 N= 1,000,000이면 시간복잡도가 NlogN=20,000,000이므로 이정도의 데이터를 혀용한다고 생각하고 문제를 풀면 무리가 없을 것임 이제, 문제를 풀어보자. 1. 상하좌우 문제 문제) 여행가 A는 N*N의 크기의 정사각형 공간 위에 서 있다. 이 공간은 1*1 크기의 정사각형으로 나누어져 있다. 가장 왼 쪽 위 좌표는..
그리디 알고리즘이란? 현재 시점에서의 최적의 선택을 하는 알고리즘입니다. 전체 시점에서는 그게 가장 좋은 답이 아닐 수 있습니다. 매 시점마다 당장 그 시점에서의 최선의 답을 찾는 방식이기 때문입니다. 아래 그림에서 거치는 노드의 숫자 합이 가장 큰 선택을 해야 한다고 합시다. 우리 입장에선 전체 노드가 보이기 때문에 당연히 왼쪽처럼 선택을 해야 숫자 합이 0+3+100 = 103이 되므로 최적의 선택이 된다는 걸 압니다. 하지만 그리디한 선택은 당시에 위치하는 노드에서 바라볼 때 가장 큰 숫자로 가는 것이므로 오른쪽 그림처럼 선택하게 됩니다. 그리디한 선택을 한 결과(0+10+8 = 18)는 실제 최적의 답(103)보다 좋지 않은 답일 수 있습니다. 즉, 그리디 알고리즘에서 모든 선택이 최적의 선택과 ..