h32j00

문제

풀이

파일안에 플래그가 있다.

다운 받아봤다.

HxD로 열어봤다.

뭔가 flag가 있는 것 같은데.. pW? 비밀번호를 쳐야되나? 하고 .zip으로 바꿈(압축 풀 때 비밀번호 넣어야하는 줄 알고..)

열어볼까나?

잉? ,, 뒷걸음질 치다가 풀었다..

사람들이 푼 것을 보니까 1f 8b 08은 gz 파일의 시그니처라고 한다,,  그래서 gz으로 확장자를 바꾸고 압축을 푸는게 정석인 듯.. 푸하~

문제

풀이

broken.. 깨져있는?

Broken.jpg 다운받아봤더니

이런 QR 코드가 나왔다.

오른쪽 위, 왼쪽 아래가 깨진 것 같긴 했는데 뭐가 잘못된 지 몰라서 검색을 해봤다..

제공된 사진(Broken.jpg)와 일반적인 QR코드는 색이 반전된 상태였다,, 

하~ jpg 구조 찾고 왜 이럴까 너무 고민했는데 부질없는 고민이었군..

그림판을 가지고 색 반전을 시킬 수 있다고 해서 해봤다.

online으로 qr read 하는 곳 발견

->

https://zxing.org/w/decode.jspx

결과

flag: 1t_S_s0_cr3atlv3

아직 문제를 풀면서 센스가 부족하다는 것을 느낌

오늘부터 1일 1 ctf-d 문제를 풀겠습니다. 땅땅땅

- 주목해야할 점

• 사진이 들어있을 수 있음
• 무언가 빠져있음

secret 파일을 다운로드 하고 HxD로 열었습니다.

PK 구조네요. 확장자를 .zip으로 변경해보았습니다.

secret.png 파일이 있습니다. 열어보겠습니다.

엥? 뭐지? HxD로 열어봤습니다.

png 파일인데 PNG 시그니처가 헤더에 없어요. -> 힌트에서 무언가 빠졌다고 했는데 이 부분이네요.

PNG 시그니처를 헤더에 넣어주겠습니다. (89 50 4E 47)

저장하였더니 플래그가 들어있는 사진이 나왔습니다.

flag: easyctf{troll3d}

문제

www.acmicpc.net/problem/1261

처음 작성한 코드

import sys
import heapq

M, N = map(int, sys.stdin.readline().split())
arr = []
queue = []
result = [sys.maxsize] * (M*N)
direction = [[-1,0], [0,1], [1,0], [0,-1]] #위, 오, 아래, 왼

result[0] = 0
heapq.heappush(queue, [0,0]) # 좌푯값[x,y]

for i in range(N):
    tmp = []
    line = map(int, sys.stdin.readline().rstrip())
    for j in line:
        tmp.append(j)
    arr.append(tmp)

while queue:
    x, y = heapq.heappop(queue)
    for i in direction:
        if 0 <= x+i[0] < N and  0 <= y+i[1] < M:
            new_x = x+i[0]
            new_y = y+i[1]
            if result[new_x * M + new_y] > result[x * M + y] + arr[new_x][new_y]:
                result[new_x * M + new_y] = result[x * M + y] + arr[new_x][new_y]
                heapq.heappush(queue, [new_x, new_y])

print(result[-1])

1. queue에는 인접한(위, 오, 아래, 왼) 좌표값들이 들어간다. 물론 최단 거리가 변경될 때에만 들어간다.
2. result에는 그 좌표까지의 최단 거리가 들어간다. 2차원 배열을 어떻게 선언하는지 잘 몰라서 1차원 배열로 했고 (0,0)은 [0]으로 접근, (0,1)은 [1]로 접근, (1,0) 은 [1*M+0] 이런식으로 접근했다.
3. 벽이 1이고 방이 0이라고 했으니까 벽을 부시고 방을 들어가면 벽 부신 횟수가 +1 이 되니까 그냥 좌표를 더해주면 된다. 그럼 빈방이면 +0, 벽이면 +1이 되기 때문이다.

깨달은 점

• 가중치 있는 그래프에서 최단 거리를 구하라고 할 때 다익스트라 알고리즘을 사용하면 될 것 같다. 

문제

www.acmicpc.net/problem/1916

처음 작성한 코드

import sys
from collections import deque

N = int(sys.stdin.readline())
M = int(sys.stdin.readline())
result = [sys.maxsize] * (N+1)
arr = {i+1:[] for i in range(N)}

for _ in range(M):
    u, v, w = map(int, sys.stdin.readline().split())
    arr[u].append([v,w])

s , e = map(int, sys.stdin.readline().split())

queue = deque()
result[s] = 0
queue.append(s)

while queue:
    u = queue.popleft()
    for v, w in arr[u]:
        if result[v] > result[u] + w:
            result[v] = result[u] + w
            queue.append(v)

print(result[e])

깨달은 점

• 단순한 다익스트라를 이용한 문제였다. 한 점에서 다른 점까지 최소거리를 구할 때 다익스트라를 쓰면 되는 것 같다. 손에 익으니까 재밌다 ㅋ ㅋ

문제

www.acmicpc.net/problem/1753

처음 작성한 코드

import sys
import heapq

V, E = map(int, sys.stdin.readline().split())
start = int(sys.stdin.readline())
INF = sys.maxsize
graph = [INF] * (V+1)
queue = []
arr = {i+1:[] for i in range(V)}

for _ in range(E):
    u, v, w = map(int, sys.stdin.readline().split())
    arr[u].append([v, w])

heapq.heappush(queue, [0, start])
graph[start] = 0

while queue:
    w, now = heapq.heappop(queue)
    for i in arr[now]:
        if graph[i[0]] > w+i[1]:
            graph[i[0]] = w+i[1]
            heapq.heappush(queue, [graph[i[0]], i[0]])

for i in range(1, V+1):
    print(graph[i] if graph[i]!=INF else 'INF')

깨달은 점

• 시간초과 5번 났는데 이유를 찾았다. 가중치가 변경될때만 queue에 넣어야하는데 안변경되도 queue에 넣어가지고 똑같은 점을 엄청 많이 방문하고 있었다....... 
• sys.maxsize를 알게됐다.
• heapq는 heap구조를 유지하며 push, pop 해주는 내장모듈인데 신기하다..

문제

www.acmicpc.net/problem/1446

처음 작성한 코드

import sys

N, D = map(int, sys.stdin.readline().split())
arr = []
for _ in range(N):
    s, e, leng = map(int, sys.stdin.readline().split())
    if e <= D:
        arr.append([s,e,leng])

distance = [i for i in range(D+1)]

for i in range(D+1):
    if i:
        distance[i] = min(distance[i], distance[i-1]+1)
    for j in arr:
        if j[0] == i:
            distance[j[1]] = min(distance[j[0]]+j[2], distance[j[1]])
    print(distance)

print(distance[-1])

1. 입력받을 때 고속도로의 길이(D)보다 지름길 끝 지점(e)이 크면 arr에 추가하지 않았다. -> 빠꾸할 수 없다고 문제에 나와있기때문에 그 지름길을 타봤자 소용이 없음.
2. 고속도로의 길이(D)만큼의 배열을 만들고 그 배열의 값을 갱신시켜주면서 최소 길이를 찾았다. -> 100킬로미터까지의 거리는 distance[100]에 접근하면 구할 수 있도록 만든것.. 마지막 출력값은 고속도로의 마지막까지의 거리를 나타낸다.

깨달은 점

• 너무너무너무 어렵다..  . . . . 언젠간 잘해지겠지..
• 다익스트라는 출발지점에서 도착지까지 최소 거리를 구할 때 사용된다고 한다.. 기억이 하나도 안난다 푸 헹헹..

문제

www.acmicpc.net/problem/4963

처음 작성한 코드

import sys
from collections import deque

def BFS(i, j):
    x = [1, 1, 1, 0, 0, -1, -1, -1]
    y = [1, 0, -1, 1, -1, 1, 0, -1]

    queue = deque()
    queue.append((i,j))

    while queue:
        now = queue.popleft()
        for i in range(8):
            next_x = now[0] + x[i]
            next_y = now[1] + y[i]
            
            if (0 <= next_x < h) and (0 <= next_y < w):
                if arr[next_x][next_y] == 1:
                    arr[next_x][next_y] = 0
                    queue.append((next_x, next_y)) 

while True:
    w, h = map(int, sys.stdin.readline().split())
    if w * h == 0:
        break
    arr = [list(map(int, sys.stdin.readline().split())) for _ in range(h)]
    cnt = 0
    for i in range(h):
        for j in range(w):
            if arr[i][j] == 1:
                cnt += 1
                arr[i][j] = 0
                BFS(i,j)
    print(cnt)

1.  arr[i][j]이 1이면 섬이기 때문에 일단 갯수를 올려주고 0으로 만들고(재방문하지않기위해) 이 섬과 인접해있는 모든 섬들을 다 0으로 만들어줄거다(BFS함수내에서). 8개의 방향을 다 돌면서 1이면 queue에 넣고 그 섬과 인접한 섬을 또 queue에 넣고 이런식으로 접해있는 모든 섬을 0으로 만들면서 진행한다.

깨달은 점

• 분명 어떻게 짤지 다 알겠는데도 어떻게 짤지 모르겠다 ㅋ ㅋ 문제는 이해했는데 코드를 못짠다 -> 그럼 문제를 이해 못한겁니다 - 나OO 교수님 - . . . 새겨듣도록 하겠습니다....

문제

www.acmicpc.net/problem/2170

처음 작성한 코드

import sys

N = int(sys.stdin.readline())
line = []
for i in range(N):
    x, y = map(int, sys.stdin.readline().split())
    line.append((x, y))
line.sort(key=lambda x:x[0])

# 현재를 기준으로 그려진 선의 시작점(선의 시작)과 끝점(선의 끝)
s = line[0][0]
e = line[0][1]

result = e - s

for i in range(1, N):
    if line[i][0] <= e and line[i][1] <= e: # 현재 그은 선이 전에 그은 선에 완전히 겹칠때
        continue

    if line[i][0] <= e <= line[i][1]: # 일부만 겹칠때, 겹친부분 빼주기
        result += (line[i][1]-line[i][0]) -(e - line[i][0])
        e = line[i][1]
        s = line[i-1][0]
    else:
        result += line[i][1]-line[i][0]
        e = line[i][1]
        s = line[i][0]

print(result)

깨달은 점

• 처음에 조건을 일부 겹치는 때만 생각을 해서 코드를 짰는데 틀렸다고 나왔다.. 두번째는 현재 선이 이전 선과 완전히 겹쳐서 더하지 않아도 될때를 찾았는데도 틀렸다고 나왔다.. 왜냐면 s, e같은 시작, 끝점을 따로 안두고 바로 앞 i-1번째와 비교를 했기 때문이다.. 사람들은 너무 똑똑하다..