알고리즘 개념14 알고리즘 문제풀이 전 코드 작성 요령 코딩테스트 코드 작성 팁코딩테스트와 개발은 다르다.남들이 보기 편한 클린코드가 아닌 가장 빠르게 풀 수 있도록 짜는 것이 훨씬 중요하다.출력 맨 마지막 공백 or 줄바꿈이 추가로 있어도 상관이 없다.디버거는 사용하지 않는다. 차라리 중간에 변수를 확인하고 싶다면 printf나 cout으로 확인한다. endl은 죽어도 쓰지 마라!!! endl은 개행문자('\n')을 출력하고 출력 버퍼를 비우라는 명령어이다. 온라인 저지 채점은 출력값만 확인하기 때문에 버퍼를 매번 비워줄 필요가 없다. (시간낭비)#include 선언vscode에서만 쓸 수 있는 구현에 필요한 헤더들을 다 인클루드해 놓은 헤더이다.#include#include#include#include#include#include#include#inclu.. 2022. 3. 12. 알고리즘 문제 풀 때 시간,공간복잡도 및 Integer overflow 문제 시간복잡도 공간복잡도입력의 크기와 문제를 해결하는데 필요한 공간의 상관관계예를 들어 크기 N짜리 2차원 배열이 필요하면 O(N²)이고, 따로 배열이 필요 없으면 O(1)이 된다.하지만 코딩테스트에서 대부분의 경우 공간복잡도의 문제보다는 시간복잡도 때문에 문제를 많이 틀린다.그러므로 공간복잡도는 크게 신경쓰지 않아도 된다. But!! 이거 하나만 기억해두자 ☞ 메모리 제한이 512MB일 때 1.2억개의 int를 사용할 수 있다는 것 Integer Overflow Integer Overflow가 발생하는 경우#includeusing namespace std;int main(){ int a = 2000000000 * 2; cout 약 21억정도 까지만 표현할 수 있으므로 40억이라는 값은 a에 저.. 2022. 3. 12. 알고리즘 시간복잡도 구하는 법 ( 반복대치 ) #include factorial(int n){ if(n == 1) return 1; //1 return n * factorial(n-1); //2}시간복잡도 : T(n) = T(n-1) + c ( c는 "1의 수행시간 + 2에서의 곱셈의 수행시간" ) 위의 factorial() 함수의 시간복잡도를 반복대치를 이용해 구해보겠다. 반복대치T(n) = T(n-1) + c = T(n-2) + 2c = T(n-3) + 3c . . . = T(1) + (n-1) * c 이때, n = 1일 때 T(1)은 1의 수행시간 밖에 들지 않으므로 1의 수행시간 + 2의 수행시간의 값을 가지는 c보다 작다. 즉, 빅오의 정의에 의해 .. 2022. 2. 27. 다이나믹 프로그래밍 ( Dynamic Programming ) 다이나믹 프로그래밍 문제는 종류가 굉장히 많으며 컴퓨터적인 사고력을 물어보기에 적합하다는 점에서 자주출제되는 문제이다. 다이나믹 프로그래밍하나의 문제는 단 한 번만 풀도록 하는 알고리즘=> 한 번 푼 것을 여러 번 다시 푸는 비효율적인 알고리즘을 개선시키는 방법dp같은 경우 문제에서 규칙성을 찾아서 점화식을 세우는 게 가장 중요하다. 다이나믹 프로그래밍을 쓰는 이유일반적으로 상당수의 분할 정복 기법은 동일한 문제를 다시 푼다는 단점을 가지고 있다.( 단, 퀵 정렬이나 병합 정렬은 동일한 문제를 다시 푸는 단점이 없다. 그러므로 매우 빠르다. ) 단순 분할 정복으로 풀게 되면 심각한 비효율성을 낳는 대표적인 예시 ' 피보나치 수열 ' 피보나치 수열은 특정한 숫자를 구하기 위해 그 앞에 있는 숫자와 .. 2022. 2. 21. 깊이 우선 탐색 ( DFS ) 깊이 우선 탐색 ( DFS )탐색을 함에 있어서 보다 깊은 것을 우선적으로 탐색하는 알고리즘미로를 탐색할 때 한 방향으로 갈 수 있을 때까지 계속 가다가 더 이상 갈 수 없게 되면 다시 가장 가까운갈림길로 돌아와서 이곳으로부터 다른 방향으로 다시 탐색을 진행하는 방법과 유사하다.깊이 우선 탐색(DFS)이 너비 우선 탐색(BFS)보다 좀 더 간단단순 검색 속도 자체는 너비 우선 탐색(BFS)에 비해 느리다. 깊이 우선 탐색 특징넓게(wide) 탐색하기 전에 깊게(deep) 탐색하는 것스택(Stack)을 사용- 사실 스택을 사용하지 않아도 구현이 가능하다. 왜냐하면 컴퓨터는 구조적으로 항상 스택의 원리를 사용하기 때문이다.자기 자신을 호출하는 재귀 알고리즘의 형태이다.탐색 과정이 시작 노드에서 한없이 깊게.. 2022. 2. 20. 너비 우선 탐색 ( BFS ) 너비 우선 탐색 ( Breath First Search )데이터를 탐색할 때 너비를 우선으로 하여 탐색을 수행하는 탐색 알고리즘현재 노드에서 가까운 것을 먼저 탐색하는 방식깊게(deep) 탐색하기 전에 넓게(wide) 탐색하는 것 너비 우선 탐색 특징재귀적으로 동작 XFIFO 원칙으로 탐색 ( Queue가 필요함 )그래프 탐색 알고리즘은 방문한 노드를 꼭 방문 처리 해줘야 한다. ( 하지 않을 경우 무한 루프에 빠질 수 있음 )너비 우선 탐색 장점과 단점출발노드에서 목표노드까지의 최단 길이 경로 보장경로가 매우 길 경우 탐색 가지가 급격히 증가함에 따라 보다 많은 저장 공간이 필요함해가 존재하지 않는다면 유한 그래프의 경우 모든 그래프를 탐색한 후 실패로 끝남무한 그래프의 경우 해가 없는 경우 해를 찾지.. 2022. 2. 15. 이전 1 2 3 다음
