목표 Greedy, Dijkstra, DP 알고리즘과 같이 대표적인 알고리즘 중 하나인 DFS 그래프 탐색 알고리즘에 대해 이해하고 학습한다. DFS(Depth First Search)란 DFS(Depth First Search) DFS란 초기 노드에서 시작하여 해를 찾을때까지 자식 노드를 계속해서 타고 들어가며 탐색하는 완전탐색 알고리즘이다. 깊이(Depth)의 노드를 우선적으로 탐색하는 BFS와 반대되는 개념이라고 생각하면 이해하기 쉽다. DFS는 Stack 또는 재귀를 이용해 구현할 수 있는데 재귀를 이용해 구현하는것이 일반적이다. BFS에 대한 개념이 부족하다면 아래 글을 읽고 오면 좋다. https://zzzzseong.tistory.com/22 [Algorithm] BFS - 넓이 우선 탐색 ..
목표 최소비용 경로문제로 대표되는 Dijkstra 알고리즘에 대해 이해하고 학습한다. Dijkstra 알고리즘을 활용할 수 있는 알고리즘 문제를 풀어보고 정형화된 템플릿을 만들어보자. Dijkstra란 Dijkstra Dijkstra란 V개의 정점과 각각의 가중치(W)를 가진 E개의 간선을 가진 그래프에서 i번 정점에서 j번 정점까지로의 최소 가중치를 가지는, 최단 경로를 찾는 알고리즘이다. 아래는 Dijkstra 알고리즘을 활용할 수 있는 그래프의 예시이다. Dijkstra 알고리즘을 활용하기 위해서는 앞서 설명한 그래프, 정점 별 최소 가중치를 저장하기 위한 1차원 배열, 그래프 탐색을 위한 자료구조가 필요하다. 그래프 탐색을 위한 자료구조는 인접행렬과 우선순위 큐를 사용할 수 있고, 인접행렬을 개선..
2번째 팀 ( Team_Tetris ) 과제 "호텔 예약 시스템" 만들기 KPT 회고 KPT 란? 본 주차 회고록도 지난주차를 따라 Keep, Try, Problem 으로 분류하여 작성한다. KEEP 팀원 모두가 성장 하려는 의지를 보였다. 협업을 위한 다양하고 새로운 시도 `Code with me` `Git` 를 통해 협업률을 높일 수 있었다. 모르거나 부족한 부분이 있으면 적극적인 질문을 통해 팀원과 상호 성장하였다. Problem 자료구조 효율적인 활용에서 난항을 겪었다. 플로우차트나 클래스 다이어그램등 UML에 익숙하지 못하여 완벽하게 활용하지 못하였다. 완성된 과제를 문서화하지 못하였다. Try 기능의 구현보다 기획 단계에 더욱 투자하여 완성도를 높이는 것이 중요하다. 팀원의 한마디 정유진 안녕..
목표 예전부터 누군가 나에게 OOP가 무엇인지 묻는다면 자동차를 예로 들거나, "원하는 객체를 만들어서 레고처럼 조립하는 거야!" 라는 식으로 두루뭉실하게 설명하며 "OOP는 무엇이다!" 라고 명확하게 정의하지 못했다. 오늘 글을 쓰면서 OOP에 대해 확실히 이해해보려고 한다. OOP언어를 배우면 가장 먼저 마주하는 내용이 OOP의 특성이다. OOP의 대표적인 4가지 특성을 글로 정리해 항상 이것을 참고하며 프로그램을 설계, 구현하고자 한다. OOP란 OOP(Object-Oriented Programming) 객체 지향 프로그래밍 현실 세계에서 어떤 제품을 만들 때는 부품을 먼저 만들고, 이 부품들을 하나씩 조립해서 완성품을 만든다. 소프트웨어를 개발할 때에도 부품에 해당하는 객체를 먼저 만들고, 이 객..
Heap Heap은 최솟값, 최댓값을 빠르게 찾기 위해 고안된 자료구조이고, 무엇인가를 차곡차곡 쌓아 놓은 더미와 비슷하다 하여 Heap이라고 부른다. Heap은 '이진 트리'이되 '완전 이진 트리이다. '이진 트리'란 각 노드가 자식 노드를 최대 두개까지 가질 수 있는 트리를 말하며 '완전 이진 트리'란 마지막 레벨을 제외하고 모든 레벨이 채워져 있는 트리를 말한다. 탐색보다는 삽입과 삭제에 최적화된 자료구조이다. Array, Linked List에서 데이터 저장의 시간 복잡도는 O(n)이지만, Heap은 O(logn)이라는 좋은 성능을 보여준다. 그 이유는 Heap에 저장할 수 있는 데이터의 수는 트리의 높이가 하나 늘 때마다 두 배씩 증가하기 때문에, 데이터의 수가 두 배 늘 때마다 비교연산의 횟수..
Priority Queue Priority Queue는 들어간 순서에 상관없이 우선순위가 높은 데이터가 먼저 나오는 자료구조이다. Queue와 구조가 비슷할 것 같지만 둘은 많은 차이가 있다. Queue는 연산의 결과로 FIFO 즉, 먼저 들어간 데이터가 먼저 나오지만 Priority Queue는 그렇지 않다. 앞서 설명한 것처럼 들어간 순서에 상관없이 우선순위가 높은 데이터가 먼저 나온다. Priority Queue는 Array, List, Heap으로 구현할 수 있다. 하지만 Array와 List는 데이터 삽입과 삽입 위치를 찾는 과정에서 성능을 저하시킬 수 있기때문에 일반적으로 Heap을 이용해 구현한다. Priority Queue의 개념은 사실상 Heap에 대한 개념과 같기 때문에 Heap에 대한..
목표 Git을 이용해 협업을 하다보면 pull시에 내가 수정한 코드를 다른 팀원도 수정해 충돌이 나는 경우가 있다. 이럴 때 충돌 상황을 해결할 수 있는 Git Stash에 대해 이해해보자. Your local changes to the followings files would be overwritten by merge 코드를 개발하다보면 팀원의 commit을 내 working directory에 반영하기 위해 pull 해야한다. 하지만, 내가 수정한 파일을 팀원도 수정했다면 제목과 같은 에러가 발생할 것이다. 이때 git stash를 사용할 수 있다. git stash를 이용하면 지금까지 working directory에서 작성한 내 코드는 모두 백업되고 가장 최근 commit으로 프로젝트를 되돌린다...
Git Commit 내역 삭제하기현재 branch의 commit 내역 확인. git log를 이용해 commit 내역을 살펴보면 현재 branch의 HEAD가 commit 3490... 에 있음을 알 수 있다.git log 현재 HEAD의 commit을 삭제하고 싶다면 1 )과 같이 입력한다. HEAD^는 현재 HEAD 1개를 가리키는 것이다. 현재 HEAD를 포함해 n개의 commit을 삭제하고 싶다면 2)와 같이 입력한다.1) git reset HEAD^2) git reset HEAD~n 다시 git log를 확인해보면 commit이 삭제된 것을 알 수 있다. 이제 변경된 Git을 Github에 반영해보자. 아래와 같이 입력해 Github저장소에도 변경내용을 반영한다.git pu..
목표 AWS EC2 Instance를 생성하고 사용하는 방법 알아보기 EC2 SSH를 이용해 Instance에 Docker 설치하기 AWS EC2란 EC2(Elastic Compute Colude) EC2는 AWS에서 제공하는 클라우드 컴퓨팅 솔루션으로 AWS region에 존재하는 독립된 컴퓨터를 임대해주는 서비스이다. EC2를 사용함으로써 서버용 컴퓨터를 따로 구비하지 않아도 되고, 초기 구입 비용이나 세팅 없이 사용한 자원만큼만 비용을 지불하면 된다는 장점이 있다. EC2 Instance EC2 서비스를 통해 사용할 수 있는 실제 컴퓨터 한 대를 의미한다. 여러개의 Instnace를 생성해 사용할 수 있다. AWS EC2 Instance 생성하기 AWS EC2 서비스에 진입해 인스턴스 시작하기 버튼..
