Simple Explain

#1517 버블 소트 https://www.acmicpc.net/problem/1517  버블정렬에서 발생하는 swap의 횟수를 구하는 알고리즘이다. 개념을 간단히 설명하면 버블 정렬은, 옆 인덱스와 크기를 비교해서 값의 위치를 찾아가는 형태의 정렬방법이다.따라서, 옆 인덱스와 값을 교환하는 swap이라는 행위가 발생한다.https://gmlwjd9405.github.io/2018/05/06/algorithm-bubble-sort.html [알고리즘] 버블 정렬(bubble sort)이란 - Heee's Development BlogStep by step goes a long way.gmlwjd9405.github.io반만 합병정렬은 분할정복의 접근법으로 정렬을 진행하는 방법이다.https://gmlwj..

#11444 피보나치 수 6 https://www.acmicpc.net/problem/11444 제일 처음 접근했던 방식은, DP를 재귀로 돌리는 형태였다. import syssys.setrecursionlimit(10000)n = int(input())division = 1000000007dp = [0, 1]def find_fibo(n): # print(n) if n 하지만 재귀의 깊이가 너무 깊어졌다. 거의 반 포기상태로 참고자료를 봤고,점화식을 훨씬 더 함축적으로 개선해야함을 느꼈다.  최종적으로 파악한 점화식은 다음과 같다.*출처https://velog.io/@kjy2134/%EB%B0%B1%EC%A4%80-11444-%ED%94%BC%EB%B3%B4%EB%82%98%EC%B9%98-%..

#11660 구간 합 구하기 5 https://www.acmicpc.net/problem/11660  역시 반복문으로 막 푸니까 시간초과가 난다. 과거에 DP를 풀었던 기억을 되내이며 고민했다.2차원으로 DP를 진행하면 된다.  import sysinput = sys.stdin.readlinen, m = map(int, input().split())maps = []dp = []# make dp and store originfor i in range(n): nums = [int(x) for x in input().split()] # store origin maps.append(nums) # make dp tmp = [] if i == 0: idx_0 = nums..

#1238 파티 https://www.acmicpc.net/problem/1238 처음 dfs, bfs를 고민하다가 다익스트라라는 사실을 깨달았다. import heapq, sysINF = sys.maxsize n, m, x = map(int, input().split())maps = [[] for __ in range(n+1)]for _ in range(m): start, dest, weight = map(int, input().split()) # 단방향 도로 maps[start].append([weight, dest])# 다익스트라 돌리기# 전체 -> x 방향,# x -> 전체 방향def dijkstra(n, start): heap = [] heapq.heappush(..

#1753 최단경로 https://www.acmicpc.net/problem/1753 import sysimport heapqINF = sys.maxsizen, e = map(int, input().split())target = int(input())# 0번 인덱스는 사용하지 않음. 1~nmaps = [[] for _ in range(n + 1)]# visited = [[False] * (n + 1) for _ in range(n + 1)]for i in range(e): start, end, weight = map(int, input().split()) # 방향그래프 maps[start].append((end, weight))q = []heapq.heappush(q, (0, target..

#11403 경로찾기 https://www.acmicpc.net/problem/11403  너무 어렵게 생각했다.bfs를 여러번 돌리면 되는데,뭔가 한 번의 함수 실행으로 완벽하게 해결하고 싶어서 더 고민을 했다.  하하하하하하 n = int(input())links = [[int(x) for x in input().split()] for __ in range(n)]# bfsanswer = [[0 for _ in range(n)] for __ in range(n)]def bfs(start): # print(start) q = [start] visited = [0 for _ in range(n)] while q: prev = q.pop(0) for i in r..

#30804 과일탕후루 https://www.acmicpc.net/problem/30804 투포인터가 처음이라서 자료를 참고하면서 했다. 이름만 들었을 때 간단한 개념일 것 같아서 별도로 학습하지 않았지만생각보다 고려해야할 점이 많았다.  중요한 점은, right는 순차적으로 증가하되 left는 특정 조건을 만족할 때 갱신해야한다는 점이다.물론, 모든 문제에서 이럴 것 같지는 않다.  투포인터의 장점은, O(n)의 시간복잡도로 해결할 수 있다는 점이다.되게 좋은 솔루션을 배운 기분이다.  import sysinput = sys.stdin.readlinen = int(input())fruits = [int(x) for x in input().split()]# 투 포인터 알고리즘# left,right 포인터..

#21736 헌내기는 친구가 필요해 (https://www.acmicpc.net/problem/21736)  유난히 바쁜 날이라만만해보이는 문제로 (class 4 중) 빠르게 풀었다. n, m = map(int, input().split())campus = []visited = []q = []for i in range(n): row = [x for x in input()] v = [False for _ in range(m)] for j in range(m): # O는 빈 공간, X는 벽, I는 도연이, P는 사람이다 if row[j] == "I": q.append([i, j]) v[j] = True elif ro..

#10026번 적록색약 (https://www.acmicpc.net/problem/10026)  그냥 풀었다.dfs를 두 번 돌리면 된다. import syssys.setrecursionlimit(10**6)n = int(input())draw = [[x for x in input()] for __ in range(n)]ans, ans_rg = 0, 0moves = [[-1, 0], [1, 0], [0, -1], [0, 1]]def is_valid(y, x): return (0   시간복잡도고 뭐고 그냥 막 풀었다. (N의 최대치가 100이라서) 근데 풀렸다. 뭐지.. 감을 다시 잡은건가

#7569 토마토 (https://www.acmicpc.net/problem/7569) 오랜만에 풀어낸 BFS문제였다. from sys import stdinfrom collections import dequeinput = stdin.readline# 쌓아올려지는 상자의 수를 나타내는 H# M은 상자의 가로 칸의 수# N은 상자의 세로 칸의 수를 나타낸다# 단, 2 ≤ M ≤ 100, 2 ≤ N ≤ 100, 1 ≤ H ≤ 100 이다m, n, h = map(int, input().split())tomato = [] # 토마토 상자 데이터red = deque() # 익은 토마토 데이터# 방문 기록visited = [[[-1 for _ in range(m)] for __ in range(n)] for _..