Kim Jisong

I am an amazing person.

solved.ac: CLASS 4

Introduction

실버

조합

import sys
import math
input = sys.stdin.readline

n, m = map(int,input().split())

up = math.factorial(n)
down = math.factorial(n-m)*math.factorial(m)
print(up//down)

A -> B

트리의 부모 찾기

골드

후위 표기식

중위 표기식이 주어졌을 때 후위 표기식으로 고치는 프로그램을 작성하시오.

-> 자료구조, 스택

피보나치 수 6

-> 분할정복, 거듭제곱

파티

https://www.acmicpc.net/problem/1238

어느 날 이 N명의 학생이 X (1 ≤ X ≤ N)번 마을에 모여서 파티를 벌이기로 했다. 이 마을 사이에는 총 M개의 단방향 도로들이 있고 i번째 길을 지나는데 Ti(1 ≤ Ti ≤ 100)의 시간을 소비한다.

각각의 학생들은 파티에 참석하기 위해 걸어가서 다시 그들의 마을로 돌아와야 한다. 하지만 이 학생들은 워낙 게을러서 최단 시간에 오고 가기를 원한다.

-> 다익스트라

import sys
import heapq
input = sys.stdin.readline

N, M, X = map(int,input().split())

edges = [[] for _ in range(N+1)]
for _ in range(M):
    start, end, cost = map(int,input().split())
    edges[start].append((cost,end))

for e in edges:
    e.sort()

INF = int(1e9)
def dijkstra(start):
    q = []
    heapq.heappush(q,(0,start))
    distance = [INF]*(N+1)
    distance[start] = 0
    while q:
        dist, now = heapq.heappop(q)
        if distance[now] < dist:
            continue
        for edge in edges[now]:
            next_dist = dist + edge[0]
            if next_dist < distance[edge[1]]:
                distance[edge[1]] = next_dist
                heapq.heappush(q,(next_dist,edge[1]))
    return distance

max_time = 0
for i in range(1,N+1):
    time = dijkstra(i)[X]+dijkstra(X)[i]
    if max_time < time:
        max_time = time
print(max_time)

웜홀

TC개의 줄에 걸쳐서 만약에 시간이 줄어들면서 출발 위치로 돌아오는 것이 가능하면 YES, 불가능하면 NO를 출력한다.

-> ??

치즈

-> 그래프?

최소비용구하기2

-> 다익스트라

거짓말

-> 그래프, 분리 집합

벽 부수고 이동하기

-> 그래프 이론, 그래프 탐색, 너비 우선 탐색

별 찍기 - 11

-> 분할 정복, 재귀

이진 검색 트리

-> 그래프 이론, 그래프 탐색, 트리, 재귀

N-Queen

-> 브루트포스 알고리즘, 백트래킹

문자열 폭발

-> 자료구조, 문자열, 스택

https://www.acmicpc.net/problem/9935

행렬 제곱

-> 수학, 분할 정복, 분할 정복을 이용한 거듭제곱, 선형대수학

가장 긴 바이토닉 부분 수열

-> 다이나믹 프로그래밍

플로이드

import sys
input = sys.stdin.readline

n = int(input())
m = int(input())

# 인접행렬 생성
INF = (1e9)
min_dist_table = [[INF]*(n+1) for _ in range(n+1)]

for a in range(1, n+1):
    for b in range(1, n+1):
        if a == b:
            min_dist_table[a][b] =0

for _ in range(m):
    a, b, c = map(int,input().split())
    min_dist_table[a][b] = min(min_dist_table[a][b],c)

## 플로이드 워셜 알고리즘 (점화식 기반)
# 경로
for k in range(1, n+1):
    # 출발
    for a in range(1, n+1):
        # 도착
        for b in range(1, n+1):
            min_dist_table[a][b] = min(min_dist_table[a][b], min_dist_table[a][k] + min_dist_table[k][b])

# 결과 출력
for a in range(1, n + 1):
    for b in range(1, n +1):
        # 노드를 방문할 수 없는 경우, '무한' 값 출력
        if min_dist_table[a][b] == INF:
            print(0, end = ' ')
        else:
            # 노드를 방문할 수 있을 경우 최단 거리 출력
            print(min_dist_table[a][b], end = ' ')
    # 개행1
    print()

숨바꼭질 2

-> 그래프 이론, 그래프 탐색, 너비 우선 탐색

시그마

-> 수학, 정수론, 분할 정복을 이용한 거듭제곱, 모듈로 곱셈 역원, 페르마의 소정리

연구소

-> 구현, 그래프 이론, 브루트포스 알고리즘, 그래프 탐색, 너비 우선 탐색

서강그라운드

-> 그래프 이론, 다익스트라, 플로이드-워셜

미세먼지 안녕!

-> 구현, 시뮬레이션

최소비용 구하기

import sys
import heapq
input = sys.stdin.readline

N = int(input())
M = int(input())

graph = [[] for _ in range(N+1)]
for _ in range(M):
    start, end, cost = map(int,input().split())
    graph[start].append((end,cost))

for g in graph:
    g.sort()

start_point, end_point = map(int,input().split())

INF = int(1e9)
costs = [INF]*(N+1)
def dijkstra(start):
    q = []
    heapq.heappush(q,(0,start))
    costs[start] = 0
    while q:
        cost, now = heapq.heappop(q)
        if costs[now] < cost:
            continue
        for next, next_cost in graph[now]:
            new_cost = cost + next_cost
            if new_cost < costs[next]:
                costs[next] = new_cost
                heapq.heappush(q,(new_cost,next))


dijkstra(start_point)

print(costs[end_point])

내려가기

-> 다이나믹 프로그래밍, 슬라이딩 윈도우

메모리 제한이 4MB이기 때문에, 2차원 배열로 만들면 메모리 초과가 발생한다.

import sys
input = sys.stdin.readline

n = int(input())

# max_dp[i][0] = max(dp[i-1][0],dp[i-1][1]) + table[i][0]
# max_dp[i][1] = max(dp[i-1][0],dp[i-1][1],dp[i-1][2]) + table[i][1]
# max_dp[i][2] = max(dp[i-1][1],dp[i-1][2]) + table[i][2]
max_data = [0,0,0]
min_data = [0,0,0]
pre_max_data = [0,0,0]
pre_min_data = [0,0,0]
for i in range(0,n):
    a, b, c = map(int,input().split())
    # MAX
    max_data[0] = max(pre_max_data[0],pre_max_data[1]) + a
    max_data[1] = max(pre_max_data[0],pre_max_data[1],pre_max_data[2]) + b
    max_data[2] = max(pre_max_data[1],pre_max_data[2]) + c
    # MIN
    min_data[0] = min(pre_min_data[0],pre_min_data[1]) + a
    min_data[1] = min(pre_min_data[0],pre_min_data[1],pre_min_data[2]) + b
    min_data[2] = min(pre_min_data[1],pre_min_data[2]) + c
    # trans
    pre_max_data[0], pre_max_data[1], pre_max_data[2] = max_data[0], max_data[1], max_data[2]
    pre_min_data[0], pre_min_data[1], pre_min_data[2] = min_data[0], min_data[1], min_data[2]

print(max(pre_max_data),min(min_data))

LCS

-> 다이나믹 프로그래밍, 문자열

평범한 배낭

-> 다이나믹 프로그래밍, 배낭 문제

냅색 알고리즘

import sys
input = sys.stdin.readline

N, K = map(int, input().split())
stuff = [[0,0]]
knapsack = [[0 for _ in range(K + 1)] for _ in range(N + 1)]

for _ in range(N):
    stuff.append(list(map(int, input().split())))


#냅색 문제 풀이
for i in range(1, N + 1):
    for j in range(1, K + 1):
        weight = stuff[i][0] 
        value = stuff[i][1]
       
        if j < weight:
            knapsack[i][j] = knapsack[i - 1][j] #weight보다 작으면 위의 값을 그대로 가져온다
        else:
            knapsack[i][j] = max(value + knapsack[i - 1][j - weight], knapsack[i - 1][j])

print(knapsack[N][K])

숨바꼭질 3

-> 그래프 이론, 그래프 탐색, 너비 우선 탐색, 다익스트라, 0-1 너비 우선 탐색

치킨 배달

-> 구현, 브루트포스 알고리즘, 백트래킹

파이프 옮기기1

-> 다이나믹 프로그래밍, 그래프이론, 그래프 탐색

dfs 시간초과 -> pypy3로 컴파일

import sys
input = sys.stdin.readline

n = int(input())
maps = []
for _ in range(n):
    maps.append(list(map(int,input().split())))

# pos, 가로(0), 세로(1), 대각선(2)
# if pos == 0:    x, y = x, y+1 or x, y = x+1, y+1
# if pos == 1:    x, y = x+1, y or x, y = x+1, y+1
# if pos == 2:    x, y = x, y+1 or x, y = x+1, y or x, y = x+1, y+1
# if x > len(maps) or y > len(maps[0]): break
# if map[x][y] == 1: break

class dfs():
    def __init__(self,map,n):
        self._map = map
        self._cnt = 0
        self._n = n-1
    def _dfs(self,x,y,pos):
        if x==self._n and y==self._n:
            self._cnt += 1
            return
        ## 이동
        # 가로
        if pos == 0:
            if y < self._n and self._map[x][y+1] == 0:
                self._dfs(x,y+1,0)
            if x < self._n and y < self._n:
                if self._map[x+1][y] == 0 and self._map[x+1][y+1] == 0 and self._map[x][y+1] == 0:
                    self._dfs(x+1,y+1,2)
        # 세로
        elif pos == 1 and x < self._n  and self._map[x+1][y] == 0:
            if x < self._n and self._map[x+1][y] == 0:
                self._dfs(x+1,y,1)
            if x < self._n and y < self._n:
                if self._map[x+1][y] == 0 and self._map[x+1][y+1] == 0 and self._map[x][y+1] == 0:
                    self._dfs(x+1,y+1,2)
        # 대각선
        elif pos == 2:
            if y < self._n and self._map[x][y+1] == 0:
                self._dfs(x,y+1,0)
            if x < self._n and self._map[x+1][y] == 0:
                self._dfs(x+1,y,1)
            if x < self._n and y < self._n:
                if self._map[x+1][y] == 0 and self._map[x+1][y+1] == 0 and self._map[x][y+1] == 0:
                    self._dfs(x+1,y+1,2)
    def run(self,start_x,start_y,start_pos):
        self._dfs(start_x,start_y,start_pos)
        print(self._cnt)

dfs = dfs(maps,n)
dfs.run(0,1,0)

dp 코드(시간 및 메모리면에서 더 좋다)

가능한 경로값 누적

# 17070 DP로 풀어보기 !!

n = int(input())
array = []
for _ in range(n):
    array.append(list(map(int, input().split())))

result = [[[0]*n for _ in range(n)] for _ in range(3)]
result[0][0][1] = 1 # 맨 처음 파이프의 위치

# x == 0 (가로 방)향 인 row 1로 초기화
for i in range(2, n):
    if array[0][i] == 0:
        result[0][0][i] = result[0][0][i-1]

for i in range(1, n):
    for j in range(2, n):
        # 대각선으로 오는 경우 - 양 옆의 세 칸이 모두 빈칸인지 확인
        if array[i][j] == 0 and array[i-1][j] == 0 and array[i][j-1] == 0:
            # 대각선으로 올때 : 가로, 세로 대각선 모두 가능!
            result[2][i][j] = result[0][i-1][j-1] + result[1][i-1][j-1] + result[2][i-1][j-1]

        if array[i][j] == 0:
            # 가로로 올 때 : 가로에서 가로, 대각선에서 가로
            result[0][i][j] = result[0][i][j-1] + result[2][i][j-1]
            # 세로로 올 때 : 세로에서 세로, 대각선에서 세로
            result[1][i][j] = result[1][i-1][j] + result[2][i-1][j]

# 총합 : 가로 세로 대각선 방향
print(result[0][n-1][n-1] + result[1][n-1][n-1] + result[2][n-1][n-1])

2022

Stack

1 minute read

Introduction

Stack

less than 1 minute read

Introduction

Download-only-one-directory

less than 1 minute read

Git 명령어를 사용한 하위 디렉토리 다운로드 Clone 할 로컬 저장소 생성

Sort

3 minute read

Introduction

Tree

less than 1 minute read

Introduction

Mutex library on C++

less than 1 minute read

#include <iostream> #include <thread> #include <chrono> #include <mutex> #include <atomic> #include <string.h>

TODO

less than 1 minute read

how to costom github blog using jekyll

Welcome to Jekyll!

less than 1 minute read

You’ll find this post in your _posts directory. Go ahead and edit it and re-build the site to see your changes. You can rebuild the site in many different wa...

Back to top ↑