지나공 : 지식을 나누는 공간

programmers.co.kr/learn/courses/30/lessons/43164# 코딩테스트 연습 - 여행경로 [["ICN", "SFO"], ["ICN", "ATL"], ["SFO", "ATL"], ["ATL", "ICN"], ["ATL","SFO"]] ["ICN", "ATL", "ICN", "SFO", "ATL", "SFO"] programmers.co.kr 아악 내 반나절을 앗아간 문제..............너어어어어는 진짜.... 반나절을 앗아갔으므로 풀이를 해야 겠다. 나는 테스트 케이스 2번이 계속 통과가 안됐었는데, 찾아보니 반례가 아래 예제였다, ICN -> A, ICN -> B, B -> ICN 알파벳 순으로 가야 하니까 이걸 정렬해서 ICN 부터 들어가게 되면 ICN -> A로 ..

코드 순서는, dfs 백트래킹 순열 일반 순열 (주어진 원소를 모두 나열) 주어진 원소 중 원하는 개수를 뽑아서 순열 주어진 원소에 일부 중복된 원소가 있을 때 중복 허용하기 중복 제거하기 (같은 것이 있는 순열) next_permutation 순열 일반 순열 (주어진 원소를 모두 나열) 주어진 원소 중 원하는 개수를 뽑아서 순열 주어진 원소에 일부 중복된 원소가 있을 때 중복 허용하기 중복 제거하기 (같은 것이 있는 순열) dfs 백트래킹 조합 중복된 원소가 없는 조합 next_permutation 조합 중복된 원소가 없는 조합 중복순열과 중복조합 구현하기 dfs 백트래킹 순열 - 일반 순열 (주어진 원소를 모두 나열) #include #include using namespace std; vectorv..

문제링크 : 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

띄어쓰기를 포함해서 원하는 글자 수 만큼 한줄로 한번에 입력받기 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)보다 좋지 않은 답일 수 있습니다. 즉, 그리디 알고리즘에서 모든 선택이 최적의 선택과 ..

c언어에서는 보통 strcmp를 이용해서 문자열 두 개를 비교하지만, c++에서는 어떤 string내에서 원하는 string이 존재하는 지, 그 위치를 반환하는 함수를 사용할 수 있다. find() 함수이다.