본문 바로가기

전체 글109

[NodeJS] 소켓을 이용한 간단한 채팅방 만들기 net 모듈을 이용하여 TCP 프로토콜로 서버-클라이언트 간 데이터를 전송하는 코드이다. 서버 | socket-server.js const net = require("net"); let pool = []; const server = net.createServer((socket) => { pool.push(socket); socket.on("data", (data) => { let d = JSON.parse(data); switch (d.type) { case "CONNECT": for (let s of pool) s.write(d.content + " connected!"); break; case "CHAT": for (let s of pool) s.write(d.content); break; } });.. 2020. 4. 30.
[BOJ] 15678. 연세워터파크 15678번: 연세워터파크 첫 줄에 징검다리의 수 N과 문제에서 설명한 D가 주어진다. (2 ≤ N ≤ 105, 1 ≤ D ≤ N-1) 이어 N개의 정수로, 각 징검다리에 쓰인 수 Ki가 1번 징검다리부터 N번 징검다리까지 순서대로 주어진다. (-109 ≤ Ki ≤ 109) www.acmicpc.net 처음에는 아무 생각 없이 그냥 DP로 짰다가... 시간초과가 났다. 당연히 그렇게 쉬울 리가 없을 거라고는 생각했지만 도저히 로직이 생각이 안 나는걸.. 2주동안 이걸 못 풀고 죽어가고 있었는데 이 사람이 풀어주셨다. O(nlogn) 풀이 | #include using namespace std; #define INF 987654321987654321 int N, D; long long a[100000], .. 2020. 4. 29.
[C++] max_element(), min_element() algorithm 헤더에 있는, 배열이나 벡터 구간 안에서 최대, 최솟값을 찾는 함수이다. max_element(arr, arr+size) 혹은 max_element(vec.begin(), arr.end()) 처럼 시작 주소 혹은 이터레이터, 끝 주소 혹은 이터레이터를 넣어주면 된다. return 형식도 주소 혹은 이터레이터이기 때문에, 값을 알고 싶다면 *max_element(arr, arr+size) 처럼 써준다. #include #include #include using namespace std; int arr[10] = {1, 2, 10, 4, 9, 3, 7, 5, 6, 8}; vector vec; int main() { vec.push_back('c'); vec.push_back('a'); ve.. 2020. 4. 29.
[포스터] 2020 KUCC GAME:JAM 사용 폰트 | Kongtext (로고) 배달의민족 을지로체 (본문) 동아리에서 간단하게 게임잼 행사를 열게 되어 포스터를 제작했다. 동아리 마스코트 캐릭터 픽셀 아트는 직접 그렸다. 2020. 4. 28.
[기타] URL과 URI의 차이 최근에 백엔드 공부를 하면서, encodeURI, decodeURI 함수를 접하게 되었는데, 처음엔 오타인 줄 알았다. URI가 URL의 오타인 것은 당연히 아니고, URL은 Uniform Resource Locator, URI는 Uniform Resource Identifier의 약자이다. 일단 결론부터 말하자면 URL은 URI에 포함되는 개념이다. URI는 통합 자원 식별자로 인터넷에 있는 자원을 나타내는 유일한 주소이다. 어떤 형식이 있는 것은 아니고, 특정 자원을 식별하는 문자열의 개념 자체를 의미한다. URL은 통합 자원 위치로 인터넷 상의 자원 위치이다. https://r4bb1t.tistory.com은 https://r4bb1t.tistory.com 라는 서버를 가리키는 URL이자 URI이다.. 2020. 4. 28.
[알고리즘] 카데인 알고리즘(Kadane's algorithm) 카데인 알고리즘(Kadane's algorithm)은 배열의 최대 부분 합을 O(n)의 시간복잡도로 구하는 알고리즘이다. i번째 인덱스를 오른쪽 끝으로 하는 부분배열들의 최대 부분 합을 M[i]라고 하면, M[i+1]은 M[i]+arr[i+1]이거나 arr[i+1]중 더 큰 값이다. M[0]은 arr[0]인 1이다. M[1]은 arr[1] = -6과 M[0] + arr[1] = -5 중 더 큰 -5이다. M[2]는 arr[2] = 4와 M[1] + arr[2] = -1 중 더 큰 4이다. 왜 M[i+1]이 max(M[i] + array[i+1], array[i+1]) 인지 이해하면 쉽다. i를 오른쪽 끝으로 하는 부분배열 중 최대 부분 합이 음수이면 굳이 더하지 않고 그냥 i+1번째 인덱스부터 새로 더하.. 2020. 4. 25.
[BOJ] 2098. 외판원 순회 2098번: 외판원 순회 첫째 줄에 도시의 수 N이 주어진다. (2 ≤ N ≤ 16) 다음 N개의 줄에는 비용 행렬이 주어진다. 각 행렬의 성분은 1,000,000 이하의 양의 정수이며, 갈 수 없는 경우는 0이 주어진다. W[i][j]는 도시 i에서 j로 가기 위한 비용을 나타낸다. 항상 순회할 수 있는 경우만 입력으로 주어진다. www.acmicpc.net 현재까지 방문한 경로를 표현할 때 비트마스크를 이용하는 문제이다. 개인적으로 DP 배열을 현재 경로와 인덱스 두 개의 인자를 써야 한다는 아이디어를 떠올리기가 힘들었다. #include #include using namespace std; #define INF 1000000000 int N, W[16][16]; int dp[65536][16]; i.. 2020. 4. 17.
[알고리즘] 비트마스크(Bit Mask) 비트마스크(Bit Mask)는 알고리즘이라기보다는 기법인데, 한 비트가 0 또는 1의 두 가지 값을 갖는다는 사실을 이용해 2진수 배열을 십진수로 변환하여 사용하는 테크닉이다. 예를 들어 {true, false, true, false}인 배열을 2진수로 1010으로 표현하고, 다시 십진수로 변환하면 10이 된다. 비트마스크 기법을 이용하면 bool 배열간의 연산을 간단하게 할 수 있다. {true, false, true, false} 배열과 {true, false, false, true} 배열을 각각 & 연산으로 비교할 때, 일반적으로는 반복문을 이용해 배열의 각 인덱스마다 비교해줘야 할 것이다. 그런데 비트마스크 기법을 이용해 {true, false, true, false} 배열을 10으로, {true.. 2020. 4. 16.
[자료구조] 세그먼트 트리(Segment Tree) 세그먼트 트리(Segment Tree)는 부분 합을 트리 구조에 저장해서, 값이 바뀔 수 있는 상황에서도 부분합을 빠르게 구할 수 있는 방법이다. 세그먼트 트리를 그려보면 이런 느낌이다. 위의 대괄호 안에 들어있는 숫자는 각 노드의 인덱스이고, 아래 큰 숫자는 부분합의 범위이다. 즉 루트 노드인 [0]에는 배열의 0~9번째 값들의 합이 저장되어 있고, [11] 노드에는 배열의 5~6번째 값들의 합이 저장되어 있는 식이다. 구현 | 1. init 배열의 초기 값을 세그먼트 트리에 처음 넣는 함수이다. 이때는 루트 노드 [0]부터 아래로 내려간다. 한 노드에 값을 채울 때는 자식 노드에 값을 먼저 채우고 그 뒤에 그 합을 쓰면 되는 것이다. 그런 식으로 말단 노드 (예를 들어, 6번째부터 6번째까지의 합 노.. 2020. 4. 14.
[알고리즘] 강한 연결 요소(Strongly Connected Component) 강한 연결 요소(Strongly Connected Component, SCC)는 어떤 양방향 그래프 내에서 다음 조건을 만족하는 부분집합이다. 임의의 강한 연결 요소 내부의 모든 정점끼리는 서로 이어진 경로가 존재한다. 임의의 강한 연결 요소 내부의 정점과 외부의 정점끼리는 서로 이어진 경로가 존재하지 않는다. 즉 이는 어떤 한 정점에 대해 첫번째 조건을 만족하는 최대의 부분집합이라고 할 수 있다. 위 그래프에서 {A, B, C, E}, {D, G, H}, {F}, {I}가 강한 연결 요소이다. 어떤 그래프에서의 SCC를 찾는 알고리즘으로는 코사라주 알고리즘이 있다. 코사라주 알고리즘 | 코사라주 알고리즘은 DFS를 이용한 위상 정렬을 토대로 SCC를 찾는 알고리즘이다. 그래프와 역방향 그래프를 준비한다.. 2020. 4. 13.
[픽셀아트] 0410 동아리방 선을 좀 더 명확하게 쓰는 연습을 했다. 찍을 때는 긴가민가 했는데, 완성본을 보고 나니 확실히 깔끔하다. 테이블 위에 올려진 유리 질감 표현하는 게 재밌었다. 테이블 다리 열심히 찍었는데 가려져서 아쉬움. 그림자 넣은 게 신의 한 수인 것 같다. 2020. 4. 12.
[자료구조] 큐(Queue) 큐(Queue) | 한 쪽 끝에서는 자료를 넣고, 반대쪽 끝에서는 자료를 뺄 수 있는 선형 자료구조. FIFO(First-In-First-Out) | 먼저 들어간 자료가 먼저 나온다. 인큐(Enqueue) | 큐에 자료를 넣는 것. 디큐(Dequeue) | 큐에서 자료를 빼는 것. 사이즈(Size) | 큐의 크기. 큐에 들어 있는 자료 수. 프론트(Front) | 큐의 가장 앞에 있는 자료. 백(Back) | 큐의 가장 뒤에 있는 자료. 2019. 11. 11.

티스토리툴바