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)라고 불리기도 합니다. 실생활에서 예를 들어볼까요? 우리가 보통 ..

[백준(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라고 불리는 이 알고리즘은 무엇일까요?? 동적 프로그래밍? 저는 이 ..

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

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