본문 바로가기

전체 글48

[바킹독 실전 알고리즘 0x07] 덱 정의와 성질 덱은 양 쪽 끝에서 삽입과 삭제가 모두 가능하다. 자료구조에서의 덱은 deque(double ended queue)이다. (deck아님) 원소의 삽입과 삭제를 O(1)의 시간복잡도를 가지고 구현할 수 있다. 가장 앞과 가장 뒤의 원소를 확인하는 데 O(1)의 시간복잡도가 소요된다. 가장 앞과 가장 뒤가 아닌 원소들의 확인/변경은 원칙적으로 불가능하다. 하지만 독특하게도 스택, 큐와 달리 STL deque에서는 인덱스로 원소에 접근할 수 있다. 기능과 구현 스택, 큐와 동일하게 배열과 연결리스트를 가지고 구현할 수 있다. 하지만 배열로 구현하는 것이 더 쉽기 때문에 이번 게시글에서는 배열로 구현하는 방법을 소개한다. const int MAX = 1000000; int data[2*MAX+1];.. 2023. 2. 1.
[C++] Visual Studio에 <bits/stdc++.h> 헤더파일 추가하기 알고리즘 문제를 풀 때, 필요한 헤더 파일들을 매번 include 해주는 과정이 귀찮게 느껴질 수 있다. 자주 쓰이는 헤더 파일들을 담은 stdc++.h 파일을 다운로드 받은 후, 코드 컴파일러의 include 파일에 자동으로 포함되도록 하면 이 번거로움을 해결할 수 있다. stdc++.h 파일은 gcc 컴파일러에는 내장되어 있다. 따라서 대표적으로 gcc 컴파일러를 사용하는 Visual Studio Code의 경우, 이 파일을 따로 다운로드 받을 필요가 없다. 하지만 많은 사람들이 C++ 코딩을 할 때 사용하는 Visual Studio의 경우 msvc 컴파일러를 사용하기 때문에 stdc++.h 파일을 직접 다운로드 받아 include 폴더에 넣어야 한다. 다음은 stdc++.h 파일이다. stdc++... 2023. 2. 1.
[바킹독 실전 알고리즘 0x06] 큐 정의와 성질 큐는 한쪽 끝에서 원소를 넣고, 다른쪽 끝에서 원소를 뺄 수 있는 자료구조이다.(FIFO) 큐에서 원소가 추가되는 곳을 rear, 즉 뒷쪽이라고 하고, 원소가 제거되는 곳을 front라고 한다. 원소의 추가나 제거를 할 때 O(1)의 시간복잡도가 필요하다. 가장 앞이나 가장 뒤 원소를 확인하려면 O(1)의 시간복잡도가 필요하다. 가장 앞이나 가장 뒤 원소를 제외한 원소들의 확인/변경은 원칙적으로 불가능하다. (앞 게시글의 스택과 비슷한 맥락) 기능과 구현 큐도 스택과 마찬가지로 배열 혹은 연결리스트를 사용해 구현이 가능하다. 배열로 구현하는 방법이 더 쉬워서 이번 게시글에서는 배열로 구현하는 것만 소개하려고 한다. const int MAX = 1000000; int data[MAX]; //원.. 2023. 2. 1.
[바킹독 실전 알고리즘 0x05] 스택 정의와 성질 LIFO(선입선출) 구조이다. 특정 위치에서만 원소의 추가나 제거가 이루어진다. 이 성질 덕분에 원소의 추가나 제거는 O(1)이다. 제일 상단의 원소를 확인하는 시간복잡도는 O(1)이다. 제일 상단이 아닌 나머지 원소들의 확인이나 변경은 원칙적으로 불가능하다. 원칙적으로 불가능해서 배열의 성질을 사용해 나머지 원소들의 확인이 가능하도록 구현할 수는 있지만, 스택의 응용 사례에는 제일 상단의 원소만을 다룬다. 기능과 구현 스택은 배열 혹은 연결 리스트를 사용해 구현할 수 있다. 그리고 둘 중 배열을 이용하는 구현 방법이 더 쉽다. 배열을 사용해 스택을 구현하는 방법은 생각보다 간단한데, 원소들을 모두 담을 큰 배열 하나와 인덱스를 저장할 변수 하나만을 필요로 한다. const int MAX =.. 2023. 1. 31.
[바킹독 실전 알고리즘 0x04] 연결 리스트 연결 리스트의 성질 k번째 원소를 확인/변경하기 위해 O(k)가 필요하다. 임의의 위치에 원소를 추가/제거는 O(1)의 시간복잡도를 가진다. 원소들이 메모리 상에 연속해있지 않아 cache hit rate가 낮지만 할당이 다소 쉽다.(코테에서는 몰라도 됨) 연결 리스트의 종류 단일 연결 리스트 이중 연결 리스트(이전+이후 원소의 주소 저장. 단일 연결 리스트보다 메모리를 많이 씀.) 원형 연결 리스트 배열과 연결 리스트는 둘 다 선형 구조라서 둘의 차이를 비교하는 문제가 면접 등에서 빈출된다. 배열 연결 리스트 k번째 원소의 접근 O(1) O(k) 임의 위치에 원소 추가/제거 O(N) O(1) 메모리 상의 배치 연속 불연속 추가적으로 필요한 공간(Overhead) - O(N) 연결리스트는 다음 원소 혹은.. 2023. 1. 31.
[Backend] 패키지 매니저 npm이란 Node Package Manager 노드의 패키지 매니저 다른 사람들이 만든 소스 코드들을 모아둔 저장소이다. 100만 개 정도 존재한다. 남이 미리 작성해둔 코드를 사용하여 프로그래밍이 가능하다. 이미 존재하는 기능을 다시 구현할 필요가 없어 효율적이다. 오픈 소스 생태계를 구성중이다. 패키지 패키지: npm에 업로드된 노드 모듈 모듈이 다른 모듈을 사용할 수 있듯, 패키지도 다른 패키지를 사용할 수 있다. 의존 관계라고 부름 package.json 서버를 작성할 때, 보통은 서버, 세션, 쿠키 http, 요청, 헤더 관리 등 거의 대부분을 다운 받아 이들을 연결하는 작업 정도만 직접 한다. 이렇게 다운 받은 파일들의 기록이 담긴 파일을 package.json이라고 부른다. 같은 패키지라도.. 2023. 1. 30.
[Backend] http 모듈로 서버 만들기 HTTP 서버 만들기 웹 브라우저에 www.naver.com 을 입력하면, 웹 브라우저가 client가 되는 것이고, 서버는 네이버의 서버(서버는 어떤 컴퓨터이다)가 된다. 클라이언트가 서버에 '메인 화면을 띄워달라'는 요청을 하면, 서버에서 이를 받아 화면을 띄우는 응답을 한다. 요청과 응답은 http라는 프로토콜을 사용해서 이루어진다. 노드에서는 http라는 모듈을 사용해서 코드를 작성하면 노드 프로그램을 돌릴 수 있다. createServer를 사용해 요청 이벤트에 대기할 수 있다. req 객체에는 요청에 관한 정보가, res 객체에는 응답에 관한 정보가 담겨 있다. createServer.js const http = require('http'); const server = http.createSe.. 2023. 1. 30.
[바킹독 실전 알고리즘 0x03] 배열 배열 정의: 메모리 상에 원소를 연속하게 배치한 자료구조. 성질: 1. O(1)의 시간복잡도만을 사용해 k번째 원소를 확인/변경이 가능하다. 메모리 상에 연속하게 배치되어있기 때문에 가능하다. 2. 추가적으로 소모되는 메모리의 양(=overhead)가 거의 없다. 3. cache hit rate가 높다. 4. 메모리 상에 연속한 구간을 잡아야해서 할당에 제약이 걸린다. 배열의 임의의 위치에 원소를 추가하는 데 걸리는 시간복잡도는 O(N)이다. 하나의 원소를 추가하기 위해 뒤에 남은 원소들을 모두 한 칸씩 밀어야하기 때문이다. 마찬가지로 임의의 원소를 제거하는 연산도 O(N)의 시간복잡도를 요구한다. 배열에 원소를 추가하거나 삭제하는 것은 다음과 같이 구현할 수 있다: //idx번째 위치에 num을 넣는 .. 2023. 1. 28.
[C++] 백준 10871 #include int main(void) { std::ios::sync_with_stdio(0); std::cin.tie(0); int n, x, a[10000]; std::cin >> n >> x; for (int i=0;i > a[i]; for (int j = 0;j < n;j++) { if (a[j] < x) { std::cout 2023. 1. 28.
[바킹독 실전 알고리즘 0x02] 기초 코드 작성 요령 II STL과 함수 인자 void func(int a){ a=5; } int main(void){ int t=0; func(t); cout 2023. 1. 28.
[바킹독 실전 알고리즘 0x01] 기초 코드 작성 요령 I 시간, 공간복잡도를 고려하라 대략적인 N의 크기에 따른 허용 시간복잡도 N의 크기 허용 시간복잡도 N 2023. 1. 26.
[Backend] 노드 기능 REPL 자바스크립트는 스크립트 언어라서 즉석에서 코드를 실행할 수 있다. js에서는 REPL이라는 콘솔이 제공된다. R(Read), E(Evaluate), P(Print), L(Loop) Window에서는 명령 프롬프트, 맥/리눅스에서는 터미널에 node 입력하면 노드를 실행할 수 있다. 모듈 만들기 노드는 자바스크립트 코드를 모듈로 만들 수 있다. 모듈: 특정한 기능을 하는 함수나 변수들의 집합 모듈로 만들면 여러 프로그램에서 재사용이 가능하다. node의 모듈 시스템(require, module.exports)은 js의 모듈 시스템(import, export)과 문법이 다르다. require를 import ~ from ' '로, module.exports 를 export default로 대체할 수 .. 2023. 1. 26.
[Backend] 프로미스 콜백 헬이라고 불리는 지저분한 자바스크립트 코드의 해결책 = 프로미스 프로미스: 내용이 실행은 되었지만 결과를 아직 반환하지 않은 객체. 결과가 출력되기 전까지 결과를 들고다닌다. then이나 catch를 붙여서 결과를 반환받을 수 있다. 실행이 완료되지 않았으면 완료된 후에 then 내부 함수가 실행됨 promise는 어떤 동작을 한다. 예를 들면 어떤 파일을 읽어 온다든지, 네이버와 같은 웹사이트에 요청을 보낸다든지. 동작의 결과(성공 or 실패)에 따라 실행되는 코드가 나뉜다. resolve(성공 리턴값)를 호출하면 then으로 연결한다. reject(실패 리턴값)를 호출하면 catch로 연결한다. finally 부분은 무조건 실행된다. const condition = true; //true면 re.. 2023. 1. 26.
비구조화 할당 javascript에서 코드를 간결하게 만들기 위해 생긴 문법이다. 예전에는 다음과 같이 세 줄로 써야했던 코드를 const example = { a:123, b: { c: 135, d:146 }} const a = example.a; const d = example.b.d; 비구조화 할당을 사용하면 한 줄로 작성 가능하다. const { a, b: {d}} = example; //example에서 a와 b 안의 d를 꺼내두라는 뜻이다. 콘솔을 찍어보면 다음과 같은 출력이 나온다. console.log(a); //123 console.log(d); //146 예제를 하나 더 살펴보자. 배열을 사용하는 경우에도 비구조화 할당을 하면 코드가 간결해진다. arr = [1,2,3,4,5]; const x = a.. 2023. 1. 26.
화살표 함수 앞서 설명한 const 와 let은 var을 완벽하게 대체할 수 있지만, 화살표 함수는 function을 완벽하게 대체할 수는 없다. function을 사용한 기존 문법 function add1(x, y) { return x+y; } 화살표 함수 사용 const add2 = (x, y) => { return x+y; }; //함수명 대신 변수명을 쓰고, = (parameters) => 를 사용. 중괄호 뒤에 바로 return문이 나온다면, 이 둘을 모두 생략해도 된다. const add3 = (x, y) => x+y; 위 방법을 사용하면 간결하지만 헷갈릴 수 있기 때문에 대부분 리턴 값을 소괄호로 묶어준다. const add4 = (x, y) => (x+y); 객체를 리턴하는 경우, 소괄호가 필수이다. .. 2023. 1. 25.

티스토리툴바