본문 바로가기

전체 글75

알고리즘 문제 풀 때 시간,공간복잡도 및 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.
백준 14852번: 타일 채우기3 ( DP 누적합 문제 => 최적화 필요 ) https://www.acmicpc.net/problem/14852 14852번: 타일 채우기 3첫째 줄에 경우의 수를 1,000,000,007로 나눈 나머지를 출력한다.www.acmicpc.net#include#includeusing namespace std;int d[1000001];int solution(int n){ if(n == 0) return 1; if(n == 1) return 2; if(n == 2) return 7; if(d[n] != 0) return d[n]; int result = 2 * solution(n-1) + 3 * solution(n-2); for(int i = 3; i 위 코드의 시간 복잡도solution(n)을 구할 때 시간       .. 2022. 2. 27.
알고리즘 시간복잡도 구하는 법 ( 반복대치 ) #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.
컴파일러와 인터프리터의 차이점 컴파일러 전체 소스코드를 보고 명령어 수집하고 재구성 고레벨 언어를 바로 기계어로 변환 인터프리터 소스코드의 각 행을 연속적으로 분석하며 실행 고레벨 언어를 바로 기계어로 번역하지 않고 중간 코드(바이트 코드)로 변환시킨 후 기계어로 변환 인터프리터의 특징 4가지 인터프리터는 고레벨 언어를 중간 코드로 변환하고 이를 각 행마다 실행한다. 컴파일러가 각 행마다 실행하는 특성을 가진 인터프리터보다 실행시간이 더 빠르다. 컴파일러는 전체 소스코드 변환 후 에러를 보고하지만 인터프리터는 각 행마다 실행하는 도중 에러가 보고되면 이후 작성된 코드를 보지 않는다. => 보안적인 관점에서 도움이 된다. 파이썬은 인터프리터 언어, C,C++은 컴파일 언어, 자바는 컴파일러와 인터프리터 모두 사용한다. Compiler와.. 2022. 2. 25.
Java의 컴파일 과정 vs C++의 컴파일 과정 컴퓨터는 0과 1로만 이루어진 기계어만 이해할 수 있기 때문에 개발자가 만든 코드를 변환해 주어야 한다. 이 역할을 하는 것이 컴파일러이다. [Java] 컴파일 과정 자바는 OS에 독립적인 특징을 가지고 있다. 그게 가능한 이유는 JVM(Java Virtual Machine) 덕분이다. 자바 컴파일 순서 1. 개발자가 자바 소스코드(.java)를 작성한다. 2. 자바 컴파일러(Javac)가 자바 소스파일을 컴파일한다. 이 때 나오는 파일은 자바 바이트 코드(.class) 파일로 아직 컴퓨터가 읽을 수 없고 JVM이 이해할 수 있는 코드이다. ( 바이트 코드의 각 명령어는 1바이트 크기의 Opcode와 추가 피연산자로 이루어져 있다. ) 3. 컴파일된 바이트 코드를 JVM의 클래스로더(Class Loade.. 2022. 2. 25.
HTTP Push & Pull PUSH 기법 인터넷 상에서의 어떠한 전송 요청이 중앙 서버에서 시작되는 정보 전달 방식 전송 요청이 클라이언트에서 시작되는 풀 기법과 대비되는 방식 사용자가 원하든 원하지 않든 방송처럼 뉴스를 제공하는 기술 푸시 방법으로 정보를 제공하던 기존의 TV나 라디오와 다른 점은 사용자가 미리 원하는 범위를 지정할 수 있다는 점이다. 사용자가 일일이 요청하지 않아도 사용자에게 자동으로 뉴스나 사용자가 원하는 특별한 정보, 예를 들면 증권시장의 주기적인 정보 같은 것을 제공한다. PUSH 기법의 가장 큰 이점 정보의 맞춤화(Customization)가 가능하다. => 사용자가 이미 등록되어 있기 때문에 등록된 사용자 정보에 의해 타겟을 정확히 선정할 수 있다. 카카오톡 등의 웹 기반 실시간 채팅 어플리케이션은 서.. 2022. 2. 24.

티스토리툴바