출처: [백준] 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())

출처: [백준] 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)

트랜잭션

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

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

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

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을 붙여서
트랜잭션을 타게 해준다.

출처: [백준] 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

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

1. 네이버-CJ, 풀필먼트 센터 확충…’당일배송·새벽배송’ 뛰어든다(종합)

네이버-CJ, 풀필먼트 센터 확충…’당일배송·새벽배송’ 뛰어든다(종합)

네이버는 CJ대한통운과 함께 네이버 스마트스토어 판매자를 중심으로 전국 빠른 배송 서비스를 구축한다고 21일 밝혔고, 기존 네이버 스마트스토어를 중심으로 운영해온 곤지암·용인·군포 풀필먼트 센터에 이어 추가로 20만평 규모의 풀필먼트 센터를 설립한다.

네이버는 지난 12일 풀필먼트 데이터 플랫폼 ‘NFA’를 열었고, 이어 네이버는 지난 20일 특수 물류 전문 업체 발렉스와 손잡고 프리미엄 배송 실험을 시작했으며, ‘희망일 배송’까지 네이버의 NFA를 통해 다양한 배송 서비스 지원을 확대할 계획이다.

• 풀필먼트는 물류 전문업체가 판매자 대신 주문의 포장과 배송까지 담당하는 서비스를 말한다.
• NFA는 네이버의 인공지능(AI)을 기술력을 이용해 물류 데이터 분석, 사업자별 물류 수요예측 등의 기능을 제공하는 서비스다.
• 프리미엄 서비스는 고가의 전자제품을 금고와 폐쇄회로(CC)TV, GPS 등이 설치된 보안 차량으로 상품을 안전하게 배송하는 서비스다.

2. 암 진단 AI ‘왓슨’ 빈자리 누가 채우나…치료까지 넘보는 한국 AI스타트업

암 진단 AI ‘왓슨’ 빈자리 누가 채우나…치료까지 넘보는 한국 AI스타트업

지난 2011년 IBM이 선보였던 인공지능(AI) 왓슨은 암 진단 정확도를 높일 주역으로 주목받았지만, 10년이 지난 현재, 기대만 못 한 정확도에 위기를 겪고 있으며, 의료AI 스타트업들이 암 치료에 도전하면서 왓슨이 설 자리는 더 좁아진 모양새다.

대표적인 곳이 국내 의료AI 스타트업인 루닛으로, 지난 19일 루닛은 미국의 바이오 헬스케어기업인 ‘가던트헬스(Guardant Health)’로부터 약 300억원 규모의 시리즈C 후속 투자를 받았다. 가던트헬스는 암 정밀 분석법인 액체생검 분야에서 선도적인 위치에 있으며, 미국 혈액종양내과 전문의 중 80%가 이곳 제품을 쓰는 것으로 알려져 있다.

3. 마이크로소프트, 윈도365로 기업 업무환경 바꾼다

마이크로소프트, 윈도365로 기업 업무환경 바꾼다

윈도365는 윈도10 환경을 클라우드서비스 애저에 구축하고, 웹브라우저를 통해 접속하는 가상데스크톱인프라(VDI) 서비스로, PC가 아닌 맥, 아이패드, 안드로이드 스마트폰 등에서도 웹브라우저를 통해 윈도 환경에 접근해 업무를 수행할 수 있고 하드웨어의 종류나 성능, 장소 제약 없이 윈도를 사용할 수 있어 원격 업무환경 지원에 용이하다.

대기업에서 필요한 재택근무 시스템은 윈도와 문서도구 외에도, 전사적자원관리(ERP), 공급망관리(SCM), 고객관계관리(SCM) 등 대규모 IT서비스와 연계가 필요하여 파트너사에 의뢰해 직접 VDI를 구축하거나, 윈도365에 필요한 기능을 더하는 추가 작업이 필수적이다.

나무기술의 권세창 과장은 “대기업과 금융권에서 VDI를 사용하기 위해선 윈도10 외에도 수백 종의 협업 도구를 포함하고 있어 윈도365 단독으로 제공하긴 어려울 것”이라며 “IT서비스 기업에게 윈도365는 대기업 VDI 구성을 위한 하나의 옵션으로 보는 것이 더 적합할 것”이라고 설명했다.

4. [유튜피아] 진격의 ‘틱톡’에 따라잡힌 유튜브…’틱톡 따라하기’ 맞불

[유튜피아] 진격의 ‘틱톡’에 따라잡힌 유튜브…’틱톡 따라하기’ 맞불

동영상 플랫폼 절대 강자 ‘유튜브’가 흔들리고 있다. 이미 일부 국가의 경우 ‘틱톡’의 이용시간이 유튜브를 앞지른 것으로 나타났다.

유튜브가 ‘숏폼’ 콘텐츠를 전면에 내세우며 틱톡 따라잡기에 나섰다면, 틱톡은 동영상의 제한 길이를 늘려 ‘유튜브’ 따라잡기에 나섰다. 틱톡은 지난 1일 영상의 길이 제한을 기존 1분에서 3분으로 대폭 늘린다는 계획을 내놨다. 15초 길이의 짧은 영상에서 60초까지 영상 길이를 늘렸던 틱톡이 3분짜리 동영상으로 유튜브를 정조준한 것이다.

5. “왜 불편하게 바꾸나” T멤버십 놓고 와글와글

“왜 불편하게 바꾸나” T멤버십 놓고 와글와글

현재 SK텔레콤 T멤버십 프로그램은 제휴 브랜드인 파리바게뜨·CU 등에서 1000원 상당의 물품을 구매하고 등급에 따라 50~100원 할인된 금액만을 결제하는 방식이지만, 앞으로는 할인 금액만큼의 포인트를 우선 적립하고, 원하는 제휴 브랜드 매장만을 골라서 적립한 금액을 한 번에 사용할 수 있다.

김대종 세종대 경영학부 교수는 “포인트 적립으로 멤버십을 바꾸는 것은 포인트가 몇 년 후 소멸된다는 점, 구매 당시 바로 할인을 받을 수 없다는 점에서 당연히 소비자에게 불리한 방식”이라고 말했다.

일각에서는 일정 수준 이상 포인트를 모아야 사용할 수 있는 ‘최소 사용 금액’ 도입을 우려하는 목소리도 나온다. 예컨대 제휴 브랜드에서 적립된 포인트를 사용하려고 해도 ‘포인트 1000원 이상 사용 가능’ 같은 기준이 정해져 있어 이 금액을 넘는 적립액을 쌓기 위한 소비를 지속적으로 해야 한다는 것이다.

출처: [백준] 11116번 교통량

문제

승민이는 마포대교의 교통량이 얼마인지를 측정하고있다. 승민이는 도로 맞은 편을 잇는 두개의 끈을 일정 간격 사이로 매달아 놓았다. 그리고 자동차가 끈위로 지나갈때 끈 끝에 있는 작은 박스에는 그 때 의 시간이 기록된다.

예를 들어, 자동차가 왼쪽에서 올 때 네 번의 기록을 얻게 된다.

• 왼쪽 줄 위로 앞 바퀴가 지나 간 시간 t
• 왼쪽 줄 위로 뒷 바퀴가 지나 간 시간 t + 500
• 오른쪽 줄 위로 앞 바퀴가 지나 간 시간 t + 1000
• 오른쪽 줄 위로 뒷 바퀴가 지나 간 시간 t + 1500

자동차가 오른쪽에서 올 때도 같은 규칙으로 오른쪽과 왼쪽을 바꾸어 측정하면 된다. 주어진 두개의 시간 기록으로 왼쪽에서 얼마나 많은 차가 왔는지 알아내면 된다. 한 끈 위에는 많아야 한 대의 차량이 지나가고 있다.

입력

첫 번째 줄에 n (1 ≤ n ≤ 100) 까지의 테스트 케이스의 개수를 입력 한다. 각각의 테스트 케이스에는 박스에서 측정 된 시간 기록의 개수 m (m ≤ 200)을 입력한다. 다음 줄에는 왼쪽 박스에서 측정된 109 보다 작은 시간 기록 m개를 입력한다. 그 다음 줄에는 오른쪽 박스에서 측정된 109 보다 작은 시간 기록 m개를 입력한다.

출력

각각의 테스트케이스에 대해 왼쪽에서 오는 차의 숫자를 출력한다.

예제 입력 1

1
2
3
4
5
6
7

2
4
17 517 1432 1932
432 932 1017 1517
6
235 451 735 951 2351 2851
1235 1351 1451 1735 1851 1951

예제 출력 1

1
2

1
2

힌트

예제의 첫 번째 테스트 케이스인 Case #1은 문제에서 예로들어서 설명한 세 개의 물품에 대한 정상가격과 할인가격 6개입니다. 또한 예제의 Case #2에서는 여러 품목이 동일한 가격을 가질 수 있고, 어떤 품목의 할인가격이 다른 품목 정상가격과 같을 수도 있습니다.

출처

• Contest > IDI Open Contest > IDI Open 2008 I번
  • 문제를 번역한 사람: tols91

알고리즘 분류

• 구현
• 자료 구조
• 큐

소스코드

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

import sys
from collections import deque

input = sys.stdin.readline

N = int(input())

for _ in range(N):
    M = int(input())
    left_box = deque(map(int, input().split()))
    right_box = deque(map(int, input().split()))

    car_count = 0
    count = 0
    while left_box:
        temp = left_box.popleft()
        if temp + 1000 in right_box:
            count += 1
        if count == 2:
            count = 0
            car_count += 1

    print(car_count)

출처: [백준] 12034번 김인천씨의 식료품가게 (Large)

문제

전설적인 인천 식료품가게의 주인인 김인천 씨는 대대적인 할인행사를 계획하고 있습니다. 계산을 단순하게하기 위해 그는 25% 할인된 가격으로 상점의 모든 품목을 판매하기로 결정했습니다. 즉, 각 품목의 판매 가격은 정상 가격의 정확히 75 %입니다. 우연하게도 인천 식료품가게에서 판매하는 모든 물건의 정상가는 4의 배수인 정수이고, 할인된 가격 역시 편리하게도 모두 정수입니다.

김인천씨는 이 할인행사를 준비하기위해서 먼저 모든 판매물품의 할인된 판매가격을 프린터로 출력을 실행했고, 또한 할인행사 종료후 다시 쓸 모든 품목에 정상가격표 역시 출력을 실행하였습니다.

손님이 찾아와 잠깐 자리를 비웠던 김인천씨가 다시 가격표의 출력을 확인하기 위해서 프린터로 돌아와보니, 공교롭게 프린터는 모든 물품의 할인가격과 정상가격을 따로 구분하지 않고 오름차순으로 정렬한 뒤 순서대로 출력하여 하나의 출력물 더미를 만들었습니다. 각 품목의 할인가격표와 정상가격표 모두가 출력물 더미의 어딘가에 있습니다. 그러나 두 유형(할인가격, 정상가격)의 가격표는 비슷하게 보이고, 모든 품목의 가격을 기억하지 못하기 때문에 김인천씨는 어느 가격표가 할인가격표인지 확신할 수 없습니다. 이 상황에서 김인천씨는 무엇이 할인가격표인지 구분해낼 수 있을까요?

예를 들어, 정상가격이 20, 80, 100 인 경우 할인가격은 15, 60, 75이며 프린터의 인쇄출력더미는 오름차순으로 정렬된 15, 20, 60, 75, 80, 100 가격표들로 구성됩니다.

입력

입력의 첫 번째 라인(줄)은 테스트 사례의 케이스의 수 T를 나타냅니다. 이후의 라인은 T개의 테스트 케이스가 이어집니다. 각 테스트 케이스는 두 줄로 구성됩니다. 첫 번째 줄에는 INU 식료품가게에 존재하는 상품수인 단일 정수 N이 포함됩니다. 두 번째 줄에는 프린터에서 가격의 오름차순으로 인쇄한 2N개의 정수 P1, P2, …, P2N이 주어집니다.

입력값의 제한은 아래와 같습니다

• 1 ≤ T ≤ 100.
• 모든 i에 대해서 1 ≤ Pi ≤ 109.
• 모든 i에 대해서 Pi ≤ Pi+1. (가격은 오름차순으로 존재)
• 정답은 단 하나만 존재하는것이 보장되어 있음.
• 1 ≤ N ≤ 100

출력

개별 테스트 케이스에 대해서 출력라인은 “Case #x: y” 형식(큰 따옴표는 제외)으로 출력하며, x는 1부터 시작하는 테스트 케이스의 번호 (인덱스)이며, y는 할인가격에 해당하는 오름차순으로 정렬된 N개의 정수들이다.

예제 입력 1

1
2
3
4
5

2
3
15 20 60 75 80 100
4
9 9 12 12 12 15 16 20

예제 출력 1

1
2

Case #1: 15 60 75
Case #2: 9 9 12 15

힌트

예제의 첫 번째 테스트 케이스인 Case #1은 문제에서 예로들어서 설명한 세 개의 물품에 대한 정상가격과 할인가격 6개입니다. 또한 예제의 Case #2에서는 여러 품목이 동일한 가격을 가질 수 있고, 어떤 품목의 할인가격이 다른 품목 정상가격과 같을 수도 있습니다.

출처

• Contest > Google Code Jam > Code Jam to I/O 2016 for Women > Code Jam A2번

알고리즘 분류

• 구현
• 자료 구조
• 큐

소스코드

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

import sys

input = sys.stdin.readline

T = int(input())

for t in range(T):
    N = int(input())
    price_list = sorted(map(int, input().split()), reverse=True)
    dc_list = []

    while price_list:
        price = price_list.pop()

        if price * 100 // 75 in price_list:
            dc_list.append(price)
            price_list.remove(price * 100 // 75)

    print("Case #{0}: ".format(t + 1), end="")
    print(*dc_list)

출처: [백준] 17952번 과제는 끝나지 않아!

문제

인터넷을 사용하기 위해서는 컴퓨터에 인터넷 회선을 연결하거나 Wi-Fi를 연결해야 한다. 이렇게 연결된 네트워크를 통해 컴퓨터에는 통신이 가능하다. 마음에 드는 노래나 동영상이 있는 곳에 파일을 전송해달라는 요청을 보내고 파일을 받는 식으로 말이다.

우리가 보낸 요청은 어떻게 목적지까지 도달하는 것일까? 컴퓨터에서는 패킷이라고 하는 형태로 정보를 주고 받는다. 네트워크의 유저들은 1:1로 연결되어 있지 않으므로, 일반적으로 패킷은 라우터라는 장비를 여러 번 거친다. 그러면 라우터에서는 패킷을 다른 라우터로 보내거나, 만약 목적지와 직접적으로 연결되어 있다면 그곳으로 보낼 수도 있다. 즉, 택배 회사의 물류 센터와 비슷한 역할을 한다고 보면 된다.

그림1. 네트워크에 존재하는 라우터들의 구성 예시

라우터 내부를 들여다보면 처리해야 할 패킷을 임시적으로 보관하기 위한 버퍼가 존재한다. 이 버퍼에는 라우터에 입력으로 들어온 패킷들이 순서대로 위치하고, 라우터에서는 먼저 온 패킷부터 하나씩 처리한 후 버퍼에서 제거한다. 만약 라우터가 패킷을 처리하는 속도보다 패킷이 들어오는 속도가 더 빠를경우 버퍼가 꽉 차거나 넘쳐버릴 것이다. 그렇게 되면 버퍼에 공간이 생길 때까지 입력받는 패킷은 모두 버려진다.

통신의 원리를 배웠으니까 간단하게 라우터의 작동 원리를 구현해보자. 물론 하나의 라우터만 존재한다고 가정하며, 우리가 다룰 부분은 라우터의 입출력이 주어졌을 때 버퍼의 상태가 어떻게 변하는가이다. 그러니까 라우터가 패킷을 구체적으로 어떤 방식으로 처리하고, 어디로 보내고 이런 것들은 생각하지 말자.

입력

첫 줄에는 라우터 내부에 존재하는 버퍼의 크기를 나타내는 자연수 N이 주어진다.

둘째 줄부터 한 줄에 하나씩 라우터가 처리해야 할 정보가 주어진다. 모든 정보는 발생한 시간순으로 주어졌다고 가정한다. 양의 정수는 해당하는 번호의 패킷이 입력으로 들어왔다는 것을 의미하고, 0은 라우터가 패킷 하나를 처리했다는 것을 의미한다. 이때, 버퍼가 비어있을때는 0이 입력으로 들어오지 않는다. -1은 입력의 끝을 나타낸다.

출력

라우터에 남아있는 패킷을 앞에서부터 순서대로 공백으로 구분해서 출력하면 된다. 만약 비어있을 경우 empty라고 출력한다.

Small (50점)

• 1 ≤ N ≤ 100,000
• 라우터가 처리해야 할 정보의 수는 N보다 작거나 같다.

Large(50점)

• 1 ≤ N ≤ 100,000
• 1 ≤ N ≤ 100,000

예제 입력 1

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

5
1
2
0
3
4
0
5
6
0
0
-1

예제 출력 1

1

5 6

예제 입력 2

1
2
3
4
5
6
7
8
9

1
1
2
3
4
5
6
7
-1

예제 출력 2

1

1

예제 입력 3

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

1
1
2
0
3
4
0
5
6
0
7
0
-1

예제 출력 3

1

empty

출처

• University > 아주대학교 > 2018 Ajou Programming Contest: Division 2 B번
  • 문제를 만든 사람: luke0201

알고리즘 분류

• 자료 구조
• 큐

소스코드

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

import sys
from collections import deque

input = sys.stdin.readline

N = int(input())
buffer = deque()
full = 0
while True:
    packet = int(input())

    if packet == -1:
        break
    elif packet == 0:
        buffer.popleft()
        full -= 1
    else:
        if full >= N:
            continue
        else:
            buffer.append(packet)
            full += 1

if buffer:
    print(*buffer)
else:
    print("empty")