Seungil Kim
All tags

Posts tagged "python"

  • 백준 9938번 방 청소
    #union-find #cpp #ps #python
    백준 9938번 방 청소 풀이. 연결된 서랍 집합의 남은 공간 수를 루트에 저장해 각 술병을 보관할 수 있는지 빠르게 판단한다.
  • 백준 9251번 LCS
    #dp #string #ps #python
    백준 9251번 LCS 풀이. 두 문자열의 접두사 조합마다 최장 공통 부분 수열 길이를 저장하는 2차원 DP를 정리한다.
  • 백준 1918번 후위 표기식
    #ps #python #stack
    백준 1918번 후위 표기식 풀이. 연산자 우선순위와 괄호 처리를 스택으로 관리해 중위 표기식을 후위 표기식으로 변환한다.
  • 백준 1422번 숫자의 신
    #sort #greedy #ps #python
    백준 1422번 숫자의 신 풀이. 두 수를 이어 붙였을 때 더 큰 순서를 비교 기준으로 삼고, 가장 큰 수를 추가로 반복해 최대 숫자를 만든다.
  • 백준 3482번 Labyrinth
    #graph #ps #python #tree
    백준 3482번 Labyrinth 풀이. 미궁을 트리처럼 보고 두 번의 BFS로 가장 멀리 떨어진 두 칸 사이의 거리를 구한다.
  • 백준 1167번 트리의 지름
    #graph #ps #python #tree
    백준 1167번 트리의 지름 풀이. 임의의 노드에서 가장 먼 노드를 찾고, 그 노드에서 다시 가장 먼 거리까지 탐색하는 두 번의 DFS를 설명한다.
  • 백준 2407번 조합
    #dp #ps #python
    백준 2407번 조합 풀이. 큰 조합 값을 직접 계산하기 위해 파스칼의 삼각형 점화식을 활용하는 방법을 정리한다.
  • 백준 9465번 스티커
    #dp #ps #python
    백준 9465번 스티커 풀이. 위아래 스티커 선택 상태를 나눠 각 위치를 선택했을 때 가능한 최대 점수를 누적한다.
  • 백준 12865번 평범한 배낭
    #dp #ps #python
    백준 12865번 평범한 배낭 풀이. 무게별 최대 가치를 저장하는 DP 테이블로 0/1 배낭 문제의 최적값을 계산한다.
  • 백준 12851번 숨바꼭질 2
    #graph #ps #python
    백준 12851번 숨바꼭질 2 풀이. BFS에서 같은 최단 시간으로 도달하는 경우도 큐에 반영해 최단 시간과 경우의 수를 함께 구한다.
  • 백준 13549번 숨바꼭질 3
    #graph #ps #python
    백준 13549번 숨바꼭질 3 풀이. 순간이동 비용이 0인 조건을 우선 처리하기 위해 우선순위 큐 기반 최단 경로 탐색을 사용한다.
  • 백준 13913번 숨바꼭질 4
    #graph #ps #python
    백준 13913번 숨바꼭질 4 풀이. BFS로 최단 시간을 구하면서 이전 위치를 함께 저장하고, 도착점에서 경로를 역추적한다.
  • 백준 17928번 오큰수
    #ps #python #stack
    백준 17928번 오큰수 풀이. 오른쪽의 후보 값을 스택으로 관리해 각 원소의 다음 큰 수를 O(N)에 찾는 방법을 정리한다.
  • 백준 1011번 Fly me to the Alpha Centauri
    #ps #python
    백준 1011번 Fly me to the Alpha Centauri 풀이. 이동 거리 패턴이 제곱수를 기준으로 대칭을 이룬다는 점을 이용해 최소 이동 횟수를 구한다.
  • 백준 11404번 플로이드
    #floyd #ps #python
    백준 11404번 플로이드 풀이. 중간 정점을 하나씩 허용하며 모든 도시 쌍의 최단 비용을 갱신하는 플로이드 워셜 알고리즘을 설명한다.
  • 백준 11660번 구간 합 구하기 5
    #dp #ps #python
    백준 11660번 구간 합 구하기 5 풀이. 2차원 누적합을 만들어 직사각형 영역 합을 포함-배제 방식으로 빠르게 계산한다.
  • 백준 1932번 정수 삼각형
    #dp #ps #python
    백준 1932번 정수 삼각형 풀이. 각 칸에 도달 가능한 왼쪽 위와 오른쪽 위 경로 중 더 큰 합을 누적하는 DP를 정리한다.
  • 백준 9935번 문자열 폭발
    #string #ps #python #stack
    백준 9935번 문자열 폭발 풀이. 문자열을 한 번 훑으며 스택의 끝이 폭발 문자열과 일치할 때 제거하는 선형 시간 접근을 정리한다.
  • 백준 2206번 벽 부수고 이동하기
    #graph #ps #python
    백준 2206번 벽 부수고 이동하기 풀이. 벽을 부쉈는지 여부를 BFS 상태에 포함해 한 번만 벽을 부수는 최단 경로를 탐색한다.
  • 백준 1504번 특정한 최단 경로
    #dijkstra #ps #python
    백준 1504번 특정한 최단 경로 풀이. 다익스트라를 여러 번 실행해 v1, v2를 지나는 두 경로 후보 중 더 짧은 값을 선택한다.
  • 백준 1753번 최단경로
    #dijkstra #ps #python
    백준 1753번 최단경로 풀이. 우선순위 큐를 사용한 다익스트라로 시작 정점에서 모든 정점까지의 최단 거리를 구한다.
  • 백준 1629번 곱셈
    #divide-and-conquer #ps #python
    백준 1629번 곱셈 풀이. 거듭제곱을 반으로 나눠 재사용하는 분할 정복과 모듈러 연산으로 O(log N)에 값을 계산한다.
  • 백준 11725번 트리의 부모 찾기
    #graph #ps #python
    백준 11725번 트리의 부모 찾기 풀이. 루트 1번에서 한 번의 DFS를 수행하며 각 노드의 부모를 동시에 기록한다.
  • 백준 16953번 A → B
    #greedy #ps #python
    백준 16953번 A → B 풀이. A에서 B로 확장하지 않고 B에서 1 제거와 2 나누기를 역으로 적용해 가능 여부와 연산 횟수를 구한다.
  • 백준 1107번 리모컨
    #brute-force #ps #python
    백준 1107번 리모컨 풀이. 만들 수 있는 채널을 완전 탐색하고, 숫자 버튼 입력 횟수와 +/- 이동 횟수의 최솟값을 비교한다.
  • 백준 10026번 적록색약
    #graph #ps #python
    백준 10026번 적록색약 풀이. 일반 시야와 적록색약 시야를 각각 BFS로 탐색해 색 영역의 개수를 비교한다.
  • 백준 2178번 미로 탐색
    #graph #ps #python
    백준 2178번 미로 탐색 풀이. BFS로 한 칸씩 이동하며 방문 칸에 거리 값을 누적해 최단 경로 길이를 계산한다.
  • 백준 1541번 잃어버린 괄호
    #greedy #ps #python
    백준 1541번 잃어버린 괄호 풀이. 첫 마이너스 이후의 덧셈 묶음을 모두 빼면 최솟값이 되는 그리디 아이디어를 정리한다.
  • 백준 15649번 N과 M
    #backtracking #ps #python #divide-and-conquer
    백준 N과 M 시리즈 풀이. 방문 여부, 오름차순 조건, 중복 제거 조건을 조합해 여러 백트래킹 문제를 한 흐름으로 정리한다.
  • 백준 1012번 유기농 배추
    #graph #ps #python
    백준 1012번 유기농 배추 풀이. 배추가 이어진 영역을 그래프의 연결 요소로 보고, 새 영역을 발견할 때마다 필요한 지렁이 수를 센다.
  • 백준 1074번 Z
    #divide-and-conquer #ps #python
    백준 1074번 Z 풀이. 전체 배열을 실제로 만들지 않고, 목표 좌표가 속한 사분면만 따라가며 방문 순서를 누적한다.
  • 백준 2579번 계단 오르기
    #dp #ps #python
    백준 2579번 계단 오르기 풀이. 마지막 계단을 반드시 밟되 세 계단 연속 금지를 만족하도록 두 가지 이전 상태를 비교하는 DP를 정리한다.
  • 백준 7576번 토마토
    #graph #ps #python
    백준 7576번 토마토 풀이. 처음 익은 토마토들을 모두 큐에 넣고 BFS로 날짜를 누적해 전체가 익는 최소 시간을 계산한다.
  • 백준 11724번 연결 요소의 개수
    #graph #ps #python
    백준 11724번 연결 요소의 개수 풀이. 방문하지 않은 노드에서 탐색을 시작할 때마다 연결 요소 하나를 세는 DFS/BFS 방식을 정리한다.
  • 백준 11726번 2xn 타일링
    #dp #ps #python
    백준 11726번 2xn 타일링 풀이. 마지막에 붙이는 타일 모양을 기준으로 n-1, n-2 경우를 더하는 DP 점화식을 설명한다.
  • 백준 1764번 듣보잡
    #hash #ps #python
    백준 1764번 듣보잡 풀이. 두 명단의 교집합을 set으로 구해 탐색 비용을 줄이고 결과를 정렬해 출력한다.
  • 백준 11279번 최대 힙
    #priority-queue #ps #python
    백준 11279번 최대 힙 풀이. Python의 최소 힙에 음수 값을 넣어 최대 힙처럼 동작하게 만드는 구현 방법을 정리한다.
  • 백준 18870번 좌표 압축
    #sort #hash #ps #python
    백준 18870번 좌표 압축 풀이. 정렬, 중복 제거, 딕셔너리 매핑을 이용해 각 좌표보다 작은 서로 다른 좌표의 개수를 빠르게 구한다.
  • 백준 1018번 체스판 다시 칠하기
    #brute-force #ps #python
    백준 1018번 체스판 다시 칠하기 풀이. 가능한 8x8 영역을 모두 확인하고 시작 색에 따른 칠해야 할 칸 수의 최솟값을 구한다.
  • 백준 10989번 수 정렬하기 3
    #sort #ps #python
    백준 10989번 수 정렬하기 3 풀이. 입력 수의 범위가 작다는 조건을 이용해 카운팅 배열로 메모리 사용을 줄여 정렬한다.
  • 백준 12015번 가장 긴 증가하는 부분 수열 2
    #dp #binary-search #ps #python
    백준 12015번 가장 긴 증가하는 부분 수열 2 풀이. 길이별 최소 끝값을 유지하고 이분 탐색으로 O(N log N)에 LIS 길이를 구한다.
  • 백준 11053번 가장 긴 증가하는 부분 수열
    #dp #ps #python
    백준 11053번 가장 긴 증가하는 부분 수열 풀이. 각 위치를 마지막 원소로 삼는 LIS 길이를 앞쪽 원소들과 비교해 갱신한다.
  • 백준 1912번 연속합
    #dp #ps #python
    백준 1912번 연속합 풀이. 누적합이 음수가 되는 지점에서 시작점을 바꾸는 카데인 알고리즘의 핵심 아이디어를 설명한다.
  • 백준 2293번 동전 1
    #dp #ps #python
    백준 2293번 동전 1 풀이. 동전을 하나씩 추가하며 각 금액을 만드는 경우의 수를 갱신하는 DP 점화식을 정리한다.
  • 백준 11399번 ATM
    #greedy #ps #python
    백준 11399번 ATM 풀이. 인출 시간이 짧은 사람부터 배치해 누적 대기 시간을 최소화하는 정렬 기반 그리디 풀이를 설명한다.
  • 백준 2606번 바이러스
    #graph #ps #python
    백준 2606번 바이러스 풀이. 1번 컴퓨터와 연결된 노드를 DFS/BFS로 탐색해 감염되는 컴퓨터 수를 계산한다.
  • 백준 11047번 동전 0
    #greedy #ps #python
    백준 11047번 동전 0 풀이. 동전 가치가 배수 관계라는 조건을 이용해 가장 큰 동전부터 사용하는 그리디 전략을 정리한다.
  • 백준 2630번 색종이 만들기
    #divide-and-conquer #ps #python
    백준 2630번 색종이 만들기 풀이. 종이를 네 조각으로 재귀 분할하며 한 색으로만 이루어진 영역의 개수를 센다.
  • 백준 1992번 쿼드트리
    #divide-and-conquer #ps #python
    백준 1992번 쿼드트리 풀이. 이미지를 네 영역으로 나누고 같은 값으로 압축 가능한지 확인하는 재귀 분할 방식을 설명한다.
  • 백준 1697번 숨바꼭질
    #graph #ps #python
    백준 1697번 숨바꼭질 풀이. 현재 위치에서 -1, +1, *2 이동을 BFS로 탐색하며 각 위치까지 걸린 시간을 기록한다.
  • 백준 1260번 DFS와 BFS
    #graph #ps #python
    백준 1260번 DFS와 BFS 풀이. 재귀 기반 DFS와 deque 기반 BFS를 구현하고, 방문 순서를 조건에 맞게 처리하는 방법을 정리한다.
  • 백준 1149번 RGB거리
    #dp #ps #python
    백준 1149번 RGB거리 풀이. 각 집을 특정 색으로 칠할 때 이전 집의 다른 색 비용 중 최솟값을 누적하는 DP 점화식을 정리한다.
  • 백준 9095번 1, 2, 3 더하기
    #ps #python
    백준 9095번 1, 2, 3 더하기 풀이. N을 1, 2, 3으로 줄여 가며 경우의 수를 나누는 재귀적 사고를 설명한다.
  • 백준 1092번 배
    #greedy #ps #python
    백준 1092번 배 풀이. 가장 강한 크레인이 가장 무거운 박스를 맡도록 정렬해 매 단계 최선의 선택을 하는 그리디 접근을 정리한다.
  • 백준 1041번 주사위
    #greedy #ps #python
    백준 1041번 주사위 풀이. 서로 마주보지 않는 면 조합의 최솟값을 구하고, 보이는 면의 개수 규칙에 맞춰 합을 계산한다.