• 유클리드 호제법을 이용하여 구했다

num1, num2 = map(int, input().split())

# 유클리드 호제법을 사용하여 최대공약수를 구함
def gcd(a, b):    
    remainder = a % b
    while remainder > 0:
        # a와 b의 값을 갱신
        a = b
        b = remainder
        remainder = a % b
    return b

print('1' * gcd(num1, num2))

- 딕셔너리를 이용하여 풀었다

import sys

n = int(sys.stdin.readline())

alphabet_dict = {}
answer = 0
pocket = []

for _ in range(n):
    alphabet = input()
    pocket.append(alphabet)

for alphabet in pocket:
    for i, char in enumerate(alphabet):
        num = 10 ** (len(alphabet) - i - 1)
        if char not in alphabet_dict:
            alphabet_dict[char] = 0
        alphabet_dict[char] += num

alphabet_list = [value for value in alphabet_dict.values() if value > 0]
sorted_list = sorted(alphabet_list, reverse=True)

for i, value in enumerate(sorted_list):
    answer += value * (9 - i)

print(answer)

- bfs를 이용하여 풀었다.

from collections import deque
import sys
input = sys.stdin.readline # 인풋 입력시간 줄이기

N,M = map(int,input().split())
arr = [list(input().rstrip()) for _ in range(N)]
q = deque([])
result = []

for j in range(N): # 지훈이부터 움직여야되니까 지훈이 위치부터 찾기
    for i in range(M):
        if arr[j][i] == 'J':
            arr[j][i] = 1 # 지훈이는 턴수로 초기화
            q.append([j,i])

for j in range(N):
    for i in range(M):
        if arr[j][i] == 'F':
            q.append([j,i])

def bfs():
    global result, flag

    directy = [-1,1,0,0]
    directx = [0,0,-1,1]

    while q:
        if result != []: # 지훈이가 탈출했다면 bfs 탈출
            break
        y,x = q.popleft()

        for k in range(4):
            dy = directy[k] + y
            dx = directx[k] + x

            if (dy < 0 or dy >= N or dx < 0 or dx >= M) and arr[y][x] != 'F': # 턴이 시작하기전 불이 아닌것이(지훈이) 밖으로 나간다면 result에 값을 넣어줌으로써 탈출여부 확인
                result.append(arr[y][x])
                break # 턴 시작전 탈출이 가능하다면 턴을 진행하지 않음

            if dy < 0 or dy >= N or dx < 0 or dx >= M or arr[dy][dx] == '#': # 배열 밖으로 벗어나거나 벽에 가로막히면 가지 않음
                continue

            if arr[dy][dx] == '.' and arr[y][x] != 'F': # 지나갈수 있는 공간이면서 현재 위치가 불이 아니라면(지훈이) 도착위치에 턴 초기화
                arr[dy][dx] = arr[y][x] + 1
                q.append([dy,dx])

            elif arr[dy][dx] == 'F' or arr[y][x] != 'F': # 현재 위치가 불이 아니면(지훈이) 갈 곳이 없으므로 패스하고, 가야할 위치가 지점이 불이라면 탐색하지않음(중복탐색방지)
                continue

            else: # 걸러지고 남은것들은 전부 불이 이동할 수 있는 위치뿐
                arr[dy][dx] = 'F'
                q.append([dy,dx])
                
bfs()

if result != []:
    print(min(result)) # 탈출이 여러번 된 경우에 가장 빨리 탈출했던것을 출력
else:
    print('IMPOSSIBLE')

놓쳤던 부분

- 불과 지훈이가 움직이는 턴을 하나로 봤어야했는데 같은턴에 가장자리에서 지훈이와 불이 만나게되더라도 지훈이가 먼저 움직여서 탈출로 출력했었다.

- 지훈이가 여러가지 방법으로 탈출이 가능하다는 것을 놓쳤다.

• 유클리드 호제법을 이용해 최대공약수를 구한 뒤, a와 b를 곱한값에 최대공약수를 나눠 최소공배수를 구했다

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

c = a*b

while b > 0: # 유클리드 호제법
    a, b = b, a % b 

print(int(c/a))

• 이동할 수 있는 경우의수가 8가지가 있는데 각각 방문표시를 하며 풀었다

from collections import deque

used = [0] * 100001

A,B,N,M = map(int,input().split())
q = deque([N])
while q:
    tmp = q.popleft()
    if tmp == M:                                   # 해당위치가 목표지점이라면 break 
        result = used[tmp]
        break
    if tmp - 1 >= 0 and used[tmp - 1] == 0:
        used[tmp - 1] = used[tmp] + 1
        q.append(tmp - 1)
    if tmp + 1 <= 100000 and used[tmp + 1] == 0:
        used[tmp + 1] = used[tmp] + 1
        q.append(tmp + 1)
    if tmp - A >= 0 and used[tmp - A] == 0:
        used[tmp - A] = used[tmp] + 1
        q.append(tmp - A)
    if tmp - B >= 0 and used[tmp - B] == 0:
        used[tmp - B] = used[tmp] + 1
        q.append(tmp - B)
    if tmp + A <= 100000 and used[tmp + A] == 0:
        used[tmp + A] = used[tmp] + 1
        q.append(tmp + A)
    if tmp + B <= 100000 and used[tmp + B] == 0:
        used[tmp + B] = used[tmp] + 1
        q.append(tmp + B)
    if tmp * A <= 100000 and used[tmp * A] == 0:
        used[tmp * A] = used[tmp] + 1
        q.append(tmp * A)
    if tmp * B <= 100000 and used[tmp * B] == 0:
        used[tmp * B] = used[tmp] + 1
        q.append(tmp * B)


print(used[tmp])

왜 틀렸을까 ?

• 인덱스에러, 문제에선 10만번까지 갈 수 있는데 if문에서 100001까지 범위를 지정하여 인덱스에러가 났었다.

• bfs(Flood Fill)을 이용하여 풀었다.

from collections import deque

N,M = map(int,input().split())
flag = "NO"												# flag값 설정
arr = [list(map(int,input())) for _ in range(N)]

def bfs(j,i):

    global flag
    q = deque([(j,i)])

    directY = [-1,1,0,0]
    directX = [0,0,-1,1]

    while q:
        y,x = q.popleft()

        for k in range(4):
            dy = directY[k] + y
            dx = directX[k] + x

            if dy < 0 or dy >= N or dx < 0 or dx >= M:  # 범위를 벗어난다면 continue
                continue
            if arr[dy][dx] == 0 and (dy == N-1):        # bfs를 돌다 제일 아래 쪽(inner side)에 도착하게 되면 flag 값 변경
                flag = "YES"
                arr[dy][dx] = 1
                q.append([dy,dx])
            elif arr[dy][dx] == 0:
                arr[dy][dx] = 1
                q.append([dy,dx])


for i in range(M):
    if arr[0][i] == 0:              # 침투가 가능한 제일 위쪽 (outer side)만 탐색하여 0이라면 함수 실행
        arr[0][i] = 1
        bfs(0,i)

print(f"{flag}")

왜 틀렸을까?

• bfs 함수에 들어가기전 if문 조건에 오타가 있었다. if arr[0][i] == 1: 로 잘못 입력했었는데도 채점이 50%이상 진행되어서 이쪽 부분을 다시 볼 생각을 못했다. 

- BFS를 3차원배열을 이용하여 풀었다

import sys
from collections import deque

directZ = [0,0,0,0,1,-1]
directY = [-1,1,0,0,0,0]
directX = [0,0,-1,1,0,0]

while True:
    mat = []
    L, R, C = map(int,input().split())

    if L + R + C == 0:
        break

    for i in range(L):
        arr = []
        for j in range(R):
            tmp = list(input())
            arr.append(tmp)
        space = input()
        mat.append(arr)

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

        while q:
            zz,yy,xx = q.popleft()

            for k in range(6):
                dz = directZ[k] + zz
                dy = directY[k] + yy
                dx = directX[k] + xx

                if dy >= R or dy < 0 or dx >= C or dx < 0 or dz >= L or dz < 0:
                    continue                                    # 배열의 범위를 벗어나면 continue
                if mat[dz][dy][dx] == 'E':
                    q = []
                    return mat[zz][yy][xx] + 1                  # E를 만나면 해당하는 숫자값 리턴

                elif mat[dz][dy][dx] == '.':                    # 갈 수 있는 길이라면 출발점의 +1을 해줌
                    q.append([dz,dy,dx])
                    mat[dz][dy][dx] = mat[zz][yy][xx] + 1

    for i in range(L):
        for j in range(R):
            for k in range(C):
                if mat[i][j][k] == 'S':                         # 3차원 배열을 돌다 S를 만나면 시작
                    mat[i][j][k] = 0
                    result = bfs(i,j,k)                         # bfs의 return값을 result에 저장

    if result != None:
        print(f"Escaped in {result} minute(s). ")
    else:
        print('Trapped!')

• 용액들을 정렬 한 뒤 투 포인터 알고리즘을 통해 0에 가까운 용액들이 나올 때 마다 a,b에 값을 갱신 한 뒤 마지막에 출력을 해주었다.

target = 21e8
N = int(input())
arr = list(sorted(map(int,input().split())))       
start, end = 0, N-1

while end > start:                                  # start가 end보다 작을 떄 까지만 진행
    
    tmp = arr[start] + arr[end]                     # tmp에 두 용액의 합을 저장

    if abs(target) > abs(tmp):                      # 용액의 합이 0에 가깝다면
        target = abs(tmp)                           # target과 a,b를 갱신 시켜줌
        a,b = arr[start],arr[end]                   
        if abs(arr[start]+arr[end-1]) > abs(tmp):   # end 인덱스를 줄였을 때 두 용액의 계산 값이 tmp값 보다 크다면 start 인덱스를 올려줌
            start += 1
        else:
            end -= 1
    else:
        if abs(arr[start]+arr[end-1]) > abs(tmp):
            start += 1
        else:
            end -= 1

print(a,b)

• bfs를 활용하여 풀었다.

import sys
from collections import deque
input = sys.stdin.readline                  # 입력 시간을 줄이기 위한 코드

N, M = map(int, input().split())
arr = []
q = deque()
Max = 0
for i in range(N):
    tmp = list(map(int, input().split()))
    arr.append(tmp)

for j in range(N):
    for i in range(M):
        if arr[j][i] == 1:                  # 입력을 전부 다 받고 완전탐색을 통해 1이 있다면 그 위치를 q에 추가시켜줌
            q.append([j,i])

def bfs():
    global Max
    directy = [-1,-1,-1,0,0,1,1,1]
    directx = [-1,0,1,-1,1,-1,0,1]

    while q:
        y,x = q.popleft()

        for k in range(8):
            dy = directy[k] + y
            dx = directx[k] + x

            if dy >= N or dy < 0 or dx >= M or dx < 0:
                continue                    # y축과 x축의 인덱스를 벗어난다면 continue
            elif arr[dy][dx] == 0:
                arr[dy][dx] = arr[y][x] + 1 # arr[dy][dx] == 0 이라면 아직 방문하지 않았다는 뜻 이므로 그 위치에 이전 값에 +1을 해줌
                if arr[dy][dx] >= Max:      # Max값을 비교하여 만약 Max값보다 크다면 갱신
                    Max = arr[dy][dx]
                q.append([dy,dx])           # q에 현재 위치를 추가해줌

bfs()

print(Max-1)                                # 출력할 땐 1부터 시작했으므로 1을 빼줘야함

• 2중 for문으로 간단하게 풀 수 있을 것 같지만, 시간제한때문에 투 포인터를 이용해 풀어야되는 문제이다.
• 처음엔 합을 만드는 것이 불가능하다면 0을 출력해야되는걸 놓쳐서 틀렸었고
• while문 빠져나오는 조건을 빼먹어서 시간초과가 났었다.
• 마지막으로는 첫번째 혹은 마지막 인덱스 하나로 목표값보다 컸을 때를 고려하지 않아서 틀렸었다.

N, target = map(int,input().split())
arr = list(map(int,input().split()))
start = 0
end = start+1
answer = 100001                                 # N의 최대길이가 100000이므로

if arr[start] >= target or arr[-1] >= target:   # 첫번째 인덱스 혹은 마지막 인덱스 하나로도 목표값보다 컸을 때의 길이를 저장
    answer = 0
tmp = arr[start] + arr[end]

while True:

    if tmp >= target:                           # 부분합이 목표값보다 컸을 때,
        if answer > end - start:                # 부분합의 길이가 현재의 answer보다 짧다면
            answer = end - start                # answer에 길이값을 저장
        if start + 1 == N - 1:                  # start의 인덱스값이 N-1 보다 커지면 안되므로 브레이크
            break
        tmp -= arr[start]                       # arr[start]의 값을 빼주고 start 인덱스 + 1
        start += 1
    else:
        if end + 1 == N:                        # end의 인덱스값이 N보다 커지면 안되므로 브레이크
            if start + 1 == N - 1:              
                break
            tmp -= arr[start]                   # arr[start]의 값을 빼주고 start 인덱스 + 1
            start += 1                          # end는 N까지 왔어도 start는 N - 1 까지 와야됨
        else:
            end += 1
            tmp += arr[end]                     # arr[end]의 값을 더해주고 end 인덱스 + 1

if answer == 100001:                            # 합을 만드는게 불가능해서 answer에 초기값인 100001이 그대로 있다면
    print(0)
else:
    print(answer + 1)

• 용액들을 정렬 한 뒤 투 포인터 알고리즘을 통해 0에 가까운 용액들이 나올 때 마다 a,b에 값을 갱신 한 뒤 마지막에 출력을 해주었다.

target = 21e8
N = int(input())
arr = list(sorted(map(int,input().split())))       
start, end = 0, N-1

while end > start:                                  # start가 end보다 작을 떄 까지만 진행
    
    tmp = arr[start] + arr[end]                     # tmp에 두 용액의 합을 저장

    if abs(target) > abs(tmp):                      # 용액의 합이 0에 가깝다면
        target = abs(tmp)                           # target과 a,b를 갱신 시켜줌
        a,b = arr[start],arr[end]                   
        if abs(arr[start]+arr[end-1]) > abs(tmp):   # end 인덱스를 줄였을 때 두 용액의 계산 값이 tmp값 보다 크다면 start 인덱스를 올려줌
            start += 1
        else:
            end -= 1
    else:
        if abs(arr[start]+arr[end-1]) > abs(tmp):
            start += 1
        else:
            end -= 1

print(a,b)

• 리스트에서 자신을 제외한 두 수의 합이 x가 되는 경우의 수를 출력하는 문제이다.
• 2중 for문(O(n^2))으로 풀면 시간초과가 나오기에 투 포인터 알고리즘(O(n))을 통해 풀었다. 

import sys
input = sys.stdin.readline      # 입력 시간을 줄이기 위한 코드

N = int(input())
arr = list(sorted(map(int,input().split()))) # 왼쪽과 오른쪽에서 가운데로 오는 투포인터 알고리즘을 쓸 것이기에 정렬을 하고 시작하였다.
target = int(input())
cnt = 0
start, end = 0, N-1

while end > start:              # start와 end가 같아진다면 끝나도록 제한
    tmp = arr[start] + arr[end] # tmp에 두 수의 합을 저장

    if tmp > target:            # tmp가 target보다 크다면 end의 인덱스를 -1
        end -= 1
    else:
        start += 1              # tmp가 target보다 작다면 start의 인덱스를 -1
        
    if tmp == target:           # tmp가 target과 같다면 cnt를 올림
        cnt += 1

print(cnt)

• 처음에 입력을 이해하는데 어려움이 있었다.
• 예제 입력 첫번째 줄에서는 (1,2)를 유니온 두번째 줄에서는 (2,1), (2,3)을 유니온, 세번째 줄에서는 (3,2)를 유니온 해주는 입력이다.
• 마지막 입력에서는 세군데의 보스를 구한 다음에 보스가 모두 같다면 모든 여행 경로를 갈 수 있다는 뜻이므로 YES를 출력하면 된다.

import sys

input = sys.stdin.readline # 입력 시간을 줄이기 위한 코드
sys.setrecursionlimit(10**8) # 재귀를 더 깊게 들어가기 위한 코드

N = int(input())
M = int(input())
arr = [-1] * 201

for i in range(len(arr)):
    arr[i] = i # 리스트를 자신의 번호로 초기화

def findboss(member):

    if arr[member] == member: # 자기 자신이 보스라면 자신을 반환
        return member

    tmp = findboss(arr[member]) # 자신의 보스가 있다면 보스의 보스를 찾아서 반환
    return tmp

def union(a,b):

    fa,fb = findboss(a),findboss(b) # a와 b의 보스를 찾음

    if fa == fb: # 보스가 같다면 리턴
        return

    arr[fb] = fa # 보스가 같지 않다면 b의 보스는 a
    return
for i in range(N):
    route = list(map(int,input().split()))

    for j in range(N):
        if route[j] == 1: # 입력시마다 for를 돌며 1이 있다면 i+1과 j+1을 유니온
            union(i+1, j+1)

plan = list(map(int,input().split()))

tmp = []

for i in range(len(plan)): # 마지막 입력의 개수만큼 돌며 각각의 보스를 tmp에 저장해줌
    tmp.append(findboss(arr[plan[i]]))

if len(set(plan)) == 1: # 만약 보스가 전부 같다면 set을 했을 때 길이가 1일 것이기에 'YES'출력
    print('YES')
else:
    print('NO')

• 같은 집합에 포함되어있는지 확인하려고 할 때 x와 y가 같은 보스를 가지고 있는지 확인하면 되기 때문에 유니온 파인드를 이용해서 풀었다
• flag를 통해 0일 때는 x,y를 유니온 1일 때는 x,y의 보스가 같은지 확인하였다.

import sys
input = sys.stdin.readline # 입력시간을 줄이기 위한 코드
sys.setrecursionlimit(100000) # 재귀를 더 깊게 들어가기 위한 코드

N,M = map(int,input().split())
arr = [-1] * (N+1)

for i in range(N+1):
    arr[i] = i # 리스트를 자기 자신의 번호로 초기화

def findboss(member):

    if arr[member] == member: # 자기 자신이 보스라면 자신을 반환
        return member
    else:
        arr[member] = findboss(arr[member]) # 보스가 있다면 보스의 보스를 찾아서 반환
        return arr[member]

def union(x, y):

    fa, fb = findboss(x), findboss(y)

    if fa == fb: # x와 y의 보스가 같다면 리턴
        return
    else:
        arr[fb] = fa # 보스가 같지 않다면 y의 보스는 x
        return


for i in range(M):
    flag,x,y = map(int,input().split())

    if flag == 0:
        union(x, y)
    else:
        if findboss(x) == findboss(y): # x와 y의 보스를 비교
            print('YES')
        else:
            print('NO')

findboss함수를 원래는 이런식으로 작성했었는데

아래와 같이 코드를 수정하니까 시간초과를 해결할 수 있었다.

 

• 유니온 파인드를 통해 문제를 해결하였다
• findboss함수에 재귀를 돌며 런타임 에러가 발생해 아래와 같은 코드를 추가하였다.

sys.setrecursionlimit(10**6)

import sys
input = sys.stdin.readline # 입력 시간을 줄이기 위한 코드
sys.setrecursionlimit(10**6) # 재귀를 더 깊게 들어가게 하기 위한 코드

M,N = map(int, input().split())
edge = []
arr = [-1] * 500001
answer = 0

def findboss(member):
    if arr[member] == -1: # 자기 자신이 보스라면 자신을 반환
        return member

    tmp = findboss(arr[member]) # 자신이 보스가 아니라면 보스 찾기

    return tmp

def union(a,b):

    fa, fb = findboss(a), findboss(b) # 두 점의 보스 찾기

    if fa == fb: # 만약 두 점의 보스가 같다면 사이클이 발생했다는 뜻
        return 1
    else:
        arr[fb] = fa # 두 점의 보스가 다르다면 a는 b의 보스가 됨


for _ in range(N):
    tmp1,tmp2 = map(int,input().split())
    edge.append([tmp1,tmp2]) # edge 리스트에 그어진 선분을 저장

for i in range(N):
    a, b = edge[i]
    result = union(a, b)
    if result == 1: # 사이클이 발생했다면
        answer = i+1 # answer에 발생한 지점 저장후 break
        break

if answer:
    print(answer)
else:
    print(answer)