기타/SW 사관학교 정글
-
[SW 정글 25일차] LCS는 왜 그렇게 될까?기타/SW 사관학교 정글 2021. 8. 27. 01:35
오늘은 다이나믹 프로그래밍, 그리디 알고리즘을 공부하는 주차로 다이나믹 프로그래밍 문제 중에 LCS(Longest Common Subsequence, 최장 공통 부분 수열)라는 문제가 있었다. https://www.acmicpc.net/problem/9251 9251번: LCS LCS(Longest Common Subsequence, 최장 공통 부분 수열)문제는 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다. 예를 들어, ACAYKP와 CAPCAK의 LCS는 ACAK가 된다. www.acmicpc.net 이전에 푼 경험이 있어 접근법을 알고 있어 나는 풀기는 했지만 다른 동료가 와서 왜 이렇게 되는지에 대한 질문을 던졌고 나는 명확한 답변을 해주지 못했다. 질문은..
-
SW 정글 3주차 회고기타/SW 사관학교 정글 2021. 8. 26. 20:08
[3주차 회고] 2021년 08월 26일 목요일, 3주차가 마무리 되는 날이고 3주차는 전체적으로 어땠는지 이 글을 쓰면서 돌아보려고 한다. 3주차는 전체적으로 여유롭고 개인적인 시간을 가질 수 있던 주였다. BFS, DFS, 위상 정렬이라는 알고리즘이 쉽다는 것이 아니라 어떻게 보면 하나의 범주이고 문제 접근방식이 비슷하기에 여유롭게 느껴진 것같다. 하지만, 3주 만에 여유라는 것을 느낀 나에게는 꿀로 위장한 독이였다고도 생각이 든다. 너무 마음이 편안한 나머지, 해이해졌다는 느낌을 받았고 그 느낌이 든 순간 다시 정신을 차리고 몰입에 시작했다. 하루를 알고리즘에 쏟아부으니 잘 집중도 안되고 특히 아침에는 너무 졸려서 새로운 것(Spring framework)를 공부해보니 재미있고 집중도 잘되고 오랜만..
-
[SW 정글 24일차] 플로이드 와샬 알고리즘이 궁금하다기타/SW 사관학교 정글 2021. 8. 26. 01:37
오늘은 DFS, BFS, 위상정렬을 공부하는 마지막 날로 복습을 하고 다른 동료들의 블로그를 보며 어떻게 문제에 접근했는지 살펴보았다. 그 중에서 알고리즘 공부를 꽤 하고 왔던 동료의 블로그를 보게 되었고 새롭고 신기한 알고리즘을 알게 되었다. https://kspsd.tistory.com/15 백준 2617 구슬 찾기(python) 문제 https://www.acmicpc.net/problem/2617 2617번: 구슬 찾기 모양은 같으나, 무게가 모두 다른 N개의 구슬이 있다. N은 홀수이며, 구슬에는 번호가 1,2,...,N으로 붙어 있다. 이 구슬 중에서 무게가 전체의 중. kspsd.tistory.com 문제를 보고 플로이드 와샬 알고리즘이 떠올라서 적용을 한 것이다. 개인적인 시간이 부족했다면..
-
[SW 정글 23일차] 트라이 (Trie) 알아보기기타/SW 사관학교 정글 2021. 8. 25. 02:22
오늘은 아래의 문제를 풀면서 새롭게 안 트라이(Trie)에 대해 정리해보려고 한다. 문제를 통해 알게 되어 내가 공부한 것을 정리하는 것도 있지만 내가 평소에 검색기능을 이용하면서 자동완성을 많이 경험하곤 했는데 이 자동완성에 쓰인 알고리즘을 알았다는 것이 신기해서 정리하는 것도 있다. 1. 트라이(Trie)란? 트라이(trie)는 문자열을 저장하고 효율적으로 탐색하기 위한 트리 형태의 자료구조이다. 여기서, 트리 형태에 대해서는 아래의 글에 정리했으니 혹시 모르겠다면 참고하면 좋을 것같다. https://straw961030.tistory.com/192 [SW 정글 13일차] 트리 구조와 이진 트리 1. 트리 구조 트리 구조는 데이터 사이의 계층 관계를 표현하는 자료 구조로 노드(node)와 가지(ed..
-
[SW 정글 22일차] 내가 생각하는 추상화는?기타/SW 사관학교 정글 2021. 8. 24. 02:07
오늘은 컴퓨터 시스템책을 읽으면서 가장 많이 나오지만 개념을 잘 알고 있지 못하는 추상화에 대해 공부를 했다. 추상화라는 단어는 그냥 어떠한 것을 구체적이고 명확하게 나타내지 않고 뭔가 흐릿하게 혹은 간단하게 생각만을 옮겨놓은 것이라고 생각한다. 하지만, 이 추상화라는 단어가 컴퓨터 구조에서는 어떻게 적용되어서 쓰이고 왜 쓰이는지가 궁금했다. 에는 추상화라는 단어가 아래와 같이 쓰였다. 운영체제는 세 가지 근본적인 추상화를 제공한다. (1) 파일은 입출력장치의 추상화다. (2) 가상메모리는 메인 메모리와 디스크의 추상화다. (3) 프로세스는 프로세서, 메인 메모리, 입출력 장치의 추상화다. 대충 문맥 상 A가 B를 추상화했구나라고 이해는 할 수 있지만 조금 더 명확하게 개념을 잡고자한다. 1. 추상화란?..
-
[SW 정글 21일차] 자료구조 복습하기기타/SW 사관학교 정글 2021. 8. 23. 00:48
오늘은 시간이 조금 여유로워서 지난 날들에 했던 정렬, 큐, 스택, 힙 등을 복습하는 시간을 가졌다. 복습을 하면서 정리하지 못했거나 처음 해본 내용들을 기록해보려고 한다. 1. 스택으로 큐 구현, 큐로 스택 구현 오늘 알아본 것 중 하나는 스택으로 큐를 구현하고 큐로 스택을 구현하는 것이다. 이미 알다시피 스택은 입출력 구조가 FILO형식이고 큐는 FIFO형식이기 때문에 스택 2개로 큐를 구현하고 큐 2개로 스택을 구현해야한다. 먼저, 스택 2개로 큐를 구현해보는 것을 알아보자. 기본적인 원리는 스택 A, 스택 B가 있다면 스택 A는 데이터를 넣어주는 용도로 쓰이고 스택 B는 데이터를 빼주는 용도로 쓸 것이다. 그림을 보며 무슨 말인지 이해해보자. 일단은 데이터가 1, 2, 3 순서대로 스택 A에 pu..
-
[SW 정글 20일차] 위상 정렬 (Topological Sort)기타/SW 사관학교 정글 2021. 8. 22. 01:47
오늘은 위상 정렬에 대해 정리해보려고 한다. 처음 듣는 알고리즘이여서 오늘 이렇게 공부를 하고 다시 복습을 하며 내 것으로 만들어야겠다. 1. 위상 정렬 (Topological Sort) 위상 정렬은 순서가 정해져있는 작업을 차례로 수행해야 할 때 그 순서를 결정해주기 위해 사용하는 알고리즘이다. 순서가 정해져있는 작업에서 각 작업들은 직전 작업에 의존하게 된다. 예를 들어 C라는 작업을 끝내기 위해서는 A작업과 B작업이 끝나야지만 가능하다고 해보자. C는 A와 B가 끝날때까지 일을 실행하지 못하므로 A와 B에게 의존하고 있다고 볼 수 있다. 여기서 위상 정렬이 순서를 결정해준다고 했지만 그 순서가 딱 하나만 존재하는 것은 아니다. 위에서 든 예시만 봐도 A -> B -> C가 될 수 있고 B-> A -..
-
[SW 정글 19일차] DFS와 BFS기타/SW 사관학교 정글 2021. 8. 21. 01:42
이번 주차는 DFS, BFS, 위상정렬에 대해 공부하는 주차로 그냥 단순히 DFS가 무엇인지, BFS가 무엇인지 알고만 알고리즘 문제를 풀어와서 이번 기회에 이렇게 글로 정리하며 개념을 다잡으려고 한다. 1. DFS (Depth-First Search) DFS는 그래프 탐색 알고리즘 중 하나로 그래프에서 깊은 부분을 우선적으로 탐색하는 알고리즘으로 시작점부터 다음 분기(branch)로 넘어가기 전에 해당 분기를 완벽하게 탐색하고 넘어가는 방법이다. DFS는 스택 자료구조나 재귀함수를 이용하여 구현할 수 있고 노드를 탐색 전에 방문 여부를 검사해야한다. DFS의 시간 복잡도는 인접 리스트로 표현된 그래프에서는 O(N+E)이고 인접 행렬로 표현된 그래프에서는 O(N^2)이다. 그래프 탐색이란? 그래프에서 하..