위치 : 서울 마포구 양화로6길 48 2층

피자 맥주 졸맛탱

평일보쌈 정식 - 10,000원

식당 : 인사동 마늘보쌈

평점 : 3.5/5.0

먹을만하지만 공기는 약간 퍽퍽한 느낌?, 보쌈 무 김치도 약간 아쉬운 맛ㅠ

식당 : LINEUP 커피

평점 : 4.0/5.0

오픈 할인해서 싸고 맛있게 잘 먹었습니다 :)

6842고기밥상

평점: 4.7/5.0

후기: 가격대는 좀 있지민 갈비정식 진짜 맛있게 먹었어요! 밑반찬도 맛있고 정갈하고 깔끔하게 나와서 잘 먹었습니다.!

카페트루어스

평점: 4.5/5.0

후기: 커피랑 케익 굿

센트로폴리스 지하 - 한옥집 김치찜

평점: 3.3 / 5.0

양이 많다.

김치찜 김치는 좀 짰던편이고 김치찜 고기는 좀 퍽퍽한편

소불고기는 적당했음 

1043_거짓말 (Python)

0. 출처

• 유형 : 유니온 파인드 (gold 4)
• 링크 : 1043번: 거짓말

1. 기록

• 22/07/06 (수)

2. 풀이

(1) 아이디어, 시간복잡도, 자료구조

1. 아이디어
>>
>>

2. 시간복잡도
>>

3. 자료구조
>>

(2) 예제 입력, 예제 출력

- 예제 입력 1 -
사람의 수 / 파티의 수
4 3

진실을 아는 사람의 수 / 그 번호
0

각 파티마다 오는 사람의 수 / 그 번호
2 1 2
1 3
3 2 3 4

- 예제 출력 1 -
3

- 예제 입력 2 -
4 1

진실을 아는 사람의 수 / 그 번호
1 1

각 파티마다 오는 사람의 수 / 그 번호
4 1 2 3 4

- 예제 출력 2 -
0

- 예제 입력 3 -
4 1
0
4 1 2 3 4

- 예제 출력 3 -
1

- 예제 입력 4 -
각 파티마다 오는 사람의 수 / 그 번호
4 5

진실을 아는 사람의 수 / 그 번호
1 1

각 파티마다 오는 사람의 수 / 그 번호
1 1
1 2
1 3
1 4
2 4 1

- 예제 출력 4 -
2

- 예제 입력 5 -
사람의 수 / 파티의 수
10 9
4 1 2 3 4

각 파티마다 오는 사람의 수 / 그 번호
2 1 5
2 2 6
1 7
1 8
2 7 8
1 9
1 10
2 3 10
1 4

- 예제 출력 5 -
4

- 예제 입력 6 -
8 5
3 1 2 7
2 3 4
1 5
2 5 6
2 6 8
1 8

- 예제 출력 6 -
5

- 반례 1 -
4 5
1 1
1 1
1 2
1 3
2 4 2
2 4 1

- 출력 -
1

(3) 코드

import sys

def input():
    return sys.stdin.readline().rstrip()

# fixme - 사람의 수 / 파티의 수
n, m = map(int, input().split())

# fixme - 진실을 아는 사람의 수 / 그 번호
temp1 = list(map(int, input().split()))

# 진실을 아는 사람이 있는 경우
if len(temp1[1:]) >= 1:
    set_temp = set(temp1[1:])

# 진실을 아는 사람이 없는 경우
else:
    set_temp = {}

cnt = 0

# fixme - parties 에는 각 파티와 구성원을 담아줄 것 입니다.
parties = []

for _ in range(m):

    # fixme - temp2 에는 문제에서 주어지는 파티의 구성원을 담아줍니다.
    temp2 = list(map(int, input().split()))
    parties.append(temp2)
    flag = False
    for t in temp2[1:]:
        # fixme - 파티원 중 1명이라도 set_temp 에 이미 있는 경우
        if t in set_temp:
            flag = True

        # fixme - 해당 파티에 있는 모든 사람들을 set_temp 에 추가해준다. (진실을 아는 사람이 됩니다.)
        if flag == True:
            for t2 in temp2[1:]:
                set_temp.add(t2)

for party in parties:
    flag = False

    for p in party[1:]:
        # fixme - 파티원 중 1명이라도 set_temp 에 이미 있는 경우
        if p in set_temp:
            flag = True

    # fixme - 파티원 중 아무도 진실을 알지 못하는 경우
    if flag == False:
        cnt += 1

print(cnt)

(4) 정리

이 문제에서 좀 더 설명이 추가한 부분은 시간 순서와 상관없이 이전 파티였어도 이후에 진실을 아는 구성원과 파티를 이룬적이 있는 구성원은 해당 구성원이 속했던 전에 파티에 있던 사람도 진실을 알게끔 처리해주어야 합니다. (마치 타임머신을 타고오듯?)
그래서 해당 구성원들을 모두 연결 시켜주어야 하며 이때 사용한 개념이 유니온 파인드입니다.
해당 알고리즘을 몰라 동빈나님 영상을 참고하고 구현하였습니다.

(5) 참고

유니온 파인트 개념 익히기

16928_뱀과 사다리 게임 (Python)

0. 출처

• 유형 : 그래프 탐색 (gold 5)
• 링크 : 16928번: 뱀과 사다리 게임

1. 기록

• 22/07/05 (화)

2. 풀이

(1) 아이디어, 시간복잡도, 자료구조

1. 아이디어
>> 정리 참고

2. 시간복잡도
>>

3. 자료구조
>>

(2) 예제 입력, 예제 출력

- 예제 입력 1 -
사다리의 수 / 뱀의 수
3 7
32 62
42 68
12 98
95 13
97 25
93 37
79 27
75 19
49 47
67 17

- 예제 출력 1 -
3

(1) 5를 굴려 6으로 이동한다.
(2) 6을 굴려 12로 이동한다. 이 곳은 98로 이동하는 사다리가 있기 때문에, 98로 이동한다.
(3) 2를 굴려 100으로 이동한다.

- 예제 입력 2 -
사다리의 수 / 뱀의 수
4 9
8 52
6 80
26 42
2 72
51 19
39 11
37 29
81 3
59 5
79 23
53 7
43 33
77 21

- 예제 출력 2 -
5

(1) 5를 굴려 6으로 이동하고, 사다리를 이용해 80으로 이동한다.
(2) 6을 굴려 86으로
(3) 6을 또 굴려 92로
(4) 6을 또 굴려 98로 이동하고
(5) 2를 굴려 100으로 이동한다.

- 반례 1 -
2 1
7 94
8 94
55 54

- 출력 1 -
2

(3) 코드

import sys
from collections import deque

def input():
    return sys.stdin.readline().rstrip()


# 사다리의 수, 뱀의 수
n, m = map(int, input().split())

# graph
graph = [[0 for _ in range(10)] for _ in range(10)]
visited = [[0 for _ in range(10)] for _ in range(10)]
cnt = [[0 for _ in range(10)] for _ in range(10)]

k = int(1)

for i in range(10):
    for j in range(10):
        graph[i][j] = k
        k = k + 1

# fixme -  사다리 (ladder) 딕셔너리와 뱀 (snake) 딕셔너리 정의
l = {}
s = {}

# fixme - 사다리 만들어주기
for _ in range(n):
    start, end = map(int, input().split())
    l[start] = end

# fixme - 뱀 만들어주기
for _ in range(m):
    start, end = map(int, input().split())
    s[start] = end


# fixme - 현재 위치마다 이동할 수 있는 범위를 체크해줍니다.
def can_move_range(x, y):
    if x <= 8:
        if y <= 3:
            d = [[0, 1], [0, 2], [0, 3], [0, 4], [0, 5], [0, 6]]

        elif y == 4:
            d = [[0, 1], [0, 2], [0, 3], [0, 4], [0, 5], [1, -4]]

        elif y == 5:
            d = [[0, 1], [0, 2], [0, 3], [0, 4], [1, -5], [1, -4]]

        elif y == 6:
            d = [[0, 1], [0, 2], [0, 3], [1, -6], [1, -5], [1, -4]]

        elif y == 7:
            d = [[0, 1], [0, 2], [1, -7], [1, -6], [1, -5], [1, -4]]

        elif y == 8:
            d = [[0, 1], [1, -8], [1, -7], [1, -6], [1, -5], [1, -4]]

        elif y == 9:
            d = [[1, -9], [1, -8], [1, -7], [1, -6], [1, -5], [1, -4]]

    elif x == 9:
        if y <= 3:
            d = [[0, 1], [0, 2], [0, 3], [0, 4], [0, 5], [0, 6]]

        elif y == 4:
            d = [[0, 1], [0, 2], [0, 3], [0, 4], [0, 5]]

        elif y == 5:
            d = [[0, 1], [0, 2], [0, 3], [0, 4]]

        elif y == 6:
            d = [[0, 1], [0, 2], [0, 3]]

        elif y == 7:
            d = [[0, 1], [0, 2]]

        elif y == 8:
            d = [[0, 1]]

        elif y == 9:
            d = [[0, 0]]

    return d


def roll_the_dice(sx, sy, cnt):
    q = deque([])
    q.append((sx, sy))

    while q:
        x, y = q.popleft()
        d = can_move_range(x, y)

        for i in range(len(d)):
            nx = x + d[i][0]
            ny = y + d[i][1]

            # fixme - 아직 방문하지 않았고
            if 0 <= nx <= 9 and 0 <= ny <= 9:
                if visited[nx][ny] != 1:

                    # fixme - 사다리 인 경우
                    if graph[nx][ny] in l.keys():
                        target = l[graph[nx][ny]]
                        for x1 in range(10):
                            for y1 in range(10):
                                if graph[x1][y1] == target and visited[x1][y1] != 1:
                                    q.append((x1, y1))
                                    visited[nx][ny] = 1
                                    visited[x1][y1] = 1
                                    cnt[x1][y1] = cnt[x][y] + 1

                    # fixme - 뱀인 경우
                    if graph[nx][ny] in s.keys():
                        target = s[graph[nx][ny]]
                        for x1 in range(10):
                            for y1 in range(10):
                                if graph[x1][y1] == target and visited[x1][y1] != 1:
                                    q.append((x1, y1))
                                    visited[nx][ny] = 1
                                    visited[x1][y1] = 1
                                    cnt[x1][y1] = cnt[x][y] + 1

                    # fixme - 그냥 칸만 있는 경우
                    else:
                        q.append((nx, ny))
                        visited[nx][ny] = 1
                        cnt[nx][ny] = cnt[x][y] + 1

    return cnt


cnt = roll_the_dice(0, 0, cnt)
print(cnt[9][9])

(4) 정리

'그림1'과 같은 경우 노란색 사다리를 타면 도착지점에 빨리 갈 수 있는 것처럼 보이지만 사실상 파란색 사다리를 타야 도착지점에 도달할 수 있습니다. 따라서 현재위치와 가까운 사타리를 타고 내려가는게 아닌 모든 칸에 대해서 몇번의 주사위를 굴려야 도착할 수 있는지 완전탐색해주어야 합니다.

풀이의 대부분이 1차원 배열로 구현해서 풀었습니다. 저는 처음에 2차원 배열로 구상하고 풀었기 때문에 j <= 3 열이 3이하인 경우 해당 행에서 6칸을 이어서 나아갈 수 있지만 i == 4 인 경우부터 i == 9 인 경우까지는 주사위를 굴릴시 열이 바뀌는 경우가 생깁니다. 해당 경우를 모두 고려하여 코드로 작성해주었습니다.
또한 i == 9 이면서 j >= 4 인 경우에는 더 이상 나아갈 수 있는 칸이 없어 해당 경우도 따로 elif 문으로 빼주었습니다.
해당 문제는 1차원 배열로 구현해서 푸는게 훨씬 쉽게 풀 수 있을거라 생각됩니다.

(5) 참고

16236_아기상어 (Python)

0. 출처

• 유형 : 시뮬레이션, 삼성 (gold 3)
• 링크 : 16236번: 아기상어

1. 기록

• 22/07/05 (화)

2. 풀이

(1) 아이디어, 시간복잡도, 자료구조

1. 아이디어
>> 상어의 위치를 찾고
>> 가장 가까운 거리의 물고리를 찾을때 visited 배열을 이용한다.
>> 가장 가까운 거리의 물고기를 찾는다. dfs() 이용

>> 이동 가능여부 판단 함수를 만든다                                                  ---- 종료조건 ★
>> graph 에 있는 숫자가 0 또는 size 보다 큰 경우 더 이상 먹을 수 있는 먹이가 없다.
>> graph 에 있는 숫자가 0 또는 size 작은경우 먹을 수 있는 먹이가 있다.

2. 시간복잡도
>>

3. 자료구조
>>

(2) 예제 입력, 예제 출력

- 예제 입력 1 -
3
0 0 0
0 0 0
0 9 0

- 예제 출력 1 -
0

- 예제 입력 2 -
3
0 0 1
0 0 0
0 9 0

- 예제 출력 2 -
3

- 예제 입력 3 -
4
4 3 2 1
0 0 0 0
0 0 9 0
1 2 3 4

- 예제 출력 3 -
14

- 예제 입력 4 -
6
5 4 3 2 3 4
4 3 2 3 4 5
3 2 9 5 6 6
2 1 2 3 4 5
3 2 1 6 5 4
6 6 6 6 6 6

- 예제 출력 4 -
60

- 예제 입력 5 -
6
6 0 6 0 6 1
0 0 0 0 0 2
2 3 4 5 6 6
0 0 0 0 0 2
0 2 0 0 0 0
3 9 3 0 0 1

- 예제 출력 5 -
48

- 예제 입력 6 -
6
1 1 1 1 1 1
2 2 6 2 2 3
2 2 5 2 2 3
2 2 2 4 6 3
0 0 0 0 0 6
0 0 0 0 0 9

- 예제 출력 6 -
39

- 반례 케이스 1 -
3
0 1 1
4 4 4
0 9 0

- 출력 1 -
0

- 반례 케이스 2 -
3
0 1 1
4 4 4
1 9 0

- 출력 1 -
1

- 반례 케이스 3 -
20
1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 3
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 3 9

- 출력 3 -
0

- 출력 -
0

(3) 코드

import sys
from collections import deque

def input():
    return sys.stdin.readline().rstrip()

n = int(input())

graph = [list(map(int, input().split())) for _ in range(n)]
visited = [[0 for _ in range(n)] for _ in range(n)]

size = 2
feed = 0
dist = 0
check3 = 0

# fixme - 최초 상어의 위치를 찾는다.
for i in range(n):
    for j in range(n):
        if graph[i][j] == 9:
            sx = i
            sy = j

# fixme - 더이상 먹을 수 있는 먹이가 없는 경우 종료시킨다.
def ending():
    flag = False

    for i in range(n):
        for j in range(n):
            # 자기 자신은 먹이가 아니므로 건너뛴다. 
            if graph[i][j] == 9:
                continue

            # 먹이를 찾은 경우
            elif graph[i][j] != 0 and graph[i][j] < size:
                flag = True

    return flag

# fixme - 먹이 먹을 곳을 찾자
def feeding(dist_check, feed, size):
    if len(dist_check) == 0:
        exit()
        return False

    dist_check = list(dist_check)
    dist_check.sort(key = lambda x:[x[2], x[0], x[1]])

    tx, ty, d = dist_check[0]

    feed += 1
    if feed == size:
        feed = 0
        size += 1

    return tx, ty, d, feed, size


def iterative_dfs(sx, sy, graph, dist, visited):

    global feed
    global size
    global check3

    feed = 0
    size = 2

    while ending():

        if check3 == 1:
            break

        dx = [0, -1, 0, 1]
        dy = [-1, 0, 1, 0]

        q = deque([])
        q.append((sx, sy))

        graph[sx][sy] = 0

        dist_check = deque([])

        while q:
            x, y = q.popleft()
            min_dist = 10000000

            # fixme - 사방이 막혀있거나 이동할 수 없는 경우
            check1 = 0
            check2 = 0
            for i in range(4):
                nx = x + dx[i]
                ny = y + dy[i]
                if 0 <= nx < n and 0 <= ny < n:
                    check1 += 1
                    if graph[nx][ny] > size:
                        check2 += 1

            if check1 == check2:
                check3 = 1
                break

            for i in range(4):
                nx = x + dx[i]
                ny = y + dy[i]
                if 0 <= nx < n and 0 <= ny < n:
                    # fixme - 먹이를 먹을 수 있는 경우 - 좌표와 거리만 체크해둔다.
                    if graph[nx][ny] != 0 and graph[nx][ny] < size:
                        if min_dist >= visited[x][y] + 1:
                            min_dist = visited[x][y] + 1
                            dist_check.append((nx, ny, visited[x][y] + 1))

                    # fixme - 이동만 가능한 경우
                    elif graph[nx][ny] == size or graph[nx][ny] == 0:
                        if visited[nx][ny] == 0:
                            q.append((nx, ny))
                            visited[nx][ny] += visited[x][y] + 1

                    # fixme - 먹이를 먹을 수 없는 경우
                    else:
                        visited[nx][ny] = -1

        if len(dist_check) >= 1:
            sx, sy, d, feed, size = feeding(dist_check, feed, size)
        elif len(dist_check) == 0:
            d = 0

        # fixme - 먹이를 먹을 수 있는 경로를 아무것도 못찾은 경우
        if d == 0 and dist == 0:
            return 0
        elif d == 0 and dist != 0:
            return dist

        dist += d

        # fixme - 재정비한다.
        graph[sx][sy] = 9
        visited = [[0 for _ in range(n)] for _ in range(n)]


    return dist

dist = iterative_dfs(sx, sy, graph, dist, visited)

print(dist)

(4) 정리

전에 풀어봤던 문제임에도 오래간만에 다시 푸는데 막히는 부분이 있었습니다.
참고 링크에 제가 막혔던 부분에 대해서 질문하고 답변받아 해결했습니다.

(5) 참고

질문 링크

11724_연결 요소의 개수 (Python)

0. 출처

• 유형 : 탐색 (silver 2)
• 링크 : 11724번: 연결 요소의 개수

1. 기록

• 22/07/01 (금)

2. 풀이

(1) 아이디어, 시간복잡도, 자료구조

1. 아이디어
6 5
graph = [[], [2,5]. [1,5], [4], [3,6], [2,1], [4]]
visited = [[], [True], [True], [False], [Faase], [True], [False]]

>> 위의 형태로 만들어 줄 것임

2. 시간복잡도
>>

3. 자료구조
>>

(2) 예제 입력, 예제 출력

- 예제 입력 1 -
정점의 개수 n / 간선의 개수 m
6 5
1 2
2 5
5 1
3 4
4 6

- 예제 출력 1 -
2

- 예제 입력 2 -
6 8
1 2
2 5
5 1
3 4
4 6
5 4
2 4
2 3

- 예제 출력 2 -
1

(3) 코드

import sys
from collections import deque


def input():
    return sys.stdin.readline().rstrip()


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

graph = [[] * m for _ in range(n + 1)]
visited = [False for _ in range(n + 1)]

for _ in range(m):
    a, b = map(int, input().split())
    graph[a].append(b)
    graph[b].append(a)


# fixme - flag로 노드 덩어리에 대해 탐색을 진행했는지 파악한다.
def iterative_bfs(s):
    q = deque([])
    q.append(s)
    flag = 0

    if visited[s] == False:
        visited[s] = True
        flag = 1

    while q:
        v = q.popleft()
        for w in graph[v]:
            if visited[w] == False:
                q.append(w)
                visited[w] = True

    return flag


# fixme - 노드 덩어리의 갯수를 찾아주기 위함
cnt = 0

for s in range(1, n + 1):
    flag = iterative_bfs(s)
    if flag == 1:
        cnt += 1

print(cnt)

(4) 정리

flag 로 방문하지 않는 노드 덩어리의 탐색 여부를 확인합니다.
flag 가 1인 경우 탐색을 했다는 의미이고 flag 가 0인 경우는 노드 덩어리를 찾지못했다는 의미입니다.

(5) 참고

11659__구간 합 구하기 4 (Python)

0. 출처

• 유형 : 구간 합 (silver 3)
• 링크 : 11659번: 구간 합 구하기 4

1. 기록

• 22/07/01 (금)

2. 풀이

(1) 아이디어, 시간복잡도, 자료구조

1. 아이디어
구하고자 하는 구간의 인덱스 숫자를 다음과 같이 바꿔준다.
0 2
1 3
4 4

[a0, a1, a2, a3, a4]
[5, 4, 3, 2, 1]

s0 = a0
s1 = a0 + a1
s2 = a0 + a1 + a2
s3 = a0 + a1 + a2 + a3
s4 = a0 + a1 + a2 + a3 + a4

[s0, s1, s2, s3, s4] 
[5, 9, 12, 14, 15]

위의 배열에서 규칙을 찾으면 쉽게 구할 수 있다.

2. 시간복잡도
>>

3. 자료구조
>>

(2) 예제 입력, 예제 출력

- 예제 입력 1 -
수의 개수 / n과 합을 구해야 하는 횟수
5 3
5 4 3 2 1
1 3
2 4
5 5


- 예제 출력 1 -
12
9
1

(3) 코드

import sys

def input():
    return sys.stdin.readline().rstrip()

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

nums = list(map(int,input().split()))

for i in range(1, len(nums)):
    nums[i] = nums[i] + nums[i-1]

for _ in range(m):
    s, e = map(int, input().split())
    s = s-1
    e = e-1
    if s == 0:
        print(nums[e])
    else:
        print(nums[e]-nums[s-1])

(4) 정리

(5) 참고