728x90 Programming Language Training90 Baekjoon Training #24499 #24499 누적합을 이용하여 풀이를 진행하고자 하였다. 누적합은 itertools module에서 accumulate 함수를 import해와서 사용할 수 있다. accumulate 함수의 작동원리를 살펴보면 다음과 같다. from itertools import accumulate arr = [1, 2, 3, 4, 5] result = accumulate(arr) for sum in result: print(sum) """ output: 1 = 1 3 = 1 + 2 6 = 3 + 3 10 = 6 + 4 15 = 10 + 5 """ 위와 같은 return갑을 내놓는 accumulate 함수를 이용하여 24499번을 풀이하였다. import sys from itertools import accumulate .. 2022. 11. 9. Bubble sort, Insertion sort, Selection sort Bubble Sorting Algorithm 서로 인접한 두 원소를 검사하여 정렬하는 알고리즘이다. 알고리즘의 흐름을 보면 이중 반복문을 통해 안쪽 반복문을 이용하여 0번 인덱스와 1번 인덱스를 비교하고 1번 인덱스와 2번 인덱스를 비교하는 방식으로 i번째 인덱스와 i+1번째 인덱스를 비교한다. 다음으로 바깥 반복문을 수행하려고 보면 마지막 인덱스에는 가장 큰 자료가 도달해있다. 그러면 마지막 인덱스를 제외하고 n-1번째까지 반복문을 진행하면 n-1번째 인덱스에 두번째로 큰 자료가 도착을한다. 따라서 바깥반복문은 j data[j+1]) { temp = data[j+1]; data[j+1] = data[j]; data[j] = temp; } } } } Time complexity Tn = (n-1)+(n-.. 2022. 11. 8. Baekjoon Training #2805 #2805 import sys input = sys.stdin.readline #시간초과 방지 N, M = map(int,input().split()) #나무 수 N, 원하는 나무 길이 M 입력 trees = [int(n) for n in input().split()] #나무들의 길이 입력 def tree_cut(): #기준 길이를 정하는 함수 define standard_len = 0 #기준 길이 0으로 초기화 while True: # 기준 길이를 1씩 늘려주며 반복 standard_len += 1 sum = 0 for i, tree in enumerate(trees): #trees 리스트의 원소를 integer type으로 그대로 입력받기 위해 이용 if tree > standard_len: #tre.. 2022. 11. 5. Baekjoon Training #1753 #1753 문제를 풀기앞서 이번 문제에서는 코드를 작성하기 전에 공부해야하는 내용이 많았다. 우선 이문제는 정점에서 정점으로의 최단거리를 계산하는 문제중 다익스트라 알고리즘을 이용하는 문제였다. 다익스트라 알고리즘은 graph 자료구조에서 우선순위큐를 사용하여 방문하지 않은 노드를 방문하는 방식으로 최단 거리를 계산하는 알고리즘이다. 이에 대한것은 Dijkstra Algorithm 게시물에서 자세하게 다뤘다. import sys import heapq input = sys.stdin.readline #시간초과 방지 INF = 10000000000 #무한을 상징 V,E = map(int, input().split()) #정점, 간선 개수 입력 K = int(input()) #시작 정점 입력 graph = .. 2022. 11. 1. Dijkstra Algorithm Dijkstra Algorithm 다익스트라(Dijkstra) 알고리즘은 graph 자료구조에서 우선순위큐(Priority Queue)를 사용하여 방문하지 않은 노드를 방문하는 방식으로 최단 거리를 계산하는 알고리즘이다. 이를 이해하기 위하여 graph와 Priority Queue의 기본적인 개념을 이해하고 가려고 한다. Graph 그래프는 연결되어있는 원소간의 관계를 표현한 자료구조이다. 아래와 같이 다양한 유형으로 그래프를 분류할 수 있다. Priority Queue 우선순위 큐(Priority Queue)는 들어오는 순서대로 나가는 FIFO(First In First Out)라는 특징을 갖고있는 일반적인 큐(Queue)와는 다르게 우선순위가 높은 데이터가 먼저 나가는 형태의 자료구조이다. 우선순위 .. 2022. 11. 1. Baekjoon Training #1012 #1012 #테스트케이스 개수 t입력 t = int(input()) #crawl 함수 정의 #지렁이가 기어다니며 배추의 해충을 제거하는 과정 정의 def crawl(x, y): #좌우, 상하로 기어다니기 위해 이동 조종키 역할을 하는 searchx,y list searchx = [1, -1, 0, 0] searchy = [0, 0, 1, -1] #좌우, 상하로 기어다니는 반복문 for i in range(4): cx = x + searchx[i] cy = y + searchy[i] #기어가는 위치가 밭의 크기를 넘지 않도록 함 if(0 2022. 10. 1. Baekjoon Training #1992 #1992 #n by n pixel의 video를 압축하는 문제 #pixel수를 결정할 n을 입력받는다. n=int(input()) #2차원 list를 입력받는다. video=[list(map(int, input())) for k in range(n)] #압축기 compressor 함수를 정의한다. def compressor(x, y, n): #parameter는 x,y좌표, n이다. pixel = video[x][y] #특정좌표의 값을 pixel값으로 설정 #pixel의 오른쪽과 아래쪽으로 퍼져나가며 조사를 진행한다. for i in range(x, x+n): for j in range(y, y+n): #조사한 부분중 pixel과 일치하지 않는 값이 존재하면 pixel을 -1로 설정 if pixel !.. 2022. 9. 27. Baekjoon Training #1543 #1543 word = str(input()) search = str(input()) #문자열과 찾고자하는 타겟 문자열을 입력받는다. count = 0 i = 0 #카운터 역할을 할 count와 i를 0으로 초기화해놓음 while i 2022. 9. 26. Baekjoon Training #1449 #1449 #물이 새는 곳의 개수 n과 테이프의 길이 l을 입력받음 n,l = map(int,input().split()) #물이 새는 위치인 pos를 list에 입력받음 pos = list(map(int,input().split())) #물이 새는 위치가 정렬이 안되어있을 수 있으니 정렬을 해줌 pos.sort() #양옆으로 0.5만큼 커버해야하니 start를 pos[0]보다 0.5만큼 왼쪽으로 잡음 start = pos[0] - 0.5 count = 1 #카운터 설정(테이프 개수) #for문 이용하여 그리디 알고리즘 실행 for i in range(1, len(pos)): #기존의 테이프로 다음 새는 곳이 커버가 된다면 새로운 테이프 이용 if start + l >= pos[i] + 0.5: cont.. 2022. 9. 26. 이전 1 ··· 4 5 6 7 8 9 10 다음 728x90
