힘들었던 3학년 2학기가 끝이 났다. 매 학기마다 그렇게 느끼지만 이번 학기도 얻어가는게 많은 학기였다.
일단 성적은 지난학기와 마찬가지로 올에이쁠이다.
1. 알고리즘
알고리즘은 교수님이 에이쁠을 2~3명만 주는 교수님이셔서 성적이 나오기 전까지 정말 심장이 쫄깃했다.
이번에도 78명 중에 에이쁠을 3명만 주셨다.
교수님 수업은 정말 유익하다. 2018-1학기에 형식언어와 오토마타, 2019-1학기에 프로그래밍 언어론을 들었을 때에도 교수님 수업은 정말 재밌었고 좋았다. 자랑 좀 하자면 그 두 과목은 각각 33명 중 1등, 74명 중 1등을 했다 ^-^
교수님이 워낙 꼼꼼하게 설명해주시는 타입이라 이번에도 역시 진도를 많이 못 나갔다.
1단원은 알고리즘 기초(시간 복잡도, 공간복잡도, 계산복잡도와 이것들을 표현하는 빅 오 표기법, 빅 세타 표기법 등)를 배웠고 2단원 분할정복, 3단원 동적계획법, 4단원 그리디 알고리즘, 5단원 백트래킹까지만 배우고 한 학기가 끝이 났다.
교수님은 6단원 분기한정법도 정말 알려주고 싶어 하셨는데 배우지 못해서 나도 정말 아쉬웠다.
솔직히 이 과목에서 배운 피보나치 수열, 퀵소트, 병합정렬, 프림 알고리즘, 크루스칼 알고리즘, 플로이드 알고리즘, 다익스트라 알고리즘 등은 이미 자료구조와 이산수학 시간에 배운 알고리즘들이었다. 하지만 자료구조 시간에는 피보나치 수열을 재귀로 푸는 방법과 반복문으로 푸는 방법을 배우고 재귀로 푸는 방법은 중복 계산이 많아 비효율적이라고만 배웠었는데 이번 알고리즘 수업을 들으면서 재귀로 푸는 것이 왜 비효율적인지 알게 되었고, 반복문으로 푸는 것이 동적계획법이라는 것을 알게 되었다. 분할정복법과 동적계획법을 각각 어느 상황일 때 사용하는 것이 좋은지 비교를 하며 자세히 알게 되었다.
그리고 최소신장트리를 만드는 방법에는 프림 알고리즘과 크루스칼 알고리즘이 있다는 것도 자료구조 시간에 배웠었고 각각을 어떤 방법으로 푸는지도 알고 있었지만 어느 그래프에서 어떤 알고리즘을 사용하는 것이 유리한지, 그리고 왜 그런지도 알게 되었다. (이음선의 개수가 많은 dense 그래프는 프림 알고리즘을, 이음선의 개수가 적은 sparse 그래프에서는 크루스칼 알고리즘을 쓰는 것이 유리하다.)
이 외에도 자료구조 시간에 배우지 않았던 0-1 배낭 채우기 문제 (0-1 Knapsack 문제), n-Queens Problem, 외판원 문제 등 유명한 알고리즘들을 알게 되어서 정말 좋았다.
특히 0-1 Knapsack 문제는 처음에 그리디 알고리즘으로 접근해보고 그리디 알고리즘으로는 해결이 안 된다는 것을 깨닫고 동적계획법으로 풀어보고 그런데 이것은 비효율적이라 조금 더 개선된 방법을 배우고 나중에는 분기한정법으로 해결해보는 식으로 배워서 동적계획법, 그리디, 분기한정법 각각의 알고리즘의 특징에 대해서 더 잘 알게 된 것 같고 배낭 채우기 문제도 확실히 알게 되었다.
또한 아직까지도 풀리지 않은 P =? NP 문제를 알게 되어 매우 흥미로웠다. 교수님이 나중에 언젠가 우리가 그 문제를 풀게 되어서 튜링상을 받게 된다면 다른건 안 바라고 학창시절에 저에게 이 문제를 소개해주신 분이라고 교수님을 꼭 언급해달라고 하셨다(ㅋㅋ).
brute-force 방법, 최적의 원칙, 최적화 문제 등 내가 몰랐던 정말 많은 것을 알게 된 수업이었다. 이 수업을 듣고 나니 백준 온라인 저지 사이트에서 알고리즘 문제를 푸는게 훨씬 수월해졌다.
물론 아직 내가 모르는 알고리즘 기법들이 많지만 이 수업을 듣고 나니 기초가 아주 탄탄해진 느낌이다.
2. 모바일 소프트웨어
이 과목은 안드로이드 프로그래밍을 배우는 과목인데, 공부량이 가장 많았던 과목이다. 이 과목을 듣기 전에 여름방학 때 교내 소프트웨어 경진대회를 나가느라 안드로이드 앱을 만들었을 때에는 리스트뷰를 어떻게 사용하는지 몰라서 정말 어려워 했던 것이 기억나는데 이제는 커스텀뷰도 쉽게 만들 수 있다.
일단 초반에는 안드로이드를 구성하는 컴포넌트 4가지(액티비티, 서비스, 브로드캐스트 리시버, 컨텐트 프로바이더), 안드로이드 버전, 안드로이드에서 사용하는 가상 머신 Dalvik과 ART를 배웠다. 그렇게 이론을 배우고 나서 레이아웃과 레이아웃을 구성할 때 필요한 속성(LinearLayout, RelativeLayout, gravity, layout_gravity, weight, LayoutParams)들을 배웠다. 그 후에는 이벤트 처리, 어댑터, 어댑터뷰, 안드로이드 내장 DB인 SQLiteDatabase, 인텐트, 퍼미션, 액티비티 생명주기, ContentProvider를 정말 빠르고 깊게 배웠다. 진도가 너무 빠르고 퀴즈와 과제까지 있어서 수업을 따라가려면 많은 노력을 들여야 했다. 이렇게 배운 후 마지막 2주 동안은 코틀린을 배웠다. 코틀린 2주 동안 최대한 빠르고 많이 가르쳐주고 싶으셔서 강의자료까지 새로 만드셨다고 한다. (교수님 수업을 3개 들었는데 교수님이 수업시간에 항상 말씀하시기를 교수님이 바라는 것은 우리가 나중에 취업할 때 여러 군데 붙어서 골라 가는 것이라고 한다. 진심으로 우리가 잘 되길 바라셔서 많은 것을 가르쳐주고 싶어 하신다. 그래서 항상 감사하다. 가끔은 우리에게 너무나도 많은 것을 알려주고 싶어하셔서 약간 버거울 때도 있는데 나중에 돌아보면 교수님 수업은 정말 얻은 게 많고 실무에 정말 유용한 것 같다.)
이 수업은 안드로이드도 배우고 코틀린까지 배울 수 있어서 정말 좋았다. 정말 듣기 잘했다. (코틀린 복습하고 혼자 더 공부해야 하는데... 할 게 너무 많다.. 코틀린 부분은 벌써 다 잊은 것 같다. 이번 방학이 끝나기 전에 코틀린 복습 꼭 해야 겠다.)
3. 네트워크분석실습
처음에 정말 수강철회하고 싶었던 과목이다. 이 과목은 '컴퓨터 네트워크 및 실습' 과목의 후속 과목인데 나는 그 선행 과목을 안 들어서 걱정이 많았다. 나는 네트워크 5계층도 모르는데 이미 그 과목을 들은 학생들이 대부분이라서 진도를 되게 빨리 나가셨다. 그리고 다른 학생들은 이미 아는 내용이라서 다 이해하는 눈치인데 나만 하나도 모르는 것 같아서 정말 답답했었다. 그래서 이 과목은 모바일 소프트웨어와 함께 가장 공부량이 많았다. 결론적으로는 듣길 잘했다. 네트워크 각 계층과 그 계층에서 사용하는 프로토콜을 배웠다. 네트워크 계층을 가장 자세히 배웠는데 라우팅이 어떻게 일어나는지 라우팅(link-state 알고리즘, distance vector 알고리즘, 핫 포테이토 라우팅 등)에 대해서 배우고 예전 방식과 SDN의 차이를 배우고 BGP, OSPF 등 프로토콜도 배웠다. 나중에는 와이어샤크로 패킷을 캡쳐해서 패킷 분석도 해봤다. 과제로는 서로 다른 두 PC(client, server)에서 client가 문자열을 보내면 서버가 대문자로 바꿔서 client에게 다시 보내주는 과제도 했었다. 지금 돌아보니 이 과목도 정말 얻어가는 게 많은 것 같고 실습을 해볼 수 있어서 정말 좋았다.
4. 파이썬 프로그래밍
이 과목도 정말 많은 것을 배웠고 얻어가는 게 정말 많은 강의였다. 이론 과목이 아니여서 그런지 얻어가는 것이 많은 게 눈에 너무 잘 보인다. 파이썬을 정말 하나도 몰랐던 내가 4개월만에 정말 빠르게 배운 것 같다. 심지어 크롤링, numpy, pandas, tensorflow까지 배웠다. 교수님이 젊으셔서 그런지 최신 기술들을 배울 수 있어서 정말 좋았다. 파이썬에서 변수를 어떻게 선언하는지도 몰랐던 나는 변수부터 리스트, 튜플, 딕셔너리, Set 등 자료구조와 GUI, 인공지능까지 많은 것을 공부하느라 힘들기도 했던 과목이다. 이 과목은 알고리즘 강의도 아닌데 빅 오 표기법, DFS, BFS, LCS, 퀵소트, 힙소트, AVL 트리, 동적계획법, 선형계획법 등도 배웠다. DFS, BFS는 원래 알고 있었지만 파이썬으로 쉽게 구현하는 방법을 알게 되어서 정말 좋았다. LCS도 유명한 문제이지만 나는 몰랐었는데 덕분에 알게 되었다. 이 모든 알고리즘을 하루 안에 다 나가셔서 힘들긴 했는데 정말 좋았다.
과제도 쉽지 않은 과제가 3번이나 있어서 조금 힘들었다. 가중치 없는 무방향 그래프에서 최단경로, 최장경로를 구하는 문제였는데 최장경로가 정말 어려웠다. 최단경로는 BFS를 쓰면 됐었는데 최장경로는 코드 짜느라 며칠을 붙잡고 있었다. 파이썬 과목이지만 덕분에 알고리즘 해결 능력도 정말 많이 향상된 것 같다. 이 과목은 정말 듣길 잘 한 것 같다.
5. 스마트시스템구조론
이 과목은 타과 강의였는데 교수님이 정말 잘 가르치신다는 소문을 들었고 나는 컴퓨터구조를 배울 때 정말 흥미로웠기 때문에 듣게 되었다. 2학년 2학기 때 컴퓨터구조라는 과목을 들었었는데 그 과목과 거의 비슷한 과목이다.
컴퓨터구조에서는 16bit picoMIPS 아키텍쳐로 배웠었는데 이 과목에서는 32bit MIPS 아키텍쳐로 배울 수 있어서 좋았다. MIPS 아키텍쳐를 만든 2017 튜링상 수상자인 데이비트 패터슨과 존 헤네시가 쓴 책으로 수업을 했다.
컴퓨터구조 시간에 배웠지만 잊고 있었던 것들을 다시 상기할 수 있어서 좋았고 함수 호출이 일어나면 쓰던 데이터들을 어떻게 백업해놓고 복구하는지는 자세히 몰랐었는데 자세히 배울 수 있어서 좋았다.
컴퓨터구조 시간에는 이론들을 중심으로 배웠다면 이 과목에서는 명령어(어셈블리어와 32비트짜리 기계어)를 배우는 느낌이 많이 들었다. 다른 과목들에 비해서 실용성은 낮은 것 같은데 (내가 CPU를 만들고 CPU 명령어를 다루는 직업을 가질 확률은 거의 없을 것 같다) 컴퓨터가 어떻게 동작하는지 이제 완전히 잘 알게 된 것 같다. 데이터패스를 배울 때에는 회로에 직접 그리는 것을 과제로 매주 내주셔서 회로적으로 어떻게 동작하는지까지 아주 자세히 배웠다. 교수님이 말이 빠르시고 진도를 빨리 나가셔서 이 과목도 만만치는 않았다.
6. 스마트네트워크 및 실습
이 과목도 스마트시스템구조론 교수님과 같은 교수님 수업이다. 이 과목은 네트워크분석실습과 거의 같은데 타과 강의이다. 네트워크분석실습이 진도가 너무 빨라서 잘 이해가 안 됐던 부분을 이 과목을 들으면서 이해했던 적도 있고 그 반대의 경우도 있어서 두 과목을 같이 듣는 시너지 효과가 있었다. 하지만 결코 만만한 과목은 아니었다. 어렵지는 않았지만 양도 많았고 기말고사 때에는 벼락치기 하느라 힘들었다. 이제 네트워크는 어느정도 꽤 알게 된 것 같다.
n = int(input())
count = 0
li = [0] * (n + 1)
for i in range(2, n + 1):
temp = []
if i % 3 == 0:
temp.append(li[i // 3] + 1)
if i % 2 == 0:
temp.append(li[i // 2] + 1)
temp.append(li[i - 1] + 1)
li[i] = min(temp)
print(li[n])
두 달 반 뒤인 2020년 4월 6일에 C++로 다시 풀어보았다.
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int main() {
int x;
cin >> x;
vector<int> dp(x + 1);
dp[1] = 0;
for (int i = 2; i <= x; i++) {
vector<int> v;
v.push_back(dp[i - 1]);
if (i % 2 == 0)
v.push_back(dp[i / 2]);
if (i % 3 == 0)
v.push_back(dp[i / 3]);
dp[i] = *min_element(v.begin(), v.end()) + 1;
}
cout << dp[x];
return 0;
}
역시 C++이 효율적인거로는 최고인 것 같다. 파이썬의 10분의 1도 안 걸렸다.
풀이법을 설명하자면
더 큰 수로 나눌 수록 무조건 좋은 건 아니다. 3으로 나누는게 2로 나누는 것보다 더 많이 줄어들기 때문에, 2로 나누는게 1로 빼는 것보다 더 많이 줄어들기 때문에 큰 수로 나눌수록 좋다고 생각할 수도 있는데 그렇지 않다.
예를 들어 10의 경우 10을 2로 나누면 10 -> 5 -> 4 -> 2 -> 1 이렇게 네 번만에 1이 되지만
10에서 1을 먼저 빼면 10 -> 9 -> 3 -> 1 이렇게 세 번만에 1을 만들 수 있다.
따라서 10 / 2인 5가 1로 빨리 가는지 10 - 1인 9가 1로 빨리 가는지 확인해보고 그것을 선택해야 한다.
즉 그것을 미리 구해놓아야 한다. 따라서 동적계획법을 사용해서 가장 작은 계산부터 해서 그 계산을 이용해서 더 큰 계산을 해나가면 된다. 1에서 i로 가는 데 걸리는 연산의 횟수를 구해서 dp[i]에 저장해놓고 dp[i + 1], dp[i * 2], dp[i * 3]은 dp[i] + 1 이런 식으로 구해나갔다. 출력은 dp[x]를 하면 된다.
코드에서 min_element() 함수의 사용법을 모른다면 아래 링크에 있는 포스팅을 참고하면 된다.
스트림 데이터는 연속된 데이터이면 된다. 데이터의 집합체라면 전부 스트림 데이터로 만들 수 있다.
스트림의 특징: 조립성, 병렬화, 선언형
선언형이라는 것은 내가 구현할 필요가 없이 선언만 하면 된다는 것이다.
스트림 연산은 메소드의 인자가 전부 다 람다식 또는 메소드 참조이다.
스트림이 뭔지 아직 감이 안 올텐데 스트림 데이터가 들어오면 내가 필요한 것만 빼낼 수도 있고 몇 개 skip할 수도 있고 개수를 count할 수도 있고 평균도 낼 수 있고 매핑도 할 수 있고 집계도 할 수 있고 많은 것을 할 수 있다.
스트림 연산은 how 방식이 아니라 what 방식이다. 어떻게(how) 코딩할까 복잡하고 디테일한 것은 신경쓰지 않고 무슨(what)동작을 수행시킬지만 명시하면 된다. 디테일한 것들은 전부 구현체에 맡겨버리는 것이다.
컬렉션 vs 스트림
1. 처리 방식
스트림은 처리방식이 스트리밍이고 컬렉션은 처리방식이 다운로드 방식이다.
따라서 컬렉션은 한 번 만들어 놓으면 재사용할 수 있다. (물론 컬렉션 객체에서 iterator를 뽑아내면 iterator는 한 번 밖에 사용 못 한다.)
따라서 컬렉션은 저장공간이 필요하고 스트림 방식은 저장공간이 필요없다.
2. 반복 방식
컬렉션은 전부 외부 방식(Iterator 방식)이다. 요즘은 for문 대신 for~each문을 많이 사용하는데 for~each문은 iterator을 뽑아서 사용하지는 않지만 자세히 생각하면 궁극적으로는 외부 iteration(외부반복)이다. 바깥에서 누군가가 건드려줘야 한다.
하지만 스트림은 iterator가 필요 없다. 내부에서 다 알아서 해 준다.
3. 코드 구현
컬렉션은 명령형, 스트림은 선언형이다. 명령형이 훨씬 더 어렵다.
4. 원본 데이터 변경 여부
컬렉션은 원본데이터가 변경되지만 스트림은 원본데이터는 변경하지 않고 소비만 한다. 한 번 쓰고 끝나는거.
여기서도 느끼는 인생의 진리는 하나를 얻으면 하나를 포기할 수밖에 없다.
컬렉션은 다운로드를 해야하므로 저장공간이 크게 필요하지만 재사용이 가능하고
스트림은 시간에 따라 흘러가는 것이므로 별도의 저장공간이 필요하지 않지만 재사용이 불가능하다.
예제로 살펴보자.
예제1
다음 두 개의 코드는 똑같은 일을 수행한다.
랜덤으로 20개의 정수를 만들어서 리스트에 추가한 뒤 그 중에서 10보다 큰 수만 뽑아서 출력하는 일을 수행한다.
public class Stream1Demo {
public static void main(String[] args) {
List list = new ArrayList<>();
List gt10 = new ArrayList<>();
Random r = new Random();
for(int i = 0; i < 20; i++) {
list.add(r.nextInt(30)); //30 미만의 정수 20개를 list에 추가
}
for (int i : list)
gt10.add(i);
Collections.sort(gt10);
System.out.println(gt10);
}
}
public class Stream1Demo {
public static void main(String[] args) {
List list = new ArrayList<>();
Random r = new Random();
for(int i = 0; i < 20; i++) {
list.add(r.nextInt(30)); //30 미만의 정수 20개를 list에 추가
}
list.stream().filter(i -> i > 10).sorted().forEach(x -> System.out.print(x + " "));
}
}
그러니까 이 4줄과
for (int i : list)
gt10.add(i);
Collections.sort(gt10);
System.out.println(gt10);
이 1줄은
list.stream().filter(i -> i > 10).sorted().forEach(x -> System.out.print(x + " "));
똑같은 일을 한다.
심지어 스트림을 사용한 코드는 gt10이라는 저장공간이 따로 필요하지 않으므로 gt10 리스트를 선언하는 부분도 필요 없으니까 코드가 4줄 더 짧은 것이다. 스트림을 사용하면 코드도 짧아지고 저장공간도 덜 든다는 것을 알 수 있다.
예제2
아래의 코드는 int 배열에서 5보다 큰 수들만 더해서 출력하는 것이다.
public class Stream2Demo {
public static void main(String[] args) {
int[] ia = {1, 6, 3, 9, 5, 4, 2};
IntStream is = Arrays.stream(ia); //배열을 스트림으로 만들 때에는 Arrays.stream(배열) 이렇게 사용
int sum = is.filter(i -> i > 5).sum();
System.out.println(sum);
}
}
실행결과는 아래와 같다.
배열을 스트림 객체로 만들고 싶을 때에는 Arrays 클래스의 static 메소드 stream(배열)를 사용하면 스트림 객체를 만들 수 있다. Arrays.stream(배열)의 인자로 int 타입의 배열이 들어가면 IntStream이 나오고 double 타입의 배열이 들어가면 DoubleStream이, long 타입의 배열이 들어가면 LongStream이 만들어진다. 이 외의 타입은 제네릭 타입의 Stream<T> 객체를 반환한다.
