파이썬

    [파이썬으로 배우는 알고리즘] DFS(깊이 우선 탐색)

    DFS란? DFS(Depth First Search)는 그래프의 모든 노드를 탐색하는 방법 중 하나로, 깊이를 우선으로 탐색한 후 더 이상 탐색할 노드가 없다면 이전으로 돌아가 탐색을 이어나가는 탐색 알고리즘입니다. 이 과정에서 재귀 알고리즘을 사용하게 됩니다. 그래프 배우기 --> 2022.07.04 - [CS/자료구조] - [파이썬으로 배우는 자료구조] 그래프(Graph) [파이썬으로 배우는 자료구조] 그래프(Graph) 1. 그래프(Graph)란? 그래프는 노드(정점)와 간선으로 이루어진 집합으로 표현되는 자료구조입니다. 위 그래프에서 A, B, C는 노드이고, 이 노드를 연결한 선이 간선입니다. 두 노드가 연결되어 c4u-rdav.tistory.com 재귀 알고리즘 배우기 --> 2022.07.0..

    [백준(BOJ)] #17144- 미세먼지 안녕! (파이썬, PyPy3)

    문제 https://www.acmicpc.net/problem/17144 17144번: 미세먼지 안녕! 미세먼지를 제거하기 위해 구사과는 공기청정기를 설치하려고 한다. 공기청정기의 성능을 테스트하기 위해 구사과는 집을 크기가 R×C인 격자판으로 나타냈고, 1×1 크기의 칸으로 나눴다. 구사 www.acmicpc.net 문제 풀이 우선 이 문제는 구현 문제로 문제 이해를 이해하고, 문제를 어떻게 코드로 작성할 수 있는지를 확인하는 것으로 느껴졌습니다. 조건을 조금이라도 놓치고 문제를 풀게 되면, 원치 않은 결과를 얻을 수 있으므로 문제를 꼼꼼하게 읽어보는 것이 필수입니다! 미세먼지 확산 과정 미세먼지의 확산은 미세먼지가 있는 모든 칸에서 동시에 일어나기 때문에 2차원 리스트를 순차적으로 돌면서 무턱대고 확..

    [파이썬으로 배우는 알고리즘] 에라토스테네스의 체

    에라토스테네스의 체란? 에라토스테네스의 체는 고대 그리스 수학자 에라토스테네스가 발견한 소수를 찾는 방법입니다. 마치 체로 치듯이 소수를 걸러낸다고 하여 '에라토스테네스의 체'라고 불립니다. 소수를 걸러내기 위해 2부터 N까지의 순서로 소수를 찾아 그 숫자의 배수들을 모두 제거하여 제거되지 않은 N까지의 모든 소수를 찾아낼 수 있습니다. 에라토스테네스의 체 적용 1) 우선 다음과 같이 1~100까지의 숫자를 나열합니다. 2) 1인 소수가 아니므로 제거합니다. 3) 2를 제외한 2의 배수를 모두 제거합니다. 4) 3을 제외한 3의 배수를 모두 제거합니다. 5) 5를 제외한 5의 배수를 모두 제거합니다. (4의 배수는 2의 배수에서 이미 제거가 되어서 지울 필요가 없음) 6) 7을 제외한 7의 배수를 모두 ..

    [파이썬으로 배우는 자료구조] 트리(Tree)

    트리(Tree)란? 트리는 노드(Node)와 엣지(Edge)로 구성되어 있습니다. 위 그림에서 원이 노드, 선이 엣지이고, 이를 이용해서 사이클(순환 구조)을 이루지 않도록 구성한 구조를 마치 나무 같다 하여 트리라고 불립니다. 사이클이 없어서 아래로만 뻗어나가고 계층적으로 표현됩니다. 용어 노드(Node): 트리에서의 개별 데이터 루트(Root): 트리 시작점에 있는 노드(최상위) 깊이(Depth): 루트를 기준으로 특정 노드까지의 깊이를 의미. 루트는 깊이가 0 높이(Height): 리프 노드를 기준으로 특정 노드까지의 높이를 의미. 리프 노드는 높이가 0 계층(Level): 트리에서 같은 깊이에 있는 노드들을 같은 계층에 있다고 함. 부모 노드(Parent Node): 어떤 노드와 이전 계층에서 연..

    [프로그래머스(Programmers)/ Level3] N으로 표현 (파이썬, Python3)

    문제 https://school.programmers.co.kr/learn/courses/30/lessons/42895 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 문제 설명 아래와 같이 5와 사칙연산만으로 12를 표현할 수 있습니다. 12 = 5 + 5 + (5 / 5) + (5 / 5) 12 = 55 / 5 + 5 / 5 12 = (55 + 5) / 5 5를 사용한 횟수는 각각 6,5,4입니다. 그리고 이중 가장 작은 경우는 4입니다. 이처럼 숫자 N과 number가 주어질 때, N과 사칙연산만 사용해서 표현할 수 있는 방법 중 N 사용 횟수의 최솟..

    [파이썬으로 배우는 알고리즘] 재귀(Recursion) 알고리즘

    재귀(recursion)란? 같은 알고리즘을 사용하여 정의한 알고리즘을 재귀 알고리즘이라고 합니다. 어떠한 역할을 하는 함수에 자기 자신을 다시 호출하여 재귀 알고리즘을 적용할 수 있고, 이러한 함수를 재귀 함수라고 합니다. 재귀 함수 재귀 함수를 배우기 전에 재귀 함수는 스택을 활용하기 때문에 우선 스택 자료구조에 대해 어느 정도 알아야 합니다. 2022.06.29 - [CS/자료구조] - [파이썬으로 배우는 자료구조] 스택(Stack), 큐(Queue) [파이썬으로 배우는 자료구조] 스택(Stack), 큐(Queue) 1. 스택(Stack) 1.1. 스택이란? 스택은 후입선출의 자료구조로 LIFO(Last In First Out)라고 불리기도 합니다. 실생활에서 예를 들어볼까요? 우리가 보통 접시를 ..

    [파이썬으로 배우는 자료구조] 그래프(Graph)

    그래프(Graph)란? 그래프는 노드(정점)와 간선으로 이루어진 집합으로 표현되는 자료구조입니다. 위 그래프에서 A, B, C는 노드이고, 이 노드를 연결한 선이 간선입니다. 두 노드가 연결되어 있으면 두 노드는 인접하다고 표현됩니다. 따라서 위의 그래프에서는 A, B가 서로 인접하고, A, C가 서로 인접합니다. 또한 그래프는 위 그림과 같이 간선이 방향을 갖고 있지 않는 무방향 그래프, 간선이 방향을 갖고 있는 방향 그래프, 그리고 간선이 가중치를 갖고 있는 가중치 그래프로 나뉩니다. 위의 그래프는 간선이 방향을 갖고 있으므로 방향 그래프입니다. 무방향 그래프처럼 A, B가 모두 연결되어 있는 것이 아니라 A, B를 잇는 간선이 A에서 B 쪽으로 방향을 갖고 있어서 A가 B로는 인접하고, B에서 A로..

    [파이썬으로 배우는 자료구조] 해시(Hash)

    해시(Hash)란? 일반적으로 말하는 해시/해쉬(Hash)는 해시 테이블(Hash Table)로 Key와 Value를 매핑해서 데이터를 저장하는 자료구조입니다. 파이썬에서는 기본적으로 제공되는 딕셔너리 자료형이 해시 테이블과 같은 구조입니다! 쉽게 이해하기 위해서 관련 용어를 먼저 설명한 뒤에 특징을 살펴보도록 하겠습니다. 용어 키(Key) - 고유의 값으로 해시 함수의 Input. 다양한 길이의 값이 될 수 있다. 해시 테이블 (Hash Table) 또는 해시 맵(Hash Map) - Key와 Value를 매핑해서 데이터를 저장하는 자료구조 해시 함수(Hash Function) - 임의의 값을 고정된 길이의 데이터로 변환하는 함수. 다양한 길이의 키를 고정된 길이의 해시로 변환시키므로 저장소를 효율적으..

    [프로그래머스(Programmers)/ Level2] N개의 최소공배수 (파이썬, Python3)

    문제 https://school.programmers.co.kr/learn/courses/30/lessons/12953 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 문제 설명 두 수의 최소공배수(Least Common Multiple)란 입력된 두 수의 배수 중 공통이 되는 가장 작은 숫자를 의미합니다. 예를 들어 2와 7의 최소공배수는 14가 됩니다. 정의를 확장해서, n개의 수의 최소공배수는 n 개의 수들의 배수 중 공통이 되는 가장 작은 숫자가 됩니다. n개의 숫자를 담은 배열 arr이 입력되었을 때 이 수들의 최소공배수를 반환하는 함수, solu..

    [프로그래머스(Programmers)/ Level3] 블록 이동하기 (파이썬, Python3)

    문제 https://school.programmers.co.kr/learn/courses/30/lessons/60063 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 문제 설명 로봇개발자 "무지"는 한 달 앞으로 다가온 "카카오배 로봇경진대회"에 출품할 로봇을 준비하고 있습니다. 준비 중인 로봇은 2 x 1 크기의 로봇으로 "무지"는 "0"과 "1"로 이루어진 N x N 크기의 지도에서 2 x 1 크기인 로봇을 움직여 (N, N) 위치까지 이동 할 수 있도록 프로그래밍을 하려고 합니다. 로봇이 이동하는 지도는 가장 왼쪽, 상단의 좌표를 (1, 1)로 하며..