그래프 순회 저번에 배운 깊이 우선 탐색(Depth First Search) - 스택을 이용하여 그래프를 순회하는 방법 너비 우선 탐색(Breadth First Search) - 큐를 이용하여 그래프를 순회하는 방법 너비 우선 탐색(BFS) 인접한 노드들을 우선 모두 색칠해 두고 뻗어나간다. 위의 그림에서 너비 우선 탐색을 사용한다고 하자. 우선 1을 큐에 넣고, (1)을 제거한다. -> 현재 노드 위치 1의 인접 노드인 2와 4를 큐에 넣는다. 이후 1의 이웃한 노드들이 모두 색칠되었으므로, 큐의 제일 앞 노드를 제거한다.(2) 2가 제거되었으므로 현재 노드 위치는 2이다. 2의 인접 노드인 3을 큐에 넣는다. 4는 이미 추가되어있으므로 추가하지 않음. 2의 인접 노드가 모두 색칠되었으므로, 큐의 제일..
5주 차에서 다룰 내용은 다음과 같다. 1. Operating System 운영체제란? 프로세스 vs 스레드 프로세스 주소 공간 Interrupt 2. Spring Test Code(JUnit5) JPA JPA 더티 체킹 Spring Security - 인증 및 권한 부여 Operating System 운영체제란? 운영 체제는 사용자가 컴퓨터를 편리하고 효과적으로 사용할 수 있도록 환경을 제공하는 시스템 소프트웨어이다. 운영체제의 역할 1. 프로세스 관리 운영체제에서 작동하는 응용 프로그램을 관리하는 기능이다. 현재 CPU를 점유해야 할 프로세스를 결정하고, 실제로 CPU를 프로세스에 할당하며, 이 프로세스 간 공유 자원 접근과 통신 등을 관리하게 된다. 2. 저장장치 관리 1차 저장장치에 해당하는 메인..
2주 차는 전 기수에도 나왔던 숫자야구였다. 문제 자체의 알고리즘을 짜는 것은 쉬웠다고 생각하였다. 하지만 MVC패턴을 적용하는 것은 생각보다 쉽지 않았다. 기존에 Spring을 했지만, 알고리즘을 MVC로 나누는 것은 처음이었다. 그래서 이번 주는 알고리즘에 대한 고민보다는 구조화에 대한 고민을 많이 하였다. 이번에도 생각보다 커밋수가 많이 나왔다. 처음에 작성했던 커밋수와 이후 리펙토링을 한 커밋의 수가 거 비슷하였다. 리펙토링은 끝이 없다고 생각한다. 1주 차 공통 피드백을 받았는데, 내용은 아래와 같다. 1. 요구 사항을 정확히 준수한다. 2. 커밋 메시지를 의미 있게 작성한다. 3. git을 통해 관리할 자원에 대해서도 고려한다. 4. Pull Request를 보내기 전 브랜치를 확인한다. 5...
그래프 순회 - 그래프라는 자료구조에 어떠한 값이 저장되어 있는가? 깊이 우선 탐색(Depth First Search) 스택을 이용하여 그래프를 순회하는 방법 스택 = 선행 관계 - 나를 먼저 방문하고 그다음으로 인접한 노드를 차례로 방문(단, 방문했던 노드는 방문하지 않는다.) 깊이 우선 탐색의 예시 위 그래프는 1 - 2 - 3 - 4 - 5 - 6 순으로 방문하게 된다. 중요한 점은 더 이상 갈 곳이 없다면, 왔던 곳으로 돌아간다.(재귀) 좀 더 복잡해 보이는 그래프를 보자. 위에 보이는 순서대로 방문하게 되고, 화살표의 모양대로 다시 돌아오게 된다. 가장 깊은 4까지 간 뒤 더 이상 갈 곳이 없기 때문에 돌아오면서 방문하지 못한 곳을 방문하게 된다. DFS 구현 DFS를 구현하고, 코드를 보며 자..
교내 SW 프로그램 경진 대회에서 운 좋게 수상하게 되어 상을 받으러 갔다. 개발을 시작하고 처음 받아보는 상이라 낯설기도 하였지만, 기분이 좋았다. 사실 아직 부족한 점이 많아서 수상을 못할 것이라 생각했었기에 얼떨떨한 마음도 있었다. 너무 일찍 가서 사람이 없었다. 밖에는 각팀들의 패널이 전시되어있었다. 우리 팀이 만든 봐라오케 패널이다. 기능을 더 추가하지 못한 게 아쉽게 느껴졌다. 운 좋게 좋은 팀들을 만나서, 협업이라는 귀한 경험을 했다. 팀원들과 함께 사진을 찍으며 마무리하였다. . 이전의 글에도 작성했지만, 이번 대회가 나에게 있어서 매우 값진 경험이었다. 단순하게 백엔드만 잘한다고 끝이 아니었다. 프론트와 소통하며, 내가 부족한 부분이 무엇인지 알게 되었다. 개발은 혼자 하는 것이 아니기 ..
그래프란 다음과 같은 모습을 가지고 있다. 즉 그래프는 각각의 정점이 간선으로 연결되어있는 모습이다. 그래프는 왜 중요한가? 현실 세계의 많은 것들을 그래프로 나타낼 수 있다. - 즉 그래프와 관련된 문제가 매우 많다. 그래프와 관련된 수학적 정리가 매우 많다. - 그래프 이론이라는 분야가 따로 있다. 그래프에 관한 중요한 수학적 지식 간선의 개수는 정점의 제곱보다 작거나 같다. -> 항상 참 각 정점의 차수의 합은 간선의 개수의 2배와 같다. -> 항상 참 - 차수는 각 정점에 연결되어 있는 간선의 수 차수의 합을 구할 때, 각 간선을 두 번씩 세기 때문이다. 그래프의 구현 : 인접 행렬 정점의 연결 관계를 2차원 배열에 0,1로 표현한다. 장점: 연결 여부를 O(1)에 알 수 있다. 단점: 인접한 정..
1주 차 과제는 알고리즘을 푸는 문제였다. 난이도가 엄청 높지는 않았지만, 단순하게 문제를 푸는데 목적을 두지 않고 클린 코드로 작성하려 하니 힘들었다. 기존에 문제를 풀 때는 변수명이나 메서드명을 단순하게 그때 풀고 끝이라는 생각을 하고 대충 지었다. 내가 기존에 작성했던 코드는 남이 봤을 때, 이해하기 어려웠을 것이라는 생각을 하였다. 그래서 모든 이름을 다 의미 있고, 알아보기 쉽게 표현하려 노력하였다. 메서드가 한 가지 일을 수행하도록 분할을 하였다. 이 방법을 사용하니, 나중에 리펙토링을 하려 할 때 매우 유용하였다. 분할을 하기 전 미리 어떠한 기능을 구현할지 나누어 작성한 다음 설계하니 더욱 편하였다. 가장 어려운 점은 인덴트를 최대한 적게 사용하는 것이었다. 기존의 코딩 방식과 달라서 이 ..
자료구조에서 트리는 다음과 같은 모습을 가진다. 아마 위의 사진만 보고도 대충 짐작을 할 수 있을 것이다. 트리는 자식 노드와 부모 노드로 이루어져 있다. 자식 노드에서 부모 쪽으로 계속해서 타고 올라가다 보면 결국 부모가 없는 하나의 노드로 이어지게 되는데, 이 노드를 루트 노드라고 부르며, 루트 노드를 중심으로 뻗어나가는 모습이 나무의 구조와 비슷하여 '트리'라는 이름이 붙여졌다. 트리의 재귀적 성질 트리는 그 안에 또 트리가 존재하게 된다. 트리안의 다른 트리를 서브 트리라고 한다. 이진트리(Binary Tree) 이름에서도 알 수 있듯이 자식 노드가 2개 이하인 트리를 이진트리라고 한다. 트리 순회 트래 내에 어떠한 자료가 담겨있는지를 알기 위해 사용한다. 전위 순회: Root - Left - R..
4주 차에서 다룰 내용은 다음과 같다. 1. Network 대칭키/공개키 HTTP / HTTPS 로드 밸런싱 Blocking, Non-blocking / Synchronous, Asynchronous Blocking / Non-Blocking I/O 2. Spring Bean Scope MVC Framework Spring Boot, SpringApplication Network 대칭키&공개키 대칭키란(Symmetric Key)? 암호화와 복호화에 같은 암호키를 사용하는 알고리즘 동일한 키를 주고받기 때문에, 매우 빠르다. 하지만 전달 과정에서 해킹 위험에 노출된다. 공개키(Public Key)/비대칭키(Asymmetric Key)란? 대칭키의 키 분배 문제를 해결하기 위해 고안됨.(대칭키일 때는 송수신..
스택과 큐는 선형 자료구조이다. (Linear) 스택 스택은 말 그대로 쌓다는 의미를 가지고 있다. 스택은 Last In First Out이다. 즉 마지막에 들어간 값이 제일 처음 나온다. 1,2,3,4를 순서대로 넣는다고 생각해보자. 위와 같이 1,2,3,4 순서대로 담기게 된다. 뺄 때는 위에서부터 한 개씩 빼게 된다. 스택을 구현할 때 우리가 생각할 부분은 스택 오버플로우와 스택 언더플로우이다. 오버플로우는 스택이 가득 찼는데, 우리가 원소를 더 넣으려 할 때 발생한다. 언더플로우는 스택이 비었을 때, 우리가 원소를 더 빼려고 할 때 발생한다. 스택 구현 구현하기에 앞서 우리가 어떤 기능을 구현할지 생각해보자. S를 스택이라 하자 S.create(x) : S의 크기를 x로 지정한다. S.push(x..
