Algorithm
[이코테] Chapter6-2 / 위에서 아래로
[이코테] Chapter6-2 / 위에서 아래로
2022.03.10하나의 수열에는 다양한 수가 존재한다. 이러한 수는 크기에 상관없이 나열되어 있다. 이 수를 큰 수 부터 작은 수의 순서로 정렬해야 한다. 수열을 내림차순으로 정렬하는 프로그램을 만드시오. [입력 조건] 첫째 줄에 수열에 속해 있는 수의 개수 N이 주어진다 (1
[이코테] Chapter6-1 / 기준에 따라 데이터를 정렬
[이코테] Chapter6-1 / 기준에 따라 데이터를 정렬
2022.03.08정렬 알고리즘 개요 정렬(Sorting)이란 데이터를 특정한 기준에 따라서 순서대로 나열하는 것을 말한다. 프로그램에서 데이터를 가공할 때 오름차순이나 내림차순 등 대부분 어떤 식으로든 정렬해서 사용하는 경우가 많기에 정렬 알고리즘은 프로그램을 작성할 때 가장 많이 사용되는 알고리즘 중 하나다. 정렬 알고리즘으로 데이터를 정렬하면 다음 장에서 배울 이진 탐색(Binary Search)이 가능해진다. 정렬 알고리즘은 이진 탐색의 전처리 과정이기도 하니 제대로 알고 넘어가자. 정렬 알고리즘은 이진 탐색의 전처리 과정이기도 하니 제대로 알고 넘어가자. 정렬 알고리즘은 굉장히 다양한데, 이 중에서 많이 사용하는 선택정렬, 삽입 정렬, 퀵 정렬, 계수 정렬만 이 책에서 언급하려 한다. 더불어 파이썬에서 제공하는 ..
[이코테] Chapter5-4 / 미로 탈출
[이코테] Chapter5-4 / 미로 탈출
2022.02.16민교는 N * M 크기의 직사각형 형태의 미로에 갇혀 있다. 미로에는 여러 마리의 괴물이 있어 이를 피해 탈출해야 한다. 민교의 위치는 (1, 1)이고 미로의 출구는 (N, M)의 위치에 존재하며 한번에 한 칸씩 이동할 수 있다. 이때 괴물이 있는 부분은 0으로, 괴물이 없는 부분은 1로 표시되어 있다. 미로는 반드시 탈출할 수 있는 형태로 제시된다. 이때 민교가 탈출하기 위해 움직여야 하는 최소 칸의 개수를 구하시오. 칸을 셀 때는 시작 칸과 마지막 칸을 모두 포함해서 계산한다. [입력 조건] 첫째 줄에 두 정수 N, M(4 = m: continue # 벽인 경우 무시 if graph[nx][ny] == 0: continue # 해당 노드를 처음 방문하는 경우에만 최단 거리 기록 if graph[nx]..
[이코테] Chapter5-3 / 음료수 얼려 먹기
[이코테] Chapter5-3 / 음료수 얼려 먹기
2022.02.15N * M 크기의 얼음 틀이 있다. 구멍이 뚫려 있는 부분은 0, 칸막이가 존재하는 부분은 1로 표시된다. 구멍이 뚫려 있는 부분끼리 상, 하, 좌, 우로 붙어 있는 경우 서로 연결되어 있는 것으로 간주한다. 이때 얼음 틀의 모양이 주어졌을 때 생성되는 총 아이스크림의 개수를 구하는 프로그램을 작성하시오. 다음의 4 * 5 얼음 틀 예시에서는 아이스크림이 총 3개 생성된다. [입력 조건] 첫 번쨰 줄에 얼음 틀의 세로 길이 N과 가로 길이 M이 주어진다. (1
파이썬 collections의 deque를 사용하는 이유(feat. time complexity)
파이썬 collections의 deque를 사용하는 이유(feat. time complexity)
2022.02.15deque의 사용성에 대해 고민하게 된 계기 탐색 알고리즘 BFS를 구현하면서, 아래와 같이 deque 를 사용하게 되었다. from collections import deque deque는 큐 자료구조를 구현해 준다. popleft()를 사용하여 큐에 가장 먼저 들어간 데이터를 가장 먼저 나오게 해준다. 그런데, 이때 한가지 궁굼증이 생겼다. 우선, 둘의 기능이 완전히 같다. [List의 pop(0)을 사용한 방법] arr = [1, 2, 3, 4] print(arr.pop(0)) [deque의 popleft()를 사용한 방법] from collections import deque arr = deque([1, 2, 3, 4]) print(arr.popleft()) 두 가지 방법으로 arr배열의 가장 첫..
[이코테] Chapter5-2 / 탐색 알고리즘 DFS/BFS
[이코테] Chapter5-2 / 탐색 알고리즘 DFS/BFS
2022.02.14스택과 큐, 재귀 함수는 DFS와 BFS에서 가장 중요한 개념이라 DFS/BFS를 배우기에 앞서 간단하게 설명했다. 이제부터 DFS/BFS 알고리즘을 살펴보겠다. DFS DFS는 Depth-First Search, 깊이 우선 탐색이라고도 부르며, 그래프에서 깊은 부분을 우선적으로 탐색하는 알고리즘이다. DFS를 설명하기 전에 먼저 그래프(Graph)의 기본 구조를 알아야 한다. 그래프는 노드(Node)랑 간선(Edge)으로 표현되며 이때 노드를 정점(Vertex)이라고도 말한다. 그래프 탐색이란 하나의 노드를 시작으로 다수의 노드를 방문하는 것을 말한다. 또한 두 노드가 간선으로 연결되어 있다면 '두 노드는 인접하다(Adjacent)'라고 표현한다. 여기에서 갑자기 노드와 간선이라는 생소한 단어가 나와서..