입력 조건을 보자.상자의 개수 N(1 ≤ N ≤ 1,000,000)과 규칙의 개수 K(1 ≤ K ≤ 10,000), 도토리의 개수 D(1 ≤ D ≤ 1,000,000,000)가 주어진다.가장 쉽게 떠올릴 수 있는 방식은?브루트포스이다. 하나의 규칙에 대해 N개의 상자를 모두 돌면서 개수를 세야하니 O(NK)가 되어서 시간초과가 된다.O(NK)가 문제이고... k개의 규칙에서 상자 순회가 존재해서는 안된다는 뜻이다.그런데 하나의 규칙을 보면 [a, b]에서 간격 c로 도토리를 넣을 때 a~b 구간의 총 도토리 개수는 O(1)로 구할 수 있다.수식은 대충 (b-a)/c + 1 정도가 되겠다. 그럼 k개의 규칙에 대해 O(k)로 구간 [1, n]에 대해서 총 도토리 개수를 구할 수 있는 것이다. 이제 가닥이 ..

https://www.acmicpc.net/problem/22866 상당히 어렵게 풀었다..각설하고 우선 완전탐색 풀이는 굉장히 쉽지만 n이 100,000이기에 불가능하다. n log n이나 n으로도 풀어야 한다. 한 번의 순회가 최대라는 것이다. (log n으로는 순회가 불가능하니 n log n이면 보통 한 번의 순회에서 log n짜리 처리를 하는 것) 이런저런 생각을 해보며 한 번의 순회로 어떻게 풀 수 있을까 고민을 해봤다. 일단 몇 가지 핵심 포인트를 찾았는데순회가 두 번은 일어나야 한다. n^2이 아니라 2n인 것. 왜냐하면, 한 번 스캔으로는 절대 모든 케이스를 찾을 수 없다. 왼쪽 -> 오른쪽 / 오른쪽 -> 왼쪽으로 잡아두자.i번째 건물에서 딱 오른쪽 방향으로만 보이는 방향을 관찰하면 무언..

epoll과 멀티플렉싱1. 전통적인 웹소켓 통신Blocking IO 기반의 멀티스레드 방식이다. 클라이언트가 accept()으로 요청하면 새로운 스레드를 생성하고, 생성된 스레드는 해당 클라이언트와 데이터 송수신을 전담한다. 이 과정에서 accept(), read(), write()와 같은 IO 함수들은 데이터가 준비될 때까지 해당 스레드를 Blocking 시킨다.따라서 특정 클라이언트의 느린 IO가 존재한다면 그 클라이언트의 해당 워커 스레드는 Block 된다. 즉, 일시정지된다.2. Non-blocking I/ONon Blocking IO는 IO 작업을 요청했을 때 그 작업이 끝날 때까지 기다리지 않고 즉시 다음 코드를 실행하는 방식이다. 조금 더 정확히 말하자면 제어권을 반환하는 방식이다.fcntl..

RDBMS, NoSQL1. RDBMSRDBMS는 데이터를 관계를 통해 관리하는 시스템이다. 여기서 관계는 테이블로 표현되며 2차원 구조이다.주요 특징Schema-on-Write : 데이터를 저장하기 전 테이블의 구조를 명확히 정의해야 한다.데이터 무결성 보장 : PK, FK 등의 제약 조건을 통해 데이터의 중복을 방지하고 관계의 유효성을 보장한다.SQL (Structured Query Language)트랜잭션 (Transaction)과 ACID 원칙RDBMS는 SQL을 사용할 수 있으며 데이터의 일관성과 신뢰성이 매우 높다. 하지만 그만큼 스키마를 미리 정의하기에 데이터 구조를 변경하기 어렵다. 또한 수평적 확장이 구조적으로 어렵고 JSON, XML 등의 비정형 데이터를 저장하고 처리하기에 비효율적이다...

입력 조건을 보자.상자의 개수 N(1 ≤ N ≤ 1,000,000)과 규칙의 개수 K(1 ≤ K ≤ 10,000), 도토리의 개수 D(1 ≤ D ≤ 1,000,000,000)가 주어진다.가장 쉽게 떠올릴 수 있는 방식은?브루트포스이다. 하나의 규칙에 대해 N개의 상자를 모두 돌면서 개수를 세야하니 O(NK)가 되어서 시간초과가 된다.O(NK)가 문제이고... k개의 규칙에서 상자 순회가 존재해서는 안된다는 뜻이다.그런데 하나의 규칙을 보면 [a, b]에서 간격 c로 도토리를 넣을 때 a~b 구간의 총 도토리 개수는 O(1)로 구할 수 있다.수식은 대충 (b-a)/c + 1 정도가 되겠다. 그럼 k개의 규칙에 대해 O(k)로 구간 [1, n]에 대해서 총 도토리 개수를 구할 수 있는 것이다. 이제 가닥이 ..

https://www.acmicpc.net/problem/22866 상당히 어렵게 풀었다..각설하고 우선 완전탐색 풀이는 굉장히 쉽지만 n이 100,000이기에 불가능하다. n log n이나 n으로도 풀어야 한다. 한 번의 순회가 최대라는 것이다. (log n으로는 순회가 불가능하니 n log n이면 보통 한 번의 순회에서 log n짜리 처리를 하는 것) 이런저런 생각을 해보며 한 번의 순회로 어떻게 풀 수 있을까 고민을 해봤다. 일단 몇 가지 핵심 포인트를 찾았는데순회가 두 번은 일어나야 한다. n^2이 아니라 2n인 것. 왜냐하면, 한 번 스캔으로는 절대 모든 케이스를 찾을 수 없다. 왼쪽 -> 오른쪽 / 오른쪽 -> 왼쪽으로 잡아두자.i번째 건물에서 딱 오른쪽 방향으로만 보이는 방향을 관찰하면 무언..

https://blog.encrypted.gg/1037 [실전 알고리즘] 0x1D강 - 다익스트라 알고리즘네 반갑습니다. 이번에는 다익스트라 알고리즘을 해보겠습니다. 플로이드 알고리즘이랑 비슷하게 구현과 경로 복원 방법 모두 BOJ에 있는 문제를 가지고 직접 풀어볼거라 별도로 연습 문제 챕터blog.encrypted.gg바킹독님의 블로그를 참고하여 공부한 내용을 기록한 글입니다.플로이드 알고리즘에서는 경로 복원을 위해 nxt[u][v]에 u -> v로 갈 때 u 바로 다음에 방문할 곳을 저장했다. 반면 다익스트라 알고리즘에서는 pre 테이블을 사용한다. 그리고 pre[u] 에는 시작점에서 u로 갈 때 u 직전에 방문해야 할 곳을 저장하면 된다. 두 알고리즘의 경로 복원 방식에 차이가 나는 이유가 뭘까?..

https://blog.encrypted.gg/1037 [실전 알고리즘] 0x1D강 - 다익스트라 알고리즘네 반갑습니다. 이번에는 다익스트라 알고리즘을 해보겠습니다. 플로이드 알고리즘이랑 비슷하게 구현과 경로 복원 방법 모두 BOJ에 있는 문제를 가지고 직접 풀어볼거라 별도로 연습 문제 챕터blog.encrypted.gg바킹독님의 블로그를 참고하여 공부한 내용을 기록한 글입니다.Naive 다익스트라 알고리즘플로이드 알고리즘은 모든 점의 쌍 (All Pair)에 대한 최단 거리를 구하는 알고리즘이다.반면 다익스트라는 한 시작점에서 다른 모든 정점까지의 최단 거리를 구한다. 또한 플로이드는 음수인 간선에 대해서도 문제 없이 최단 거리를 구할 수 있고, 음수 사이클의 경우만 제한이 존재했다. 다익스트라는 음수..

epoll과 멀티플렉싱1. 전통적인 웹소켓 통신Blocking IO 기반의 멀티스레드 방식이다. 클라이언트가 accept()으로 요청하면 새로운 스레드를 생성하고, 생성된 스레드는 해당 클라이언트와 데이터 송수신을 전담한다. 이 과정에서 accept(), read(), write()와 같은 IO 함수들은 데이터가 준비될 때까지 해당 스레드를 Blocking 시킨다.따라서 특정 클라이언트의 느린 IO가 존재한다면 그 클라이언트의 해당 워커 스레드는 Block 된다. 즉, 일시정지된다.2. Non-blocking I/ONon Blocking IO는 IO 작업을 요청했을 때 그 작업이 끝날 때까지 기다리지 않고 즉시 다음 코드를 실행하는 방식이다. 조금 더 정확히 말하자면 제어권을 반환하는 방식이다.fcntl..

RDBMS, NoSQL1. RDBMSRDBMS는 데이터를 관계를 통해 관리하는 시스템이다. 여기서 관계는 테이블로 표현되며 2차원 구조이다.주요 특징Schema-on-Write : 데이터를 저장하기 전 테이블의 구조를 명확히 정의해야 한다.데이터 무결성 보장 : PK, FK 등의 제약 조건을 통해 데이터의 중복을 방지하고 관계의 유효성을 보장한다.SQL (Structured Query Language)트랜잭션 (Transaction)과 ACID 원칙RDBMS는 SQL을 사용할 수 있으며 데이터의 일관성과 신뢰성이 매우 높다. 하지만 그만큼 스키마를 미리 정의하기에 데이터 구조를 변경하기 어렵다. 또한 수평적 확장이 구조적으로 어렵고 JSON, XML 등의 비정형 데이터를 저장하고 처리하기에 비효율적이다...

정보검색의 꽃. 굉장히 중요한 부분이다!이번 챕터의 Term frequency, Tf-idf ranking, Vector space model은 반드시 시험에 나오니 잘 익혀두자.1. Ranked retrieval기존에는 단어가 포함된 문서를 찾는 boolean retrieval을 다루었다. 그런데 어떤 단어는 많은 관련이 있고 어떤 단어는 등장하기만 할 수 있다. 중요도가 없는 것이다. expert users, application에게는 boolean retrieval이 좋을 수 있다. 전문가는 &, |를 잘 설정해서 관련된 문서의 개수를 잘 조절할 수 있지만 일반 사용자들에게는 불가능하다.예를 들어 변호사는 오래 걸리더라도 관련된 모든 정보를 다 봐야 하지만일반 사용자들은 1000개가 넘는 문서를 다..

RDBMS가 수학에 기반한 모델이기에 견고하게 구성되어 있고 모델 뿐 아니라 모델을 잘 활용할 수 있는 인터페이스가 중요했다. 그 인터페이스 중 SQL로 수렴이 됐고 잘 만들어진 언어이다. SQL은 술어논리로 이루어져 있는데 그래서 닫힘 성질을 가지고 있다. operation을 수행했을 때 input과 output이 같은 집합에 속해있다는 것이다. 예를 들어 어떤 집합에 SQL 연산을 수행하면 결과 또한 집합이다.이러한 닫힘 성질 덕분에 operation set 하나만 디자인하면 된다. 만약 결과가 집합이 아니라면 그 결과에 따른 다른 operation set을 만들어야 한다.1. SQL Data Definition and Data TypesSQL 에서는 Table, Row, Column 용어를 사용하고..

오늘은 인턴에서 시킨 번역에 관해서 공부를 먼저 좀 했다. 규모도 작겠다 그냥 API로 번역하면 안 되나 싶었지만 무언가 문제가 있다고 하셔서 여러 방법을 생각해 보았다. 1. 아고다에서는 KantanAI를 사용하고 있었다. 라이브러리나 오픈소스 개념은 아닌 것 같고 AI 모델을 사용해야 하는 것 같은데 아직 AI에 관한 지식이 부족해서 비용이 얼마나 드는지, 중소기업 규모에서 사용할만한지는 판단할 수 없었다. KantanAI- The worlds most advanced machine translation enginesKantanAI is the world’s leading custom neural machine translation technology developer and creators of t..

학기 중엔 바빠서 TIL을 쓸 생각을 딱히 못했는데 방학도 했겠다 슬슬 다시 시작하려 한다. 매일매일의 목표부터 짚고 가자!1일 1문제 풀기1일 1커밋 (CS 스터디, AI 스터디 등)인턴 가기 전 운동정해진 공부 중 하나 꼭 하기 오늘은 인턴 시간에는 대표님이 시키신 아고다 등의 사이트에서 사용하는 언어 번역 방법을 조사했다. 그 과정에서 CMS라는 걸 새로 배웠는데 콘텐츠 관리 시스템이라는 웹사이트 제작 툴이었다. 그냥 쉽게 만드는 툴뿐 아니라 서버와 DB까지 제공하고 플러그인도 많이 제공한다는 것 같은데 솔직히 잘 모르겠다. 크게 쓸 일이 없을 것 같다. 그 외에도 번역 툴을 좀 공부했는데 크게 세 가지가 있다. 파파고, 구글 등 번역 API, CMS 사용, 플러그인 사용여기서 API는 지금 바로 ..

웹 소프트웨어 - 카드피디아템플릿 엔진 사용법과 프론트, 백의 기본 개념이 다져졌다. 생각하지 못한 이득이었다. 사실 뭐 사용법과 개념은 공부하면 되는 거고 진짜 느낀 점은 근거 있는 디버깅의 중요성이었다. 내가 풀스택을 도와가면서 하다보니 백에서 일어나는 오류는 로그로, 프론트에서도 로그로 해결하려 했다. 그런데 규모가 커지다 보니 로그가 어떻게 찍히는지도 모르겠고 많은 오류를 겪어서 차근차근 인터넷 도구의 네트워크 탭과 소스 탭을 확인하고, 로그를 찍어보고, 논리적으로 판단하여 이 부분은 문제가 없다. 혹은 이 부분에 무조건 문제가 있다. 이런 걸 잘 판단하는 능력이 길러졌다. 또 깃을 그나마 체계적으로 사용하면서 원격 저장소, 원본 저장소, 로컬 저장소의 개념을 좀 깨달을 수 있었다. 전문 프로젝트..

오늘은 오랜만에 문제를 하나 풀었다. 그간 스프링 강의만 듣고 문제풀이는 안 했는데 스프링 강의만 듣다 보니 문제풀이 감도 떨어지고 블로그에 글도 잘 안올리게돼서 대회 출처 문제정도만 매일 하나씩 풀기로 계획을 바꿨다. 스프링 강의는 일단 입문은 다 들었다. 스프링과 JDBC에 대해 공부했는데 이게 어떤 기술인지, 어떤 방식으로 작동하는지 정도는 이제 익혔고 다른 강의를 들으면서 더 공부할 예정이다. 개강까지 한 달 정도 남았는데 HTTP 지식과 스프링 지식을 좀 채워서 프로젝트 과목에서 써먹는 게 목표다. 프로젝트를 할 때 좀 중점적으로 해보고싶은게 있는데 주제와 구현 기술 쪽보다는 git를 이용한 협업을 좀 잘해보고 싶다. Test code도 각 메서드별로도 짜놓고 통합도 미리 짜놓고 해서 유지보수가..