김성수의 개발 블로그

오늘은 알고리즘 중에서도 다이나믹 프로그래밍, 최단 경로 알고리즘, 그래프에 대해서 정리해볼까 합니다. 첫번째는 다이나믹 프로그래밍입니다. 다이나믹 프로그래밍(동적 계획법)은 하나의 큰 문제를 여러 개의 작은 문제로 나누어서 그 결과를 저장하여 다시 큰 문제를 해결할 때 사용하는 알고리즘입니다. 다이나믹 프로그래밍을 적용하기 위해서는 Overlapping Subproblem(부분 반복 문제), Optimal Substructure(최적 부분 구조)을 만족시켜야 합니다. 두번째는 최단 경로 알고리즘입니다. 최단 경로(Shortest Path) 알고리즘은 이름에서부터 알 수 있듯이 가장 짧은 거리를 찾는 알고리즘입니다. 일반적으로는 네비게이션이나 길찾기 등에 사용되고 최단 경로 알고리즘에는 크게 다익스트라(..

오늘은 알고리즘 중에서도 그리디, 구현, DFS, BFS, 선택정렬, 삽입정렬, 퀵정렬, 계수정렬, 탐색, DP에 대해서 정리해볼까 합니다. 첫번째는 그리디 알고리즘입니다. 그리디 알고리즘은 탐욕 알고리즘 또는 욕심쟁이 알고리즘이라고도 불리는 알고리즘으로 미래를 생각하지 않고 각 단계에서 가장 최선의 선택을 하는 기법입니다. 즉, 최적의 선택을 하지는 않는 알고리즘입니다. 지금 당장 좋은 것만을 고르다보니 현재의 선택이 나중에 어떤 영향을 미칠지는 모른다는 것입니다. 그렇기에 최선이 될 수도 있지만 아닐 수도 있는 알고리즘입니다. 두번째는 구현입니다. 구현은 알고리즘을 소스코드를 바꾸는 과정을 말합니다. 풀이를 떠올리는 것은 쉽지만 소스코드로 옮기기 어려운 것이 문제입니다. 세번째는 DFS(깊이우선탐색)..

goto문은 어느 특정 줄 번호나 레이블로 건너뛰거나 돌아갈 때 쓰는 명령어인데요. 하지만 유연성이 떨어지는 것은 물론 스파게티 코드, 즉, 코드가 꼬이기에 웬만하면 사용하지 않습니다. 아래는 예시 코드입니다. #include int main() { int n; input: scanf("%d", &n); if(n != 0) { printf("%d\n", n); scanf(" "); goto input; //goto 명령어에 의해 6번째 줄로 이동 } if(n == 0) return -1; return 0; }

일부 상황에서는 포인터를 쓰는 경우가 있는데요. 밑에는 예시 및 실행 결과입니다. #include int main() { int *p, i; int a[5] = {55, 78, 95, 66, 96}; p = a; for(i = 0; i < 5; i++) printf("%d ", a[i]); printf("\n"); for(i = 0; i < 5; i++) { printf("%d ", *(p+i)); printf("%d ", *p+i); } printf("\n"); return 0; } 55 78 95 66 96 55 55 78 56 95 57 66 58 96 59

Collection Framework는 다수의 요소를 하나의 그룹으로 묶어 효율적으로 저장하고, 관리할 수 있는 기능을 제공하는 클래스이 집합인 것과 동시에 가변적인 크기를 가지고 있기 때문에 배열의 단점을 보완해주는 컬렉션이기도 한데요. 이 그림은 Collection Framework의 구조인데요. 대표적으로는 List, Queue, Set, Map 인터페이스로 구성이 되어있으며 여러 클래스가 해당 인터페이스를 구현하거나 다른 인터페이스가 상속받는 구조로 되어있는 것을 알 수 있습니다. 밑에는 Collection Framework 중에서도 자바에서 많이 쓰이는 자료구조인 ArrayList와 HashMap의 예시 코드입니다. import java.util.ArrayList; //ArrayList를 imp..

#include int main() { char str[101]; int i; printf("Input String: "); scanf("%s", str); printf("Output String: "); for(i = 0; str[i] != '\0'; i++) { if(str[i] >= 'A' && str[i] = 'a' && str[i]

#include int main() { int a = 10, b = 15, total; double avg; int *pa, *pb; int *pt = &total; double *pg = &avg; pa = &a; pb = &b; *pt = *pa + *pb; *pg = *pt / 2.0; printf("두 정수의 값: %d, %d\n", *pa, *pb); printf("두 정수의 합: %d\n", *pt); printf("두 정수의 평균: %.1lf\n", *pg); return 0; }

#include int main() { int i, j, n; scanf("%d", &n); for(i = 1; i

%x는 16진수를 나타냅니다. for문을 활용하여 1부터 15까지 곱합니다. #include int main() { int i, j, a; scanf("%x", &a); for(i = 1; i

switch문을 사용하여 작성하였습니다. #include int main() { char a; scanf("%d", &a); switch(a) { case 12: case 1: case 2: printf("winter"); break; case 3: case 4: case 5: printf("spring"); break; case 6: case 7: case 8: printf("summer"); break; case 9: case 10: case 11: printf("fall"); break; } return 0; }