파이썬

[파이썬으로 배우는 알고리즘] 버블 정렬(Bubble Sort)

버블 정렬(Bubble Sort)이란? 서로 인접한 두 원소를 비교하고, 순서가 맞지 않으면 교체하는 방식으로 정렬하는 정렬 알고리즘입니다. 원소가 마치 거품처럼 올라오는 듯해 버블 정렬이라는 이름이 붙었다고 합니다. 버블 정렬 과정 위와 같이 정렬되어 있지 않은 배열을 버블 정렬 알고리즘을 사용하여 정렬해보겠습니다. 먼저 배열의 맨 앞부터 인접한 원소를 비교합니다. 11은 10보다 크므로 대소 관계를 만족합니다. 따라서 교체하지 않습니다. 그다음으로 인접한 11과 2를 비교합니다. 2는 11보다 작으므로 대소 관계를 만족하지 않습니다. 따라서 위와 같이 두 원소의 자리를 교체합니다. 그다음으로 인접한 11과 4를 비교합니다. 4는 11보다 작으므로 대소 관계를 만족하지 않습니다. 따라서 위와 같이 두 ..

[백준(BOJ)] #1525- 퍼즐 (파이썬, PyPy3)

문제 https://www.acmicpc.net/problem/1525 1525번: 퍼즐 세 줄에 걸쳐서 표에 채워져 있는 아홉 개의 수가 주어진다. 한 줄에 세 개의 수가 주어지며, 빈 칸은 0으로 나타낸다. www.acmicpc.net 문제 풀이 BFS 알고리즘 적용하여 해결 1) 입력받은 board를 문자열로 변환 2) 완성된 퍼즐 모양이 나올 때까지 문자열의 인덱스를 조정해가면서 탐색. 퍼즐 모양이 나오면 움직인 횟수를 출력하고 퍼즐 모양을 만들 수 없으면 -1 출력 위와 같은 모양의 board에서 빈칸(0)을 움직이면서 퍼즐을 완성시키는 것이 목적입니다. BFS 알고리즘을 적용하여 퍼즐을 완성시키기 위해 2차원 모양의 board를 문자열로 변환시킵니다. 순서에 맞게 문자열로 변환시키면 문자열은 ..

[백준(BOJ)] #1103- 게임 (파이썬, PyPy3)

문제 https://www.acmicpc.net/problem/1103 1103번: 게임 줄에 보드의 세로 크기 N과 가로 크기 M이 주어진다. 이 값은 모두 50보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에 보드의 상태가 주어진다. 쓰여 있는 숫자는 1부터 9까지의 자연수 또는 www.acmicpc.net 문제 풀이 처음에 DFS 알고리즘을 적용하여 풀었는데 시간 초과가 발생했습니다. 다른 풀이를 참고하여 DP를 함께 적용하여 풀 수 있다는 것을 알았습니다. 문제 풀이는 다음 이 블로그의 풀이를 참고하여 풀었습니다. 2022.07.12 - [PS/알고리즘 이론] - [파이썬으로 배우는 알고리즘] DFS(깊이 우선 탐색) [파이썬으로 배우는 알고리즘] DFS(깊이 우선 탐색) DFS란? DFS(..

[백준(BOJ)] #1194- 달이 차오른다, 가자. (파이썬, PyPy3)

문제 https://www.acmicpc.net/problem/1194 1194번: 달이 차오른다, 가자. 첫째 줄에 미로의 세로 크기 N과 가로 크기 M이 주어진다. (1 ≤ N, M ≤ 50) 둘째 줄부터 N개의 줄에 미로의 모양이 주어진다. 같은 타입의 열쇠가 여러 개 있을 수 있고, 문도 마찬가지이다. 그리고, www.acmicpc.net 문제 풀이 BFS와 비트마스크 활용 2022.07.14 - [PS/알고리즘 이론] - [파이썬으로 배우는 알고리즘] BFS(너비 우선 탐색) [파이썬으로 배우는 알고리즘] BFS(너비 우선 탐색) BFS란? BFS(Breadth First Search)는 DFS와 마찬가지로 그래프의 모든 노드를 탐색하는 방법 중 하나로, 너비를 우선으로 탐색한 후 인접한 노드부..

[백준(BOJ)] #1655- 가운데를 말해요 (파이썬, PyPy3)

문제 https://www.acmicpc.net/problem/1655 1655번: 가운데를 말해요 첫째 줄에는 백준이가 외치는 정수의 개수 N이 주어진다. N은 1보다 크거나 같고, 100,000보다 작거나 같은 자연수이다. 그 다음 N줄에 걸쳐서 백준이가 외치는 정수가 차례대로 주어진다. 정수는 -1 www.acmicpc.net 문제 풀이 우선순위 큐 사용 2022.07.19 - [CS/자료구조] - [파이썬으로 배우는 자료구조] 우선순위 큐(Priority Queue), 힙(Heap) [파이썬으로 배우는 자료구조] 우선순위 큐(Priority Queue), 힙(Heap) 우선순위 큐(Priority Queue)란? 일반적인 큐(Queue) 자료구조는 FIFO 구조라는 것을 배웠습니다. 큐 배우기 -..

[백준(BOJ)] #1300- K번째 수 (파이썬, PyPy3)

문제 https://www.acmicpc.net/problem/1300 1300번: K번째 수 세준이는 크기가 N×N인 배열 A를 만들었다. 배열에 들어있는 수 A[i][j] = i×j 이다. 이 수를 일차원 배열 B에 넣으면 B의 크기는 N×N이 된다. B를 오름차순 정렬했을 때, B[k]를 구해보자. 배열 A와 B www.acmicpc.net 문제 풀이 배열의 크기 N이 10^5보다 작거나 같은 자연수이기 때문에 일차원 배열로 변환하고 정렬해서 구하기는 불가능합니다. 이분 탐색을 사용하여 이 문제를 해결할 수 있습니다. 2022.08.11 - [PS/알고리즘 이론] - [파이썬으로 배우는 알고리즘] 이분 탐색(Binary Search) [파이썬으로 배우는 알고리즘] 이분 탐색(Binary Search..

[백준(BOJ)] #2436- 공약수 (파이썬, PyPy3)

문제 https://www.acmicpc.net/problem/2436 2436번: 공약수 첫째 줄에 두 개의 자연수가 빈칸을 사이에 두고 주어진다. 첫 번째 수는 어떤 두 개의 자연수의 최대공약수이고, 두 번째 수는 그 자연수들의 최소공배수이다. 입력되는 두 자연수는 2 이상 100,0 www.acmicpc.net 문제 풀이 최대공약수와 최소공배수의 성질을 이용해 풀이 2022.07.01 - [PS/프로그래머스] - [프로그래머스(Programmers)/ Level2] N개의 최소공배수 (파이썬, Python3) [프로그래머스(Programmers)/ Level2] N개의 최소공배수 (파이썬, Python3) 문제 https://school.programmers.co.kr/learn/courses/30..

[백준(BOJ)] #1725- 히스토그램 (파이썬, PyPy3)

문제 https://www.acmicpc.net/problem/1725 1725번: 히스토그램 첫 행에는 N (1 ≤ N ≤ 100,000) 이 주어진다. N은 히스토그램의 가로 칸의 수이다. 다음 N 행에 걸쳐 각 칸의 높이가 왼쪽에서부터 차례대로 주어진다. 각 칸의 높이는 1,000,000,000보다 작거나 같은 www.acmicpc.net 문제 풀이 스택 자료구조 사용, 백준 블로그 참고 2022.06.29 - [CS/자료구조] - [파이썬으로 배우는 자료구조] 스택(Stack), 큐(Queue) [파이썬으로 배우는 자료구조] 스택(Stack), 큐(Queue) 스택(Stack) 스택이란? 스택은 후입선출의 자료구조로 LIFO(Last In First Out)라고 불리기도 합니다. 실생활에서 예를 ..

[백준(BOJ)] #1914- 하노이 탑 (파이썬, PyPy3)

문제 https://www.acmicpc.net/problem/1914 1914번: 하노이 탑 세 개의 장대가 있고 첫 번째 장대에는 반경이 서로 다른 n개의 원판이 쌓여 있다. 각 원판은 반경이 큰 순서대로 쌓여있다. 이제 수도승들이 다음 규칙에 따라 첫 번째 장대에서 세 번째 장대로 www.acmicpc.net 문제 풀이 재귀 알고리즘 적용 2022.07.05 - [PS/알고리즘 이론] - [파이썬으로 배우는 알고리즘] 재귀(Recursion) 알고리즘 [파이썬으로 배우는 알고리즘] 재귀(Recursion) 알고리즘 재귀(recursion)란? 같은 알고리즘을 사용하여 정의한 알고리즘을 재귀 알고리즘이라고 합니다. 어떠한 역할을 하는 함수에 자기 자신을 다시 호출하여 재귀 알고리즘을 적용할 수 있고,..

[백준(BOJ)] #15997- 승부 예측 (파이썬, PyPy3)

문제 https://www.acmicpc.net/problem/15997 15997번: 승부 예측 첫 번째 줄에 조별리그를 진행할 국가명 네 개가 공백으로 구분되어 주어진다. 주어지는 모든 국가명은 알파벳 대문자로만 구성된 길이가 1 이상 10 이하인 문자열이다. 두 번째 줄부터 일곱 번 www.acmicpc.net 문제 풀이 DFS 알고리즘으로 완전 탐색을 하여 해결하였습니다. 2022.07.12 - [PS/알고리즘 이론] - [파이썬으로 배우는 알고리즘] DFS(깊이 우선 탐색) [파이썬으로 배우는 알고리즘] DFS(깊이 우선 탐색) DFS란? DFS(Depth First Search)는 그래프의 모든 노드를 탐색하는 방법 중 하나로, 깊이를 우선으로 탐색한 후 더 이상 탐색할 노드가 없다면 이전으로..