기타
-
[SW 정글 14일차] 분할 정복기타/SW 사관학교 정글 2021. 8. 15. 23:00
1. 분할 정복 분할 정복은 주어진 문제를 원래 문제와 유사하지만 크기가 작은 몇 개의 부분 문제로 분할하고 부분 문제를 재귀적으로 풀고 찾은 해를 결합하여 원래 문제의 해를 만들어 내는 방법이다. 분할 정복으로 해결할 수 있는 예시는 하노이탑이 대표적일 것이다. 세 개의 기둥이 있고 n개의 원판이 있으면 규칙을 지키며 첫 번째 기둥에서 세 번째 기둥으로 옮겨야한다. 우리는 여기서 1 ~ n-1개의 원판을 두번째에 옮기고 n번째 원판을 세 번째 기둥으로 옮기고 마지막으로 1 ~ n-1개의 원판을 세번째 기둥으로 옮기면 문제가 해결된다. 즉, 전체 문제를 풀어해치는 것이 아닌 분할하여 재귀적으로 답을 얻어내는 것이다. 분할 정복은 세 가지 단계로 구성된다. ① 분할: 현재의 문제를 같은 문제를 다루는 다수..
-
[SW 정글 13일차] 트리 구조와 이진 트리기타/SW 사관학교 정글 2021. 8. 14. 23:47
1. 트리 구조 트리 구조는 데이터 사이의 계층 관계를 표현하는 자료 구조로 노드(node)와 가지(edge)로 구성되어있다. 간단한 트리 구조를 아래의 그림으로 표현해 보았다. 그림을 보며 각각의 단어들이 어떠한 것을 뜻하는지 알아보자. - 루트(root): 트리의 가장 위쪽에 있는 노드를 뜻하며 트리 하나에 루트는 오직 1개만 존재한다. - 리프(leaf): 리프는 자기 자신으로부터 더 이상 가지가 뻗어나가지 않는 노드를 의미한다. 리프는 다른 말로 단말 노드, 외부 노드라고도 한다. - 비단말 노드(non-terminal node): 비단말 노드는 트리 내에서 리프를 제외한 노드를 의미한다. 다른 말로 내부 노드라고도 한다. - 자식 노드(child node): 노드와 노드가 가지로 연결되어있을 때..
-
SW 정글 1주차 (하루 늦은)회고기타/SW 사관학교 정글 2021. 8. 14. 02:36
지난 4일차, 0주차를 마치고 주어진 특별한 과제를 할 겸 0주차 회고를 같이 작성했다. 이번에도 12일차에 1주차가 마무리되고 2주차가 시작되면서 1주차에는 어땠는지에 대해 작성하려고 했다. 12일차에 같이 쓰려고 했으나 내가 배운 내용들과 함께 글을 써보니까 내용이 너무 많아지고 글의 주제가 여러 개다 보니까 읽기 싫어지는 글처럼 보였다. 그래서 이렇게 각 주차별 회고는 따로 작성하려고 한다. [1주차 회고] 2021년 08월 12일 목요일, 오늘부로 SW 사관학교 정글에 들어온지 11일차, 1주차가 마무리 되고 2주차가 시작하는 날이다. 지난 주 목요일(08월 05일)에 나는 소규모 면담에 참여하여 운영진님들과 코치님에게 질문을 드렸다. Q. 전체적인 프로세스가 CS에 맞춰져있어서 기술적인 역량을 ..
-
[SW 정글 12일차] 스택과 큐 알아보기기타/SW 사관학교 정글 2021. 8. 13. 22:30
오늘은 스택과 큐에 대해 정리해보려고 한다. 스택과 큐가 대충 어떠한 성격의 자료구조인지는 알고 있었지만 세세하게 알아본 적은 없었다. 기본적인 자료구조인 만큼 내가 공부한 내용을 정리하며 개념을 제대로 잡고자 한다. 1. 스택 (stack) 스택은 데이터를 임시로 저장하는 자료구조로 후입선출(LIFO)방식이다. 후입선출(LIFO)은 먼저 들어온 데이터가 나중에 나간다는 의미이다. 이렇게 말로만 설명하면 감이 잘 안올텐데 프링글스를 생각해보자. 단, 깨진 짜잘짜잘한 조각들은 생각하지 않고 프링글스를 만들 때는 과자칩을 하나하나 통에 넣을 것이다. 이렇게 하나, 둘 쌓인 과자칩은 우리가 가게에서 사게 될 것이고 우리는 프링글스를 위에서부터 하나씩 꺼내서 먹을 것이다. 위에서부터 꺼내 먹게 되면 들어온 순서..
-
[SW 정글 11일차] 검색 알고리즘기타/SW 사관학교 정글 2021. 8. 12. 23:22
오늘은 2주차 시작으로 검색 알고리즘에 대해 공부를 시작했다. 검색 알고리즘에 대해 거의 모르다시피 살고 코딩테스트에서는 in 을 써서 값이 배열 안에 있는지 없는지 확인만 하는 수준이였다. 오늘부로 검색 알고리즘 개념을 잡고자 한다. 1. 선형 검색 (linear search) 선형 검색은 배열에서 원소를 검색하는 방법 중 가장 기본적인 알고리즘이다. 원하는 값을 찾기 위해 배열의 맨 앞부터 순서대로 확인하며 검색하는 것이다. 어떠한 방식으로 검색이 이루어지는지 아래의 그림을 보며 이해해보자. 배열의 맨 앞부터 순서대로 3인지를 확인하고 아니면 다음 원소로 넘어가면서 3인 원소를 찾았을 때 검색을 멈추게 된다. 선형 검색의 종료 조건은 2가지가 존재한다. - 찾고자하는 값을 찾지 못하고 배열의 맨 끝을..
-
[파이썬 코테 6기] 3주차 세션 정리기타/파이썬 코테 스터디 6기 2021. 8. 11. 22:57
이 글은 프로그래머스에서 진행하는 코딩테스트와 실무 역량 모두 잡는 알고리즘 스터디(Python반) 6기를 참여하면서 일주일에 한 번(매주 수요일) 진행되는 세션에서 배운 내용을 정리하는 글이다. 오늘은 3주차 세션(2021년 08월 11일 진행)에서 배운 내용을 정리해보려고 한다. https://programmers.co.kr/learn/courses/12441 [스터디/6기] 코딩테스트와 실무 역량 모두 잡는 알고리즘 스터디(Python반) 🚀 아쉽지만 6기는 마감되었어요. 12월 시작 예정인 7기 오픈 알림을 신청하고, 최저가에 수강하세요! 최저가 알림 받기 코딩테스트와 실무 역량 모두 잡는 스터디: Python반 코딩테스트 운영진과 programmers.co.kr 1. *의 또다른 기능 우리는 보..
-
[SW 정글 10일차] 전역 변수와 지역 변수 참조기타/SW 사관학교 정글 2021. 8. 11. 22:50
오늘은 백준에서 문제를 풀면서 처음 경험하는 현상을 발견하여 그 현상과 원인을 정리해보려고 한다. 현상에 대한 원인을 알려주신 분은 코발트에서 개발자로 일하고 계신 이선협님이다. 내가 겪은 현상은? 먼저, 내가 푼 문제는 백준 알로리즘 저지에 있는 외판원 순환 2라는 문제이다. https://www.acmicpc.net/problem/10971 10971번: 외판원 순회 2 첫째 줄에 도시의 수 N이 주어진다. (2 ≤ N ≤ 10) 다음 N개의 줄에는 비용 행렬이 주어진다. 각 행렬의 성분은 1,000,000 이하의 양의 정수이며, 갈 수 없는 경우는 0이 주어진다. W[i][j]는 도시 i에서 j www.acmicpc.net 완전탐색으로 모든 경우의 수를 구해 접근하려 했고 처음에는 시간초과가 났다...
-
[SW 정글 9일차] 순열과 조합 사용하기기타/SW 사관학교 정글 2021. 8. 10. 22:56
오늘은 알고리즘 문제를 풀면서 사용한 순열과 조합에 대해서 정리해보려고 한다. 문제를 보고 '아, 배열 안에 있는 수를 순서를 바꾼 모든 경우를 얻고 싶은데 어떻게 하지..'라는 생각을 가진 적이 많고 그 때마다 항상 인터넷 검색을 하고 순열을 쓰면 되는구나 혹은 조합을 쓰면 되는구나 했다. 오늘은 이렇게 글로 정리하면서 다음부터는 바로바로 떠올릴 수 있도록 해보고자 한다. 1. 순열 (permutation) 순열을 사용하는 경우는 어떠한 경우일까? 먼저 순열은 서로 다른 n개의 원소에서 r개를 중복없이 골라 순서에 상관있게 나열하는 것을 말한다. 여기서 더 깊게 얘기하면 수학적인 개념을 얘기해야하므로 간단히 순열이 무엇인지만 얘기하고 넘어가겠다. 이러한 순열은 우리가 어떠한 배열을 가지고 있는데 그 배..