전체 글689 [계산 이론] The Halting Problem 컴퓨터를 전공 배우고 있는 사람 입장에서, Halting Problem정도는 한번 증명해 보고 정리해 두면 좋을 것 같다 생각하여 글을 남겨봅니다! 1. Halting Problem 이란? 우선 정의부터 살펴보자! There’s no algorithm that can look at a program’s source code and always correctly determine if the program will run forever or not. 사람의 언어로 조금 바꿔보면, 유한시간안에 프로그램을 실행해보지 않고 정지할지 말지를 결정하는 알고리즘은 존재하지 않는다는 의미이다! 2. Proof by contradiction 다음과 같이 "input과 output을 갖는 halt라는 프로그램(알고리즘)이.. CS/Computation Theory (2023-2) 2023. 12. 12. [계산 이론] Some languages are not Turing-recognizable 이번 증명을 통하여 Turing Machine이 recognize하지 못하는 Language가 있음을 보일 것 이다. 1. 모든 Turing Machine은 countable 하다 모든 튜링머신이 Countable함을 보이기 전에, 우선 모든 String의 집합(∑*)이 모든 alphabet ∑에 대하여 count할 수 있음을 보일것 입니다. ∑* 의 list를 길이가 0, 길이가 1, 길이가 2 ... 순으로 아래로 적어내려 갈 수 있습니다. 또한 각 lenght마다 finite한 수의 String이 있습니다. 이를 그림으로 살펴보면 다음과 같은데, 길이가 0인 String에는 입실론이, 1에는 0과 1, 등등 이 존재합니다. 모든 자연수 1, 2, 3, ... N에 대하여 mapping가능한 하나의 .. CS/Computation Theory (2023-2) 2023. 12. 12. [계산 이론] Non-Context-Free Languages 1. The Pumping Lemma for Context-Free-Languages(CFL) 우리는 보조 정리인 Pumping Lemma를 활용하여 CFL이 아님을 보일 것 이다. 만약 A가 Context-free-lenaguage라면, pumping length p가 존재하며, A의 어떤 String S라도 최소 p만큼의 길이를 갖는다. 또한 그러한 S는 5조각, 즉 S = uvxyz로 나눌 수 있으며, 다음 조건을 만족한다. 조건 2에 의하여 v 또는 y 가 동시에 empty string일수는 없다. 조건 3에 의하여 v,x,y의 길이는 최대 p이다. 2. Proof G를 CFL A의 Context-Free-Grammer(CFG)라 하자. b를 symbol의 최대 수 라고 하자. 예를 들면 다음 C.. CS/Computation Theory (2023-2) 2023. 12. 10. [알고리즘] 최소 공통 조상 LCA(Lowest Common Ancestor) 1. LCA란? LCA(Lowest Common Ancestor)는 주어진 두 노드 a와 b의 최소 공통 조상을 찾는 알고리즘입니다. 예를 들어 다음 그림과 같은 트리가 있다고 했을 때, 12번과 15번 노드의 최소 공통 조상 LCA는 5번 노드가 됩니다. 우선 두 노드의 LCA를 찾는 가장 간단한 O(N)이 걸리 방법으로 2가지 정도가 있다. 2가지에 대하여 간단하게 알아본 후, 이글의 Main 목표인 O(LogN) 안에 해결하는 알고리즘에 대하여 알아보자. 2. O(N) 알고리즘 2-1) 두 Node의 Level을 통일시키는 방식 A와 B의 깊이가 다를 경우 더 깊은 정점의 부모를 따라 하나씩 올라가면서 A와 B의 깊이를 맞춘다. 위의 결과 A와 B가 같다면 A(or B)가 최소 공통조상이다. A !.. Algorithm/PS 알고리즘 정리 2023. 12. 8. [Kafka] Kafka Connect on Docker 1. 문제의 상황 MSA 토이프로젝트를 진행하던 도중 Local에서만 사용하던 Kafka와 Kafka Connector를 Container로 만들어 사용해야 하는 일이 발생하였다. 따라서 모든 서비스에 Dockerfile을 만들어 커테이너화 시켜주었으며, 추가적으로 DB와 Kafka또한 컨테이너화 시켜야 했다. 우선 MSA 토이 프로젝트의 구조는 다음과 같다!! 간단한 쇼핑몰 서비스 이며, 오늘 글에서 다룰 부분은 Order-Service와 Kafka 부분이다. 그냥 Kafka 자체만 필요하면 제공되는 Docker 이미지 사용하면 끝이라 쉽지만, 그 외 Connector를 함께 사용하려 하니 준비해야 할 점이 추가적으로 있었다. 또한 DB에 저장하기 위해 최종적으로 JDBC 라이브러리 또한 필요하여 추가.. BackEnd/Kafka 2023. 12. 6. [알고리즘] HeapSort보다 QuickSort가 더 빠른 이유 1. 왜 HeapSort보다 QuickSort가 현실적으로 더 빠를까? HeapSort와 QuickSort는 대표적으로 O(NlogN)안에 동작하는 정렬알고리즘이다. 하지면 현실성면에서 QuickSort가 더 빠르다는것은 익히 들어 알고있을 것 이다. 왜 그런것 일까? 이에 대하여 알아보자 1-1) 알고리즘의 성능 요인 크게 정렬 알고리즘에서 성능을 미치는 원인은 크게 3가지로 볼 수 있다. 비교 및 스왑을 수행하기 위한 반복자(loop) = 반복자가 어떻게 구현되어있는가의 문제 유효 접근 시간 (지역성) 메모리 소비량 1번의 경우 대부분 시간복잡도를 측정할때 고려하는 요소라, O(NlogN)이라는 표기안에 포함되어있는 개념이다. 따라서 HeapSort와 QuickSort의 차이는 2번인 유효 접근 시간.. Algorithm/PS 알고리즘 정리 2023. 10. 13. [쿠링] 사용자 인증의 시작부터 끝까지의 여정 항상 프로젝트를 진행할 때마다 한 번씩은 고민해 왔던 문제가 있다. 바로 "인증, 인가 가 과연 해당 서비스의 핵심 비즈니스 로직인가?"에 대한 고민이다. 경험이 부족했던 시점에야 당연히 이러한 생각조차 하지 못하여 논의할 내용조차 없었다 경험이 조금 있는 시점에서는 일단은 API수준에서 구현은 가능하지만 이를 어떤 방식으로 분리해야 할지 몰랐다. 이번 글에서는 이러한 나의 고민을 스스로 적어보고, 해결해나가는 과정을 기술할 것이다! (즉, 지극히 개인적인 내용.... 태클 환영) 고민 1 : Core Business란 무엇인가? 경계가 있는가? 가장 우선적으로 고민했던 부분은 Core Business라는 것 이 뚜렷한 경계가 있는 것 인가였다? 이에 대한 확인을 위해 위대하신 GPT에게 질문을 던져보았.. BackEnd/쿠링 2023. 10. 7. [쿠링] 효율적인 Log 관리를 위한 여정 - 1 1. 문제가 되는 상황 여유가 생겼을 때 쿠링이 Log를 남기고 있는 과정에 대하여 한번 고민해보고 싶었다. 오늘 글은 크게 3가지에 대한 고민으로부터 시작되었다. 1) Log의 level이 적합한가? (이번 글에서 해결할 내용) 2) Log 파일의 사이즈가 너무 커지지 않도록 나뉘어 저장되고 있는가? (이번 글 에서 해결할 내용) 3) Log의 모니터링이 편리하게 되고 있는가? (추가 글에서 다룰 예정) 일단 2가지에 대하여 답해보면, 현 쿠링은 "아니요"라고 답할 수 있을 거 같다. 크게 기준없이 설정된 log들의 level, 더 나아가 log를 보기 위해서는 직접 EC2에 접근하여 로그 파일을 살펴봐야 했다... 또한 로그가 중요하다는 생각에 무분별하게 남기는 것이 과연 좋은가? 나는 습관적으로 예.. BackEnd/쿠링 2023. 8. 27. [Nexters] 23기 7주차 기록 1. 7주 차 활동 이번주는 넥나잇(넥스터즈 밤샘의 날) 기간이었다!! 나이가 들어 그런지 ㅋㅋㅋㅋㅋㅋㅋ 10시에 바로 집에 갈 생각부터 들더라 ㅋㅋㅋㅋㅋ 실제로도 우리 팀은 전원 정규시간인 10시까지만 작업을 수행한 후, 모두 귀가하게 되었다!! 이번 7주 차는 특히 네이버 클라우드에서 지원해 주신 가방들과, 여러 상품을 걸고 게임과 이벤트 등이 있었다!! 밤샘 시간에는 "피카추 배구 토너먼트"도 있었다고 한다 (우리 팀은 집에서 자고 있었을 듯...??? 크허...) 또한 Nexters에서 맛있는 간식을 준비해 주셨는데!! 간식을 가져가는 순서가 사다리로 정해지게 되었다!! ㅋㅋㅋㅋㅋ 우리 팀은 10팀 중 10등!!! 가장 마지막으로 간식을 가지고 가게 되었는데..... 와 이걸 10등을 하네? 스스.. Life/Nexters 2023. 8. 20. [Linkllet] 검색 쿼리 개선하기 (by 커버링 인덱스) 우선 이번 테스트는 M1 맥북, 메모리 16G의 노트북에서 docker 환경의 MySQL에서 수행되었습니다. 전체 article 데이터 약 87만건을 기준으로 실험하였습니다. 1. 문제 되는 상황 우선 원래의 "프로그램"을 검색하는 query는 다음과 같다. select a.article_id, a.title, a.link, a.created_at from article a where a.member_id = 1 and (a.title like '%프로그램%' escape '!') order by a.created_at asc; 실행 결과는 다음과 같다. 약 2.4초가 걸렸으며, 데이터의 건수는 485건이 조회된다. 검색 쿼리의 실행계획은 다음과 같다. 몇 가지 살펴보자! type이 ALL로 되어 있는거.. BackEnd/Linkllet 2023. 8. 13. [Kafka] Multi-Service 간의 데이터 동기화 1. 문제의 상황 여러 개의 독립된 Order Service가 동작하고 있는 상황에서, 각 OrderService마다 DB를 할당하게 된다면 동기화 작업이 힘들어진다. 예를 들어 초콜릿의 재고가 초기에 10이었을 때, OrderService A에 주문이 들어와 3개가 감소하여 7개가 되었다 생각해 보자. 하지만 OrderService B에 할당된 DB에는 여전히 재고가 10개 있으며, 이는 DB 간의 데이터 동기화를 어렵게 만드는 주범이 될 것이다! 예를 들면 다음과 같은 것이다! 현재 사이드로 구현 중인 미니 프로젝트에서 UserService에서 주문 요청 -> Service Discovery를 통해 해당 서비스 찾기 -> 해당 OrderService에 주문 요청을 하게 된다. 2개의 OrderServ.. BackEnd/Kafka 2023. 8. 8. [Nexters] 23기 5주차 기록 1. 5주 차 활동 이번 주차는 중간발표의 날이었다! 이번 주차의 경우 각 팀별로 중간 점검을 함과 동시에, 발표를 진행하는 시간이었다! 당연히 나 같은 경우 발표를 길게 하는 스타일이 아니기 때문에 "어떻게 해야 핵심만 전달하고 끝날까?"를 고민했고, 그 결과 다음과 같이 단 한 장의 메인을 중심으로 PPT 발표를 진행하게 되었다! 우리 팀 앱 스토어에 나왔다~ 스토어에 Linkllet 앱을 배포하게 되었다!, 당시에 안드로이드는 심사 중이라 배포가 되지 못했지만, 금방 2일 안에 배포되어 현제는 구글스토어에서도 확인해 볼 수 있다! 이 이상 뭐가 필요한가! 이후에는 앱의 메인 기능을 짧게 설명한 후, 현 상태에서 아쉽게 느껴지는 기능들을 설명한 후 어떻게 개선할지 설명하게 되었다. 다행히 생각한 것처.. Life/Nexters 2023. 8. 3. 이전 1 2 3 4 5 ··· 58 다음
