티끌모아 태산

순열 (permutation) 서로 다른 n 개 중 r 개를 골라 순서를 정해 나열하는 가짓수이며 순열이라는 의미의 영어 ‘Permutation’의 첫 글자 P를 따서 nPr로 표시합니다. 따라서 순열은 순서를 고려하기 때문에 [A, B, C]의 리스트에서 2개의 원소를 골라 순서를 정해 나열하면 [(A, B), (A, C), (B, A), (B, C), (C, A), (C, B)] 가 나오게 됩니다. 즉 순열에서는 (A, B)와 (B, A)는 다른 것입니다. from itertools import permutations arr = ['A', 'B', 'C'] nPr = permutations(arr, 2) print(list(nPr)) [('A', 'B'), ('A', 'C'), ('B', 'A'), ..

이번 시간에는 '알고리즘 분석' 주제로 공부해 보겠습니다. 알고리즘을 왜 배워야 할까요? 코딩은 다했고, 배포도 끝났으며 소스코드에 버그도 없는데 이유 모르게 어플이 느릴때. 이때 코드 최적화를 통해 속도를 높이고 싶을 때 데이터 구조와 알고리즘을 배워야합니다. Aims How do we define a “good” data structure? A “good” data structure is fast (efficient) at performing various operations as data grows: Finding stuff Adding stuff Deleting stuff Operations are algorithms! How do we measure the speed (running time) ..

그리디 알고리즘은 '탐욕법'이라고도 하는데, 탐욕적으로 문제를 푸는 알고리즘이다. 핵심은 '현재 상황에서 지금 당장 좋은 것만 선택하는 방법' 이다. 그리디 알고리즘을 이용하면 ❗️매 순간 가장 좋아보이는 것을 선택하며 나중에 미칠 영향에 대해서는 고려하지 않는다. 보통 코딩테스트 유형을 보면 정형화 되어있는 문제들이 있는데, 그리디 알고리즘은 그렇지 않다. 사전에 외우지 않고 알고리즘 사고 능력을 통해 풀어야 하는 문제들이 출제된다. 즉, 문제의 유형이 매우 다양하기 떄문에 암기한다고 해서 항상 잘 풀 수 있는 알고리즘 유형이 아니다. 결국에는 많은 문제를 풀어보면서 훈련해야한다. 만약 회사 코딩테스트에서 문제로 그리디 알고리즘 문제를 출제했다면 문제를 풀기 위한 최소한의 아이디어를 떠올릴 수 있는 능..

이번 시간에는 자료구조의 기본인 '배열'을 이해하고 배우는 시간을 갖도록 하겠습니다. 하지만 기본적으로 파이썬에는 배열과 100% 상응하는 자료형은 없습니다. 변수를 선언할 때 자료형을 따로 명시하지 않고, 고정된 크기만큼 정보를 담을 수 있는 자료형도 없기 때문입니다. 대신 어떤 자료형이든 제한 없이 여러 개 담을 수 있는 리스트(List)가 있습니다. Python에서 사용하는 리스트 자료구조는 Array List로 구현되어 있습니다. Array list 배열을 기반으로 구성된 list 자료구조 입니다. 이 Array list는 static array로 구현할 수 있고, dynamic array로 구현할 수도 있습니다. Static Array 고정된 데이터 공간 순차적으로 데이터 저장 ❗️데이터의 갯수..

저번시간에는 그래프의 정의와 종류 그리고 구현하는 방식에 대해서 알아보았습니다. 그렇다면 이번 시간에는 그래프를 순회하는 방식에 대해서 알아보도록 하겠습니다. *자료구조란 데이터를 표현하고 관리하고 처리하기 위한 구조이다. *탐색이란 많은 양의 데이터 중에서 원하는 데이터를 찾는 과정. 그래프 순회 그래프를 순회 한다는 것은 모든 노드를 지나야 한다는 것입니다. 대표적인 방식이 DFS와 BFS 입니다. BFS(Breadth Frist Search) BFS는 너비 우선 탐색이라는 의미이고 쉽게 말하면 가까운 노드부터 우선적으로 탐색하는 알고리즘 입니다. 그래프 순회를 할 때, 시작점이 주어질텐데, 이를 루트 노드라 생각하여, level 별로 탐색을 하는 것이 BFS입니다. 이때, BFS를 구현하는 방식은 ..

그래프란 그래프(G)는 노드(정점, Vertex)들의 집합 V와 이들을 연결하는 간선(Edge)들의 집합 E로 구성된 자료구조입니다. 쉽게말해, 그래프는 노드와 간선으로 이루어진 자료구조이다. 그래프의 종류 무향 그래프(undirected graph): 방향이 정해져있지 않은 양방향 그래프를 의미합니다. ❗️코딩테스트에서 주로 많이 다룬다. 방향 그래프(directed graph): 방향이 정해져 있는 그래프로 단뱡향 그래프를 의미합니다. 즉, 아래 사진과 같이 방향이 정해진 그래프 입니다. 그래프를 살펴보면 들어오는 간선과 나가는 간선이 있는데, 들어오는 간선을 indgree라 하며, 나가는 간선을 outdgree라 합니다. 예를들어, 아래 노드 B는 노드 A와 C로 부터 들어오고 E로 나가기 때문에 ..

기본적인 자료구조를 공부하기 전에 대부분의 기업 채용 과정에서 보는 코딩테스트가 무엇인지 알아보자. 코딩테스트란? 말 그대로 "주어진 문제를 프로그래밍 언어(코드)로 작성하여 해결하는 것"을 말한다. 그러면 기업들은 왜 코딩테스트를 볼까? 문제 해결 과정을 보는 것 생각하는 실력을 다지는 것 똑같은 결과를 빠르고 효율적으로 푸는 것. 모든 것의 기초는, 생각하는 실력을 다지는 것으로 "어떻게" 문제를 효율적으로 해결할 수 있는지를 생각하는 것이 중요하다. 그래야 예를들어, 이 상황에서는 왜 그 코드를 사용해야하는지, 아니면 이렇게 적용하는 것이 왜 좋은지를 설명할 수 있기 때문이다. 따라서 코딩테스트를 준비하기 위해 문제를 풀 때 단순히 이 문제는 이 방법으로 풀어야 한다는 형태로 암기하지 말고 문제를 ..