[WIL] 개발일지: 항해99 3주차

3월 셋째 주 : 항해99 3주차

 

 

1. 알고리즘, 자료구조 문제풀이(BAEKJOON)

 

파이썬 언어에 꽤나 익숙해졌지만, 새로운 알고리즘을 이해하는데 시간투자가 필요했다. 기본수학, 최대공약수/최소공배수, 정수론 및 조합론 등의 수학적 이론을 요하는 문제들은 다른 문제에 비해 쉬워보였지만 개념을 정확히 짚을 수 있어서 좋았다. 지난 주 어려웠던 동적 계획법, DFS와 BFS 문제들과 함께 새로운 알고리즘 개념도 접했다.

 

그 중 개념은 어렵지 않지만 코드를 짜는 것도 다른 사람들의 풀이를 해석하는 것도 쉽지 않았던 부분이 백트래킹 문제였다. DFS와 재귀를 적절히 잘 활용해야 했는데 실제로 N과 M(2) 문제는 간단해 보이면서도 그 구조를 이해하기가 쉽지 않아 거의 하루를 한 문제만 고민하며 보냈던 것 같다. 이해를 위하여 모든 경우를 표로 하나하나 그려보았고 끝내 해결할 수 있었다.

 

 

<이번주 새로 배운 개념>

 

(1) 브루트 포스(Brute Force)

이름처럼 무식한 방법을 사용하는 알고리즘이다. 문제 해결을 위해 가능한 모든 경우를 직접 해보는 방식으로 주로 while문을 많이 사용한다. 문제를 풀다보면 '이게 맞나..? 너무 무식한 방법인거 같은데..' 정말 그게 맞을 때가 많았다.

 

(2) 그리디(Greedy) 알고리즘

이 또한 이름에서 유추할 수 있듯이 깊게 생각하지 않고 지금 당장의 단계에서 가장 좋은(최선의) 선택을 하는 문제해결 방법이다. 그리디 알고리즘은 동적프로그래밍(DP)에서 지나치게 많은 연산과정을 거치는 것을 보완하기 위해 나온 개념이지만 모든 경우에 최선의 선택을 보장하는 것은 아니다. 사실 대다수의 경우 올바른 답을 주진 않지만 쉽고 적은 연산으로 문제를 해결하는데 좋은 결과를 보장한다는 점에서 많이 사용되는 개념이다. (ex.  #11047 동전0 문제: 금액 총합을 최소 갯수의 동전을 이용해만들기 위해 가장 큰 단위로 먼저 나누고 보고 안되면 그 다음으로 큰 단위만큼 빼고 다시 가장 큰 단위로 나누어 보며 찾는다.)

 

(3) 분할정복(Divide and Conquer)

분할 정복은 주어진 큰 문제를 둘 이상으로 분할해 부분으로 문제로 해결하고 그것을 조합하는 문제해결 방식으로 재귀호출을 이용한다. 문제를 나누어 해결하기 때문에 간단한 f(x)를 찾기만 하면 부분으로 어려운 문제를 벙렬적으로 해결할 수 있다는데 큰 장점이 있지만, 함수를 재귀적으로 호출한다는 점에서 오버헤드가 발생할 수 있다는 단점이 있다.

백준 #2630 색종이 만들기 처럼  주어진 큰 정사각형을 일정한 규칙에 따라 잘라서 자양한 크기를 가진 정사각형 모양을 만드는 문제들이 많다. 주어지는 N은 2,4,8,16 처럼 2의 제곱들로 이루어져있는 경우가 많다.

 

(4) 백트래킹(Backtracking)

조건 만족 문제, 퇴각검색 이라고 불리는 백트래킹 문제 해결의 핵심은 조건을 만족하는 경우를 찾아 불필요한 탐색을 하지 않는 것이다. 백트래킹은 깊이 우선 탐색(DFS) 방법을 사용하는데 이 때 모든 경우를 탐색하는 것이 아니라 탐색 도중 경로가 promosing 하지 않다고 판단되는 경로는 더 이상 가지 않고(가지치기, prunning) 그 다음 가지를 탐색하는 방법이다. 가지치기를 얼마나 잘하느냐에 따라 효율성이 결정된다. DFS 방법으로 stack을 활용하기도 하는데 True/False 혹은 visited 개념을 잘 이용하여 함수를 짜주는 것이 핵심이다.

 

  <지난주 알고리즘 문제풀이 리스트(BAEKJOON)>

번호	옵션	백준 문제번호	난이도	개념	문제 제목
1	옵션1	1316	하	문자열	그룹 단어 체커
2	옵션1	2839	하	기본 수학 1	설탕 배달
3	옵션1	1011	중	기본 수학 1	Fly me to the Alpha Centauri
4	옵션1	4948	하	기본 수학 2	베르트랑 공준
5	옵션1	1436	중	브루트포스	영화감독 숌
6	옵션1	9184	하	동적 계획법 1	신나는 함수 실행
7	옵션1	9461	하	동적 계획법 1	파도반 수열
8	옵션1	1149	하	동적 계획법 1	RGB 거리
9	옵션1	1932	중	동적 계획법 1	정수 삼각형
10	옵션1	11047	중	그리디 알고리즘	동전 0
11	옵션1	11399	중	그리디 알고리즘	ATM
12	옵션1	1037	하	정수론 및 조합론	약수
13	옵션1	2609	하	정수론 및 조합론	최대공약수와 최소공배수
14	옵션1	1934	하	정수론 및 조합론	최소공배수
15	옵션1	11050	하	정수론 및 조합론	이항 계수 1
16	옵션1	1010	중	정수론 및 조합론	다리 놓기
17	옵션1	10828	하	스택	스택
18	옵션1	10773	하	스택	제로
19	옵션1	9012	중	스택	괄호
20	옵션1	18258	하	큐, 덱	큐 2
21	옵션1	1260	중	DFS와 BFS	DFS와 BFS
22	옵션1	2108	중	정렬	통계학
23	옵션1	2630	중	분할정복	색종이 만들기
24	옵션1	15650	중	백트래킹	N과 M(2)
25	옵션1	9663	중	백트래킹	N-Queen
26	옵션2	2579	중	동적 계획법 1	계단 오르기
27	옵션2	1002	중	기본 수학 2	터렛
28	옵션2	2798	중	브루트포스	블랙잭
29	옵션2	1992	중	분할정복	쿼드트리

(추가로 풀어보아야 할 문제들 : #2231 분해합. #1541 잃어버린괄호, #11866 요세푸스 문제0, #11054 가장 긴 바이토닉 부분 수열, #1753 최단경로)

 

 

 

2. 3/19(금) 알고리즘 시험 

 

'2시간 3문제 + 1시간 문제풀이 영상 제출' 

한 문제 밖에 풀지 못했던 지난 주에 비하면 일취월장한 시험이었다. 첫번째 문제는 이분탐색 문제로 지난 주 시험문제와 유사해 어렵지 않게 풀 수 있었고, 두번 째 문제는 위에서 말했듯이 내가 절대적인 시간을 투제했던 백트래킹 문제 매우 유사했다. N과 M(2) 문제는 수열의 조합을 구하는 문제였다면 시험문제는 N과 M(1) 문제로 순열을 구하는 문제였다. 실제로 연습 문제를 풀었을 때 계속 조합이 아닌 순열로 나와서 이를 해결하기 위해 고민했었다..!! 세번째 문제는 동적계획법(DP)의 단골문제인 피보나치 수열 문제였다.

 

 

 

3. Chapter 3 주특기 선택 및 시작

 

항해99 4주차 부터는 Node.js, Spring, React, React Native 중 본인의 주특기를 결정하고 기본기부터 심화까지 집중적으로 다룰 수 있게 된다. 사실 주특기를 결정하기에는 너무 짧은 시간이었고, 백엔드도 더 배워보았으면 하는 아쉬움이 있지만, 너무 깊게 생각하지 말고 본인이 재밌는 걸 선택하라는 튜터님의 조언대로  나는 프론트엔드 REACT 로 결정했다. 디자인을 전공한 나는 아무래도 눈에 화면이 바뀌는 과정이 보이는 프론트엔드에 더 흥미를 느끼는 것 같았기 때문이다.

Chapter 3-1은 리액트의 기본을 학습하고 개인 과제를 수행하게 된다. 처음 접하는 프로그램에 첫 개인프로젝트라 걱정도 되지만 기대도 된다.

 

 

3주차도 화이팅 !!!