의식이 흐르는대로 해보는 프로그래밍

Training Method LoRA: Low-Rank Adaptation of Large Language Models QLoRA: Efficient Finetuning of Quantized LLMs Dataset Orca: Progressive Learning from Complex Explanation Traces of GPT-4 Model Textbooks Are All You Need: Phi-1 SOLAR 10.7B: Scaling Large Language Models with Simple yet Effective Depth Up-Scaling Extra MoE(Mixture of Experts) MoE 관련 논문들 Velog

접근 세상에나 중간에서 만나기라는 알고리즘이 있다는 것이 신기하다. 부분수열의 합은 고등학생 때 부분집합의 갯수를 구하는 공식을 떠올려보면 이해하기 쉽다. 고등학생 때 전체 집합의 원소의 갯수가 $ N $ 개라면, 부분집합의 갯수는 $ 2^N $이 되었다. 그런 이유는 공집합에 원소마다 [넣기 / 안넣기] 2가지의 선택권밖에 없었기에, $ 2 * 2 * ... * 2 = 2^N $으로 도출될 수 있는 것이다. 여기선 최악의 경우를 생각해보면, $ O(2^{40}) $의 시간복잡도가 나오게 된다. 중간에서 만나기는 이분 탐색과 분할 정복의 형태와 비슷하다. 이분 탐색은 매 탐색마다 $ N / 2 $ 를 수행해서 시간 복잡도가 log 단위로 나오는 반면, 중간에서 만나기는 처음 한번 $ N / 2 $ 수행하..

접근 팰린드롬 문자열의 전체 분할 갯수의 최솟값을 구하는 문제이다. 문자열의 최대 길이는 2,500자이기에 인덱스 연산으로 팰린드롬 분할 전체를 구해내는 것은 힘들어보였다. 사실 이 문제는 DP 문제인데. 팰린드롬 공부를 좀 더 자세히 해보고싶어서 찾아보다, Manacher's Algorithm을 알게 되었다. 그래서 팰린드롬을 공부하는겸 Manacher's Algorithm을 이용해서 한번 문제를 해결해봤다. 해결 Manacher's Algorithm Manacher씨가 개발한 Longest Palindromic Substring을 $ O(n) $ 의 시간복잡도로 찾는 엄청난 알고리즘이다. 이 문제를 해결하면서 아래의 링크들을 참고했다. https://en.wikipedia.org/wiki/Longes..

요즘 내 일상 오전 9시30분즈음 기상 오전 10시 30분즈음 아침식사 오전 11시 50분즈음 스터디카페 도착 커피 다과 좀 즐기고 오후 12시30분즘 공부 시작 알고리즘 해결 및 블로그 포스팅 평균 약 3시간 즈음 하는 듯 오후 4시부터 다른 공부 시작 => 일반적으로 AI소식 찾아보기 / 사이드 프로젝트 프론트엔드 구현.. 오후 5시 30분즈음 저녁식사 복귀 후 오후 7시부터 공부 다시 시작 오후 9시30분에서 10시즘 귀가 취준 생활 진행하며 최근에는 거의 이러고 살고 있는 것 같다. 지루한가? 지루하단 생각도 안든다. 생각보다 내가 하고 있는 것들의 흥미는 아직 붙어있는 상태. 요즘은 Small-LLM(내 기준 7B에서 13B)모델들이 많이 나오기 시작하며, 해당 모델들에 대한 관심이 크다. 또 ..

접근 보석 도둑이라 그래서 DP 문제일 줄 알았지만, 그리디 형태로 접근하는 문제였다. 아. 그리디 너무 싫다. 너무 어렵다. 문제 자체는 간단한데 풀이방법에서 이게 맞을까? 하면 이게 맞는 그런 문제들이다 항상.. 처음 접근은 수집하지 않은 보석을 저장해두기 위해, heap트리 두개를 사용해서 접근했는데 시간초과가 났다. 분명 접근은 맞는 것 같은데, 시간 초과를 해결할 수가 없어서, 질문 게시판을 찾아보며 다른 사람들은 어떻게 구현했는지 보고 구조를 참고하여 해결했다. 해결 그리디 문제는 욕심쟁이기 때문에, 문제에 정렬이나, 우선순위 큐(힙 트리 등) 구조를 활용하여 조건이 되는 애들 중에 가장 큰 값을 챙기려고 하는 의도가 담겨있다. 그 의도를 생각하며, 아래 해결을 참고해보자. 먼저 보석과 가방의..

접근 주어진 그래프에서, 가중치가 최소가 되도록 하는 모든 정점을 연결하는 부분 그래프를 구하는 문제이다. 최소 스패닝 트리는 대표적으로 Kruskal 알고리즘을 활용할 수 있다. Kruskal 알고리즘은 아래와 같은 절차를 따른다. 간선들의 가중치를 오름차순으로 정렬 오름차순으로 간선들의 탐색을 진행하며, 사이클을 만들지 않는 정점들을 연결 포함된 간선의 갯수가 `정점의 갯수 - 1` 가 되면 종료 Kruskal 알고리즘을 진행할 때, 사이클을 체크하는 과정은 대표적으로 Union-Find 알고리즘을 활용한다. 간단하게 생각하면 A-B 친구, B-C 친구, A-C? => 친구 이런식의 해결방법이다. 아래는 알고리즘 진행에 대한 좋은 설명 자료이다. 해결 Kruskal 알고리즘과 Union-Find를 이..

접근 순차적인 접근으로, 우선시 되는 건물의 건설 시간 중 가장 긴 시간을 갖도록 목표 건물의 건설 시간을 구하는 문제. 느낌적으로 봤을 땐, DP, 그래프 탐색 이론등을 통해 해결할 수 있을 것 같다. 또한 사이클이 존재하지 않는다면, 위상정렬을 통해 또한 해결이 가능할 것 같아 보였다. 결론적으로는 위상정렬을 사용해서 해결했다. 위상정렬은 뭔가? https://ko.wikipedia.org/wiki/%EC%9C%84%EC%83%81%EC%A0%95%EB%A0%AC 위상정렬 - 위키백과, 우리 모두의 백과사전 위키백과, 우리 모두의 백과사전. 위상 정렬(topological sorting)은 유향 그래프의 꼭짓점들(vertex)을 변의 방향을 거스르지 않도록 나열하는 것을 의미한다. 위상정렬을 가장 잘..

접근 이진 탐색 트리의 전위 순회 결과만을 이용해서, 후위 순회 결과를 복원해내는 문제이다. 이진 탐색 트리의 전위, 중위 순회결과를 이용해서 트리를 복원해내는 방법이 있는데, 그 방법을 차용해서 해결했다. 해결 전위, 중위 순회 결과만이 있다면, 이진 탐색 트리는 복원이 가능하다. 전위 순회 결과는 항상 맨 처음의 값이 루트 노드이다. 중위 순회 결과는 `Left - Root - Right` 순서이기에, 특정 노드 기준으로 왼쪽 부분결과는 Root보다 작은 값들이고, 오른쪽 부분 결과는 큰 값들이다. 이 두가지 성질을 이용한다면, 이진 탐색 트리를 복원해낼 수 있다. 하지만 우리는 중위 순회 결과가 없기에, 중위 순회 결과를 만들어내야한다. 그냥 그건 간단하다. Root Node보다 작은 값들을 찾아서..

접근 치즈가 녹아내리는 문제다. 치즈 안쪽으로는 냉기가 있어서, 바깥쪽부터 녹는다는 아주 현실적인 문제. 중요한 포인트는 두가지다. 치즈 바깥쪽의 공기를 인식하는 것. 외부 공기와 접촉한 치즈만을 판단하는 것. 이 두가지만을 주의하고 문제를 해결하면 쉽게 해결이 가능하다. 해결 치즈 바깥쪽의 공기만을 인식하는 건 어떻게 하면될까? 치즈 내부의 공기를 생각해보자. 치즈 내부의 공기는 치즈로 둘러싸여있을 것이다. 그렇다면, 치즈인 곳은 탐색을 진행할 때 어떤 탐색(dfs, bfs)이든, 넣어주지 않게되면, 치즈 안쪽으로는 절대 탐색이 불가능하게 될 것이다. 그걸 이용해서 치즈 외부공기를 먼저 인식해주자. 그렇게 외부공기를 인식한다음, 그냥 이중 반복문으로 해결해도 되고, 또 효율적인 탐색법을 이용해도 좋으니..

접근 문제 자체는 복잡해보이지 않았다. 지나온 알파벳은 다시 들리지 않는다. 이게 이 문제의 중점이었던 것 같은데, 나는 백트래킹 최적화에 애를 먹어서 몇가지 기억하려고 남기려한다. 해결 사실 백트래킹 방법이 아니라, 충분히 BFS로 풀 수 있어보이지만 그냥 앞서서 N과M 문제 풀다보니, 백트래킹으로 해결하려고 시간을 썼다. 근데... 자꾸만 시간 초과가 나서 몇가지 최적화를 진행했다. 일단 백트래킹에 대해서 잠깐 서술해보자면, 영어 그대로 Back Tracking이다. 백트래킹은 재귀적으로 접근하는 알고리즘이다. 모든 경우를 고려하며, 재귀적으로 탐색을 진행하다가 특정 조건에 맞지않는 경우를 제외하고, 다시 탐색을 진행하는 것이다. DFS를 재귀로 구현할 때를 생각하면 형태가 거의 비슷하여 알고리즘의 ..