728x90 Programming Language Training/Python73 Baekjoon Training #2579 #2579 계단 오르기 #계단 수 입력 n = int(input()) #계단 세팅 stair = [0]*301 for i in range(n): stair[i] = int(input()) #점수를 담아둘 리스트 point_set = [0]*301 #1칸인 경우 point_set[0] = stair[0] #2칸인 경우 point_set[1] = stair[0]+stair[1] #3칸인 경우 point_set[2] = max(stair[0]+stair[2], stair[1]+stair[2]) #4칸이상인 경우 for i in range(3, n): #n-3칸까지의 최대값과 최종 두계단의 합과 n-2칸까지의 합과 최종 계단 둘중 큰 값을 point_set[n]에 저장 point_set[i] = max(poin.. 2023. 1. 31. Baekjoon Training #9461 #9461 파도반 수열 나의 풀이 num_list=[1,1,1,2,2] n = int(input()) for i in range(n): a = int(input()) for j in range(len(num_list), a): new_num=num_list[j-1]+num_list[j-5] num_list.append(new_num) print(num_list[a-1]) 파도반 수열이라는 것이 무엇인지 몰라서 그림에서 규칙을 찾았다. n번째 삼각형의 변이 n-1번째 삼각형과 n-5번째 삼각형과 맞다아 있어서 P(n) = P(n-1) + P(n-5)라는 식을 이끌어내었고 그것을 기반으로 코드를 작성하였다. 소스코드의 흐름을 보자면 이미 구성된 num_list의 길이 이후부터 고려하여 목표값까지 P(n)을 .. 2023. 1. 29. Baekjoon Training #1446 #1446 지름길 import heapq import sys input = sys.stdin.readline INF = int(1e9) #다익스트라 알고리즘 기본 함수 이용 def dijkstra(start): queue = [] distance[start] = 0 #시작 값은 0으로 설정 heapq.heappush(queue,(0,start)) #시작 노드부터 탐색 while queue: #queue에 남은 노드가 없으면 반복문 종료 cur_distance, cur_destination = heapq.heappop(queue) #탐색할 노드와 거리 가져옴 #현재 거리가 기존의 거리보다 크면 고려하지 않음 if cur_distance > distance[cur_destination]: continue f.. 2023. 1. 27. Baekjoon Training #1620 #1620 List 이용한 풀이 import sys input = sys.stdin.readline n, m = map(int,input().split()) pkm_list=[] for i in range(n): pkmon=input() pkm_list.append(pkmon) for i in range(m): ans=input() if ans in pkm_list: print((pkm_list.index(ans))+1) else: print(pkm_list[int(ans)-1]) 처음에는 list를 이용하여 해결하려고 했다. 우선 포켓몬들을 입력받고 문제가 포켓몬을 물어보면 list에 존재할 것이니 그 인덱스를 찾아서 1을 더해서 번호를 출력해주고 번호를 물어보는 경우에는 list에 존재하는 내용이 아.. 2023. 1. 26. Baekjoon Training #15650 #15650 #N,M 입력 N,M=map(int,input().split()) #빈 리스트 만들어둠 s = [] #dfs기반의 함수 def dfs(start): #s의 길이가 M이되면 입력중지하고 출력해줌 if len(s) == M: print(' '.join(map(str,s))) return #s의 길이가 M이 아닌경우 N회 반복 for i in range(start, N + 1): #시작점을 start로 설정 if i in s: #이미 존재하는 수인 경우 넘어감 continue s.append(i) #리스트에 수 입력 dfs(i+1) #시작점을 한칸 미뤄서 재귀호출 s.pop() #재귀호출 종료되면 제거 dfs(1) #함수실행 지난 글에서 백트래킹 연습을 더하보려고 했던게 생각나서 한문제 더 풀어보.. 2023. 1. 21. Baekjoon Training #2751 #2751 import sys input=sys.stdin.readline n=int(input()) num_list=[] for i in range(n): x=int(input()) num_list.append(x) num_list.sort() for i in range(n): print(num_list[i]) 파이썬 내장함수인 sorted를 사용하려하니 시간초과가 발생하는 문제가 존재하였다. 이를 해결하기 위해서는 몇몇 방법이 존재한다. 우선 내장함수 대신 성능이 좋은 sorting algorithm을 이용하는 것이다. 그러나 이는 간단한 문제가 아니고 c++ 공부중에 다양한 sorting algorithm을 다뤄봤으니 python 버전으로 다시 공부할때 작성해보도록 하고 조금 더 합리적이고 간단한 .. 2023. 1. 21. Baekjoon Training #15649 #15649 백트래킹 알고리즘에 대해서 공부하기 위해서 문제들을 풀어보고자하는데 우선 백트래킹 알고리즘은 DFS 방식을 기반으로 불필요한 경우를 배제하며 정답을 탐색하는 전략이다. DFS를 기반으로 하기 때문에 stack을 이용하여 퇴각을 하면서 다음 탐색을 진행하기 때문에 백트래킹이라고 불린다. #N,M 입력 N,M=map(int,input().split()) #빈 리스트 만들어둠 s = [] #dfs기반의 함수 def dfs(): #s의 길이가 M이되면 입력중지하고 출력해줌 if len(s) == M: print(' '.join(map(str,s))) return #s의 길이가 M이 아닌경우 N회 반복 for i in range(1, N + 1): if i in s: #이미 존재하는 수인 경우 넘어감.. 2023. 1. 15. Baekjoon Training #2178 #2178 미로 탐색 #deque class를 collections module에서 import from collections import deque N, M = map(int, input().split()) maze = [list(map(int, input())) for _ in range(N)] def bfs(maze, start): queue = deque([start]) #행의 개수 (세로 길이) n = len(maze) #열의 개수 (가로 길이) m = len(maze[0]) #전체 좌표의 distances값을 -1 default값으로 설정 distances = [[-1 for _ in range(m)] for _ in range(n)] distances[start[0]][start[1]] = .. 2023. 1. 10. Baekjoon Training #2563 #2563 n = int(input()) #색종이 수 입력 num_list = [[0] * 100 for _ in range(100)] #0으로 채워진 100 by 100 2차원 배열 생성 for _ in range(n): #색종이 수 만큼 반복 x,y=map(int,input().split()) #색종이의 좌하단 점 입력 #색종이의 좌하단 점으로부터 우상단으로 10 by 10 색종이가 걸치는 좌표의 값을 1로 설정 for i in range(10): for j in range(10): num_list[x+i][y+j] = 1 ans = 0 #결과 값을 0으로 세팅 #열을 기준으로 값이 1인 좌표들을 counting하여 그 수만큼 ans에 더해줌 for a in num_list: ans+=a.count(.. 2023. 1. 7. 이전 1 2 3 4 5 6 7 8 9 다음 728x90
