코딩뚠뚠

투포인터 알고리즘 : 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..

헤더파일을 추가하여 순열을 자동으로 구해줄 수 있다. ​ 필요성 : 알고리즘 문제를 풀며 위 함수의 필요성을 느끼게 되었다. 모든 경우에 대해 순열을 바꿔주어 입력을 넣어줘야되는데 일일히 넣어주기는 귀찮았다. permutation 함수를 써서 자동으로 모든 순열을 구할 수 있었다. (1 2 3 4로 기본 순서가 정해져있었다면 1 2 4 3 / 1 4 2 3 / 1 4 3 2 / 2 1 3 4 등 모든 순열을 구함) ​ - next_permutation : 현재 나와있는 수열에서 범위에 해당하는 다음 순열을 구하고 true를 반환한다. 다음 순열이 없다면 flase를 반환 ​ - prev_permutation : 현재 나와있는 수열에서 범위에 해당하는 이전 순열을 구하고 true를 반환한다. 이전 순열이 ..

삼성 역량테스트를 C++로 준비하며 필요한 input의 방법들을 공부하며 정리해봤다. 1. 길이를 알고있는 숫자를 입력하고 이를 한글자씩 잘라서 input을 받아야 하는 상황 ex) 입력 : 길이 7의 숫자 1234567를 한번에 입력해야되고, 이를 1 / 2 / 3 / 4 / 5 / 6 / 7 이렇게 따로 받아야 되는상황 int a[7]; for(int i=0;i> a; for (int i = 0; i < a.size(); i++) { temp += a[i] - '0'; } return 0; } 3. 공백을 포함해서 받는방법 ex) 입력 : "abc de fg" 를 name에 한번에 저장하기 string name; getline(cin,name); char name[1000]; gets_s(name,1..

C++ standard header는 뒤에 .h 형태의 확장자가 붙지않게끔 명명되어있는데 기존 C standard header 들이 C++로 넘어오면서 .h가 떼지고 앞에 c가 붙게되었다. 따라서 cmath 도 math.h에서 넘어오게 된 것인데 사용이 완전히 동일한 것은 아니다. 사용법과 기본 주요 함수들을 알아보자 ​ ​ pow (제곱함수) double pow (double a, double b) pow(10,2)// = 10^2 ​ sqrt (제곱근함수) double sqrt(double x) sqrt(4)// = 2 ​ ceil (올림) ceil(3.14)// = 4 ​ floor (내림) floor(1.89)// =2 ​ floor(a+0.5) (반올림) flo..