분류 전체보기48 [바킹독 실전 알고리즘 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. 이전 1 2 3 4 5 6 다음
