문제 풀이

두 번의 for문을 사용 -> 시간 초과 발생, 보통 부분합은 dp를 이용한다

정답 코드

"""
https://www.acmicpc.net/problem/1912
"""
N=int(input())
nums = list(map(int,input().split()))

dp = [0]*N
dp[0] = nums[0]

for i in range(1,N):
    # 여기까지 모두 더한 값이랑 현재 값을 비교, 현재까지 더한 값이 더 작으면 앞의 값을 사용할 이유가 없음
    # 현재값부터 dp[i]에 다시 저장
    dp[i] = max(nums[i],dp[i-1] + nums[i])

print(max(dp))

추가적인 개념

dp에 대한 이해가 중요함 앞의 값을 더하지 않고 다시 수열을 시작하는 기준이 어떻게 되는지 파악할 것 -> 이 문제의 경우엔 현재까지 더한 값이 현재 값보다 작다면 굳이 앞의 값을 사용할 이유가 없으므로 해당 위치부터 다시 수열을 시작한다.

문제 풀이

현재 단어와 다음 단어를 비교했을 때 같으면 pass, 다르면 list에 저장되어있는지 확인 후 저장되어있지 않으면 append, 이미 저장되어 있으면 cnt-=1하고 break

정답 코드

"""
https://www.acmicpc.net/problem/1316
"""
N = int(input())
cnt = N
for _ in range(N):
    word = input()
    l = []
    for idx in range(len(word)):
        if idx == len(word) - 1:
            if word[idx] in l:
                cnt -= 1
        elif word[idx] == word[idx + 1]:
            pass
        else:
            if word[idx] not in l:
                l.append(word[idx])
            else:
                cnt -= 1
                break
print(cnt)

다른 사람 코드 (optional)

N = int(input())
cnt = N

for i in range(N):
    word = input()
    for j in range(0, len(word)-1):
        if word[j] == word[j+1]:
            pass
        elif word[j] in word[j+1:]:
            cnt -= 1
            break

print(cnt)

string에 대해서 slicing으로 문자열 일부를 자른 후 그 안에 현재의 원소가 들어있는지 판단. in/not in은 반드시 list에서만 쓰는 것이 아닌 문자열에도 사용할 수 있다.

문제 풀이

첫번째 코드를 구현할 때 각 자릿수를 누를 수 있는 버튼 중 그 차이가 가장 작은 값을 불러와서 정답을 내렸다. 그러나 테스트케이스7번과 같이 target channel보다 자릿수가 작은 경우가 답인 경우에는 오답이 발생했다. 해당 케이스를 따로 구현하려하다가 단순히 전체를 탐색했을 때 답을 구할 수 있음을 알 수 있었다.

정답 코드

첫번째 코드(unsolved) - about test_case7

"""
https://www.acmicpc.net/problem/1107
"""
# test_case 7번 해결
channel = 100
N = input()
M = int(input())
if M != 0:
    broken = set(map(int, input().split()))
else:
    broken = set([])
nums = set([0, 1, 2, 3, 4, 5, 6, 7, 8, 9])
buttons = list(nums - broken)
ans = []

for num in N:
    if int(num) in buttons:
        ans.append(0)
    else:
        ans.append(min(map(lambda x: abs(x - int(num)), buttons)))

answer = 0
for idx, i in enumerate(ans):
    answer += i * 10 ** (len(ans) - idx - 1)
print(min(answer + len(N), abs(int(N) - channel)))

두번째 코드(solved)

"""
https://www.acmicpc.net/problem/1107
"""
N=int(input())
M=int(input())
if M==0: broken=[]
else: broken=input().split()
answer=abs(100-N) # 현재 채널 100에서 그냥 옮길 때 누르는 횟수
for num in range(1000001): # 이동하려는 채널과는 별개로 채널은 무한히 존재한다
    for idx,i in enumerate(str(num)):
        if i in broken:
            break
        elif idx==len(str(num))-1: # num이 누를 수 있는 번호일 경우
            answer=min(answer,abs(N-num)+len(str(num)))
print(answer)

추가적인 개념 (optional)

때때로 안 풀릴 땐 완전 탐색도 시도해보기

EOF Error는 "End of File Error"의 줄임말로, 파일 또는 입력 스트림에서 더 이상 읽을 데이터가 없을 때 발생하는 오류를 나타낸다. M이 0일 때는 broken에 대한 입력이 발생하지 않는데 이 경우를 고려하지 않고 코드를 작성

다른 사람 코드 (optional)

두번째 풀이와 같다

문제 풀이

bfs로 검색 -> 시간초과 발생 dfs로 풀이 -> 해당 위치에서의 방문 여부를 list로 구현하기보다 True/False로 구현하는 것이 더 편리, 이 때 ord()를 사용해서 그 idx를 파악했다.

• visited=[]로 리스트에 해당 문자가 존재하는지 여부를 파악하는 것을 조건문으로 걸었다. 이 때 반드시 방문이 끝날 때는 마지막 방문에서 더 이상의 움직임이 이뤄지지 않았으므로 방문처리를 취소한다.(pop(), or True->False) 이와 같은 방법은 시간초과가 발생했는데 list에 append하고 search하는 과정의 시간복잡도가 O(n)인 반면에 visited=[False]*26은 idx로 접근할 수 있기 때문에 그 시간복잡도가 O(1)이다.

정답 코드

"""
https://www.acmicpc.net/problem/1987
"""
R,C=map(int,input().split())
board=[list(input().rstrip()) for _ in range(R)]
visited = [False]*26 # 알파벳 수 26
# 상하좌우
dx=[-1,1,0,0]
dy=[0,0,-1,1]

max_distance=0

def dfs(x,y,distance):
    global max_distance
    max_distance=max(max_distance, distance)
    visited[ord(board[x][y])-ord('A')]=True
    for i in range(4):
        nx=x+dx[i]
        ny=y+dy[i]
        # 이동할 수 있는 경우라면
        if 0<=nx<R and 0<=ny<C and not visited[ord(board[nx][ny])-ord('A')]:
            dfs(nx,ny,distance+1) # 그 위치에서 다시 dfs탐색 시작

    visited[ord(board[x][y]) - ord('A')] = False # 이동할 수 없다면 해당 위치 방문 취소

dfs(0,0,1)
print(max_distance)

추가적인 개념 (optional)

dfs에서의 순환함수

• 가능한 모든 경로 탐색: 이 문제에서는 알파벳을 이동하면서 최대한 많은 알파벳을 방문하는 것이 목표입니다. DFS를 사용하면 모든 가능한 경로를 탐색할 수 있습니다. DFS는 한 경로를 끝까지 탐색하고 나서 다른 경로로 넘어가는 방식으로 동작하므로, 가능한 많은 알파벳을 방문하는 경로를 찾을 수 있습니다.

• 백트래킹: DFS는 백트래킹(Backtracking)을 활용하여 불필요한 경로를 더 이상 탐색하지 않고 중단할 수 있습니다. 만약 한 경로가 더 이상 진행할 수 없는 상황(예: 이미 방문한 알파벳)에 놓이면, 이전 단계로 돌아가서 다른 경로를 탐색합니다.(다음 for문 실행 or 더이상 이동할 수 없으면 정지) 이를 통해 효율적으로 가능한 최대 경로를 찾을 수 있습니다.

• 깊이 우선 탐색: 문제에서는 "깊이 우선 탐색"으로 경로를 찾는 것이 자연스럽습니다. 즉, 한 방향으로 최대한 깊게 파고들어가면서 탐색하는 것이 문제의 특성과 잘 어울립니다. DFS는 이러한 탐색 방법을 구현하기에 적합합니다. <-> BFS를 사용하지 않은 이유

다른 사람 코드 (optional)(feat.gpt)

# 입력 받기
R, C = map(int, input().split())
board = [list(input().rstrip()) for _ in range(R)]

# 방문한 알파벳 체크용 배열
visited = [False] * 26

# 상, 하, 좌, 우 이동 방향
dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]

# 최대 이동 거리 초기화
max_distance = 0

# DFS 함수 정의
def dfs(x, y, distance):
    global max_distance
    max_distance = max(max_distance, distance)

    # 현재 알파벳 방문 처리
    visited[ord(board[x][y]) - ord('A')] = True

    # 네 방향으로 이동
    for i in range(4):
        nx, ny = x + dx[i], y + dy[i]
        if 0 <= nx < R and 0 <= ny < C and not visited[ord(board[nx][ny]) - ord('A')]:
            dfs(nx, ny, distance + 1)

    # 현재 알파벳 방문 해제
    visited[ord(board[x][y]) - ord('A')] = False

# 시작 위치는 (0, 0)부터 시작
dfs(0, 0, 1)

print(max_distance)

문제 풀이

nums로 숫자 값을 받은 뒤 그 안에 들어있는지 탐색

1. 그냥 단순 구현 : in nums로 check했더니 시간초과 발생 ( list 내의 모든 값을 서치하는 데에 시간이 오래 걸림 ) list에서의 탐색 함수의 시간 복잡도는 O(n)
2. 이분탐색을 이용 : l,r값을 지정한 후 sorted(nums)에서 인덱스를 이용한 크기 비교를 통해 l, r 값을 업데이트하며 비교 -> 통과
3. set을 이용 : nums를 set로 받은 후 search할 때의 시간 복잡도 함수는 O(1)로 list에서의 탐색보다 훨씬 빠른 속도를 가짐 -> 통과

정답 코드

# 2번 코드
"""
https://www.acmicpc.net/problem/1920
"""
import sys

input = sys.stdin.readline
N = int(input())
nums = sorted(map(int, input().split()))
M = input()
check = map(int, input().split())
for i in check:
    l, r = 0, N - 1  # 이분탐색 초기 설정값
    find = False

    # 이분탐색 시작
    while l <= r:  # l이 r과 커지면 정지
        mid = (l + r) // 2
        if i == nums[mid]:
            find = True
            print(1)
            break
        elif i > nums[mid]:
            l = mid + 1
        else:
            r = mid - 1
    if not find:
        print(0)

############################################
# 3번 코드
"""
https://www.acmicpc.net/problem/1920
"""
import sys

input = sys.stdin.readline
N = int(input())
nums = set(map(int, input().split()))
M = input()
check = map(int, input().split())
for i in check:
    print(1) if i in nums else print(0)

추가적인 개념 (optional)

set에서의 탐색 함수의 시간 복잡도는 O(1)로 list의 이분탐색보다 성능이 더 좋다. 각 함수의 시간 복잡도를 알고 최적의 함수를 이용하는 것이 골드 문제 풀 때 많이 도움 된다. ( 답은 맞지만 시간 초과로 통과하지 못하는 경우가 매우 많음...😢

문제 풀이

인근에 위치한 부등식만 만족하는 조건 하에 하나씩 찾을 것, 이 때 시간을 최소화하기 위해 max값과 min값의 순서 배열 시작을 다르게 함 max=9876543210 min=0123456789로 시작 op로 부등호를 받은 후 idx값을 이용해서 하나하나 비교, 식이 성립하지 않을 때마다 배열의 앞뒤 값을 바꿔주며 while문을 반복한다. 부등식이 모두 만족하면 반복문을 중지하고 값을 출력한다.

정답 코드

"""
https://www.acmicpc.net/problem/2529
"""
N=int(input())
op=input().split()
max=[9,8,7,6,5,4,3,2,1,0]
min=[0,1,2,3,4,5,6,7,8,9]
ans_max=max[:N+1]
ans_min=min[:N+1]

def check(arr):
    sat=1
    while sat!=0:  
        sat=0
        for idx in range(N):
            a=arr[idx]
            b=arr[idx+1]
            if op[idx]=='>':
                if a>b:
                    pass
                else:
                    arr[idx]=b
                    arr[idx+1]=a
                    sat+=1
            if op[idx]=='<':
                if a<b:
                    pass
                else:
                    arr[idx]=b
                    arr[idx+1]=a
                    sat+=1
    return arr

print(*check(ans_max),sep='')
print(*check(ans_min),sep='')

추가적인 개념

다른 사람들도 비슷한 아이디어에서 시작했으나 코드의 간단 명료함이 다른 것이 아쉽다. sat변수를 이용한 while문의 중지말고 다른 방법이 있을지 알아보기

문제 풀이

L개 이상의 연속된 수의 합으로 N을 나타내는 문제, L의 제한이 100이었으므로 하나하나 체크하는 것이 옳은 방법이라고 생각해서 while문으로 L이 100이 되는 순간까지 식을 반복했다. 식을 세우는 과정에서 약간 버벅임이 있었다.

정답 코드

"""
https://www.acmicpc.net/problem/1024
"""
N, L = map(int,input().split())
while L<=100:
    sum = 0
    for i in range(L+1):
        sum += i
    K = L*((N-sum)//L) + sum
    if K == N and N-sum>=-L:
        ans = []
        for i in range(L):
            ans.append((N-sum)//L+i+1)
        print(*ans)
        break
    L += 1
if L>100:
    print(-1)

추가적인 개념 (optional)

풀이가 너무 난잡한 것 같다. N-sum < L이라는 특정 상황에서만 쓰이는 코드를 좀 더 일반적으로 표현할 수는 없을까? -> 다른 사람 코드 참고했을 때 다들 비슷하게 수학적인 표현을 가지고 풀이를 진행하는 것 같다.

문제 풀이

단순 구현, 조금 더 고차원 list를 다루는 데에 익숙했으면 쉽게 금방 풀이를 완료했을 수 있었을 것이다.

정답 코드

"""
https://www.acmicpc.net/problem/1283
"""
N = int(input())
keys = [] # 대문자로 통일
words = [ input() for _ in range(N) ]

for word in words:
    check = 0
    l = word.split()
    for j in l: # 단어 첫글자 기준 key값 추가
        if j[0].upper() not in keys:
            keys.append(j[0].upper())
            check += 1
            break
    if check == 0: # 단어 첫글자가 모두 key로 존재한다면
        l = ''.join(l)
        for k in list(l):
            if k.upper() not in keys:
                keys.append(k.upper())
                check += 1
                break
    if check == 0:
        keys.append('.')

ans = []
for key,word in zip(keys,words):
    check = 0
    l = word.split()
    word = list(word)
    for idx,j in enumerate(l):
        if j[0].upper() == key:
            new = list(j)
            new[0] = '['+new[0]+']'
            check += 1
            l[idx] = ''.join(new)
            ans.append(l)
            break


    if check == 0:
        for idx,i in enumerate(word):
            if i == ' ':
                pass
            if i.upper() == key:
                word[idx] = '['+i+']'
                check += 1
                word = ''.join(word)
                ans.append([word])
                break

    if check == 0:
        ans.append([''.join(word)])

for i in ans:
    print(' '.join(i))

다른 사람 코드

n = int(input())
words = []
for _ in range(n):
  words.append(input())

shortcut = set([' ']);
splited = []
for w in words:
  temp = w.split()
  haveShortcut = False
  for i in range(len(temp)):
    if temp[i][0].upper() not in shortcut:
      shortcut.add(temp[i][0].upper())
      temp[i] = '[' + temp[i][0] + ']' + temp[i][1:]
      splited.append(" ".join(temp))
      haveShortcut = True
      break
  if not haveShortcut:
    for i in range(len(w)):
      if w[i].upper() not in shortcut:
        shortcut.add(w[i].upper())
        splited.append(w[:i] + '[' + w[i] + ']' + w[i+1:])
        haveShortcut = True
        break
  if not haveShortcut:
    splited.append(" ".join(temp))
for s in splited:
  print(s)

여기서 나는 word에 대해 list를 만들고 각 원소에 대해 다시 list를 만들어서 두 개의 for문으로 접근했다면 word[a][b]형태로 한 번에 접근 가능하도록 하는 것이 코드를 간편하게 만드는 데에 있어서 도움이 될 것이다.

문제 풀이

1. k값을 정하고, 그 값에 따라 list를 돌면서 l과 r값을 정의한다. S를 미리 sorted했으나 처음부터 k보다 큰 값이 나오면 오류가 생겼다 -> 코드를 짤 때 특수한 경우에만 국한되지 않도록 인덱스를 이용해서 무언갈 하는 것은 좋지 못한 것 같다.
2. cnt를 두고 이미 max값이 한 번 지정되었을 경우 더이상 변화가 없도록 설정했다. 그러나 idx가 0일 경우 -1로 가장 마지막 값이 l에 할당되면서 오류가 생겼다
3. min,max로 둔 후 가장 가까운 값을 따로 지정했다.
4. combination을 이용해서 그 경우를 계산하려 했으나 단순 식으로 구현가능했기에 사용하지 않았다.

정답 코드

from itertools import combinations
N = int(input())
S = sorted(map(int,input().split()))

k = int(input())
l = 0
r = 0
cnt = 0
ans = 0
if N == 1:
    l = 1
    r = S[0]-1
else:
    for idx,i in enumerate(S):
        if k == i:
            ans = -1
            break
        if k<i and cnt == 0:
            if idx == 0:
                r = S[idx]-1
                l = 1
            else:
                r = S[idx]-1
                l = S[idx-1]+1
            cnt += 1 # 한 번만 실행되도록

if ans == -1:
    print(0)
else:
    print(l)
    print((k-l)*(r-k+1) + (r-k))

위 코드에선 N이 1일경우, S[0]가 k보다 클 경우를 모두 고려하지 못했고 이런 특수한 케이스에 대해 하나하나 조건문을 제시하고 있어 효율적인 코드라고 볼 수 없다.

다른 사람 코드 (optional)

N = int(input())
S = sorted(map(int,input().split()))

k = int(input())
min = 0
max = 0
ans = 0
if k in S:
    ans = -1
else:
    for i in S:
        if i < k: # i 가 k보다 작다면
            min = i
        elif i > k and max == 0:
            max = i 
min = min+1
max = max-1
if ans == -1:
    print(0)
else:
    print((k-min)*(max-k+1) + (max-k))

min값과 max값을 경우에 따라 나누어서 따로따로 구하고있다. 나의 경우에는 k보다 i가 커지는 시점에 두 개의 값을 모두 결정했다면 min과 max를 따로 정의해서 충돌이 나지 않고 있다.

문제 풀이

단어 길이와 단어를 함께 list에 넣은 후 key값에 따라 정렬 순서를 기재하여 정렬한다. for문의 range를 N이 아닌 수치로 지정하고, 공통되는 값을 제거해주지 않아서 오답 과정을 거침

정답 코드

"""
https://www.acmicpc.net/problem/1181
"""
N = int(input())
l = []
for _ in range(N):
    word = input()
    if [len(word),word] not in l:
        l.append([len(word),word])

l.sort(key = lambda x:(x[0], x[1]))

for i in l:
    print(i[1])

추가적인 개념 (optional)

sort함수 사용법 sort(), sorting, sorted()를 매번 헷갈려하는데 이에 대해 정확히 정리해보겠다.

1. sort()
   • 리스트 자체를 변경하여 정렬한다.
   • 원본 리스트를 직접 수정하며, 정렬된 결과 반환은 따로 없다.
   • 기본적으로 오름차순으로 정렬되며 key, reverse를 사용하여 정렬 기준 or 순서를 지정할 수 있다.
2. sorted()
   • 새로운 정렬된 리스트를 반환한다. 원본 리스트는 변경되지 않는다.
   • 마찬가지로 key와 reverse를 사용하여 정렬 기준과 순서를 지정할 수 있다.
3. sorting
   • python의 내장함수가 아니고, 제공되지 않는다...^^

     # 예시 코드
     my_list = [3, 1, 4, 1, 5, 9, 2, 6, 5]
     # sort() 메서드를 사용하여 원본 리스트를 정렬
     my_list.sort()
     print(my_list)  # 출력: [1, 1, 2, 3, 4, 5, 5, 6, 9]
     # sort() 메서드를 사용하여 내림차순으로 정렬
     my_list.sort(reverse=True)
     print(my_list)  # 출력: [9, 6, 5, 5, 4, 3, 2, 1, 1]
     # sorted() 함수를 사용하여 새로운 정렬된 리스트 반환
     new_list = sorted(my_list)
     print(new_list)  # 출력: [1, 1, 2, 3, 4, 5, 5, 6, 9]
     # 이 때는 my_list는 변경되지 않는다.
     print(my_list) # 출력: [3, 1, 4, 1, 5, 9, 2, 6, 5]
     # sorted() 함수를 사용하여 내림차순으로 정렬된 리스트 반환
     new_list = sorted(my_list, reverse=True)
     print(new_list)  # 출력: [9, 6, 5, 5, 4, 3, 2, 1, 1]

문제 풀이

키가 작은 순서대로 입력, answer를 [0]*N의 list로 만들었을 때, 0의 수가 현재 사람이 기억하는 자기보다 큰 사람의 수와 같아야 성립한다. -> 본인보다 큰 사람이 있을 경우를 고려했기 때문에 계속해서 오류가 발생

정답 코드

"""
https://www.acmicpc.net/problem/1138
"""
n = int(input())
line = list(map(int, input().split()))

answer = [0] * n

for i in range(1, n + 1):
    temp = line[i - 1]
    cnt = 0
    for j in range(n):
        if temp == cnt and answer[j] == 0:
            answer[j] = i
            break
        elif answer[j] == 0:
            cnt += 1

print(*answer)

추가적인 개념 (optional)

greedy algorithm → 미래를 생각하지 않고, 현재 상황에서 가장 최선인 선택을 선택하는 것 / 현재 상황에서 최선인 것들의 집합이 반드시 최종적인 해답에서의 최적의 값이라는 보장은 할 수 없다.

• 문제를 해결하는 방법 : 현재 상황에서의 최선의 선택 → 선택이 문제의 조건을 만족하는지 검사 → 원래의 문제가 해결되었는지 검사, 해결되지 않았다면 선택으로 돌아가 위의 과정을 반복
• 근사 알고리즘으로 사용할 수 있으며, 대부분의 경우 계산 속도가 빠르기 때문에 실용적이다.

동적 프로그래밍과 비슷하나 훨씬 더 효율적이다. 그러나 최적의 값을 항상 만족하는 것은 아니기 때문에 보완하는 개념으로 알려진다.

문제 풀이

bfs순회로 경우를 찾되, 가장 작은 경우일 때를 출력한다. 최대 거리가 주어졌으니 해당 범위에 맞춰서 수를 미리 설정해둘 수 있다.

정답 코드

from collections import deque

N, K = map(int,input().split())
queue = deque()
queue.append((N, 0))
visited = [False] * 100001
result = 0

while queue:
    num, count = queue.popleft()
    if num == K:
        print(count)
        break

    if 0 <= 2 * num <= 100000 and visited[2 * num] == False:
        queue.append((2 * num, count + 1))
        visited[2 * num] = True
    if 0 <= num + 1 <= 100000 and visited[num + 1] == False:
        queue.append((num + 1, count + 1))
        visited[num+1] = True
    if 0 <= num - 1 <= 100000 and visited[num-1] == False:
        queue.append((num - 1, count + 1))
        visited[num-1] = True

문제 풀이

prices 리스트를 정의하고 가능한 가격을 모두 append시킨 후에 min(prices)를 출력한다.

1. 한 브랜드 내에서만 구매해야하는 줄 알았다. -> A브랜드 package + B브랜드 single로 구매해서 더 싼 경우 발생
2. 여러 브랜드도 고려해서 구매. 기타줄 개수 맞춰서 6의 배수인 경우 min(package_price)x몫, 아닌 경우에는 min(package_price)x몫 + min(single_price)x나머지로 append -> 개수 맞춰사지 않고, 패키지로만 구매해서 필요한 기타줄보다 더 구매해도 싼 경우가 발생
3. (최종) 여러 브랜드 고려해서 기타줄 맞춰서 구매한경우 + 패키지로 구매한 경우 모두 고려해준다. 1번의 brand 입력에 대해서 (나누어 떨어질 때 패키지로 구매한 경우, 나누어 떨어지지 않을 때 패키지로만 구매한 경우, 개수 맞춰서 패키지+single로 구매한 경우, 모두 낱개로 구매한 경우) 총 4개의 price를 append시킨다.

정답 코드

"""
https://www.acmicpc.net/problem/1049
"""
N, M = map(int,input().split())
pack = []
single = []
prices = []

for _ in range(M):
    a,b = list(map(int,input().split()))
    pack.append(a)
    single.append(b)
    if N%6 == 0:
        prices.append(min(pack)*(N//6)) 
    else:
        prices.append(min(pack)*(N//6)+min(single)*(N%6))
        prices.append(min(pack)*(N//6+1))
    prices.append(min(single)*N)

print(min(prices))

문제 풀이

일단 계절 별 구현 3차원 tensor 이용해서 풀이 각 나무의 나이를 리스트에 저장해서 햇수를 반복하며 실행

1. 오답입니다 -> 5의 배수가 아닌 5 이상으로 알고 구현, 봄&여름에서 list에서 새로운 list를 이용했는데, remove를 여전히 사용하고 있어서 값의 변동이 있었다.
2. 시간초과 -> 반복문 내에서 동시에 처리할 수 있는 것들은 동시에 처리 ex)봄과 여름, 가을과 겨울은 한 번에 처리할 수 있으므로 한 번의 for문에서 처리, list대신 deque를 사용해서 appendleft()이용 - sort를 매번 해주지 않아도 됨, pypy3로 제출하기..ㅎ

   정답 코드

   """
   https://www.acmicpc.net/problem/16235
   """
   # (r,x)는 graph의 좌표를 직접적으로 의미
   # 양분은 모든 칸에 5씩
   # 봄 : 어린 나무부터 해당 칸의 양분 먹기, 나이만큼 못 먹으면 죽음, 그 후에 나이 +1
   # 여름 : 죽은 나무 -> 양분, 나이//2만큼 추가
   # 가을 : 나이 5이상 나무 번식, 주변 칸에 나무 추가, 벗어나면 X
   # 겨울 : 양분 추가 
   # K년이 지난 후 살아있는 나무 개수
   # 각 칸에 대해 존재하는 나무의 나이를 list에 추가
   # 5이상이 아닌 5의 배수에서 번식
   # 천년테케 통과 못함.. -> 통과
   # 시간초과 해결 
   # ->1. 반복문 중복 최대한 감소, 2. deque()사용,
   # 3.input = sys.stdin.readline사용, 4. pypy3로 제출
   import sys
   from collections import deque
   input = sys.stdin.readline
   N,M,K = map(int,input().split())
   nutr = [[5]*N for _ in range(N)]
   add_nutr = [list(map(int,input().rstrip().split())) for _ in range(N)]
   graph = [[deque() for _ in range(N)] for _ in range(N)] 
   # 그냥 한 행에 대해서 곱해주면 모든 행이 같아지므로
   # for문을 이용해서 독립적으로 생성해줘야함
   for _ in range(M):
    x,y,age = map(int,input().rstrip().split())
    graph[x-1][y-1].append(age)
   def year(graph,nutr):
    dx = [0,0,1,1,1,-1,-1,-1]
    dy = [1,-1,0,1,-1,0,1,-1]
    # spring, summer
    for i in range(N):
        for j in range(N):
            be_nutr = 0
            alive = deque()
            for age in graph[i][j]: # 양분 먹기
                if nutr[i][j]>=age:
                    nutr[i][j] = nutr[i][j] - age
                    alive.append(age+1) # 양분 먹은 나무는 나이+1
                else: # 양분 없어서 죽음
                    be_nutr += age//2
            nutr[i][j] += be_nutr # 죽은 나무 양분화
            graph[i][j] = alive # 나이 먹음
    # fall
    for i in range(N):
        for j in range(N):
            if graph[i][j]:
                for tree in graph[i][j]:
                    if tree%5==0: 
                    # 5이상이 아니라 5의 배수...;;
                        for k in range(8):
                            nx = i+dx[k]
                            ny = j+dy[k]
                            if 0<=nx<N and 0<=ny<N:
                                graph[nx][ny].appendleft(1)
            # winter
            nutr[i][j] += add_nutr[i][j]
    return graph, nutr
   for _ in range(K):
    graph,nutr = year(graph,nutr)
   answer = 0
   for i in range(N):
    for j in range(N):
        answer += len(graph[i][j])
   print(answer)

추가적인 개념 (optional)

시간 단축할 때는 무조건 시간 복잡도 함수를 낮추는 것이 중요하다. 그러나 레벨이 높아질 수록 사소한 차이로 시간초과가 날 수 있다. 실버 때는 시간 복잡도 함수가 달라지면 시간초과여부가 갈렸는데 이 문제는 3n^2, 2n^2에 따라 그 여부가 갈렸다.

😭

문제 풀이

• two pointer로 문제를 푸는 것이 익숙하지 않아서 itertools의 combination을 이용했다 -> 당연하게도 모든 경우를 확인하는 것이니 시간 초과가 발생

• 따라서 two pointer로 문제를 해결하려했다. sorted(list)에서 left, right를 지정하고 비교 대상과 크기를 비교해서 경우에 따라 left += 1, right -= 1로 값을 변화시키며 경우를 탐색하였다.
• testcase가 여러개 주어진다는 것은 확인했지만 실제 테케는 1개만 주어져있어서 처음엔 고려하지 못햇었다 (25%에서 오답처리) -> 여러가지 시도해보았으나 try,except 구문을 이용해서 해결했다.

정답 코드

import sys

input = sys.stdin.readline
# combination 활용 -> 시간초과
# two pointer 사용

while True:
    try:
        hole = (int(input()))*10**7
        n = int(input())
        pieces = sorted([int(input()) for _ in range(n)])
        answers = {}
        left, right = 0, n-1
        while left < right:
            if pieces[left] + pieces[right] < hole:
                left += 1
            elif pieces[left] + pieces[right] > hole:
                right -= 1
            else:
                answers[pieces[right]-pieces[left]] = [pieces[left], pieces[right]]
                break
        if answers:
            print('yes', answers[max(answers.keys())][0], answers[max(answers.keys())][1])
        else:
            print('danger')
    except: # 입력 값이 없는 경우 예외처리하는 방법
        break

추가적인 개념 (optional)

try-except 구문에 대한 이해 -> except에 error의 종류를 기재해서 특정 에러일 때 어떤 행동을 할지 결정할 수 있다. 이번 문제의 경우에는 EOFError였지만 그 외의 error는 발생하지 않았기 때문에 굳이 조건으로 설정하지 않았다.

(ㅎr.....)

문제 풀이

주어진 상자의 x,y 좌표를 이용해서 graph를 만들고 graph가 0일 경우에만 bfs를 실행해서 인접한 영역을 모두 방문처리 한다. 이 때 더 이동할 곳이 없으면 bfs를 종료하고 regions에 +1씩 추가하며 영역의 수를 구한다. bfs내에서 q에 append시킬 때마다 (인접한 영역을 1개 발견할 때마다) cnt를 +1씩 해주면서 해당 영역의 크기를 return한다.

정답 코드

"""
https://www.acmicpc.net/problem/2583
"""
from collections import deque

M, N, K = map(int, input().split())
graph = [[0]*N for _ in range(M)]


def bfs(graph,i, j):
    q = deque()
    q.append((i, j))
    dx = [0, 0, -1, 1]
    dy = [1, -1, 0, 0]
    cnt = 1
    while q:
        y, x = q.popleft() # 좌표이므로
        for k in range(4):
            ny = y+dy[k]
            nx = x+dx[k]
            if (0 <= ny < M) and (0 <= nx < N) and graph[ny][nx] == 0:
                graph[ny][nx] = 1
                q.append((ny, nx))
                cnt += 1
    return cnt


for _ in range(K):
    x1, y1, x2, y2 = map(int, input().split())
    for i in range(y1, y2):
        for j in range(x1, x2):
            graph[i][j] += 1

answer = []

for i in range(M):
    for j in range(N):
        if graph[i][j] == 0:
            graph[i][j] += 1
            answer.append(bfs(graph,i, j))

print(len(answer))
ans = ''
for i in sorted(answer):
    ans = ans + str(i)+' '
print(ans.rstrip())

추가적인 개념 (optional)

마지막에 출력 형태를 맞출 때 join함수를 사용해서 띄어쓰기를 이용해서 list의 내용을 합쳐서 출력하자. ex)

l = [1, 2, 3, 4]
print(' '.join(map(str, l)))

''.join()은 ''안에 이어줄 문자를 넣어준다. 아무것도 안 넣으면 list의 내용 모두 이어서 출력. join()의 괄호에는 list 등의 sequence문자열을 넣어서 사용한다.

좌표와 행렬의 표현 방식이 달라서 범위를 지정하는 데에 있어서 어려움이 있었다. 그리고 graph 탐색할 때 있어서 enumerate를 사용해서 idx를 지정해서 graph의 원소를 출력했는데 그럴필요 없이 그냥 주어진 graph의 크기로 in range(N)을 사용해서 바로 i값을 이용하면 더 편하다.

문제 풀이

bfs를 이용한 연결된 범위 탐색. 나는 visited와 graph를 따로 생각했는데 그냥 한 번에 생각해도되는 문제였다. bfs관련 문제들이 여전히 처음에 시작하는 것이 꺼려지지만 이전보다 많이 이해하고, 도전할 수 있어서 재미도 느끼고 있다.

정답 코드

"""
https://www.acmicpc.net/problem/1012
"""
from collections import deque

# idx에 따라 상하좌우
dx = [0,0,-1,1] 
dy = [1,-1,0,0]

N = int(input())

def bfs(graph, a, b):
    queue = deque()
    queue.append((a,b)) # 현재 위치
    graph[a][b] = 0 # graph에서 방문처리

    while queue:
        x, y = queue.popleft()
        for i in range(4): # 4방향 모두 탐색
            nx = x+dx[i]
            ny = y+dy[i]
            if nx < 0 or nx >=n or ny < 0 or ny >= m: # 범위 넘어서면 그냥 지나간다
                continue
            if graph[nx][ny] == 1:
                graph[nx][ny] = 0 # 방문처리하고
                queue.append((nx, ny)) # 해당 위치 q에 append
    return

for i in range(N):
    cnt = 0
    n, m, k = map(int,input().split())
    graph = [[0]*m for _ in range(n)]

    for j in range(k):
        x, y = map(int, input().split())
        graph[x][y] = 1

    for a in range(n): # 1인 부분 만나면 연결된 부분 탐색(through bfs)
        for b in range(m):
            if graph[a][b] == 1:
                bfs(graph, a, b)
                cnt += 1
    print(cnt)

추가적인 개념 (optional)

import sys를 통해 input = sys.stdin.readline.strip()으로 실행했을 때 런타임에러가 발생했는데 그 이유가 무엇일까? sys.stdin.readline은 python에서 input에서의 시간초과 문제 때문에 종종 사용했었다. -> 아마원인은 strip()에서 있었을 것 같다. 가장 오른쪽의 공백(줄바꿈)만 삭제해주면 에러가 일어나지 않을 것 같다. (아님 여전히 발생함. 이유가 뭘까...)

문제 풀이

그래프는 노드와 간선으로 이루어져있으며 서로 연결된 노드의 그룹 수를 출력하는 문제. 개념 자체가 어려워서 찾아보면서 문제 풀이 진행 dfs와 bfs 중 bfs의 개념 이해 (한 노드에 연결된 노드를 우선적으로 탐색) visited와 link list를 잘 활용할 줄 알아야함. 시간 초과 문제가 있을 수 있기 때문에 import sys, deque를 import해서 input(), popleft()를 사용 -> 시간을 단축시킬 수 있다.

정답 코드

"""
https://www.acmicpc.net/problem/11724
"""
from collections import deque
import sys # 시간초과 발생
input = sys.stdin.readline

def bfs(start, edges, visited): # bfs 정의
    q = deque([start])
    visited[start] = True
    while q: # q가 존재하지 않으면 탐색이 완료된 것으로 반복문 종료
        now = q.popleft()
        for e in edges[now]: # e와 연결된 node는 모두 탐색
            if not visited[e]:
                q.append(e) # 방문하지 않았던 곳이면 해당 node와 연결된 다른 node도 순회하기 위해 q에 append
                visited[e] = True

N,M = map(int, input().split())
edges = [[] for _ in range(N + 1)] # n+1개의 빈 list 정의 (node번호와 idx를 같게하기위해 N+1까지 반복)
for _ in range(M): # node와 연결된 node를 정리한 list
    node1, node2 = map(int, input().split())
    edges[node1].append(node2) 
    edges[node2].append(node1)
    # node1와 node2는 서로 연결되어 있음을 의미

result = 0
visited = [False] * (N + 1) # 방문 여부를 확인하는 list 생성
for i in range(1, N + 1):
    if not visited[i]: # 서로 연결되지 않은 node의 수를 찾는다.
        result += 1 # 연결되지 않았을 때 1씩 추가
        bfs(i, edges, visited)
print(result)

추가적인 개념 (optional)

자료구조의 그래프 단순히 노드와 그 노드를 연결하는 간선을 하나로 모아 놓은 자료 구조로 그래프 중 일부에 트리가 속한다. 정점(node) : 위치라는 개념 간선(edge) : 노드 간의 관계. 노드를 연결하는 선 (link라고도 부름) 노드와 간선 참고

트리 구조 탐색 시 DFS, BFS의 개념을 이해하고, 이를 구현할 줄 알아야 함.

n, m = map(int, input().split())
edges = [[] for _ in range(n + 1)] # 간선을 의미
visited = [False] * (n + 1) # 방문 여부 확인
def bfs(v, edges, visited):
    q = deque([v])
    visited[v] = True
    while q: # q가 존재할 때만
        now = q.popleft() # 왼쪽부터 차례로 방문
        for e in edges[now]: # 여기가 이해가 안가네
            if not visited[e]: # False라면
                q.append(e)
                visited[e] = True # 방문처리

dfs 개념 추가할 것

문제 풀이

국가의 금, 은, 동에 대해 매달 순으로 list.sort(key = x lambda : x = l[0]) 이런 식으로 배열한 후에 rank를 출력하면 되는 간단한 문제 라고 생각했으나 배열을 country.sort(key = lambda x : (x[3],x[2],x[1])) 위와 같이 짜버려서 메달 순서에 따른 list 나열이 잘못되었다. 그러나 예시 코드의 답이 다 맞았어서 오류 찾느라 정말 시간 소모가 많이 걸렸다..

정답 코드

N, K = list(map(int,input().split()))
country = []
for i in range(N):
    medal = list(map(int,input().split()))
    country.append(medal)
country.sort(key = lambda x : (-x[1],-x[2],-x[3])) # 나열 방법 다시 확인
for i in range(N):
    if country[i][0] == K:
        index = i
for i in range(N):
    if country[index][1:] == country[i][1:]:
        print(i + 1)
        break

추가적인 개념 (optional)

country.sort(key = lambda x : (x[3],x[2],x[1])) 이처럼 어떤 list에 다양한 값을 갖는 원소가 있다면 특정 원소를 지정해서 sort할 수 있다. (key값을 이용해서) 이 때, 나열 순서도 정할 수 있다.

문제 풀이

check_p, check_pnum으로 팰린드롬과 소수를 판별하는 함수를 정의한 뒤 두 함수의 return값이 모두 1일 때의 출력을 구했다 이 때 1은 팰린드롬이긴하지만 소수가 아니어서 1일 때는 2로 출력해주는 예외를 적어줘야 한다.(...)

정답 코드

"""
문제 바로가기 https://www.acmicpc.net/problem/1747
"""
def checkp(a:str)->int:
    if a == a[::-1]:
        return 1
    else:
        return 0

def checkpnum(a:int)->int:
    cnt = 0
    for i in range(1,int(a**(1/2))+1):
        if a%i == 0:
            cnt += 1
    if cnt == 1:
        return 1
    else:
        return 0
N = int(input())
i = N
while True:
    if i == 1:
        print(2)
        break
    if checkp(str(i)) == 1 and checkpnum(i) == 1:
        print(i)
        break
    i += 1

추가적인 개념 (optional)

def checkpnum(a:int)->int:
    cnt = 0
    for i in range(1,int(a**(1/2))+1):
        if a%i == 0:
            cnt += 1
    if cnt == 1:
        return 1
    else:
        return 0

소수임을 판단하는 함수로 제곱근을 사용할 때의 범위를 잘 파악해두면 좋다. 함수에서 a : int , -> int는 각각 입력값, 출력값의 타입을 의미하는 것으로 코드의 가독성을 높인다.