본문 바로가기
[백준][파이썬] 11726 2Xn 타일링 num = int(input()) numlist= [2,3] for i in range(2,num-1): tem1 = i-2 tem2 = i-1 tem = numlist[tem1]+numlist[tem2] numlist.append(tem%10007) if num == 2: print(2) elif num == 1: print(0) else: print(numlist[-1]) 다이나믹 프로그래밍 문제이다. 피보나치 수열이지만, 문제를 보고 바로 피보나치 수열이라는것을 파악하진 못했다. 결국 다이나믹 프로그래밍 문제는 규칙을 찾는것이 중요하다. 메모리를 아끼려면, 리스트에 저장을 안하고 구해도 괜찮을것 같다. 중요한점은 10007을 매번 나눠주어야 한다는 것이다. num ==1일때 print(1)로 해야한다. 2020. 7. 21.
[백준][파이썬] 1463번 1로 만들기 다이나믹 프로그래밍의 기본 문제다. 핵심은 "한번만 연산" 한다는 것이다. 탐색이나 bf 로도 풀 수 있겠지만 문제 특성상 반복되는 부분이 많고 이러한 반복되는 부분을 중복 계산 하지 않기 위해서 다이나믹 프로그래밍을 한다. cnt리스트에 100000을 붙인 이유는 나누기3 나누기2 마이너스1 중에서 해당사항이 없는 요소는 min에 값이 포함시키지 않기 위해서이다. 너무 오랜만에 파이썬으로 풀어서 문법이 헷갈릴 정도였다. 시험도 끝났으니 앞으로 매일 1~2문제씩은 꾸준히 열심히 푸는것을 목표로 해야겠다. num = int(input()) cnt = [100000] + [0 for i in range(num)] for i in range(2,num+1): div3 = 0 div2 = 0 if i % 3 =.. 2020. 7. 19.
[SW테스트 기출][파이썬] 13458 시험감독 브론즈2 로 아마 역량테스트 중에 가장 쉬운 문제일것같다. 하지만.. 시간초과 가 났다. while문 대신 나누기로 바꿔서 해결했다. num = int(input()) nums = list(map(int,input().split())) b, c = map(int,input().split()) count = 0 for i in nums: count +=1 mans = i - b if mans >0: if mans % c == 0: count += mans//c else: count += (mans//c)+1 print(count) 2020. 5. 2.
[SW 역량테스트 기출][파이썬] 14499번 주사위 굴리기 삼성 역테 문제 테트로미노(?) 랑 유사한 부분이 있다. 삼성역테는 많은 경우의 수를 직접 해야하지만, 그것을 좌표화 시켜서 빠르게 처리하는 능력을 보는 문제들 있는거 같다. 주사위 굴리기 문제도 처음에 접근했을떄 그 상황마다 모두 고려하며 코드를 짜려고 했다. 하지만 그렇게 되면, 코드가 더러울 뿐만 아니라, 하다가 너무 많아서 포기하게 된다. 하지만 밑 처럼 다음 이동을 좌표화 시켜서 푼다면 편하다. 다른 문제들에서도 상황상 복잡해 보인다면 좌표화 시키는 것을 활용해보자! from collections import deque n,m, x,y,num = map(int,input().split()) map1 = [] for _ in range(n): a = list(map(int,input().split.. 2020. 5. 2.
[백준][파이썬] 3190 :뱀 [핵심] 1. 뱀의 형태를 deque로 저장하기 처음에 True false 맵으로 뱀의 상태를 저장하려 했으나, 뱀의 움직임을 고려하는것이 매우 복잡했다. FIFO 이러한 형태의 문제를 잘 기억할것 2. if 와 elif는 다르다. if와 elif의 차이를 정확히 기억하자(이것때매 오류 발생) -다시 검토하고 싶을 땐 if 두번 -다시 검토 아닐때 if , eilf 3. time을 언제줄지도 중요! from collections import deque num = int(input()) map1 = [[0 for i in range(num)] for j in range(num)] gogo = deque() capple = int(input()) # 사과의 수 #dchange = [] # 사과 저장 for .. 2020. 4. 28.
[백준][파이썬] 벽 부수고 이동하기 2 import sys from collections import deque n,m,chance = map(int,sys.stdin.readline().split()) map1 =[] for i in range(n): tt = list(sys.stdin.readline()) map1.append(tt) dx = [0,0,-1,1] dy = [1,-1,0,0] def go(stack): while stack: x,y,dim = stack.popleft() for i in range(4): X = x+dx[i] Y = y+dy[i] if 0 2020. 4. 14.
[백준][파이썬] 2206 벽 부수고 이동하기 - 메모리초과 BFS문제이지만 기존의 문제들과는 조금의 차이가 있다. 벽을 뚫을수 있다는 것을 체크해줘야한다. 1. 벽 뚫기를 위해 [x,y, 횟수] 이런식으로 저장을 해준다. 2. visited를 활용할때 주의할 점은 벽 안뚫기 / 벽 뚫었을때 따로 방문여부를 체크해줘야한다 (만약에 체크해주지 않으면, 벽뚫 vs 안뚫 이 만났을 때 오류가 생긴다 3. 메모리초과를 해결하지 못했다..... import sys import collections n, m = map(int,sys.stdin.readline().split()) map1 = [list(map(int,[*input()])) for k in range(n)] def recu(stack): stack.append([0,0,0]) cnt = 1 while stack.. 2020. 4. 13.
[백준][파이썬] 16768 Mooyo Mooyo [핵심] 1. gravity함수 letsdel 함수 n, k = map(int,input().split()) map1 = [] for i in range(n): tt = list(input()) map1.append(tt) #str로 저장한거 기억하기 def gravity(map1): #중력 temto = [] temchange = [] for i in range(10): #열마다 tem = [] for j in range(n):#숫자저장 if map1[j][i] != "0": tem.append(map1[j][i]) for k in range(n-len(tem)): #뒤에 0채워주기 tem.insert(0,"0") temto.append(tem) for i in range(n): #행열 바꿔주기 tem.. 2020. 4. 8.
[백준][파이썬] 3055번 탈출 -BFS 기본적인 BFS 문제에서 조금의 변형이 들어간 문제다. 처음 활용된 것은 물이라는 장애물도 퍼져나간다는것이다. 물 -> 길 ->물 ->길을 while안에서 활용했다 -항상 특정지점의 주변 모두를 한턴에 체크(FALSE)할때는 for(len(stack))구조로 활용해 주면 된다. -추가적으로 최단거리를 세기 위해서는 다른 리스트를 하나 더 만들어 수를 파악해주면 된다 import sys import collections n,m = map(int,input().split()) lit =[] ans =0 for i in range(n): tt = list(sys.stdin.readline()) lit.append(tt) dx = [0,0,1,-1] dy = [1,-1,0,0] def bfs(start,wate.. 2020. 4. 7.

티스토리툴바