출처: [백준] 15501번 부당한 퍼즐

문제

현욱은 퍼즐 게임을 굉장히 좋아한다. 어느 날 현욱은 친구로부터 간단한 플래시 퍼즐 게임을 하나 추천 받았는데, 이 퍼즐 게임은 다음과 같은 규칙을 갖고 있다.

1. 플레이어는 1 ~ n 까지 숫자가 한 번씩만 나타나는 수열을 하나 가지고 시작한다.
2. 또 다른 1 ~ n 까지 숫자가 한 번씩만 나타나는 수열이 주어졌을 때, 처음 수열을 적절히 변형해서 처음 받은 수열을 이 수열과 동일한 수열로 만들어야 한다.
3. 이때, 플레이어가 수열에 대해서 할 수 있는 동작은 다음 두 가지가 있다. 동작은 몇 번이라도 수행할 수 있다.
   • 뒤집기 : 현재 수열을 거꾸로 뒤집는다. ex) 1 2 3 4 5 -> 5 4 3 2 1
   • 밀기 : 현재 수열을 왼쪽 혹은 오른쪽으로 한 칸 민다. ex) 1 2 3 4 5 -> 5 1 2 3 4

퍼즐을 풀던 현욱은 분명히 엄청 쉬운 규칙인데도 불구하고 문제가 안 풀려서, 한참을 고민하다가 다시 잘 비교해보니 정답 수열을 주어진 동작만으로는 절대 만들 수가 없는 문제였다!

화가 난 현욱은 퍼즐 제작자에게 따지기 위해 주어진 문제가 올바른 문제인지 아닌지 확인하는 프로그램을 만들기로 결심했다. 현욱을 도와 괘씸한 퍼즐 제작자를 응징해주자.

입력

첫째 줄에 n이 주어진다(1 ≤ n ≤ 1,000,000).

둘째 줄에 1에서 n까지의 수가 한 번만 나타나는 수열이 순서대로 주어진다.

셋째 줄에 주어진 두 연산을 수행해서 구성할 수 있는지 확인할 1에서 n까지 수가 한 번만 나타나는 수열이 순서대로 주어진다.

출력

주어진 두 가지 연산만을 가지고 처음 수열을 결과 수열로 만들 수 있다면 good puzzle, 아니면 bad puzzle을 출력한다.

예제 입력 1

1
2
3

5
1 2 3 4 5
4 3 2 1 5

예제 출력 1

1

good puzzle

예제 입력 2

1
2
3

5
1 2 3 4 5
1 2 4 3 5

예제 출력 2

1

bad puzzle

출처

• Contest > 소프트콘 > 제1회 소프트콘 A번
  • 문제를 만든 사람: jwvg0425
  • 잘못된 데이터를 찾은 사람: tncks0121

알고리즘 분류

• 구현
• 자료 구조
• 덱

소스코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

import sys

input = sys.stdin.readline

N = int(input())
sequence = list(map(int, input().split()))
compare = list(map(int, input().split()))

# 순방향
first_idx = compare.index(sequence[0])  # 기준점
new_list1 = compare[first_idx:] + compare[:first_idx]

# 역방향
compare = compare[::-1]
first_idx = compare.index(sequence[0])  # 기준점
new_list2 = compare[first_idx:] + compare[:first_idx]

# 둘 중 하나 맞으면 good puzzle
if sequence == new_list1 or sequence == new_list2:
    print("good puzzle")
else:
    print("bad puzzle")

소스코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49

import sys

input = sys.stdin.readline

N = int(input())
sequence = list(map(int, input().split()))
compare = list(map(int, input().split()))

new_list1 = []
new_list2 = []

first_idx = compare.index(sequence[0])  # 기준점

# 순방향인 경우
start = first_idx - N
end = first_idx

for i in range(start, end):
    new_list1.append(compare[i])

# 역방향인 경우
start = first_idx
end = first_idx - N

for i in range(start, end, -1):
    new_list2.append(compare[i])

# 둘 중 하나 맞으면 good puzzle
if sequence == new_list1 or sequence == new_list2:
    print("good puzzle")
else:
    print("bad puzzle")

'''
5
1 2 3 4 5
3 4 5 1 2

6
1 2 3 4 5 6
3 2 1 6 5 4
4 5 6 1 2 3

11
11 10 9 8 7 6 5 4 3 2 1
1 2 3 4 5 6 7 8 9 10 11

'''

출처: [2019 카카오 개발자 겨울 인턴십] 크레인 인형뽑기 게임

문제

게임개발자인 “죠르디”는 크레인 인형뽑기 기계를 모바일 게임으로 만들려고 합니다.
“죠르디”는 게임의 재미를 높이기 위해 화면 구성과 규칙을 다음과 같이 게임 로직에 반영하려고 합니다.

게임 화면은 “1 x 1” 크기의 칸들로 이루어진 “N x N” 크기의 정사각 격자이며 위쪽에는 크레인이 있고 오른쪽에는 바구니가 있습니다. (위 그림은 “5 x 5” 크기의 예시입니다). 각 격자 칸에는 다양한 인형이 들어 있으며 인형이 없는 칸은 빈칸입니다. 모든 인형은 “1 x 1” 크기의 격자 한 칸을 차지하며 격자의 가장 아래 칸부터 차곡차곡 쌓여 있습니다. 게임 사용자는 크레인을 좌우로 움직여서 멈춘 위치에서 가장 위에 있는 인형을 집어 올릴 수 있습니다. 집어 올린 인형은 바구니에 쌓이게 되는 데, 이때 바구니의 가장 아래 칸부터 인형이 순서대로 쌓이게 됩니다. 다음 그림은 [1번, 5번, 3번] 위치에서 순서대로 인형을 집어 올려 바구니에 담은 모습입니다.

만약 같은 모양의 인형 두 개가 바구니에 연속해서 쌓이게 되면 두 인형은 터뜨려지면서 바구니에서 사라지게 됩니다. 위 상태에서 이어서 [5번] 위치에서 인형을 집어 바구니에 쌓으면 같은 모양 인형 두 개가 없어집니다.

크레인 작동 시 인형이 집어지지 않는 경우는 없으나 만약 인형이 없는 곳에서 크레인을 작동시키는 경우에는 아무런 일도 일어나지 않습니다. 또한 바구니는 모든 인형이 들어갈 수 있을 만큼 충분히 크다고 가정합니다. (그림에서는 화면표시 제약으로 5칸만으로 표현하였음)

게임 화면의 격자의 상태가 담긴 2차원 배열 board와 인형을 집기 위해 크레인을 작동시킨 위치가 담긴 배열 moves가 매개변수로 주어질 때, 크레인을 모두 작동시킨 후 터트려져 사라진 인형의 개수를 return 하도록 solution 함수를 완성해주세요.

제한

• board 배열은 2차원 배열로 크기는 “5 x 5” 이상 “30 x 30” 이하입니다.
• board의 각 칸에는 0 이상 100 이하인 정수가 담겨있습니다.
  • 0은 빈 칸을 나타냅니다.
  • 1 ~ 100의 각 숫자는 각기 다른 인형의 모양을 의미하며 같은 숫자는 같은 모양의 인형을 나타냅니다.
• moves 배열의 크기는 1 이상 1,000 이하입니다.
• moves 배열 각 원소들의 값은 1 이상이며 board 배열의 가로 크기 이하인 자연수입니다.

입출력

입출력 예 1

인형의 처음 상태는 문제에 주어진 예시와 같습니다. 크레인이 [1, 5, 3, 5, 1, 2, 1, 4] 번 위치에서 차례대로 인형을 집어서 바구니에 옮겨 담은 후, 상태는 아래 그림과 같으며 바구니에 담는 과정에서 터트려져 사라진 인형은 4개 입니다.

풀이

-

소스코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

def solution(board, moves):
    N = len(board)  # 보드의 길이
    answer = 0
    basket = []
    for move in moves:
        for i in range(N):
            if board[i][move - 1] > 0:  # Move별로 맨 위에 있는 인형을 바구니에 넣고, 빈칸으로 전환
                basket.append(board[i][move - 1])
                board[i][move - 1] = 0
                break

        if len(basket) > 1:  # 바구니가 2개이상일 때부터
            if basket[-1] == basket[-2]:  # 가장 최신에 들어온 것과 그 전에 들어온 것이 같으면 두개 삭제
                basket.pop()
                basket.pop()
                answer += 2

    return answer


print(solution([[0, 0, 0, 0, 0], [0, 0, 1, 0, 3], [0, 2, 5, 0, 1], [4, 2, 4, 4, 2], [3, 5, 1, 3, 1]],
               [1, 5, 3, 5, 1, 2, 1, 4]))

1. NHN페이코, 오프라인 결제 인프라 확대…’페이코 단말기’ 보급한다

NHN페이코, 오프라인 결제 인프라 확대…’페이코 단말기’ 보급한다

NHN페이코는 자체 개발한 ‘페이코(PAYCO) 결제 단말기’의 보급을 통해 오프라인 결제 인프라(기반시설) 확대에 나선다고 21일 밝혔다.

• 페이코 결제 단말기(C2100)는 서명 패드와 각종 결제 리더기를 일체화한 올인원 단말로 IC, 마그네틱, NFC, QR·바코드, 비자(VISA) 콘택트리스(비접촉식) 결제를 모두 지원하고 전후면에 고해상도 LCD와 IC카드 슬롯을 각각 탑재해 가맹점주, 고객의 양방향 결제가 가능한 것이 특징이다.

신종 코로나바이러스 감염증(코로나19)로 수요가 확대된 QR·바코드 결제는 별도 리더기 없이 내장 카메라를 통해 지원하고 카드를 긁거나 삽입하지 않고 단말기에 대는 것만으로 결제가 이뤄지는 비자 콘택트리스 결제도 가능하다.

• 비자 콘택트리스는 EMV 규격 기반의 IC칩 보안 기술 및 비자 토큰 서비스(VTS·Visa Token Service)를 적용해 편의성과 보안성을 높인 결제 기술이다.

NHN페이코는 동반성장위원회 지원사업을 시작으로 향후 주요 VAN사와 협력해 단말기 보급을 본격적으로 확대해 나갈 계획으로 다양한 업종에서 페이코 결제 인프라를 지속적으로 확대하기로 했으며, 기존 단말기가 QR·바코드 결제를 지원하지 않아 페이코 결제 도입이 어려웠던 매장이 가맹점으로 유입되는 효과가 있을 것으로 기대된다.

2. 네이버, 매출 절반이 ‘신사업’ e커머스·핀테크 성장 힘준다

네이버, 매출 절반이 ‘신사업’ e커머스·핀테크 성장 힘준다

올 2·4분기 매출 1조6635억원 중 절반 이상을 △e커머스(3653억원) △핀테크(2326억원) △콘텐츠(1448억원) △클라우드(949억원)에서 벌어들인 것으로 이는 검색·디스플레이 광고가 핵심인 서치플랫폼 매출(8260억원)을 넘어선 규모다.

스마트스토어 당일배송-신용대출

네이버 스마트스토어 46만 판매자들 대상으로 ‘네이버 풀필먼트 얼라이언스(NFA)’를 출시하고, CJ대한통운과 전국 당일배송 풀필먼트 체계를 구축하기로 했으며, 핀테크 부문 관련 네이버파이낸셜 신용평가모델을 더욱 정교화해 더 많은 네이버페이 이용자들이 다양한 혜택을 누릴 수 있도록 할 것이라고 했으며, 네이버는 사업자 전용 신용대출 등 기업간거래(B2B) 분야 핀테크 역량도 강화한다.

미래먹거리 ‘제페토’, 매출 70% 늘어

메타버스 플랫폼 ‘제페토’ 관련, “전 세계 이용자가 2억명에 달하는 제페토는 최근 삼성전자, 현대차, 구찌, 디올 등의 광고 확대로 매출이 전년 대비 70% 이상 성장했다”면서 “이용자가 직접 아바타 아이템을 만들 수 있는 ‘제페토 스튜디오’에서 게임까지 제작할 수 있는 기능을 연내 출시할 계획”이라고 밝혔다.

3. “야놀자가 우리몫 다 뺏는다” 모텔 사장님들 뿔났다

“야놀자가 우리몫 다 뺏는다” 모텔 사장님들 뿔났다

여행 플랫폼 ‘야놀자’의 광고 수수료 체계가 ‘지역 톱’ ‘지역 인기’ ‘지역 리스트’ 등 성격이 겹치는 카테고리를 여러 개 만들어 각각 광고료를 책정하는 정책 때문에 숙박업주들에게 과도한 부담을 지우고 있다는 불만이 커지고 있다.

22일 헤럴드경제 취재를 종합하면, 숙박업소 단체 대한숙박업중앙회의 일부 지회는 야놀자의 광고 및 수수료 체계의 불공정함을 지적하기 위한 단체 행동을 준비하고 있고 일부 업주는 공정거래위원회 국민신문고에 민원을 접수하고 야놀자 측 소명을 기다리고 있는 상황이다.

4. “콘텐츠 대전 시작됐다”…네이버 vs 카카오, 주도권 싸움 치열

“콘텐츠 대전 시작됐다”…네이버 vs 카카오, 주도권 싸움 치열

네이버는 왓패드 웹툰 스튜디오를 앞세워 글로벌 창작자 약 570만명이 만든 10억개 이상의 원천 콘텐츠를 바탕으로 드라마·영화·애니메이션 등 다양한 영상화 프로젝트를 선보인다는 구상으로 특히 1000억원 규모의 펀드를 조성하고 남미·유럽·동남아시아 등 글로벌 영상화 사업에서 두각을 나타낼 방침이다.

다음웹툰컴퍼니도 8월부터 ‘카카오웹툰 스튜디오’로 거듭나며, 기존 다음웹툰은 물론 ‘이태원 클라쓰’ ‘나 혼자만 레벨업’ ‘사내맞선’ ‘나빌레라’ ‘승리호’ ‘경이로운 소문’ ‘취향저격 그녀’ 등 카카오페이지의 콘텐츠 IP도 통합해 제공한다.

5. 저커버그 “메타버스는 모바일 인터넷의 진정한 후계자”

저커버그 “메타버스는 모바일 인터넷의 진정한 후계자”

마크 저커버그는 22일(현지시각) 미 IT 전문매체인 더버지와 인터뷰를 갖고 “메타버스는 매우 거대한 주제”라며 “메타버스는 모바일 인터넷의 후계자”라고 했으며, “많은 사람들이 메타버스를 단순히 게임의 한 부분이 될 것이라고 생각하지만, 그것을 뛰어넘을 것”이라며 “나는 메타버스가 기술 산업의 다음 장을 여는 큰 부분이 될 것이라고 본다”고 했다.

저커버그가 생각하는 메타버스는 현재 테크 기업들이 내놓은 메타버스 플랫폼과는 다른 형태로 현재 게임 로블록스나 네이버의 제페토 등 메타버스를 기반으로 한 플랫폼이 존재하지만 그는 “메타버스는 공공장소 같은 온라인 공간이 돼야 한다”며 “사람들이 공동으로 상호작용하는 모든 것이 메타버스여야 한다. 각 회사마다의 자체 메타버스는 없어야 한다”고 주장했다.

출처: [백준] 2346번 풍선 터뜨리기

문제

1번부터 N번까지 N개의 풍선이 원형으로 놓여 있고. i번 풍선의 오른쪽에는 i+1번 풍선이 있고, 왼쪽에는 i-1번 풍선이 있다. 단, 1번 풍선의 왼쪽에 N번 풍선이 있고, N번 풍선의 오른쪽에 1번 풍선이 있다. 각 풍선 안에는 종이가 하나 들어있고, 종이에는 -N보다 크거나 같고, N보다 작거나 같은 정수가 하나 적혀있다. 이 풍선들을 다음과 같은 규칙으로 터뜨린다.

우선, 제일 처음에는 1번 풍선을 터뜨린다. 다음에는 풍선 안에 있는 종이를 꺼내어 그 종이에 적혀있는 값만큼 이동하여 다음 풍선을 터뜨린다. 양수가 적혀 있을 경우에는 오른쪽으로, 음수가 적혀 있을 때는 왼쪽으로 이동한다. 이동할 때에는 이미 터진 풍선은 빼고 이동한다.

예를 들어 다섯 개의 풍선 안에 차례로 3, 2, 1, -3, -1이 적혀 있었다고 하자. 이 경우 3이 적혀 있는 1번 풍선, -3이 적혀 있는 4번 풍선, -1이 적혀 있는 5번 풍선, 1이 적혀 있는 3번 풍선, 2가 적혀 있는 2번 풍선의 순서대로 터지게 된다.

입력

첫째 줄에 자연수 N(1 ≤ N ≤ 1,000)이 주어진다. 다음 줄에는 차례로 각 풍선 안의 종이에 적혀 있는 수가 주어진다. 종이에 0은 적혀있지 않다.

출력

첫째 줄에 터진 풍선의 번호를 차례로 나열한다.

예제 입력 1

1
2

5
3 2 1 -3 -1

예제 출력 1

1

1 4 5 3 2

출처

• 잘못된 데이터를 찾은 사람: tncks0121

알고리즘 분류

• 자료 구조
• 덱

소스코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

import sys
from collections import deque

input = sys.stdin.readline

N = int(input())

balloons = [x for x in range(1, N + 1)]
papers = list(map(int, input().split()))

bomb = deque()
for balloon, paper in zip(balloons, papers):
    bomb.append([balloon, paper])

while bomb:
    balloon, paper = bomb.popleft()
    print(balloon, end=" ")
    if bomb:
        if paper > 0:
            for _ in range(paper - 1):
                bomb.append(bomb.popleft())
        else:
            for _ in range(-paper):
                bomb.appendleft(bomb.pop())

출처: [백준] 20301번 반전 요세푸스

문제

요세푸스 문제는 다음과 같다.

1번 사람 오른쪽에는 2번 사람이 앉아 있고, 2번 사람 오른쪽에는 3번 사람이 앉아 있고, 계속하여 같은 방식으로 N명의 사람들이 원을 이루며 앉아 있다. N번 사람 오른쪽에는 1번 사람이 앉아 있다. 이제 K(≤N)번 사람을 우선 제거하고, 이후 직전 제거된 사람의 오른쪽의 K번째 사람을 계속 제거해 나간다. 모든 사람이 제거되었을 때, 제거된 사람의 순서는 어떻게 될까?

이 문제의 답을 (N, K)–요세푸스 순열이라고 하며, (7, 3)–요세푸스 순열은 ⟨3,6,2,7,5,1,4⟩가 된다.

하지만 한 방향으로만 계속 돌아가는 건 너무 지루하다. 따라서 요세푸스 문제에 재미를 더하기 위해 M명의 사람이 제거될 때마다 원을 돌리는 방향을 계속해서 바꾸려고 한다. 이렇게 정의된 새로운 문제의 답을 (N, K, M)–반전 요세푸스 순열이라고 하며, (7, 3, 4)–반전 요세푸스 순열은 ⟨3,6,2,7,1,5,4⟩가 된다.

N, K, M이 주어질 때, (N, K, M)–반전 요세푸스 순열을 계산해 보자.

입력

첫째 줄에 정수 N, K, M이 주어진다. (1≤N≤5 000, 1≤K,M≤N)

출력

(N, K, M)–반전 요세푸스 순열을 이루는 수들을 한 줄에 하나씩 순서대로 출력한다.

예제 입력 1

1

7 3 4

예제 출력 1

1
2
3
4
5
6
7

3
6
2
7
1
5
4

출처

• University > 서강대학교 > 2020 Sogang Programming Contest (Master) C번
  • 문제를 검수한 사람: gumgood, jhnah917, pichulia, QuqqU, rhs0266, shiftpsh, sogangcse, woonikim
  • 문제를 만든 사람: sbrus_1213

알고리즘 분류

• 구현
• 자료 구조
• 시뮬레이션
• 덱

소스코드 (최초)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

import sys
from collections import deque

input = sys.stdin.readline

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

people = deque(x for x in range(1, N + 1))

count = 0
direction = 1
while people:
    if direction:  # 오른쪽
        for _ in range(K - 1):
            people.append(people[0])
            people.popleft()
    elif not direction:  # 왼쪽
        for _ in range(K):
            people.appendleft(people.pop())

    print(people.popleft())
    count += 1
    if count == M:
        count = 0
        direction = not direction

소스코드 (수정)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

import sys
from collections import deque

input = sys.stdin.readline

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

people = deque(x for x in range(1, N + 1))

while people:
    for _ in range(M):
        people.rotate(-(K - 1))  # 오른쪽
        if not people:
            break
        print(people.popleft())

    for _ in range(M):
        people.rotate(K)  # 왼쪽
        if not people:
            break
        print(people.popleft())

트랜잭션

일이 처리되기 위한 가장 작은 단위

트랜잭션들이 모여 하나의 트랜잭션을 이룰 수 있고, 서비스가 된다.

→ 하나의 작업을 수행하기 위해 필요한 데이터베이스의 연산들을 모아놓은 것

DB 격리수준

• 오라클 기본 격리수준 (Read Committed)

READ COMMIT

T1: 트랜잭션 시작 → Update문 (테이블 내의 정보 수정 - 222.Busan -> 222.Jeju)

T2: T1이  Update하는 동안 그 부분을 Select를 하면 T2는 수정되기 전의 정보를 Select한다.
222.Busan (Undo영역 수정 전)

-------------------------

T1: Update한 것을 Commit  (Undo영역이 수정 됨)

T2: T1이 commit하기 전에는 수정하기 전 정보를 Select하게 되고, Commit 이후에 Select하면 수정 된 정보를 볼 수 있다.
222.Jeju (Undo영역 수정 됨)

READ COMMIT 정합성 문제

T2는 트랜잭션을 실행하지않고, Select만 한다.
Busan이 나오다가 갑자기 Jeju가 나와버렸다.

만약에, T2입장에서 T1과 비슷한 시기에 트랜잭션을 실행하고, Select를 계속 한다.
그리고 마지막에 그 Select한 결과들을 모아 Insert연산을 하고 Commit을 한다면...

중간에 데이터가 변경되어 결과가 예상과 달라져버리면 문제가 된다.

이런 문제는 금전적인 처리에서 주로 발생한다.

총 3번 각각 만원씩 Select를 할려고 했는데, 마지막 Select에서 2만원이 나오면,

예상은 3만원 Insert를 하려고 했는데, 4만원이 Insert - Commit이 되어버린다.

→ 정합성이 깨진다 = 부정합, 똑같은 Select에서 다른 것이 나왔을 때

➡ PHANTOM READ(데이터가 보였다 안보였다), 아에 결과가 없을 때

이를 해결하기 위해 REPEATABLE READ방식을 사용해야한다.

• MySQL 기본 격리수준 (Repeatable Read 이상) –> 부정합 발생 X

transaction Id부여

T2가 먼저 Transaction 시작(Id=10)
222를 Select하면 Busan

T1이 Transaction 시작 (Id=12)
222.Busan --> Jeju upate
commit

하지만 T2입장에서는 아직 자신의 Transaction이 종료되지 않았기 때문에, 항상 동일한 결과를 보여준다.
그래서 시작했을 때는 Busan이 나왔으므로, 끝까지 Busan이 나온다.

자신의 Transaction Id보다 작은 Undo로그를 보고 select한다.

Spring에서는

CRUD

C(Insert), U(Update), D(Delete) --> commit이 필요하므로
@Transactional 붙인다.

R(Select)는 보통 붙이지 않는데, 정합성을 위해 꼭 @Transactional을 붙여서
트랜잭션을 타게 해준다.

출처: [백준] 5464번 주차장

문제

시내 주차장은 1부터 N까지 번호가 매겨진 N개의 주차 공간을 가지고 있다. 이 주차장은 매일 아침 모든 주차 공간이 비어 있는 상태에서 영업을 시작하며, 하룻동안 다음과 같은 방식으로 운영된다. 차가 주차장에 도착하면, 주차장 관리인이 비어있는 주차 공간이 있는지를 검사한다. 만일 비어있는 공간이 없으면, 차량을 빈 공간이 생길 때까지 입구에서 기다리게 한다. 만일 빈 주차 공간이 하나만 있거나 또는 빈 주차 공간이 없다가 한 대의 차량이 주차장을 떠나면 곧바로 그 장소에 주차를 하게 한다. 만일 빈 주차 공간이 여러 곳이 있으면, 그 중 번호가 가장 작은 주차 공간에 주차하도록 한다. 만일 주차장에 여러 대의 차량이 도착하면, 일단 도착한 순서대로 입구의 대기장소에서 줄을 서서 기다려야 한다. 대기장소는 큐(queue)와 같이, 먼저 대기한 차량부터 주차한다.

주차료는 주차한 시간이 아닌 차량의 무게에 비례하는 방식으로 책정된다. 주차료는 차랑의 무게에다 주차 공간마다 따로 책정된 단위 무게당 요금을 곱한 가격이다.

주차장 관리원은 오늘 M대의 차량이 주차장을 이용할 것이라는 것을 알고 있다. 또한, 차량들이 들어오고 나가는 순서도 알고 있다.

주차 공간별 요금과 차량들의 무게와 출입 순서가 주어질 때, 오늘 하룻동안 주차장이 벌어들일 총 수입을 계산하는 프로그램을 작성하라.

입력

반드시 표준 입력으로부터 다음의 데이터를 읽어야 한다.

• 첫 번째 줄에는 정수 N과 M이 빈칸을 사이에 두고 주어진다.

• 그 다음 N개의 줄에는 주차 공간들의 단위 무게당 요금을 나타내는 정수들이 주어진다. 그 중 s번째 줄에는 주차 공간 s의 단위 무게당 요금 Rs가 들어있다.

• 그 다음 M개의 줄에는 차량들의 무게를 나타내는 정수들이 주어진다. 차량들은 1 부터 M 까지 번호로 구분되고, 이 번호는 출입 순서와는 상관없다. 이 M개의 줄 중 k번째 줄에는 차량 k의 무게를 나타내는 정수 Wk가 들어있다.

• 그 다음 2*M 개의 줄에는 차량들의 주차장 출입 순서를 나타내는 정수들이 한 줄에 하나씩 주어진다. 양의 정수 i는 차량 i가 주차장에 들어오는 것을 의미하고, 음의 정수 -i는 차량 i가 주차장에서 나가는 것을 의미한다. 주차장에 들어오지 않은 차량이 주차장에서 나가는 경우는 없다. 1 번부터 M 번까지 모든 차량은 정확하게 한 번씩 주차장에 들어오고, 한 번씩 주차장에서 나간다. 또한 입구에서 대기 중인 차량이 주차를 하지 못하고 나가는 경우는 없다.

• 1 ≤ N ≤ 100 주차 공간의 수

• 1 ≤ M ≤ 2,000 차량의 수

• 1 ≤ Rs ≤ 100 주차 공간 s의 단위 무게당 요금

• 1 ≤ Wk ≤ 10,000 차량 k의 무게

출력

출력은 반드시 표준 출력으로 하여야 하며, 하나의 줄에 한 개의 정수를 출력한다. 이 정수는 오늘 하룻동안 주차장이 벌어들인 총 수입이다.

예제 입력 1

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

3 4
2
3
5
200
100
300
800
3
2
-3
1
4
-4
-2
-1

예제 출력 1

1

5300

예제 입력 2

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

2 4
5
2
100
500
1000
2000
3
1
2
4
-1
-3
-2
-4

예제 출력 2

1

16200

힌트

• 차량 3이 주차 공간 1에 주차한다. 주차료는 300 * 2 = 600 이다.
• 차량 2가 주차 공간 2에 주차한다. 주차료는 100 * 3 = 300 이다.
• 차량 1이 차랑 3이 떠난 주차공간 1에 주차한다. 주차료는 200 * 2 = 400 이다.
• 차량 4가 마지막 남은 주차 공간 3에 주차한다. 주차료는 800 * 5 = 4,000 이다.

출처

• Olympiad > International Olympiad in Informatics > IOI 2009 5번

알고리즘 분류

• 구현
• 자료 구조
• 시뮬레이션
• 큐

소스코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48

import sys
from collections import deque
import heapq

input = sys.stdin.readline

N, M = map(int, input().split())
# N~: 단위 무게당 요금을 나타내는 정수, N: 주차공간 1,2,3....
# M~: 차량들의 무게


fees = [int(input()) for _ in range(N)]
weights = [int(input()) for _ in range(M)]

parking = {}
for i in range(M + 1):
    parking[i + 1] = []

waiting = deque()
total_fee = 0

parking_idx = [x for x in range(N)]
heapq.heapify(parking_idx)

for i in range(2 * M):
    if parking_idx and waiting:
        car_num = waiting.popleft()
        idx = heapq.heappop(parking_idx)
        parking[car_num] = [idx, fees[idx], weights[car_num - 1]]

    car_num = int(input())
    if car_num > 0:  # 입차
        if parking_idx:
            idx = heapq.heappop(parking_idx)
            parking[car_num] = [idx, fees[idx], weights[car_num - 1]]
        else:
            waiting.append(car_num)

    else:
        car_num = abs(car_num)
        idx = parking[car_num][0]
        fee = parking[car_num][1]
        weight = parking[car_num][2]
        total_fee += fee * weight
        heapq.heappush(parking_idx, idx)

print(total_fee)

출처: [백준] 3190번 뱀

문제

‘Dummy’ 라는 도스게임이 있다. 이 게임에는 뱀이 나와서 기어다니는데, 사과를 먹으면 뱀 길이가 늘어난다. 뱀이 이리저리 기어다니다가 벽 또는 자기자신의 몸과 부딪히면 게임이 끝난다.

게임은 NxN 정사각 보드위에서 진행되고, 몇몇 칸에는 사과가 놓여져 있다. 보드의 상하좌우 끝에 벽이 있다. 게임이 시작할때 뱀은 맨위 맨좌측에 위치하고 뱀의 길이는 1 이다. 뱀은 처음에 오른쪽을 향한다.

뱀은 매 초마다 이동을 하는데 다음과 같은 규칙을 따른다.

• 먼저 뱀은 몸길이를 늘려 머리를 다음칸에 위치시킨다.
• 만약 이동한 칸에 사과가 있다면, 그 칸에 있던 사과가 없어지고 꼬리는 움직이지 않는다.
• 만약 이동한 칸에 사과가 없다면, 몸길이를 줄여서 꼬리가 위치한 칸을 비워준다. 즉, 몸길이는 변하지 않는다.

사과의 위치와 뱀의 이동경로가 주어질 때 이 게임이 몇 초에 끝나는지 계산하라.

입력

첫째 줄에 보드의 크기 N이 주어진다. (2 ≤ N ≤ 100) 다음 줄에 사과의 개수 K가 주어진다. (0 ≤ K ≤ 100)

다음 K개의 줄에는 사과의 위치가 주어지는데, 첫 번째 정수는 행, 두 번째 정수는 열 위치를 의미한다. 사과의 위치는 모두 다르며, 맨 위 맨 좌측 (1행 1열) 에는 사과가 없다.

다음 줄에는 뱀의 방향 변환 횟수 L 이 주어진다. (1 ≤ L ≤ 100)

다음 L개의 줄에는 뱀의 방향 변환 정보가 주어지는데, 정수 X와 문자 C로 이루어져 있으며. 게임 시작 시간으로부터 X초가 끝난 뒤에 왼쪽(C가 ‘L’) 또는 오른쪽(C가 ‘D’)로 90도 방향을 회전시킨다는 뜻이다. X는 10,000 이하의 양의 정수이며, 방향 전환 정보는 X가 증가하는 순으로 주어진다.

출력

첫째 줄에 게임이 몇 초에 끝나는지 출력한다.

예제 입력 1

1
2
3
4
5
6
7
8
9

6
3
3 4
2 5
5 3
3
3 D
15 L
17 D

예제 출력 1

1

9

예제 입력 2

1
2
3
4
5
6
7
8
9
10
11

10
4
1 2
1 3
1 4
1 5
4
8 D
10 D
11 D
13 L

예제 출력 2

1

21

예제 입력 3

1
2
3
4
5
6
7
8
9
10
11
12

10
5
1 5
1 3
1 2
1 6
1 7
4
8 D
10 D
11 D
13 L

예제 출력 3

1

13

출처

• Olympiad > Croatian Highschool Competitions in Informatics > 2005 > National Competition #1 - Juniors 2번
  • 문제의 오타를 찾은 사람: dlwocks31, hax3
  • 빠진 조건을 찾은 사람: doju, joonas, zhsks311
  • 문제를 번역한 사람: sehun

알고리즘 분류

• 구현
• 자료 구조
• 시뮬레이션
• 덱
• 큐

소스코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58

import sys
from collections import deque

input = sys.stdin.readline

N = int(input())
board = [[0] * (N) for _ in range(N)]  # NxN 보드 생성

K = int(input())  # 사과 개수
for _ in range(K):  # 사과 위치 지정 0:없음, 1:있음
    y, x = map(int, input().split())
    board[y - 1][x - 1] = 2

# 우, 하, 좌, 상 // 시계방향
dx = [1, 0, -1, 0]
dy = [0, 1, 0, -1]

L = int(input())  # 방향 전환 횟수
times = deque()
directions = deque()
for _ in range(L):
    time, dire = input().rstrip().split()
    times.append(int(time))
    directions.append(dire)

count = 0
direction = 0
nx, ny = 0, 0  # 초기위치
visited = deque([[ny, nx]])

while True:
    count += 1
    # 칸 이동
    nx += dx[direction]
    ny += dy[direction]
    if 0 <= nx < N and 0 <= ny < N and board[ny][nx] != 1:  # 보드 체크
        # 사과가 있으면 그냥 추가, 없으면 꼬리 제거하고 추가
        if board[ny][nx] == 0:  # 사과가 없으면
            temp_y, temp_x = visited.popleft()
            board[temp_y][temp_x] = 0  # 꼬리 줄어듬
        board[ny][nx] = 1
        visited.append([ny, nx])

    else:
        print(count)
        exit(0)

    if count in times:
        dire = directions.popleft()
        if dire == 'D':
            direction += 1
            if direction > 3:
                direction = 0
        else:
            direction -= 1
            if direction < 0:
                direction = 3

회원가입 시 Ajax를 사용하는 이유

요청에 대한 응답을 HTML이 아닌 Data(JSON)로 받기 위해서

클라이언트 (브라우저)는 서버에 요청을 하고, 서버는 클라이언트에게 응답한다.

클라이언트가 서버에게 화면을 요청하면, 서버가 .html로 응답하여 브라우저는 그 html 파일을 읽는다.

메인화면에서 회원가입 수행을 요청하면, 서버는 DB에 회원가입을 수행하고 완료하면 다시 메인화면으로 돌아올 것이고, 결국 html로 응답해줘야하는데…

그 클라이언트가 꼭 브라우저인 것은 아니다. 앱일 경우, html를 반환해주면 이해하지 못한다.

그래서 Data만 반환해주고, 화면을 앱안에서 자체적으로 띄운다.

➡ 브라우저를 위한 서버, 앱을 위한 서버 두개를 따로 만들어야하지만, 차라리, Data를 반환해주는 서버 하나를 만들면 되지 않을까…

서버는 브라우저/앱에게 정상이라는 Data를 반환해준다.

브라우저는 다시 서버에서 request를 보내 html파일을 반환하게 한다.

앱은 자체적으로 화면이동을 한다.

그래서 Data를 Ajax를 사용한다.

비동기 통신을 하기 위해서

보통 일을 수행할 때 1, 2, 3, 4, 5, … 순서대로 실행-종료,실행-종료… 절차적으로 수행한다.

그리고 1: 화면에 그림(내장), 2: 연산, 3: 그림 다운로드(외장), 4: 그림을 그림, 5: 화면에 그림(내장) 이라는 상황일 때, 1,2번이 수행되고, 3번 다운로드하는 10초 pending동안 앱은 멈춰있을 것이다.. 10초 다운로드가 끝나면 4,5번이 수행된다. 이 결과 UX가 나빠진다. 프로그램을 사용하고 싶지 않을 듯

비동기 통신은 절차적으로 일을 수행하는데, 일의 순서에 상관없이 수행한다.

1,2 수행하고, 3번을 비동기 처리하고 4번은 3번이 수행되어야 동작할 수 있기때문에, 5번을 수행하고 있는다.

3번 다운로드하는 동안 4번은 3번을 기다리고, 5번 그림 그리기 수행

• 5번 수행중 3번이 완료되면 4번으로 콜백한다. 4번이 완료되면 5번 멈췄던 지점부터 다시 시작한다.
• 5번이 끝난 후에 3번이 완료되면 4번으로 돌아간다.

➡ 비동기라고 한다.

git status나 commit 할 때, 한글이름을 가지는 파일일 경우에 \352\271\200\ 이런식으로 파일명이 깨지는 경우가 있다.

위 사진처럼 한글이 깨진다면, 아래 코드 한줄을 입력한다.

1

git config --global core.quotepath false

다시 확인해보면, 아래 사진과 같이 파일명이 잘 나오는 것을 볼 수 잇다.