[실전 알고리즘] 0x11강 - 그리디안녕하세요, 그리디를 공부해봅시다. 그리디 알고리즘을 한국어로 번역하면 욕심쟁이 알고리즘입니다. 그리디라고 부를 때랑 다르게 욕심쟁이 알고리즘이라고 하면 떼쓰는 어린 아이가 생각나blog.encrypted.gg바킹독님의 블로그를 바탕으로 정리한 글입니다.그리디 알고리즘은 탐욕적으로 지금 상태에서 가장 최적인 답을 선택하는 알고리즘이다.이를 다르게 말하면 관찰을 통해 탐색 범위를 줄이는 알고리즘이다.조금 더 쉽게 풀어보자면 현재 상태를 관찰해서 원래라면 O(N^2) 만큼 탐색해야 하는걸 O(N) 정도로 줄이는 것이다.예를 들어 merge sort를 생각해보자. 병합 과정의 한 step을 생각해보면, 정렬된 결과 배열에 들어갈 하나의 원소를 선택해야 한다.이 과정에서 현..

1. 프로젝트 소개 1-1. Co-Labor : 외국인 근로자 서포트 플랫폼외국인 근로자들이 한국에서 안정적으로 정착하고 적응할 수 있도록 돕는 플랫폼일자리, 정보 부족, 법률 등 외국인 근로자들이 겪을 수 있는 다양한 문제 해결에 도움을 줌프로젝트 인원 : 4명 ( 백엔드 3명, 프론트 1명)개발기간: 2024.07.01 ~ 2024.07.22 / 2024.07.30 ~ 2024.08.02 / 2024.10.03 ~ 2024.10.18  이 프로젝트는 사회적 약자 지원에 대한 주제에서 외국인 근로자도 사회적 약자에 포함되지 않을까? 에서 시작된 프로젝트이다. 우리나라의 저출산은 점차 심해지며, 일손은 부족해지고 이에 따라 외국인 채용을 늘리는 추세이다. 대한민국이 아시아 최초의 다문화 국가가 된 그 흐..

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

이제 위에서 만든 ER 다이어그램을 테이블로 만들기 전에 Relational Data Model과 RDB가 가지고 있는 제약사항을 알아야 한다.1. Relational Model ConceptsRelation에 대한 개념부터 짚고 넘어가자. Relation을 원래 table로 생각을 했지만 이해를 쉽게 하기 위해 table로 생각한 것이지 원래 Relation은 집합을 근본으로 한다. 집합을 근본으로 하는 만큼 정교한 수학을 기반으로 하기에 Relation 개념은 견고하다.Relational Model Concepts은 Dr.E.F.Codd에 의해 집합을 근거로 고안된 수학적인 컨셉이다. 이 컨셉은 구현에 관해서는 전혀 신경쓰지 않고, 이 컨셉을 구현할 때 table을 이용해서 구현하게 된 것이다.Inf..

[실전 알고리즘] 0x11강 - 그리디안녕하세요, 그리디를 공부해봅시다. 그리디 알고리즘을 한국어로 번역하면 욕심쟁이 알고리즘입니다. 그리디라고 부를 때랑 다르게 욕심쟁이 알고리즘이라고 하면 떼쓰는 어린 아이가 생각나blog.encrypted.gg바킹독님의 블로그를 바탕으로 정리한 글입니다.그리디 알고리즘은 탐욕적으로 지금 상태에서 가장 최적인 답을 선택하는 알고리즘이다.이를 다르게 말하면 관찰을 통해 탐색 범위를 줄이는 알고리즘이다.조금 더 쉽게 풀어보자면 현재 상태를 관찰해서 원래라면 O(N^2) 만큼 탐색해야 하는걸 O(N) 정도로 줄이는 것이다.예를 들어 merge sort를 생각해보자. 병합 과정의 한 step을 생각해보면, 정렬된 결과 배열에 들어갈 하나의 원소를 선택해야 한다.이 과정에서 현..

https://www.acmicpc.net/problem/5904N이 10^9 개로 N번째 글자를 구한다는 것이 몇 번째 수열을 구해야 하는지 감도 안잡히고 굉장히 큰 수여서 long long으로도 담지 못한다.즉, 재귀적으로 길이가 n 이상인 수열을 구해서 n번째 문자를  찾으려 한다면 절대 풀 수 없다.조금 다르게 생각해서 n번째 글자만 알면 되므로 어떤 수열에 대해 n번째 글자를 알아내는 과정을 재귀로 생각하여야 한다. 사실 다 풀고 나서야 이렇게 명료하게 말할 수 있지만 풀 때는 다음과 같은 과정을 거쳤다.수열의 길이가 n 이상인 moo 수열 구하기 -> 구현을 다 하고 보니 n이 얼마 이상 커지면 오류k번째 moo 수열 S(k)에 대해 S(k-1)의 길이를 알면 S(k)를 알 수 있음. 그럼 길..

https://www.acmicpc.net/problem/1647예제7 121 2 31 3 23 2 12 5 23 4 47 3 65 1 51 6 26 4 16 5 34 5 36 7 4ans : 8문제의 요구사항은 다음과 같다.도시를 2개로 분할하라.분할된 2개의 도시 사이에는 간선이 존재하지 않는다.각 도시의 마을은 MST로 구성되어 있다.일단 3번 조건을 보면 MST를 구현해야하긴 하는데 어떻게 2개로 분할해야 가장 Minimum한 MST를 만들 수 있을지가 고민된다.N이 100개정도면 완전탐색으로 구현해도 될테지만 N은 10만... 완전탐색은 아니다. 만약 도시 분할 조건이 없다면 바로 MST를 구해도 된다. 그렇다면 MST를 구하는 과정에 Union-Find를 하게 되고 이 부분을 응용해서 2개의 ..

[알고리즘] 최소 신장 트리 - 크루스칼 알고리즘과 Union Find, 백준 1197번 C++ 풀이[실전 알고리즘] 0x1B강 - 최소 신장 트리안녕하세요, 오늘 다룰 주제는 최소 신장 트리(Minimum Spanning Tree)라는 개념입니다. 보통 코딩 좀 치는 사람들 사이에서는 MST라고 많이들 부릅니다. 그런데 Sjun-n.tistory.com  [알고리즘] 최소 스패닝 트리 - 프림 알고리즘이전 글에 이어지는 글입니다. [알고리즘] 최소 신장 트리 - 크루스칼 알고리즘과 Union Find, 백준 1197번 C++ 풀이[실전 알고리즘] 0x1B강 - 최소 신장 트리안녕하세요, 오늘 다룰 주제는 최소 신장 트jun-n.tistory.com크루스칼과 프림이 뭔지 모른다면 위의 두 글을 읽고오자...

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

이제 위에서 만든 ER 다이어그램을 테이블로 만들기 전에 Relational Data Model과 RDB가 가지고 있는 제약사항을 알아야 한다.1. Relational Model ConceptsRelation에 대한 개념부터 짚고 넘어가자. Relation을 원래 table로 생각을 했지만 이해를 쉽게 하기 위해 table로 생각한 것이지 원래 Relation은 집합을 근본으로 한다. 집합을 근본으로 하는 만큼 정교한 수학을 기반으로 하기에 Relation 개념은 견고하다.Relational Model Concepts은 Dr.E.F.Codd에 의해 집합을 근거로 고안된 수학적인 컨셉이다. 이 컨셉은 구현에 관해서는 전혀 신경쓰지 않고, 이 컨셉을 구현할 때 table을 이용해서 구현하게 된 것이다.Inf..

1. Compression정보검색에서의 압축은 다음과 같은 의미를 가진다.dictionary의 크기를 줄이는 것은 메인 메모리에 많이 올릴 수 있다는 것이다.posting file을 줄이는 것은 disk space를 줄이고, disk를 읽는 시간을 줄이는 것이다.Lossy손실이 있는 압축이다.소문자로 바꾸거나 stemming, stop word 제거하는것 등이다.Lossless손실이 없는 압축이다.zip 등이다.딕셔너리를 디스크에 올려놓는게 굉장히 빠르고 좋은데 너무 크다. 따라서 압축을 해야 한다. 압축을 하는 경우 압축을 푸는 시간이 들긴 하지만 디스크에 접근하는 것 보다 훨씬 빠르다.2. Term statistics통계를 다시 보자.number를 제외하거나 case folding, stopword ..

1. IntroductionHardware basics하드디스크보다 메모리가 훨씬 빠르다.그러나 메모리의 양이 매우 적기에 양을 나누어서 메모리에 넣고, external sort를 수행해서 inverted index를 만드는 방식으로 작동하게 된다.디스크에서 정보를 찾는 seek time은 굉장히 느리다. 참고로 seek는 트랙을 찾는 것이고 섹션을 찾는 rotate는 비교적 빠르다.모든 operation을 디스크를 거치지 않고 메모리에서 하면 굉장히 빠르다.한 번 트랙을 찾으면 최대한 많이 읽어오는 것이 유리하고 그래서 block 단위로 저장하는 것이 좋다.Fault tolerance는 비싸다.RCV1 collection정보 검색을 테스트하기 위해 원래 셰익스피어의 희곡을 사용했는데 양이 너무 적었다...

오늘은 인턴에서 시킨 번역에 관해서 공부를 먼저 좀 했다. 규모도 작겠다 그냥 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도 각 메서드별로도 짜놓고 통합도 미리 짜놓고 해서 유지보수가..