기타
-
[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 활용하기 ..
-
[SW 정글 17일차] 오늘 배운 점들기타/SW 사관학교 정글 2021. 8. 18. 23:08
오늘은 지난 날들처럼 어떠한 주제를 잡고 정리하는 것이 아닌 알고리즘 문제를 풀면서 마주했던 오류를 해결하거나 코드를 바꿔보면서 알았던 내용을 정리하려고 한다. 1. TypeError: unhashable type: 'list' 위 에러는 list를 set으로 바꿀 때 나온 것이다. 정확히 말하면 list 안의 요소는 또 다른 list로 이루어져 있는 상태이다. 나는 list에 들어있는 원소들의 중복 제거를 하고 싶었고 for문을 돌리면서 조건문을 써도 되지만 set이라는 배열의 특징을 이용했다. set의 특징은 중복 원소를 허용하지 않는다는 것과 순서가 없다는 것(인덱스 접근 불가)이다. 그래서 중복 값이 들어있는 list를 set으로 형변환을 해준다면 자동으로 중복 값을 제거할 수 있다. 그래서 se..
-
[SW 정글 16일차] Locality는 무엇일까기타/SW 사관학교 정글 2021. 8. 17. 23:19
오늘은 컴퓨터 시스템 3판을 읽으면서 Locality라는 말을 접하게 되었고 설명이 없어 구글링을 하며 찾아본 내용들을 정리하려고 한다. 1 ~ 4주차는 알고리즘과 자료구조 공부기간이지만 1주일마다 컴퓨터 시스템 3판 읽을 분량을 정해준다. 엄청 어렵거나 세부적으로 파고드는 부분들이 아니여서 내가 이전에 배운 OS 지식을 리마인드하고 locality같은 개념이 확실히 잡히지 않은 용어를 정리해보는 시간으로 생각하며 책을 읽었다. 1. Locality란? 프로그램은 항상 메모리의 특정 주소를 찾아가서 데이터를 읽어오고 특정 주소로 찾아가서 데이터를 쓰는 행위들이 기본이다. 여기서 locality라는 개념이 적용되는데 locality는 프로그램이 data나 instructions를 사용하려고 할 때, 이전에..
-
[SW 정글 15일차] 세그먼트 트리기타/SW 사관학교 정글 2021. 8. 16. 23:14
오늘은 분할 정복 문제를 풀면서 다른 사람의 코드를 찾아보는 일이 많았다. 다른 사람들의 문제 풀이에 대한 설명에서는 세그멘트 트리라는 용어가 종종 보였고 이것에 대한 개념 자체가 없어서 오늘 공부한 것을 바탕으로 정리해보려고 한다. 1. 세그먼트 트리 (Segment Tree) 세그먼트 트리는 데이터의 합을 가장 빠르고 간단하게 구할 수 있는 자료구조로 여러 개의 데이터가 연속적으로 존재할 때 특정한 범위의 데이터의 합을 구하고자 할 때 사용한다. 세그먼트 트리를 쓰지않고 특정한 범위의 데이터의 합을 구할 때는 선형적인 방법을 사용할 것이다. 선형적인 방법이라 함은 어떠한 배열이 있을 때 인덱스 i ~ j까지 요소의 합을 구하려면 해당 범위의 요소를 하나씩 더해나가는 것이다. 이렇게 되면 시간복잡도가 ..