서린이의 기술 블로그

https://www.acmicpc.net/problem/2480

1. 메인 아이디어

  - 조건 그대로 조건문 로직을 만든다.

  - dictionary를 활용하여 max_number, max_count로도 문제풀이가 가능하다

- 단순 구현법

import sys
input = sys.stdin.readline

a, b, c = map(int, input().split())

if a == b == c:
    print(10000 + a * 1000)
elif (a == b != c) or (b == c != a):
    print(1000 + b * 100)
elif a == c != b:
    print(1000 + a * 100)
else:
    print(max(a,b,c) * 100)

- 딕셔너리를 이용한 방법

import sys
input = sys.stdin.readline

a, b, c = map(int, input().split())

# 주사위 숫자의 개수를 센다
count = {a: 0, b: 0, c: 0}
count[a] += 1
count[b] += 1
count[c] += 1

# 가장 많이 나온 숫자와 그 개수 찾기
max_num = max(count, key=lambda x: count[x])
max_count = count[max_num]

if max_count == 3:
    prize = 10000 + max_num * 1000
elif max_count == 2:
    prize = 1000 + max_num * 100
else:
    prize = max(a, b, c) * 100

print(prize)

1. 메인 아이디어

  - m을 60으로 나눈 몫을 시간에 더함

  - t에 다시 t를 24로 나눈 나머지로 대입 (24시간 형식 맞추도록)

  - m을 60으로 나눈 나머지가 분

import sys
input = sys.stdin.readline

t, m = map(int, input().split())
m2 = int(input())

m += m2

t += m // 60
t %= 24
m %= 60

print(t, m)

https://www.acmicpc.net/problem/2870

1. 메인 아이디어

  - prev를 도입하여 이전 숫자/단어가 알파벳인지 아닌지 검증한다.

  - 알파벳이 아닐 경우 무조건 str += w로 담고본다.

  - 알파벳 -> 숫자가 나오는 시점에는 str += w를 더한다.

  - 숫자 -> 알파벳이 나오는 시점에는 digits 리스트에 str을 int형으로 담고, str을 ''로 초기화한다.

    > digits 리스트에 str을 담을 때, str이 애초에 ''이 아닌지도 검증이 필요하다 (if str != '' and str_lstrip != '':)

    > str 검증을 하지않으면 '' 빈 공백이 digits에 담기기 때문임

  - digits 리스트의 오름차순으로 정렬한 후, print한다.

    > digits 리스트의 원소 타입이 '' 스트링 타입이면, 숫자 크기가아닌 사전순 정렬이 되므로 주의한다.

       > ex:) 0 2 2 4 23223 5 (X) -> 0 2 2 4 5 23223 (O)

  - 안쪽 for 문이 끝나면 ( for w in s: ) input_digit_or_zero 함수를 한번더 호출한다

    > 왜냐면, ... 002 이런식으로 문장이 끝나면 2를 담지 못하기 때문에 한번 더 담아줘야함

2. 소스 코드

import sys
input = sys.stdin.readline

alphabet = 'abcdefghijklmnopqrstuvwxyz'


n = int(input())
lines = []
digits = []
for _ in range(n):
    lines.append(input().strip())

def input_digit_or_zero(str):
    str_zero = str.lstrip('0')
    if str != '':
        if str_zero == '':
            digits.append(0)
        else:
            digits.append(int(str_zero))

for s in lines:
    str = ''
    prev = -1

    for w in s:
        if prev == -1:
            if w not in alphabet:
                str += w
        else:
            if w not in alphabet:
                str += w
            elif prev not in alphabet and w in alphabet:
                input_digit_or_zero(str)
                str = ''
            elif prev in alphabet and w not in alphabet:
                str += w
        prev = w
    input_digit_or_zero(str)
        
for i in sorted(digits):
    print(i)

https://www.acmicpc.net/problem/2910

1. 메인 아이디어

  - 각 원소에 대해 [빈도, 순번]을 정렬할 자료구조를 생각한다 -> dictionary가 적합

  - dictionary를 key=lambda(=익명함수)를 기준으로 정렬한다

    > -x[1][0] = 각 원소의 빈도를 우선으로 내림차순

    > x[1][1] = 각 원소의 순번을 그 다음으로 오름차순

  - result에 정렬된 dictionary를 원소 * 빈도로 extend한다 ( dictionary 내부 원소는 list 이므로 extend 써야함)

    > result = [], extend ([2,3], [1,2] ..) => result = [2, 2, 2, 1, 1]

2. 소스 코드

# 백준 2910 빈도 정렬
# 수열은 N개로 이루어져 있고 숫자는 모두 C보다 작거나 같다
# 수열 내에 두 수 X와 Y가 있을 때 X가 더 앞에 있어야 함
# 메시지의 길이 N과 C가 주어진다 

# 5 2
# 2 1 2 1 2
import sys
input = sys.stdin.readline

# 입력 받기
n, c = map(int, input().split())
seq = list(map(int, input().split()))

# 빈도와 첫 번째 인덱스를 저장할 딕셔너리
count = {}
for idx, num in enumerate(seq):
    if num in count:
        count[num][0] += 1  # 빈도 증가
    else:
        count[num] = [1, idx]  # 빈도와 첫 등장 인덱스 저장

# 빈도와 인덱스를 기반으로 정렬
sorted_numbers = sorted(count.items(), key=lambda x: (-x[1][0], x[1][1])) # -x[1][0] 은 빈도를 기준으로 내림차순, x[1][1] 순서를 기준으로 오름차순
# x[1]은 count[num] -> ex:) [3, 0]
# x[1][0]은 특정 숫자의 빈도를 의미

# 결과 리스트 생성
result = []
for num, (freq, _) in sorted_numbers:
    result.extend([num] * freq)  # 각 숫자를 빈도만큼 추가

# 결과 출력
print(*result)

https://www.acmicpc.net/problem/2828

1. 메인 아이디어

- l(=left)와 r(=right)를 고려한다. (left는 바구니 왼쪽, right는 바구니 오른쪽)

- 바구니의 길이가 1이기 때문에 시작 l = 1, r = 1 이다 ( r = 2 가아님, 2가되면 바구니의 길이가 2임)

- l을 통하여 r을 정의하면, r = l + m - 1

- 바구니가 사과보다 왼쪽, 오른쪽에 있을 때를 고려한다.

2. 소스코드

import sys
input = sys.stdin.readline

# 5 1
# 3
# 1
# 5
# 3

#     1      2    3   4  5
# |        |   |   |   |   |
# |        |   |   |   |   |
# |        |   |   |   |   |
# l=1,   r =1 , r은 2가아님, 왜냐하면 바구니 길이가 1이기 때문

n, m = map(int, input().split())
J = int(input())
l, ret = 1, 0 # r = l + m - 1 -> r = 1

for i in range(J):
    r = l + m - 1
    apple = int(input())
    if l <= apple <= r: continue
    else:
        if apple < l: # 사과보다 바구니가 오른쪽
            ret += l - apple
            l = apple
        else: # 바구니가 사과보다 왼쪽
            l += apple - r
            ret += apple - r
print(ret)

https://www.acmicpc.net/problem/1992

1. 풀이 알고리즘 : DFS(선택), BFS, 분할정복

2. 핵심 아이디어

   2-1. 입력값 하나하나를 행렬에 원소로 담기

   2-2. (0,0)과 size로부터 시작

   2-3. 한번에 4개씩 재귀적으로 호출하며, 각각 재귀는 왼쪽위, 오른쪽위, 왼쪽아래, 오른쪽아래와 size / 2를 계속 매개변수로 담아서, size가 1이 될 때까지 계속 호출한다.

   2-4. 문제 조건에 따라서 ret에 계속 String을 담아서 값을 만들어 호출한다.

3. 분할정복 알고리즘의 순차적 흐름 예시

4. 소스 코드

import sys

input = sys.stdin.readline

def quard(y, x, size):
    y = int(y)
    x = int(x)
    size = int(size)
    if size == 1:
        return str(a[y][x]) # 기저 조건(=종료 조건), size가 1일 때는 더 이상 쪼개지지 않는다.
    b = a[y][x] # 1개를 뽑아냄
    ret = ''
    for i in range(y, y + size): # y로 부터 size만큼 쪼갠다
        for j in range(x, x + size): # x로 부터 size만큼 쪼갠다
            if b != a[i][j]:
                ret += '('
                ret += quard(y, x, size / 2) # 왼쪽 위
                ret += quard(y, x + size / 2, size / 2) # 오른쪽 위
                ret += quard(y + size / 2, x, size / 2) # 왼쪽 아래
                ret += quard(y + size / 2, x + size / 2, size / 2) # 오른쪽 아래
                ret += ')'
                return ret
    return str(a[y][x])

n = int(input())
a = [[0] * n for _ in range(n)]
s = ''

for i in range(n):
    s = input()
    for j in range(n):
        a[i][j] = s[j]

print(quard(0, 0, n))

5. 소스 코드의 시각화

출처 : https://www.acmicpc.net/problem/2583

import sys
sys.setrecursionlimit(100000)
input = sys.stdin.readline

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

a = [list(map(int, input().split())) for _ in range(k)]

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

visited = [[0] * m for _ in range(n)]

for i in range(k):
    s = a[i]
    for i in range(n):
        for j in range(m):
            if s[0] <= i < s[2] and s[1] <= j < s[3]:
                visited[i][j] = 1

s_list = []
tmp_list = []

def dfs(x, y):
    visited[x][y] = 1
    tmp_list.append(1)
    for i in range(4):
        nx = x + dx[i]
        ny = y + dy[i]
        if nx < 0 or ny < 0 or nx >= n or ny >= m:
            continue
        if visited[nx][ny] == 0:
            dfs(nx, ny)

for i in range(n):
    for j in range(m):
        if visited[i][j] == 0:
            dfs(i, j)
            s_list.append(sum(tmp_list))
            tmp_list.clear()

s_num = len(s_list)
print(s_num if s_num > 0 else 1)
print(*sorted(s_list))

1. 풀이 알고리즘 : DFS(선택), BFS, 인접 리스트 etc

2. 핵심 아이디어

   2-1. K 개의 사각형 영역을 먼저 방문처리

   2-2. 방문되지 않은 영역을 깊이우선탐색하여 영역의 넓이과 갯수를 구함

   2-3. 다른 풀이 방법 :

K 개의 사각형 영역을 먼저 방문하지 않고, 방문되어야할 영역을 한번에 걸러서 처리하면 더 빠를 것으로 생각함

BFS로도 풀어보면 좋을 것 같음

3. 어려웠 던 부분

  3-1. (0,0) 의 위치가 왼쪽 하단에 있어서 Matrix를 만들 때 너무 헷갈려서, n과 m을 거꾸로 넣어버림

  3-2. 탐색 시 영역의 넓이를 누적하는 로직을 스택 함수에 넣었더니, 스택을 빠져나오면서 값이 원복되었음

-> tmp_list에 1씩 담아서 나중에 s_list에 담기 전에 sum()을 통해 누적합 하여 해결함

-> 다른 방법이 있는지 탐구 필요

4. 코드 개선

import sys
sys.setrecursionlimit(100000)
input = sys.stdin.readline

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

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

a = [list(map(int, input().split())) for _ in range(k)]

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

visited = [[0] * m for _ in range(n)]

for i in range(k):
    s = a[i]
    for i in range(n):
        for j in range(m):
            if s[0] <= i < s[2] and s[1] <= j < s[3]:
                visited[i][j] = 1

s_list = []

def dfs(x, y):
    visited[x][y] = 1
    ret = 1 # dfs 들어갈때마다 1을 return하기위해서 ret = 1로 둠, 가중치가 2면 ret = 2 로 해야함
    for i in range(4):
        nx = x + dx[i]
        ny = y + dy[i]
        if nx < 0 or ny < 0 or nx >= n or ny >= m:
            continue
        if visited[nx][ny] == 0:
            ret += dfs(nx, ny) # 모든 dfs 의 결과값인 return ret을 ret에 더한다
    return ret

for i in range(n):
    for j in range(m):
        if visited[i][j] == 0:
            s_list.append(dfs(i, j))

s_num = len(s_list)
print(s_num if s_num > 0 else 1)
print(*sorted(s_list))

1. s_list에 담는 시점에 dfs(i, j)를 호출

2. ret = 1인 이유는, 가중치가 1이기 때문임 -> dfs 깊이를 들어간 만큼 return ret (=1) 을 계속 반환

3. 반환한 값들을 ret += dfs(nx, ny)에서 모두 더함 -> 빈 영역의 넓이 = 사각형의 갯수

4. 다 더한 후에 s_list.append(dfs(i, j))를 통하여, 빈 영역의 넓이를 담는다.

5. 빈 영역이 총 3개 이고 각각 1, 7, 13 이다