3460번

내 풀이

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

for i in n:
    result = list(map(int,reversed(bin(i)[2:])))
    for j in range(len(result)):
        if result[j] ==1:
            print(j,end=' ')
        else:
            continue
    print()

bin() 함수는 이진수 문자열을 반환하는 함수이다.
정수가 담긴 리스트로 안바꿔도 되고 join함수 이용해서 문자열로 바로 사용해도 됨.

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

for i in n:
    result = ''.join(reversed(bin(i)[2:]))
    for j in range(len(result)):
        if result[j] =='1':
            print(j,end=' ')
        else:
            continue
    print()

아님 reversed안쓰고 리스트 슬라이싱 사용해도 됨

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

for i in n:
    result = bin(i)[2:]
    for j in range(len(result)):
        if result[-j-1] =='1':
            print(j,end=' ')
        else:
            continue
    print()

2309번

array = []
for _ in range(9):
    array.append(int(input()))
over = sum(array)-100

for i in range(9):
    if over-array[i] in array[i+1:]:
        num1 = array[i]
        num2 = over-array[i]
        array.remove(num1)
        array.remove(num2)
        break
        
array.sort()
for i in range(7):
    print(array[i])

리스트의 총 합에서 100을 뺀 값을 over로 하고 두 수를 합쳐서 over과 같은 경우를 구함.
처음에는 array.pop()를 사용했는데 pop에는 인덱스가 들어가야하고 인덱스 구하기가 복잡함.

 idx = array.index(over-array[i])
        array.pop(idx)
        array.pop(i)

리스트에서 원소 제거할때는 remove 사용하는게 편하다!
다른 사람들 풀이

list = [int(input()) for i in range(9)]

total = sum(list)

for i in range(9):
    for j in range(i+1,9):
        if 100 == total - (list[i] + list[j]): 
            num1,num2=list[i],list[j]

            list.remove(num1)
            list.remove(num2)
            list.sort() # 오름차순 정리

            for i in range(len(list)):
               print(list[i])
            break

    if len(list)<9:
        break

한줄로 리스트 안에 입력값들 넣는게 좋아보임.

2581

소수 구간합 구하는 문제.

import math
m = int(input())
n = int(input())
array = []
def is_prime_num(x):
    if x <=1:
        return False
    for i in range(2,int(math.sqrt(x))+1):
        if x%i == 0:
            return False
    return True

for i in range(m,n+1):
    if is_prime_num(i):
        array.append(i)
if len(array) >0:
    print(sum(array))
    print(min(array))
else:
    print(-1)

나는 return을 사용하는게 편해서 함수를 사용했는데 백준 채점을 해보니 함수를 사용하는거나 그냥 함수 바깥에서 쓰는거나 수행시간은 차이가 없었다. sqrt()로 나누는 횟수를 줄이니 실행시간이 636ms에서 80으로 큰 폭으로 줄었다.

14888번

연산자 끼워넣기 문제

import sys
input  = sys.stdin.readline

maxv = -sys.maxsize-1
minv = sys.maxsize
n = int(input())
num_list= list(map(int,input().split()))
a,b,c,d = map(int,input().split())

def cal(num,idx,add,sub,multi,div):
    global n, maxv,minv
    if idx ==n:
        maxv = max(num,maxv)
        minv = min(num,minv)
        return 
    else: 
        if add: 
            cal(num+num_list[idx], idx+1, add-1, sub,multi,div)
        if sub: 
            cal(num-num_list[idx], idx+1, add, sub-1,multi,div)
        if multi: 
            cal(num*num_list[idx], idx+1, add, sub,multi-1,div)
        if div: 
            cal(int(num/num_list[idx]), idx+1, add, sub,multi,div-1)


cal(num_list[0],1,a,b,c,d)
print(maxv)
print(minv)

순열을 이용해서 풀수도 있지만 재귀함수 이용하는게 더 빠르다.
sys.stdin.readline을 쓰면 실행속도 좀 더 빨라짐
sys.maxsize를 이용하는 이유는 들어가는 값이 1e9처럼 값을 정해놓으면 그것보다 큰 값이 들어가는 경우가 있기때문에 더 안전함.
이렇게 할 경우 모든 경우의 수가 계산되는데 파이썬은 위에서부터 순서대로 계산하고 재귀함수를 실행했을때 계산 다 끝날때까지 다음 라인으로 넘어가지 않음.
예로
3
3 4 5
1 0 1 0
넣으면 1 0 1 0이 if문 하나씩 조건 비교하면서 add 실행하고 같은 값으로multi도 실행하게 되면서 모든 경우의 수 계산하게 되는거다.

1700번

from collections import Counter

n,k = map(int,input().split())
array = list(map(int,input().split()))
dict = Counter(array)
count = 0
plug = []
def full(stack):
    if len(stack) >=n:
        return True
    return False

for i in array:
    if not full(plug) and i not in plug:
        plug.append(i)
    elif full(plug) and i not in plug:
        min = plug[0]
        for j in range(len(plug)):
            if dict[plug[j]] < dict[min]:
                min = plug[j]
        plug.remove(min)
        plug.append(i)
        count+=1
    else:
        continue
print(count)

내 풀이는 사용 횟수가 가장 적은 플러그를 먼저 뽑는 식으로 진행하게 만들었는데 오답이 나왔다. 인덱스를 구해서 가장 나중에 쓰이는 플러그를 먼저 뽑는것으로 해야한다.

n,k = map(int,input().split())
kind = list(map(int,input().split()))
cnt = 0
plug = []

for i in range(k):
    if kind[i] in plug:
        continue
    if len(plug) < n:
        plug.append(kind[i])
        continue
    idxs= []
    for j in range(n):
        try:
            idx = kind[i:].index(plug[j])
        except:
            idx = 101
        idxs.append(idx)

    plug_out = idxs.index(max(idxs))
    del plug[plug_out]
    plug.append(kind[i])
    cnt+=1

print(cnt)

출처: 알파이리즘

1303번 전투

from collections import deque

dx = [1, 0, -1, 0]
dy = [0, 1, 0, -1]
n, m = map(int, input().split())
graph = [list(input()) for _ in range(m)]
visited = [[False] * n for i in range(m)]

def bfs(x,y,color):
    queue = deque([(x,y)])
    tmp = 0
    while queue:
        x,y = queue.popleft()
        if graph[x][y] == color and not visited[x][y]:
            tmp+=1
            visited[x][y] = True
        for i in range(4):
            nx = x+dx[i]
            ny = y+dy[i]
            if nx>=m or nx<0 or ny>=n or ny<0:
                continue
            if graph[nx][ny] == color and not visited[nx][ny]:
                tmp+=1
                visited[nx][ny] = True
                queue.append((nx,ny))
    return tmp

white,blue= 0,0
for i in range(m):
    for j in range(n):
       if graph[i][j] == 'W' and not visited[i][j]:
           white +=bfs(i,j,'W') **2
       elif graph[i][j] == 'B' and not visited[i][j]:
           blue+=bfs(i,j,'B')**2

print(white,blue)
            

2178번 미로탐색

from collections import deque

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

n,m = map(int,input().split())
array = []
for i in range(n):
    arr = list(map(int,input()))
    array.append(arr)

def bfs(x,y):
    queue = deque([(x,y)])
    while queue:
        x,y = queue.popleft()
        for i in range(4):
            nx = x+dx[i]
            ny = y+dy[i]
            if nx>=n or nx<0 or ny>=m or ny<0:
                continue
            if array[nx][ny] ==0:
                continue
            if array[nx][ny] == 1:
                array[nx][ny] = array[x][y]+1
                queue.append((nx,ny))
    return array[n-1][m-1]
    

print(bfs(0,0))

2805번 나무 자르기

import sys
input = sys.stdin.readline
    
n,m = map(int,input().split())
array = list(map(int,input().split()))
start = 0
end = max(array)
result = 0
while start<=end:
    total = 0
    mid = (start+end)//2
    for i in array:
        if i>mid:
            total+=i-mid
    if total < m:
        end = mid-1
    else:
        result = mid
        start = mid+1
print(result)

이코테에 있는 떡볶이 떡 자르기와 같은 문제다. 이진탐색도 마찬가지로 값을 찾아내는 것은 쉬워도 최적화에 사용하려면 헷갈린다. 여기서는 나무의 길이가 요청받은 최소길이 m보다 작아지면 안되므로 그런 경우에는 값을 저장하지 않고 total의 길이가 m보다 크거나 같은 경우에만 저장한다. while문 내에서 과정을 반복할수록 정답에 가까운 값이 저장된다.

1463번 1로 만들기

모든 경우의 수에 대해서 연산하고 그 값을 저장해 둔 다음에 가장 작은 수로 갱신하기 위해서 BFS를 써 봤다. 답은 잘 나오지만 시간초과 판정을 받았다. 사실 dp테이블은 반복되는 연산을 안 하기 위해서 있는건데 이렇게 하면 의미가 없다. 지금은 그냥 값 저장용으로 사용되고 있다. 예를 들어서 1을 빼는 연산은 수가 3이나 2로 나눠지든 안 나눠지든 계속되고 있기 때문에 모든 수에 대해 입력값에서 해당하는 수 까지의 1을 뺀 횟수를 계산하고 비교연산하고 있다. time함수를 통해서 시간을 재 보면 26만 넣어도 1.2초의 수행시간이 걸린다.. 이렇게 모든 경우의 수를 잴 수 없는 경우에는 DP테이블의 값을 활용하여 계산해야한다.

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

n = int(input())
INF = int(1e9)
cnt = 0
dp = [INF]*(n+1)
queue = deque([(n,0)])
result = 0
while queue:
    x,cnt = queue.popleft()
    if x ==1 :
        result = dp[1]
    if x%2 == 0:
        queue.append((x//2,cnt+1))
        dp[x//2] = min(dp[x//2],cnt+1)
    if x%3 == 0:
        queue.append((x//3,cnt+1))
        dp[x//3] = min(dp[x//3],cnt+1)
    if x>1:
        queue.append((x-1,cnt+1))
        dp[x-1] = min(dp[x-1],cnt+1)

print(result)

DP를 통한 풀이

n= int(input())

d = [0]*(n+1)

for i in range(2,n+1):
    d[i] = d[i-1] +1
    if i%2 == 0:
        d[i] = min(d[i],d[i//2]+1)
    if i%3 == 0:
        d[i] = min(d[i],d[i//3]+1)

print(d[n])

Bottom-up방식을 통한 풀이다. 작은 수부터 시작해서 그 수를 만들기까지의 최소 횟수를 구해서 n까지의 값을 구한다.
작은 문제를 하나씩 풀어서 큰 문제를 풀 수 있거나 연산횟수가 너무 많은 것 같은 경우에는 bottomup 방식으로 문제를 풀 수 있는지 먼저 생각해봐야 할 것 같다. 값을 저장만 한다고 dp방식인것이 아니다. 저장한 값을 다음 연산에 사용해서 dp다.

XOR 연산

result = [0,0]
v =[[1,2],[1,3],[2,3]]
for i in range(2):
    result[i] = v[0][i] ^ v[1][i] ^ v[2][i]
print(result)

xor연산으로 3가지 값 중에서 1가지 값만 다르다면 다른 하나를 반환한다. 서로 다 다르다면 합한 값을 반환한다.