코딩뚠뚠

풀이 일시 : 2020-07-28 ​ 퀵정렬 -> 피벗값을 설정하고 나눈다. 보통 첫번째 원소를 피벗으로 설정 -> 피벗값보다 큰 값을 왼쪽부터 찾고 피벗보다 작은값을 오른쪽부터 찾는다. -> 피벗값보다 작은값,큰값찾으면 : 작은값의 인덱스가 큰 값의 인덱스보다 크면 값끼리자리바꿈 -> 피벗값보다 작은값,큰값찾으면 : 작은값의 인덱스가 큰 값의 인덱스보다 작으면 피벗과 작은값 자리바꿈. 시간복잡도는 O(N*logN) ​ 문제 : 1 10 5 8 7 6 4 3 2 9 다음 숫자들을 오름차순으로 정렬하는 프로그램을 작성하시오 풀이 : #include int number = 10; int data[] = { 1, 10, 5, 8, 7, 6, 4, 3, 2, 9 }; void quickSort(int* data..

풀이 일시 : 2020-07-28 ​ 버블정렬 : ->인접한 두 원소를 검사하여 앞의 원소의 크기가 더 크다면 자리를 바꾼다. -> 처음 i가 0일때 실행한다면 인덱스의 맨 끝값이 가장 큰 값으로 설정될 것이다. -> i를 늘려가며 끝까지 실행하면 뒤에서부터 정렬이 완료 될 것이다. 시간복잡도는 O(N^2) ​ 문제 : 1 10 5 8 7 6 4 3 2 9 다음 숫자들을 오름차순으로 정렬하는 프로그램을 작성하시오 풀이 : #include int main() { int array[10] = { 1, 10, 5, 8, 7, 6, 4, 3, 2, 9 }; int temp,i,j; for (i = 0; i < 10; i++) { //0~9까지 증가해야한다. j = 0; for (j = 0; j < 9 - i; ..

풀이 일시 : 2020-07-28 ​ 문제 : 1 10 5 8 7 6 4 3 2 9 다음 숫자들을 오름차순으로 정렬하는 프로그램을 작성하시오 풀이 : -> 주어진 리스트 중 최소값을 찾는다 -> 그 값을 맨 앞에 위치한 값과 교체한다 -> 맨 앞 인덱스를 뺀 나머지 리스트에서 다음 과정을 반복한다. 시간복잡도는 O(N^2) #include int main(void) { int i, j, min, index, temp; int array[10] = { 1,10, 5, 8, 7, 6, 4, 3, 2,9 }; for (i = 0; i < 10; i++) { min = 9999; //9999보다 큰 값은 array 내에 없으므로 최소값을 9999로 초기화한다. for (j = i; j < 10; j++) {//..

투포인터 알고리즘 : 1차원 배열이 있고 이 배열에서 각자 다른 원소를 가리키고 있는 두개의 포인터를 조작해서 원하는 인덱스, 값을 얻는 방법 쓰는 이유 : 아래와 같은 문제를 투포인터로 풀이할 수 있다. BP로 풀게된다면 시간복잡도가 O(N^2)가 되어 시간초과가 날 수 있다. https://www.acmicpc.net/problem/2003 2003번: 수들의 합 2 첫째 줄에 N(1 ≤ N ≤ 10,000), M(1 ≤ M ≤ 300,000,000)이 주어진다. 다음 줄에는 A[1], A[2], …, A[N]이 공백으로 분리되어 주어진다. 각각의 A[x]는 30,000을 넘지 않는 자연수이다. www.acmicpc.net 사용 방법 : ​ 1. 포인터를 두 개 준비한다. left, right (초기..

set container 란 - 컨테이너 는 map, vector 등 여러가지가 있는데 set도 그 중 하나이다. - container 중 연관 컨테이너 (associative container) 이다. - 노드기반 컨테이너이며 균형이진트리로 구성되어있다. - key들로 이루어져있으며 중복이 허용되지 않는다. - key가 insert 되면 key는 자동으로 정렬되어 들어간다. - default는 less(오름차순) 이다. ​ 가장 큰 특징 : 중복을 없앤다 그래서 visit상태를 나타낼 때 사용되기도 한다. ​ ​ set 의 사용 #include 선언방법 set s; sets; 멤버함수 s.begin() //맨 첫번째 원소를 지칭 s.end() //맨 마지막원소를 가리키는 부분을 알 때 s.clear()..

백트래킹 (Backtraking) 이란 ​ 기본적으로 가능한 모든 방법을 탐색하기 위해 고안된 아이디어이다. 완전 탐색을 위해서는 DFS를 사용할 수 있다. DFS는 모든곳을 방문하기때문에 굳이 목표지점이 있지 않은 경로로 빠져서 자칫 비효율 적일 수도 있다. ​ 이런 비효율성을 개선하기 위해 옳지 않은 경로를 차단하고 목표지점에 갈수있는 가능성을 가진 루트만 검사하는 것이 백트래킹 알고리즘이다. DFS에 가지치기를 옳을 가능성이 높은 방향으로만 치게하는 것. ​ 프로그래밍에서 가지치기란 break 나 return 등 으로 구현할 수 있다. ​ ​ 예시1 이렇게 생긴 경로가 생성되어있다. 1에서 출발하여 문자열을 붙여가며 15에 도착했을때 "1 3 9 15"하는 것이 목표이다. ​ dfs를 실행하면 1-..

BF (brute force)란brute force 로 직역하면 '무식한 힘' 알고리즘이다. 가능한 모든 경우를 탐색하며 요구조건에 충족되는 결과만을 찾는다. 예외없이 100%의 확률로 정답을 출력한다.- 전체를 탐색하기 위해 탐색 알고리즘을 사용한다. 순차탐색, dfs, bfs를 도구로 이용한다.​​BF의 사용 예시10의 약수의 합을 구해보자-> 순차탐색을 이용해서 첫번째 원소부터 마지막 원소까지 탐색한다.-> 10의 약수가 되는 값만 남겨둔다. (10을 현재원소로 나누었을때 나눠떨어지면 10의 약수)-> sum+=i 로 모두 합쳐준다. int sum=0; n=10; for(int i=0; i

Dynamic Programing, DP, 동적프로그래밍, 동적계획법 으로 중요한 알고리즘 중 하나이다. DP란 큰 문제를 작은 문제로 나눠서 푸는 알고리즘이다. 방식은 분할정복과 같으나 분할정복은 계산한 부분문제를 단 한번만 쓰고 더이상 사용하지않는다. 그러나 동적프로그래밍에서는 계산한부분을 남겨놓고 계속해서 필요할때 끌어다 쓴다. 동작방식 1. 구하고자 하는 큰 문제를 작은 문제들로 나눈다. (점화식을 세운다.) 2. 가장 작은 부분문제를 푼 뒤 값을 저장한다. = 메모이제이션 3. 메모이제이션 된 문제들의 값을 이용해 점차 더 큰 문제들의 답을 구한다. 4. 가장 큰 문제를 풀이할때까지 반복한다. ☆무엇을 어떻게 저장할지 정하는게 중요하다. 적용방법 1. Botton-Up 방식 : 반복문을 이용 e..