WINK-(Web & App)/알고리즘 스터디 (12) 썸네일형 리스트형 [2025 1학기 알고리즘 스터디] 남윤찬 #3주차 그리디 알고리즘정리그리디 알고리즘(Greedy Algorithm), 직역하면 탐욕 알고리즘이다. 이름에서 직관적으로 알 수 있듯이, 매 선택에서 최선으로 보이는 답을 선택하는 알고리즘이다. 그만큼 빠르고 단순하지만 항상 최적해를 보장하지는 못한다.조건그리디 알고리즘을 적용시키기 위해서는 두 가지의 조건이 필요하다탐욕 선택 속성: 앞의 선택이 이후의 선택에 영향을 주면 안된다. 현 시점에서의 최선의 선택이 전체적으로도 최선의 선택이어야 한다. 이 말이 완벽히 이해되지는 않는데, 가장 큰 예시인 활동 선택 문제를 떠올리면 받아들이기는 비교적 수월할 것 같다.최적 부분 구조: 전체 문제의 최적해가 부분 문제의 최적해로 구성될 수 있어야 한다. 쉽게 말해 점화식이다. 해결하고자 하는 문제를 부분으로 나눈 작은 .. [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를 사용하여 빈도수를 계산한 후, 최빈값을 찾음.정렬하여 최빈값이 같은 경우 가장 작은 숫자 선택.카운팅 함수 없이 문제를 해결하고자 한다면, 딕셔너리를 선언한고 이러한 딕셔너리를 의.. 이전 1 2 다음
