Nnnnnnnnn

Recursion 자기 자신을 호출하는 함수. 순환, 재귀 recursion이 항상 무한루프에 빠지는 것이아니다. 무한루프에 빠지지 않는 적절한 구조 Base case : 적어도 하나의 recursion에 빠지지 않는 경우가 존재해야 한다. Recursive case : recursion을 반복하다보면 결국 base case로 수렴해야 한다. 수학적귀납법과의 비교 Ex) n=0인 경우 0을 반환한다. 임의의 양의 정수 k에 대해서 n1), 최대공약수(Euclid Method) public static int gcd(int p, int q){ if(q==0) return p; else return gcd(q, p%q); } Recursive Thinking 문자열의 길이 계산 public static in..

알고리즘의 시간 복잡도 알고리즘의 수행 시간을 지배하는 것은 반복문이다. 입력의 크기가 커질수록 반복문이 알고리즘의 수행 시간을 지배한다. 반복문의 수행 횟수는 입력의 크기에 대한 함수로 표현한다. 시간 복잡도란 가장 널리 사용되는 알고리즘의 수행 시간 기준으로, 알고리즘이 실행되는 동안 수행하는 기본적인 연산의 수를 입력의 크기에 대한 함수로 표현한 것이다. 기본적인 연산이란 더 작게 쪼갤 수 없는 최소 크기의 연산이다. 시간 복잡도가 높다는 말은 입력의 크기가 증가할 때 알고리즘의 수행 시간이 더 빠르게 증가한다는 의미이다. 시간 복잡도가 낮다고 해서 언제나 더 빠르게 동작하는 것은 아니다. 입력의 크기가 작을땐 시간 복잡도가 높은 알고리즘이 더 빠르게 동작할 수도 있다. 시간 복잡도가 낮은 알고리즘..

산술 오버플로우 계산 과정에서 변수의 표현 범위 값 벗어나지 않도록 주의.결과 값이 너무 크거나, 중간 연산되는 값이 커 비트를 초과한 경우 해당 비트 범위 값만 취해서 결과가 달라질 수 있음. 배열 범위 밖 원소 접근 Off-by-one 오류 하나가 모자라거나 하나가 많아서 틀리는 코드의 오류들. 스택 오버플로우 프로그램의 실행 중 콜 스택이 오버플로우하여 프로그램이 강제 종료됨.스택 오버플로우는 대개 재귀 호출의 깊이가 너무 깊어져서 옴. C++의 경우 지역 변수로 선언한 배열이나 클래스 인스턴스가 기본적으로 스택 메모리를 사용하기 때문에 특히나 스택 오버플로우를 조심해야 함. 연산자 우선 순위 주의 if(a & 1 == 0) 일 때, & 연산자는 == 보다 우선순위가 낮음. 디버깅 1. 작은 입력에..

cin / scanf 알고리즘 문제를 풀다가 시간 초과가 나는 경우가 많다. 오늘 계속 시간 초과가 떠서 코드를 수정하던 중, 입력을 받을 시 cin 대신 scanf를 사용하니 시간 초과가 나타나지 않았다. cin과 scanf의 속도 차이를 알아보니, 입력 크기에 따라 그 속도가 많게는 8배 정도가 차이나는 것 같다. 코드 앞에 sync_with_stdio(false) 를 쓰면 cin의 속도가 빨라지지만, 어떤 경우에는 똑같이 시간 초과가 발생하였다. 또한 cout의 경우에도 endl 사용 시 많이 느리다는 것도 알 수 있었다. 출처 : https://algospot.com/forum/read/2496/

비트마스크 134를 2진수로 나타내면 10000110 이다. 해당 비트에 1인 경우를 집합으로 나타내면 {1, 2, 7} 이다. 만약 134의 2진수 집합에 0이 포함되어 있는지 검사하려면, 134 & (1

비트마스크 비트연산을 통해서 부분집합을 표현한다. bitwise operation으로는 & (and), | (or), ~ (not), ^ (xor) 이 있다.비트연산을 하는 경우, 가장 뒤의 자리부터 하나씩 비교해가며 연산을 수행한다. A=25, B=51이라면 A는 2진수로 11001이고 B는 110011이다.ex)A & B011001110011--------010001 ==> 17 not 연산은 자료형에 따라 결과값이 다르게 나타난다. 8비트와 32비트의 자료형을 비교하면 그 결과가 달라질 수 있다. 또한 signed와 unsigned에 따라서도 그 결과가 다르다. shift register를 떠올려보면, shift left와 shift right이 있었다. 말 그래도 shift left면 왼쪽으로 비..