Kyun2Da Blog

알고리즘 블로그

[백준 / Python] 1918 후위 표기식

스택

1️⃣ 서론 이 문제는 백준 1918 후위 표기식 문제에 대한 풀이이며 파이썬(Python)으로 해결하였다. 2️⃣ 문제 설명 이 문제는 중위 표기법으로 되어 있는 식을 후위 표기법으로 바꾸는 문제이다. 3️⃣ 풀이 중위 표기법을 후위 표기법으로 바꾸는 과정은 다음과 같다. 피연산자가 들어오면 바로 출력한다. 연산자가 들어오면 자기...

[백준 / Python] 1967 트리의 지름

알고리즘 - 트리의 지름

1️⃣ 서론 이 문제는 백준 1967 트리의 지름 문제에 대한 풀이이며 파이썬(Python)으로 해결하였다. 2️⃣ 문제 설명 트리(tree)는 사이클이 없는 무방향 그래프이다. 트리에서는 어떤 두 노드를 선택해도 둘 사이에 경로가 항상 하나만 존재하게 된다. 트리에서 어떤 두 노드를 선택해서 양쪽으로 쫙 당길 때, 가장 길게 늘어나는 경우가 있...

[백준 / Python] 9252 LCS 2

1️⃣ 서론 이 문제는 백준 9252 LCS 2 문제에 대한 풀이이며 파이썬(Python)으로 해결하였다. 2️⃣ 문제 설명 최장 공통 부분 수열(LCS)의 길이와 최대 길이에 대한 문자열을 출력하는 문제이다. 3️⃣ 풀이 LCS문제는 전형적으로 dp로 해결이 가능한 문제이다. dp에 대한 수도 코드는 다음과 같다. function LCS...

[백준 / Python] 10942 팰린드롬

1️⃣ 서론 이 문제는 백준 10942 팰린드롬? 문제에 대한 풀이이며 파이썬(Python)으로 해결하였다. 2️⃣ 문제 설명 자연수 n개가 있는 배열이 주어지고, 해당하는 구간이 팰린드롬이면 1을 출력하고 팰린드롬이 아니면 0을 출력하는 문제이다. 3️⃣ 풀이 처음에 아이디어를 잘 생각해내지 못해서 쉽게 풀지 못했다. 단순히 브루트포스를 사...

[백준 / Python] 9466 텀 프로젝트

1️⃣ 서론 이 문제는 백준 9466 텀 프로젝트 문제에 대한 풀이이며 파이썬(Python)으로 해결하였다. 2️⃣ 문제 설명 학생들이(s1, s2, …, sr)이라 할 때, r=1이고 s1이 s1을 선택하는 경우나, s1이 s2를 선택하고, s2가 s3를 선택하고,…, sr-1이 sr을 선택하고, sr이 s1을 선택하는 경우에만 한 팀이 될 수...

[백준 / Python] 2096 내려가기

1️⃣ 서론 이 문제는 백준 2096 내려가기 문제에 대한 풀이이며 파이썬(Python)으로 해결하였다. 2️⃣ 문제 설명 첫째 줄에 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 N개의 줄에는 숫자가 세 개씩 주어진다. 숫자는 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 중의 하나가 된다. 첫째 줄에 얻을 수 있는 최대 점수와 최소...

[백준 / Python] 2493 탑

1️⃣ 서론 이 문제는 백준 2493 탑 문제에 대한 풀이이며 파이썬(Python)으로 해결하였다. 2️⃣ 문제 설명 모든 탑의 레이저 송신기는 레이저 신호를 지표면과 평행하게 수평 직선의 왼쪽 방향으로 발사하고, 탑의 기둥 모두에는 레이저 신호를 수신하는 장치가 설치되어 있다. 하나의 탑에서 발사된 레이저 신호는 가장 먼저 만나는 단 하나의 탑...

[백준 / Python] 2146 다리 만들기

1️⃣ 서론 이 문제는 백준 2146 다리만들기 문제에 대한 풀이이며 파이썬(Python)으로 해결하였다. 2️⃣ 문제 설명 여러 섬으로 이루어진 나라가 있다. 이 나라는 N x N 크기의 이차원 평면상에 존재하고 여러 섬으로 이루어져 있으며, 동서남북으로 육지가 붙어있는 덩어리를 말한다. 0은 바다, 1은 육지를 나타내며, 지도가 주어질 때, ...

[백준 / Python] 1504 특정한 최단 경로

1️⃣ 서론 이 문제는 백준 1504 특정한 최단 경로 문제에 대한 풀이이며 파이썬(Python)으로 해결하였다. 2️⃣ 문제 설명 세준이는 1번 정점에서 N번 정점으로 최단 거리로 이동하려고 한다. 또한 임의로 주어진 두 정점은 반드시 통과해야 한다. 주어진 두 정점을 반드시 거치면서 최단 경로로 이동하는 최단 경로의 길이를 구하는 문제이다. ...

[백준 / Python] 17144 미세먼지 안녕!

1️⃣ 서론 이 문제는 백준 17144 미세먼지 안녕! 문제에 대한 풀이이며 파이썬(Python)으로 해결하였다. 2️⃣ 문제 설명 R x C 크기의 격자판이 있고 공기 청정기는 항상 1열 어딘가에 위치해 있다. 미세먼지는 다음과 같은 규칙으로 퍼지거나 움직인다. 1초 동안 아래 적힌 일이 순서대로 일어난다. 미세먼지가 확산된다. 확산은...