본문 바로가기

분류 전체보기53

[바킹독 실전 알고리즘 0x08] 스택의 활용(수식의 괄호 쌍) 이번 게시글에서는 스택을 사용해 수식의 괄호 쌍이 올바르게 짝지어져 있는지 판별하는 문제를 해결하고자 한다. 문제 해결을 위한 관찰 idea) 문자열을 앞에서부터 읽어나갈 때, 닫는 괄호는 남아있는 괄호 중에서 가장 최근에 들어온 여는 괄호와 짝을 지어 없애버리는 명령이라고 생각하자. 그리고 다음 그림을 보고 괄호 문제의 풀이법을 떠올려보자. 여는 괄호를 만나면 스택에 삽입하고, 닫는 괄호를 만나면 가장 최근에 들어온 여는 괄호를 삭제한다. 괄호가 담긴 문자열을 모두 읽었을 때, 스택에 남아있는 괄호가 없다면 모든 괄호가 짝을 이뤘다고 판단할 수 있다. 올바르지 않은 괄호 쌍을 가지는 경우는 다음과 같다: 1. 여는 괄호와 닫는 괄호의 짝이 맞지 않는 경우 2. 괄호 쌍의 수가 맞지 않는 경우 3. 닫는.. 2023. 2. 2.
[git] git fetch upstream 원격 저장소 연결하기 [git bash를 사용해 코드를 push하는 방법] 1. 우선 원하는 경로에 git repository를 clone 받을 폴더로 만들고, git bash에서 해당 경로로 이동한다. 그리고 git clone [repo주소] 명령어를 사용해 클론받는다. 2. 클론 받은 폴더 안에 repository 이름명으로 만들어진 폴더 내부로 들어간다. 3. 이쯤에서 새 브랜치를 만들어준다. 4. VSCode로 원하는 코드를 추가/수정하는 작업을 마친 뒤, git add . 와 git commit -m [커밋메시지] 명령어를 사용해 코드를 올려준다. 5. git push origin [브랜치명] 명령어를 사용해 Github에 코드를 push해준다. [git fetch upstream을 사용하는 방법] 여러 사람이 함께.. 2023. 2. 1.
[바킹독 실전 알고리즘 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.

티스토리툴바