WINK-(Web & App)/알고리즘 스터디 (11) 썸네일형 리스트형 [2025 1학기 알고리즘 스터디] 박현빈 #2주차 Dynamic Programming동적 계획법, 다이나믹 프로그래밍(Dynamic Programming, DP) : 큰 문제를 작게 나누고, 같은 문제라면 한번씩만 풀어 문제를 효율적으로 해결하는 알고리즘 기법이다.최적의 해를 구하는 문제는 많은 연산 시간과 메모리가 필요해 컴퓨터로도 해결하기 어려운 문제이다. 이러한 문제들 중에서 특정 문제는 메모리 공간을 약간 더 사용하면 연산 속도를 비약적으로 상승 시킬 수 있다. 기존의 알고리즘이 해결하지 못하는 문제들 중 다이나믹 프로그래밍 기법을 통해서 해결할 수 있는 문제가 있다. 대표적인 예시로 피보나치 수열이 있다.DP 기법을 적용시키기 위한 조건다이나믹 프로그래밍을 사용하기 위해서는 해당 하는 문제가 다음 2가지 조건을 만족해야 한다.최적 부분 구조(O.. [2025 1학기 알고리즘 스터디] 김민재 #2주차 가장 긴 증가하는 부분 수열import java.util.Scanner;public class Main { public static void main(String[] args) { Scanner sc = new Scanner(System.in); int n = sc.nextInt(); int[] arr = new int[n+1]; int[] dp = new int[n+1]; for (int i = 1; i 1로 만들기import java.util.Scanner;public class Main { public static void main(String[] args) { Scanner sc = new Scanner(Sy.. [2025 1학기 알고리즘 스터디] 김민주 #2주차 알고리즘 스터디 2주차 : DP 1. 1로 만들기 https://www.acmicpc.net/problem/1463 💡문제 분석 및 알고리즘 설계처음에는 2 or 3의 배수이면 무조건 나누기 먼저한 후에 -1을 해서 1을 만드는 방식으로만 구현했었는데,10의 경우, " -1 => /3 => /3 " 의 순서대로 행하는 것이 최소 연산 횟수임을 알게 되었습니다. 따라서 두 방식으로 모두 계산하면서 그 중 최소값을 취하는 방식으로 설계하게 되었습니다. #include #include #include using namespace std;int n;int DP[1000000];void calc(int i){ DP[i] = DP[i-1] + 1; if (i%2 == 0) { DP[.. [2025 1학기 알고리즘 스터디] 이서영 #2주차 *파이썬으로 풀었습니다- 1463: 1로 만들기- 2579: 계단 오르기- 11053: 가장 긴 증가하는 부분 수열 1463: 1로 만들기정수 X에 사용할 수 있는 연산은 다음과 같이 세 가지 이다.X가 3으로 나누어 떨어지면, 3으로 나눈다.X가 2로 나누어 떨어지면, 2로 나눈다.1을 뺀다.정수 N이 주어졌을 때, 위와 같은 연산 세 개를 적절히 사용해서 1을 만들려고 한다. 연산을 사용하는 횟수의 최솟값을 출력하시오. 1. Greedy 3으로 나눌 수만 있다면 무조건 최선이라 생각했습니다.import sysinput = sys.stdin.readlineN = int(input())count = 0while N!=1: if N % 2 != 0 and N % 3 != 0: N-=1.. [2025 1학기 알고리즘 스터디] 남윤찬 #2주차 이번 2주차는 DP(Dynamic Programing)입니다. 일단 문제 블로깅에 앞서 DP가 뭔가 간단하게 요약해봤습니다. DP로 푸는 조건 및 방식dp(dynamic programming)은 복잡한 문제를 하위 문제로 나누어 해결하는 알고리즘 설계 기법이다. 여러 블로그를 찾아보았는데 공통적으로 있는 말로는, dp라는 명칭을 고안한 Richard Bellman이 멋있어서 이렇게 지었다고 한다ㅋㅋ.아무튼 dp는 재귀적으로 문제를 푸는 방식인데, 여기에 메모이제이션(Memoization)을 하는 방식이다. 점화식을 세워 재귀로 탐색을 하다보면 중복되는 값이 있을텐데, 이것을 피하며 문제를 풀어나가는 것이 dp이다. DP로 푸는 조건 및 방식dp가 적용되려면 두 가지 조건이 필요하다. 겹치는 소문제 .. [2025 1학기 알고리즘 스터디] 1주차 김민재 수 정렬하기3처음에 너무 간단해 왜 간단할까 생각하며 코드를 작성했고 바로 시간 초과가 떴다import java.util.Arrays;import java.util.Scanner;public class NumSort3 { public static void main(String[] args) { Scanner sc = new Scanner(System.in); int n = sc.nextInt(); int[] num = new int[n]; for (int i = 0; i num[j+1]) {// int tmp;// tmp = num[j];// nu.. [2025 1학기 알고리즘 스터디] 1주차, 박현빈 10989번: 수 정렬하기 3각 수에 대응하는 리스트를 생성하여 나오는 숫자 만큼 카운팅하고, 출력import sysN = int(sys.stdin.readline())count = [0] * 10001 for _ in range(N): count[int(sys.stdin.readline())] += 1 for num in range(10001): if count[num] > 0: for _ in range(count[num]): print(num) 11652번: 카드Counter를 사용하여 빈도수를 계산한 후, 최빈값을 찾음.정렬하여 최빈값이 같은 경우 가장 작은 숫자 선택.카운팅 함수 없이 문제를 해결하고자 한다면, 딕셔너리를 선언한고 이러한 딕셔너리를 의.. [2025 1학기 알고리즘 스터디] 이서영 #1주차 * 파이썬으로 풀었습니다.10989번: 수 정렬하기311652번: 카드18870번: 좌표압축 1. 10989번: 수 정렬하기3문제 : N개의 수가 주어졌을 때, 이를 오름차순으로 정렬하는 프로그램을 작성하시오.정답률(23.935%)을 보자마자 든 생각은나는 무조건 틀리겠다.바로 sort를 생각한 저를 의심한 후 정렬 알고리즘에 대해 공부해줍니다. 정렬 알고리즘: n개의 숫자가 입력으로 주어졌을 때, 기준에 맞게 정렬하는 알고리즘 1. 선택 정렬: 현재 위치에 들어갈 값을 찾아 정렬 ( 시간복잡도 : O(n^2) ) 2. 삽입 정렬: 현재 위치에서 그 이하 배열들을 비교하여 자신이 들어갈 위치를 찾아 그 위치에 삽입 ( 시간복잡도 : O(n^2) )3. 버블정렬: 매번 연속된 2개 인덱스를 비교한.. 이전 1 2 다음 목록 더보기
