본문 바로가기

전체 글345

[그래프] 백준 1261 알고스팟 최소한의 벽을 뚫고 목적지까지 도달해야한다. >>> 최소한의 벽 2022. 3. 16.
[그래프] 백준 1197 최소 스패닝 트리(kruskal/prim) 최소 스패닝 트리란? 모든 정점을 포함하며/ 사이클이 만들어지지 않고/ 최소한의 가중치 값의 합 을 만족하는 트리이다. 1. kruskal 알고리즘 - 그리디 - 가중치가 가장 작은 값부터 선택하면서 - 사이클이 만들어진다면 버리고 - 반복 import sys V, E = map(int, sys.stdin.readline().split()) root = [i for i in range(V+1)] # root[i]는 i의 루트 정점을 의미 edges=[] for _ in range(E): u, v, w = map(int, sys.stdin.readline().split()) edges.append([w, u, v]) edges.sort() # 오름차순 def find_root(x): if x!=root[x.. 2022. 3. 14.
[그래프] 백준 2206 벽 부수고 이동하기 https://www.acmicpc.net/problem/2206 2206번: 벽 부수고 이동하기 N×M의 행렬로 표현되는 맵이 있다. 맵에서 0은 이동할 수 있는 곳을 나타내고, 1은 이동할 수 없는 벽이 있는 곳을 나타낸다. 당신은 (1, 1)에서 (N, M)의 위치까지 이동하려 하는데, 이때 최단 경로 www.acmicpc.net import sys from collections import deque N,M = map(int, sys.stdin.readline().split()) graph = [list(map(int, sys.stdin.readline().strip())) for _ in range(N)] dy = [-1, 1, 0, 0] dx = [0, 0, 1, -1] def bfs(): v.. 2022. 3. 13.
[dp] 백준 12865 평범한 배낭/ 14728 벼락치기 두 문제 모두 "평범한 배낭" 문제와 같다. 변수명만 다르게 하면 될 뿐, 코드까지 똑같은 문제이다. import sys N, T = map(int, sys.stdin.readline().split()) time_score = [list(map(int, sys.stdin.readline().split())) for _ in range(N)] dp = [[0]*(T+1) for _ in range(N+1)] for y in range(1, N+1): time = time_score[y-1][0] score = time_score[y-1][1] for x in range(1, T+1): if time 2022. 3. 13.
[dp/dfs] 백준 15691번 루트가 있는 트리에서 각 노드 이하로 몇 개의 노드가 있는지 카운트해야한다. 처음 문제를 봤을때 쉽게 생각했는데 시간초과/메모리초과 문제로 꽤나 오래 걸렸다. dfs를(재귀를) 이렇게 활용할 수 있구나 깨달아서 좋은 문제 import sys sys.setrecursionlimit(10**5) N, R, Q = map(int, sys.stdin.readline().split()) graph = [[] for _ in range(N+1)] dp = [0 for _ in range(N+1)] for _ in range(N-1): a, b = map(int, sys.stdin.readline().split()) graph[a].append(b) graph[b].append(a) def dfs(x): dp[x]=.. 2022. 3. 12.
[multimedia] 이 그림에는 뭔가 좀 수상한... 단순히 png 파일을 열면 다음과 같다. 하지만 forensically에서 확인해보면 뭔가 다른 사진이 중첩되어있음을 충분히 의심할 수 있다. binwalk를 사용하기 위해 (윈도우에 설치를 하지 않아...) kali로 넘어가서 분석을 진행했다. jpeg 파일이 있다. 이제 이걸 빼내기위해 foremost를 사용했다. ABCTF{PNG_S0_COO1} 물론 png를 hxd로 열어서 png, jpg header signature를 검색하면서 찾아도 된다. 하지만 이때 조심할 점은 jpg header signature를 검색할 때 ff d8, ff d9가 엄청 많이 나오는 것을 파악할 수 있다. ff d8 다음에 나오는 값들도 보면서 jpg인지 아닌지 파악해야 한다. 내가 파악한 바로는 가장 마지막 ff d.. 2022. 3. 12.

티스토리툴바