PS

[백준(BOJ)] #17298- 오큰수 (파이썬, PyPy3)

문제 https://www.acmicpc.net/problem/17298 17298번: 오큰수 첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄에 수열 A의 원소 A1, A2, ..., AN (1 ≤ Ai ≤ 1,000,000)이 주어진다. www.acmicpc.net 문제 풀이 저는 스택 자료구조를 사용해서 이 문제를 풀었습니다. 2022.06.29 - [CS/자료구조] - [파이썬으로 배우는 자료구조] 스택(Stack), 큐(Queue) [파이썬으로 배우는 자료구조] 스택(Stack), 큐(Queue) 스택(Stack) 스택이란? 스택은 후입선출의 자료구조로 LIFO(Last In First Out)라고 불리기도 합니다. 실생활에서 예를 들어볼까요? 우리가 보통 ..

[파이썬으로 배우는 알고리즘] 선택 정렬(Selection Sort)

선택 정렬(Selection Sort)이란? 선택 정렬은 해당 순서에 원소를 넣을 위치는 이미 정해져 있고, 그 위치에 어떤 원소를 넣을지 "선택"하는 정렬 알고리즘입니다. 선택 정렬 과정 위와 같이 정렬되어 있지 않은 배열을 선택 정렬 알고리즘을 사용하여 정렬해보겠습니다. 제일 왼쪽 인덱스 0 즉, 제일 작은 원소가 들어갈 자리를 정하고, 해당 인덱스에 어떤 원소를 넣을지 다음 원소부터 순서대로 탐색합니다. 11, 2, 4, 3 원소 중에는 2가 제일 작으므로 2의 인덱스 2를 기억합니다. 인덱스 0에 저장된 원소 10과 인덱스 2에 저장된 2를 비교하여 2가 더 작은 것을 알 수 있습니다. 2가 더 작기 때문에 두 원소를 서로 바꿔줍니다. 1회전이 끝나고 인덱스 0의 원소를 구했습니다. 그다음으로 왼..

[백준(BOJ)] #1520- 내리막 길 (파이썬, Python3)

문제 https://www.acmicpc.net/problem/1520 1520번: 내리막 길 여행을 떠난 세준이는 지도를 하나 구하였다. 이 지도는 아래 그림과 같이 직사각형 모양이며 여러 칸으로 나뉘어져 있다. 한 칸은 한 지점을 나타내는데 각 칸에는 그 지점의 높이가 쓰여 있으 www.acmicpc.net 문제 풀이 DFS + 동적 계획법 2022.07.22 - [PS/알고리즘 이론] - [파이썬으로 배우는 알고리즘] 동적 계획법(Dynamic Programming) [파이썬으로 배우는 알고리즘] 동적 계획법(Dynamic Programming) 동적 계획법(Dynamic Programming)이란? 동적 계획법(Dynamic Programming), 다이나믹 프로그래밍, DP라고 불리는 이 알고리..

[백준(BOJ)] #4485- 녹색 옷 입은 애가 젤다지? (파이썬, PyPy3)

문제 https://www.acmicpc.net/problem/4485 4485번: 녹색 옷 입은 애가 젤다지? 젤다의 전설 게임에서 화폐의 단위는 루피(rupee)다. 그런데 간혹 '도둑루피'라 불리는 검정색 루피도 존재하는데, 이걸 획득하면 오히려 소지한 루피가 감소하게 된다! 젤다의 전설 시리즈의 주 www.acmicpc.net 문제 풀이 다익스트라 알고리즘의 개념, BFS 알고리즘 2022.07.31 - [PS/알고리즘 이론] - [파이썬으로 배우는 알고리즘] 다익스트라(Dijkstra) 알고리즘 [파이썬으로 배우는 알고리즘] 다익스트라(Dijkstra) 알고리즘 다익스트라(Dijkstra) 알고리즘이란? 다익스트라(Dijkstra) 알고리즘은 최단 경로 알고리즘으로 그래프에서 특정한 노드에서 다..

[백준(BOJ)] #10026- 적록색약 (파이썬, Python3)

문제 https://www.acmicpc.net/problem/10026 10026번: 적록색약 적록색약은 빨간색과 초록색의 차이를 거의 느끼지 못한다. 따라서, 적록색약인 사람이 보는 그림은 아닌 사람이 보는 그림과는 좀 다를 수 있다. 크기가 N×N인 그리드의 각 칸에 R(빨강), G(초록) www.acmicpc.net 문제 풀이 DFS 알고리즘 적용! 2022.07.12 - [PS/알고리즘 이론] - [파이썬으로 배우는 알고리즘] DFS(깊이 우선 탐색) [파이썬으로 배우는 알고리즘] DFS(깊이 우선 탐색) DFS란? DFS(Depth First Search)는 그래프의 모든 노드를 탐색하는 방법 중 하나로, 깊이를 우선으로 탐색한 후 더 이상 탐색할 노드가 없다면 이전으로 돌아가 탐색을 이어나가..

[백준(BOJ)] #2014- 소수의 곱 (파이썬, PyPy3)

문제 https://www.acmicpc.net/problem/2014 2014번: 소수의 곱 첫째 줄에 K(1 ≤ K ≤ 100), N(1 ≤ N ≤ 100,000)이 주어진다. 다음 줄에는 K개의 소수가 오름차순으로 주어진다. 같은 소수가 여러 번 주어지는 경우는 없으며, 주어지는 소수는 모두 541보다 작거나 www.acmicpc.net 문제 풀이 우선순위 큐를 사용해 문제를 해결할 수 있습니다. 2022.07.19 - [CS/자료구조] - [파이썬으로 배우는 자료구조] 우선순위 큐(Priority Queue), 힙(Heap) [파이썬으로 배우는 자료구조] 우선순위 큐(Priority Queue), 힙(Heap) 우선순위 큐(Priority Queue)란? 일반적인 큐(Queue) 자료구조는 FIF..

[백준(BOJ)] #1507- 궁금한 민호 (파이썬, PyPy3)

문제 https://www.acmicpc.net/problem/1507 1507번: 궁금한 민호 첫째 줄에 도시의 개수 N(1 ≤ N ≤ 20)이 주어진다. 둘째 줄부터 N개의 줄에 각각의 도시 사이에 이동하는데 필요한 시간이 주어진다. A에서 B로 가는 시간과 B에서 A로 가는 시간은 같다. 또, A와 B www.acmicpc.net 문제 풀이 입력으로 모든 도시로 가는 최소 이동 시간이 주어져 이를 역으로 풀어야 합니다. 즉, 플로이드 워셜 알고리즘을 역으로 적용하는 문제입니다. 2022.08.01 - [PS/알고리즘 이론] - [파이썬으로 배우는 알고리즘] 플로이드 워셜(Floyd Warshall) 알고리즘 [파이썬으로 배우는 알고리즘] 플로이드 워셜(Floyd Warshall) 알고리즘 플로이드 ..

[백준(BOJ)] #1561- 놀이 공원 (파이썬, PyPy3)

문제 https://www.acmicpc.net/problem/1561 1561번: 놀이 공원 첫째 줄에 N(1 ≤ N ≤ 2,000,000,000)과 M(1 ≤ M ≤ 10,000)이 빈칸을 사이에 두고 주어진다. 둘째 줄에는 각 놀이기구의 운행 시간을 나타내는 M개의 자연수가 순서대로 주어진다. 운행 시간은 1 이상 30 www.acmicpc.net 문제 풀이 해당 문제는 이분 탐색으로 해결할 수 있습니다. 2022.08.11 - [PS/알고리즘 이론] - [파이썬으로 배우는 알고리즘] 이분 탐색(Binary Search) [파이썬으로 배우는 알고리즘] 이분 탐색(Binary Search) 이분 탐색(Binary Search)이란? 이분 탐색(Binary Search)이란 탐색 범위를 절반으로 나눠가..

[백준(BOJ)] #1562- 계단 수 (파이썬, PyPy3)

문제 https://www.acmicpc.net/problem/1562 1562번: 계단 수 첫째 줄에 정답을 1,000,000,000으로 나눈 나머지를 출력한다. www.acmicpc.net 문제 풀이 해당 문제는 쉬운 계단 수 문제의 심화 버전이라고 볼 수 있습니다. 계단 수를 구하는 것은 같지만, 0부터 9까지 숫자가 모두 등장하는 계단 수가 총 몇 개인지를 구해야 합니다. 쉬운 계단 수를 풀때와 마찬가지로 동적 계획법을 사용했고, 추가로 비트마스크를 사용했습니다. 2022.07.22 - [PS/알고리즘 이론] - [파이썬으로 배우는 알고리즘] 동적 계획법(Dynamic Programming) [파이썬으로 배우는 알고리즘] 동적 계획법(Dynamic Programming) 동적 계획법(Dynamic..

[백준(BOJ)] #10844- 쉬운 계단 수 (파이썬, PyPy3)

문제 https://www.acmicpc.net/problem/10844 10844번: 쉬운 계단 수 첫째 줄에 정답을 1,000,000,000으로 나눈 나머지를 출력한다. www.acmicpc.net 문제 풀이 동적 계획법을 사용해 입력받은 자리 수의 계단수에 대한 경우의 수를 구할 수 있습니다. 2022.07.22 - [PS/알고리즘 이론] - [파이썬으로 배우는 알고리즘] 동적 계획법(Dynamic Programming) [파이썬으로 배우는 알고리즘] 동적 계획법(Dynamic Programming) 동적 계획법(Dynamic Programming)이란? 동적 계획법(Dynamic Programming), 다이나믹 프로그래밍, DP라고 불리는 이 알고리즘은 무엇일까요?? 동적 프로그래밍? 저는 이 ..