BOJ_21314 민겸 수

문제 분석

1. 관찰
- 연속된 M은 M의 개수(cnt) -1이 자리수이다 -> 1E(cnt-1)
- K가 있는 경우 -> 5E(cnt)
- K에서 끊어준다.

- M 묶음으로 끊어주면 최소값이 된다.
- M과 K를 묶음으로 해준 경우 최대값이 된다.
... 코드 참고


2. 복잡도
- O(N) = S의 길이 >> 가능

3. 자료구조
- 최대, 최소 : 문자열

해결 코드

import sys
si = sys.stdin.readline

S = si().strip()
MAX = "" 
MIN = ""
cnt_m = 0  # 연속된 m의 개수 count

for i in range(len(S)):
    if S[i] == 'M':
        cnt_m +=1
    elif S[i] == 'K':
        if cnt_m: # M이 연속된 경우
            MAX += str(5*(10**cnt_m)) # M, K 함께 5의 배수로
            MIN += str(10**cnt_m+5) # M은 1의 배수로, K는 5로 더해서 추가
        else: # K만 단독으로 있는 경우, K는 단독으로 있기 때문에 5로만 끊어서 추가한다.
            MAX += "5"
            MIN += "5"
        cnt_m = 0

if cnt_m: # 끝이 M으로 끝나는 경우
    MIN += str(10**(cnt_m-1))
    while cnt_m: # 최대값을 만들기 위해서는 M의 연속의 경우 1111로 만들어 주어야 함으로 loop
        MAX += "1"
        cnt_m -= 1

print(MAX)
print(MIN)

BOJ_2667 단지번호붙이기 - Python3

문제 접근

1. 아이디어
- dfs로 단지 방문
- 방문하며 단지 번호 붙이기
- dfs에서 가구수 카운팅

2. 복잡도
- O(V+E) : 5*25*25 >> 가능

3. 자료구조
- 지도: int[][]
- 방문기록: bool[][]

해결 코드

import sys
input = sys.stdin.readline

N = int(input())

map = [input().strip() for _ in range(N)]
visited = [[0]*N for _ in range(N)]

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

groupCnt = 0
houseCnt =[]

def dfs(y,x):
    visited[y][x] = 1
    houseCnt[groupCnt]+=1
    for i in range(4):
        ny,nx = y + dy[i], x + dx[i]
        if 0<= ny < N and 0<= nx < N:
            if map[ny][nx] == '1' and visited[ny][nx] == 0:
                dfs(ny,nx)

for j in range(N):
    for i in range(N):
        if map[j][i] == '1' and visited[j][i] == 0:
            houseCnt.append(0)
            dfs(j,i)
            groupCnt +=1

print(groupCnt)
houseCnt.sort()
for e in houseCnt:
    print(e)

BOJ_1012 유기농 배추 - Python3

문제 접근

1. 아이디어
- BFS로 그룹 탐색
2. 복잡도
- O(V+E) : (50*50 + 4*50*50)T  >> 가능
3. 자료구조
- gragh: int[][]
- visited: bool[][]

해결 코드

from collections import deque  
import sys  
input = sys.stdin.readline

T = int(input().strip())

for \_ in range(T):  
m, n, k = map(int, input().strip().split()) # 배추밭의 가로, 세로, 배추가 심어져 있는 위치의 개수


farm = [[0]*m for _ in range(n)]
for _ in range(k):
    x, y = map(int, input().strip().split())
    farm[y][x] = 1

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

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

def bfs(y,x):
    q = deque()
    q.append([y,x])

    while q:
        y, x = q.popleft()
        visited[y][x] = True
        for i in range(4):
            nx, ny = x + dx[i], y + dy[i]
            if 0<= nx <m and 0<= ny <n:
                if farm[ny][nx] == 1 and visited[ny][nx] == False:
                    visited[ny][nx] = True
                    q.append([ny,nx])

for j in range(n):
    for i in range(m):
        if farm[j][i] == 1 and visited[j][i] == False:
            visited[j][i] = True
            bfs(j,i)
            answer +=1

print(answer)

BOJ_1260 DFS와 BFS - Python3

문제 분석

1. 아이디어
- bfs
- dfs
2. 복잡도
- O(V+E): 2000 >> 가능
- V : 1000
- E : 1000
3. 자료구조
- 그래프: int[][]
- 방문기록: bool[][]

해결 코드

from collections import deque
import sys
input = sys.stdin.readline

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

graph = [[] for _ in range(n+1)]

for _ in range(m):
    v1, v2 = map(int, input().strip().split())
    graph[v1].append(v2)
    graph[v2].append(v1)

for e in graph:
    e.sort()

visited_b =[False]*(n+1)
visited_d =[False]*(n+1)

def dfs(start):
    visited_d[start] = True
    print(start, end=' ')
    for i in graph[start]:
        if not visited_d[i]:
            dfs(i)

def bfs(start):
    q = deque([start])
    visited_b[start] = True
    while q:
        n = q.popleft()
        print(n, end=' ')
        for i in graph[n]:
            if not visited_b[i]:
                visited_b[i] = True
                q.append(i)

dfs(v)
print()
bfs(v)

BOJ_2441 별 찍기 - 4 - Python3

문제 접근

1. 아이디어

• .rjust(n,"") 로 우측정렬, 왼쪽 채우기

2. 복잡도

• O(n) loop

3. 자료구조

• 문자열

해결 코드

import sys
input = sys.stdin.readline

n = int(input())

for i in range(n,0,-1):
    star="*"*i
    print(star.rjust(n," "))

코멘트

• 문자열 정렬, 공백의 수, 공백 대체 포멧팅의 경우 rjust(n,"") 혹은 ljust(n,"") 활용

BOJ_10870 피보나치 수 5 - Python3

해결 코드

1) 재귀 함수

import sys
input = sys.stdin.readline

def f(n):
    if n <=1:
        return n
    return f(n-1) + f(n-2)

n = int(input())
print(f(n))

2) for loop

import sys
input = sys.stdin.readline

n = int(input())
f = [0, 1]
for i in range(2, n+1):
    num = f[i-1] + f[i-2]
    f.append(num)
print(f[n])