seungineer

Week 1 ~ 3, '컴퓨팅 사고로의 전환'이 마무리 되었다. 발제명과 같이 기존 사고 방식을 컴퓨팅과 동일한 사고 방식으로 전환하기 위해 알고리즘 문제를 활용하였다. 알고리즘 문제를 컴퓨터가 해결할 수 있도록 파이썬으로 코드를 짠다. 이렇게 코드를 짜며 내가 사고하는 방식을 컴퓨터가 처리할 수 있는 방식대로 동기화하는 주차였다. 3주간 알고리즘 문제들을 컴퓨터에게 해결시켜(?) 본 결과 어느정도 사고 방식이 동기화가 되는 것 같다(아주 조금). 다만, 아직도 time, space complexity 를 줄일 수 있는 방식을 떠올리지 못 하고 있다. 조금 더 공부하고자 하는 부분이다. 또한 백준에 아직 접근해보지 못 한 문제들이 많이 남아 있다. 이러한 문제들을 경험해보면서 더 능숙하게 컴퓨터에게 일을..

재귀에 대해서 공부하면서 '절차지향적 사고'가 아닌 '귀납적 사고'로 접근해야 한다는 얘길 들었다. 그 당시에 어렴풋이 이해했던 부분이 동적프로그래밍을 공부하면서 좀 더 선명히 이해가 되는 것 같아 기록해두고자 한다. 백준 9084 이 문제는 동전의 type이 주어질 때 주어진 금액을 만드는 모든 방법의 수를 출력하는 것이다. 동전의 최대, 최소 개수가 아닌 경우의 수를 모두 합한 값을 출력해야 한다. 주어진 금액에서 시작하여 모든 경우를 절차대로 타고 들어가면 복잡하다. 또한 '중복 부분 문제'가 발생한다. 그러므로 DP를 활용해본다. 1. 테이블 정의하기 dp[i] 는 'i를 만들기 위해 필요한 모든 방법의 수로 정의한다. 이렇게 정의해본 이유는 간단히 dp[주어진 금액] 하면 정답을 찾을 수 있기 ..

백준 1931 문제를 풀다가 85%에서 '틀렸습니다'가 나왔고, 틀리게 만든 케이스에 대해서 고민을 하였다. 몇 가지 반례를 찾을 수 있었다. 이를 해결한 코드를 제출하여 '맞았습니다'가 나왔다. 제출 이후 문득 생각난 케이스가 있어 '맞았습니다'가 나온 코드에 넣어서 테스트해 보았다. 예상 결과와 다른 값을 출력했다. 백준에서 검증하지 않은 케이스인 줄 알았지만, 글을 쓰면서 내가 생각을 잘못했다는 것을 깨달았다... 💩 그래도 잠깐이나마 백준 사이트의 '데이터를 추가한 사람' 리스트에 이름을 올릴 수 있나 행복회로를 돌렸기에 기록해두고자 한다. 백준 1931 문제 요약 입력되는 N개의 회의 시작, 끝 시각을 바탕으로 가장 많은 회의를 진행할 수 있는 경우의 수를 출력하는 것이다. 물론 회의실이 1개이..

동적 프로그래밍(DP)은 '큰 문제를 '작은 문제를 해결하며 나온 해'를 결합하여 해결하는 것'이다. 이는 분할 정복법과 유사해 보인다. 분할 정복법 또한 '원래 문제를 몇 개의 부분 문제로 분할하며 재귀적으로 해결'한다. 이렇게 찾은 부분 문제의 해를 결합하여 원래 문제의 해를 찾는다. 그렇다면 DP와 차이점은? DP는 문제에 최적 부분 구조(optimal substructure)와 중복 부분 문제(overlapping subproblems)가 있을 때 적용할 수 있다. 최적 부분 구조란, 부분 문제의 최적해가 원래 문제의 최적해 속에 포함되어 있다는 것이다. 중복 부분 문제는 부분 문제들을 해결해 가는 과정에서 중복되는(=동일한 값을 계산하기 위한) 값을 반복해서 풀게 되는 것이다. 위 그림은 분할 ..

python을 통해 한 리스트를 다른 변수에 할당하는 경우가 자주 있다. 리스트를 변수에 할당하는 것이 (새로운 변수에)복사되었다고 착각할 때, 예상과 다른 결과가 출력될 것이다. 아래 케이스는 착각하게 되는 시나리오이다. list1 = [1, 2, 3, 4] list2 = list1 # list1을 list2에 '복사' # list2 수정 list2[1] = 100 list2.append(5) # list2 출력 print(list2) # [1, 100, 3, 4, 5] # list1은 그대로겠지? print(list1) # [1, 100, 3, 4, 5] 🤔 list2를 수정(조작)했는데, list1이 동일하게 변경되었다. 의도한 것이 아닐 것이다. 이렇게 작동 되는 이유에 대해 알아본다. pyth..