주제

#python

글 56개

백준 9938번 방 청소

2021년 11월 26일 #union-find #cpp #ps #python

연결된 서랍 집합의 남은 자리를 루트에 저장하는 유니온 파인드로 술병 보관 여부 판단하기
백준 9251번 LCS

2021년 10월 14일 #dp #string #ps #python

두 문자열의 접두사 쌍마다 최장 공통 부분 수열 길이를 저장하는 2차원 DP
백준 1918번 후위 표기식

2021년 10월 13일 #ps #python #stack

연산자 우선순위와 괄호를 스택으로 처리해 중위 표기식을 후위 표기식으로 바꾸기
백준 1422번 숫자의 신

2021년 10월 10일 #sort #greedy #ps #python

a+b와 b+a를 비교하는 정렬 기준으로 이어 붙이고, 가장 큰 수를 반복해 남은 자리를 채우기
백준 3482번 Labyrinth

2021년 10월 7일 #graph #ps #python #tree

칸 사이 경로가 하나뿐인 미궁을 트리로 보고 두 번의 BFS로 가장 먼 두 칸 사이 거리 구하기
백준 1167번 트리의 지름

2021년 10월 5일 #graph #ps #python #tree

아무 노드에서 가장 먼 노드를 찾고 거기서 다시 가장 먼 거리를 재는 두 번의 DFS가 맞는 이유
백준 2407번 조합

2021년 10월 2일 #dp #ps #python

파스칼의 삼각형 점화식으로 큰 조합 값을 직접 계산하기
백준 9465번 스티커

2021년 10월 2일 #dp #ps #python

두 줄 DP 테이블에 각 스티커를 골랐을 때의 최대 점수를 대각선 방향으로 누적하기
백준 12865번 평범한 배낭

2021년 9월 30일 #dp #ps #python

무게별 최대 가치를 저장하는 DP 테이블로 완전 탐색 없이 푸는 0/1 배낭 문제
백준 12851번 숨바꼭질 2

2021년 9월 29일 #graph #ps #python

같은 최단 시간으로 도착하는 경우도 큐에 넣어 최단 시간과 방법의 수를 함께 구하는 BFS
백준 13549번 숨바꼭질 3

2021년 9월 29일 #graph #ps #python

비용 0인 순간이동을 먼저 처리하는 최단 경로, 우선순위 큐 대신 0-1 BFS로도 가능
백준 13913번 숨바꼭질 4

2021년 9월 29일 #graph #ps #python

BFS로 최단 시간을 구하며 직전 위치를 함께 저장하고 도착점에서 경로를 거꾸로 따라가기
백준 17928번 오큰수

2021년 9월 29일 #ps #python #stack

다음 큰 수 후보를 스택으로 관리해 각 원소의 오큰수를 O(N)에 찾기
백준 1011번 Fly me to the Alpha Centauri

2021년 9월 26일 #ps #python

1, 121, 12321처럼 제곱수를 기준으로 대칭인 이동 거리 패턴에서 최소 이동 횟수 구하기
백준 11404번 플로이드

2021년 9월 25일 #floyd #ps #python

거쳐 갈 노드를 가장 바깥 반복문에서 고정해야 하는 플로이드 워셜, 반복문 순서 주의
백준 11660번 구간 합 구하기 5

2021년 9월 25일 #dp #ps #python

행과 열 방향으로 누적한 2차원 누적합에서 포함-배제로 직사각형 합 구하기
백준 1932번 정수 삼각형

2021년 9월 25일 #dp #ps #python

왼쪽 위와 오른쪽 위 중 큰 합을 고르며 내려가는 정수 삼각형 DP
백준 9935번 문자열 폭발

2021년 9월 24일 #string #ps #python #stack

글자를 스택에 쌓다가 끝부분이 폭발 문자열과 같으면 지워 한 번의 순회로 처리하기
백준 2206번 벽 부수고 이동하기

2021년 9월 23일 #graph #ps #python

벽을 부쉈는지 여부를 BFS 상태에 넣어 한 번만 부수고 가는 최단 경로 찾기
백준 1504번 특정한 최단 경로

2021년 9월 19일 #dijkstra #ps #python

1→v1→v2→N과 1→v2→v1→N 중 짧은 쪽을 다익스트라 여러 번으로 비교하기
백준 1753번 최단경로

2021년 9월 19일 #dijkstra #ps #python

비용 기준 우선순위 큐 다익스트라, 일반 큐와 노드 번호 기준 정렬로 시간 초과가 났던 실수
백준 1629번 곱셈

2021년 9월 18일 #divide-and-conquer #ps #python

지수를 반으로 나눠 제곱하는 분할 정복 거듭제곱과 모듈러 연산으로 O(log N) 계산
백준 11725번 트리의 부모 찾기

2021년 9월 15일 #graph #ps #python

루트 1번에서 DFS 한 번으로 모든 노드의 부모를 함께 기록하기, 노드마다 탐색해 시간 초과가 난 첫 시도
백준 16953번 A → B

2021년 9월 14일 #greedy #ps #python

A에서 B로 가는 대신 B에서 끝자리 1을 지우고 2로 나누며 거꾸로 내려가는 풀이
백준 1107번 리모컨

2021년 9월 12일 #brute-force #ps #python

0번부터 100만 번까지 갈 수 있는 채널을 모두 시도해 +/- 버튼 이동과 비교하는 완전 탐색
백준 10026번 적록색약

2021년 9월 7일 #graph #ps #python

같은 색 영역을 BFS로 세고, R을 G로 바꾼 격자에서 한 번 더 세는 적록색약 시야 처리
백준 2178번 미로 탐색

2021년 9월 6일 #graph #ps #python

한 칸씩 이동하며 거리를 1씩 더하는 기본 BFS 최단 경로
백준 1541번 잃어버린 괄호

2021년 9월 5일 #greedy #ps #python

처음 나온 마이너스 뒤의 수는 괄호로 묶어 모두 뺄 수 있다는 그리디
백준 9663번 N-Queen

2021년 7월 15일 #backtracking #ps #python #divide-and-conquer

퀸 위치를 1차원 배열로 두고 열과 대각선 충돌을 검사하는 백트래킹
백준 15649번 N과 M

2021년 7월 12일 #backtracking #ps #python #divide-and-conquer

방문 여부, 오름차순, 중복 제거 조건을 바꿔 가며 N과 M 시리즈를 하나의 백트래킹으로 풀기
백준 1012번 유기농 배추

2021년 7월 11일 #graph #ps #python

이어진 배추 영역을 연결 요소로 보고 DFS가 새 영역을 찾을 때마다 지렁이 수 세기
백준 1074번 Z

2021년 7월 11일 #divide-and-conquer #ps #python

10억 칸 배열을 만들지 않고 목표 좌표가 속한 사분면만 따라 내려가며 방문 순서 누적하기
백준 2579번 계단 오르기

2021년 7월 9일 #dp #ps #python

세 계단 연속 금지와 마지막 계단 필수 조건을 두 가지 이전 상태로 처리하는 DP
백준 7576번 토마토

2021년 7월 9일 #graph #ps #python

처음 익은 토마토를 모두 큐에 넣고 BFS로 날짜를 누적해 전체가 익는 날 구하기
백준 11724번 연결 요소의 개수

2021년 7월 8일 #graph #ps #python

방문하지 않은 노드에서 탐색을 시작할 때마다 하나씩 세는 연결 요소, Python 재귀 깊이 제한 풀기
백준 11726번 2xn 타일링

2021년 7월 8일 #dp #ps #python

마지막에 세로 타일 하나를 붙이는 경우와 가로 타일 두 개를 붙이는 경우를 더하는 점화식
백준 1764번 듣보잡

2021년 7월 8일 #hash #ps #python

리스트 비교 대신 set 교집합으로 O(N)에 두 명단의 공통 이름 찾기
백준 11279번 최대 힙

2021년 7월 5일 #priority-queue #ps #python

최소 힙만 있는 heapq에 음수를 넣어 최대 힙처럼 쓰는 방법
백준 18870번 좌표 압축

2021년 7월 5일 #sort #hash #ps #python

정렬, 중복 제거, 딕셔너리 매핑으로 각 좌표보다 작은 서로 다른 좌표 수를 빠르게 구하기
백준 1018번 체스판 다시 칠하기

2021년 7월 4일 #brute-force #ps #python

가능한 모든 8x8 영역에서 W 시작, B 시작 체스판과 비교해 다시 칠할 칸 수의 최솟값 찾기
백준 10989번 수 정렬하기 3

2021년 7월 4일 #sort #ps #python

천만 개 입력을 정렬 대신 값 범위 1만짜리 카운팅 배열로 처리해 메모리 초과 피하기
백준 12015번 가장 긴 증가하는 부분 수열 2

2021년 7월 1일 #dp #binary-search #ps #python

길이별로 가장 작은 끝값을 유지하고 이분 탐색으로 갱신하는 O(N log N) LIS
백준 11053번 가장 긴 증가하는 부분 수열

2021년 6월 29일 #dp #ps #python

각 원소를 끝으로 하는 LIS 길이를 앞의 원소들과 비교해 갱신하는 O(N²) DP와 그 한계
백준 1912번 연속합

2021년 6월 27일 #dp #ps #python

누적합이 음수가 되면 다음 원소에서 새로 시작하는 카데인 알고리즘
백준 2293번 동전 1

2021년 6월 26일 #dp #ps #python

동전을 하나씩 추가하며 금액별 경우의 수를 갱신하는 d2[i] = d1[i] + d2[i-v] 점화식
백준 11399번 ATM

2021년 5월 25일 #greedy #ps #python

인출 시간이 짧은 사람부터 줄을 세워 누적 대기 시간을 최소로 만드는 정렬 그리디
백준 2606번 바이러스

2021년 5월 25일 #graph #ps #python

1번 컴퓨터와 연결된 노드를 DFS나 BFS로 세는 기본 그래프 탐색
백준 11047번 동전 0

2021년 5월 24일 #greedy #ps #python

동전 가치가 서로 배수일 때만 성립하는, 가장 큰 동전부터 쓰는 그리디
백준 2630번 색종이 만들기

2021년 5월 24일 #divide-and-conquer #ps #python

종이를 넷으로 나눠 한 색이면 세고 아니면 다시 나누는 재귀 분할
백준 1992번 쿼드트리

2021년 5월 23일 #divide-and-conquer #ps #python

이미지를 넷으로 나눠 모두 같은 값일 때만 압축하는 재귀 분할
백준 1697번 숨바꼭질

2021년 5월 22일 #graph #ps #python

-1, +1, ×2 이동을 BFS로 탐색하며 각 위치까지 걸린 시간을 기록하기
백준 1260번 DFS와 BFS

2021년 5월 21일 #graph #ps #python

재귀로 짠 DFS와 deque로 짠 BFS, 작은 번호부터 방문하는 순서 처리
백준 1149번 RGB거리

2021년 5월 20일 #dp #ps #python

이전 집을 다른 색으로 칠한 최소 비용 중 작은 쪽을 고르는 RGB 거리 DP 점화식
백준 9095번 1, 2, 3 더하기

2021년 5월 19일 #ps #python

N에서 1, 2, 3을 빼 나가며 순서가 다른 경우까지 모두 세는 재귀
백준 1092번 배

2021년 5월 18일 #greedy #ps #python

가장 센 크레인이 가장 무거운 박스를 맡는 그리디, Python3에서는 시간 초과지만 PyPy3로는 통과
백준 1041번 주사위

2021년 5월 17일 #greedy #ps #python

마주 보지 않는 세 면 조합의 최솟값을 구하고 보이는 면 개수 규칙대로 더하기, int 범위 주의