코딩테스트

[백준(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)는 그래프의 모든 노드를 탐색하는 방법 중 하나로, 깊이를 우선으로 탐색한 후 더 이상 탐색할 노드가 없다면 이전으로..

[백준(BOJ)] #11053- 가장 긴 증가하는 부분 수열 (파이썬, PyPy3)

문제 https://www.acmicpc.net/problem/11053 11053번: 가장 긴 증가하는 부분 수열 수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이 www.acmicpc.net 문제 풀이 가장 긴 증가하는 부분 수열은 동적 계획법의 대표적인 문제 중 하나로 LIS(Longest Increasing Subsequence)로 잘 알려져 있습니다. 2022.07.22 - [PS/알고리즘 이론] - [파이썬으로 배우는 알고리즘] 동적 계획법(Dynamic Programming) [파이썬으로 배우..

[백준(BOJ)] #13459- 구슬 탈출 (파이썬, PyPy3)

문제 https://www.acmicpc.net/problem/13459 13459번: 구슬 탈출 첫 번째 줄에는 보드의 세로, 가로 크기를 의미하는 두 정수 N, M (3 ≤ N, M ≤ 10)이 주어진다. 다음 N개의 줄에 보드의 모양을 나타내는 길이 M의 문자열이 주어진다. 이 문자열은 '.', '#', 'O', 'R', 'B' www.acmicpc.net 문제 풀이 구현 문제로 BFS 알고리즘을 사용하여 빼낼 수 있는지 없는지를 알 수 있습니다. 2022.07.14 - [PS/알고리즘 이론] - [파이썬으로 배우는 알고리즘] BFS(너비 우선 탐색) [파이썬으로 배우는 알고리즘] BFS(너비 우선 탐색) BFS란? BFS(Breadth First Search)는 DFS와 마찬가지로 그래프의 모든 ..