분류 전체보기
-
[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)이다. 그래프 탐색이란? 그래프에서 하..
-
[SW 정글 18일차] 끄적인 글기타/SW 사관학교 정글 2021. 8. 20. 01:33
[오늘의 나는 어땠을까?] 오늘은 새로운 주차가 시작된 날이고 평소에 친해지지 못한 동료들과 조가 되어 만족스럽다. 오늘 오전에 본 모의고사 코테 결과는 1솔이다. 첫 번째 문제는 접근방식은 알았으나 재귀에서 출력값을 어떻게 내줄지를 생각하지 못해서 풀지 못했다... 아쉬웠지만 너무 나에게 채찍질을 하지 않고 긍정적으로 또 하나를 배웠구나, 그래도 분할 정복이라는 개념을 쓸 수 있는 수준은 됐구나 생각하려고 한다. 오후에는 매주 목요일마다 진행되는 소규모 면담에 참여했다. 질문내용 중 하나는 크래프톤에서 아웃게임 개발은 무엇인지 물어봤다. 이 질문에 대한 답변을 듣고 협력사 중 가고 싶은 1순위가 토스에서 크래프톤으로 바뀌었다. 이전에 나는 게임 회사에서 개발자로 일하는 것에 대한 조금 부정적인 선입견이..
-
SW 정글 2주차 회고기타/SW 사관학교 정글 2021. 8. 19. 23:25
[2주차 회고] 2021년 08월 19일 목요일, 2주차가 마무리 되는 날이고 2주차는 전체적으로 어땠는지 이 글을 쓰면서 돌아보려고 한다. 2주차에는 지난 날들보다 조금 더 밝은 모습으로 보낸 것같다. 정글에 들어오고 나서도 1주차 때까지는 여기서 내 단기 목표를 이루고 싶은 마음이 강해 불안감과 걱정이 매우 컸다. 그리고 내가 정글에 들어오기 전에 공부한 알고리즘, 코딩 테스트 준비가 잘못되었다는 생각이 들었고 열등감도 많이 드는 날들이였다. 하지만, 2주차가 시작되고나서는 조금 마음을 정리하고 지금 내게 주어진 일들에 대해서만 생각하며 지내자고 다짐했다. 그래서인지 한결 가벼운 마음으로 주어진 것들을 해결해나갈 수 있었던 것같다. 내 마음의 변화 뿐만 아니라 한 주동안 같은 조였던 동료들도 큰 힘이..
-
[파이썬 코테 6기] 4주차 세션 정리기타/파이썬 코테 스터디 6기 2021. 8. 19. 00:39
이 글은 프로그래머스에서 진행하는 코딩테스트와 실무 역량 모두 잡는 알고리즘 스터디(Python반) 6기를 참여하면서 일주일에 한 번(매주 수요일) 진행되는 세션에서 배운 내용을 정리하는 글이다. 오늘은 3주차 세션(2021년 08월 11일 진행)에서 배운 내용을 정리해보려고 한다. https://programmers.co.kr/learn/courses/12441 [스터디/6기] 코딩테스트와 실무 역량 모두 잡는 알고리즘 스터디(Python반) 🚀 아쉽지만 6기는 마감되었어요. 12월 시작 예정인 7기 오픈 알림을 신청하고, 최저가에 수강하세요! 최저가 알림 받기 코딩테스트와 실무 역량 모두 잡는 스터디: Python반 코딩테스트 운영진과 programmers.co.kr 1. itertools 활용하기 ..