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-%..

#1629번 곱셈 https://www.acmicpc.net/problem/1629 1629번: 곱셈 첫째 줄에 A, B, C가 빈 칸을 사이에 두고 순서대로 주어진다. A, B, C는 모두 2,147,483,647 이하의 자연수이다. www.acmicpc.net 거듭제곱을 해결하는 문제인데, 자료구조 수업에서 다룬 적이 있던 것 같다. 틀린 코드 from sys import stdin input = stdin.readline a, b, c = map(int, input().split()) def fpow(C, n): if n == 1: return C else: x = fpow(C, n//2) if n % 2 == 0: return x * x else: return x*x*C print(fpow(a, ..

#1780번 종이의 개수 https://www.acmicpc.net/problem/1780 1780번: 종이의 개수 N×N크기의 행렬로 표현되는 종이가 있다. 종이의 각 칸에는 -1, 0, 1 중 하나가 저장되어 있다. 우리는 이 행렬을 다음과 같은 규칙에 따라 적절한 크기로 자르려고 한다. 만약 종이가 모두 같은 수 www.acmicpc.net 평범한 분할정복 문제라고 생각하고 열심히 짰다. 틀린코드 N = int(input()) matrix = [list(map(int, input().split())) for _ in range(N)] answer = [0, 0, 0] # 0, 1, -1 def check(mat): pivot = None for r in mat: for c in r: if pivot..

분할 정복 (Divide and Conquer) : 문제를 나눌 수 없을 때까지 나누어 각각의 부분을 연산한 뒤 다시 합치며 답을 얻는 알고리즘이다. 의사코드(psuedo code)를 작성해 본다면 다음과 같다. function F(x): if 문제를 더 이상 나눌 수 없는 조건: return 계산한 값 else: x를 문제의 조건 내에서 분할 return F(x1), F(x2) .... 분할한 데이터로 함수를 재귀적으로 호출 이 의사코드를 보고난 후, 문제를 어떻게 풀어야 할지 감이 바로 왔다. #2630번 색종이 만들기 https://www.acmicpc.net/problem/2630 2630번: 색종이 만들기 첫째 줄에는 전체 종이의 한 변의 길이 N이 주어져 있다. N은 2, 4, 8, 16, 3..