Algorithm/etc.
0515_알고리즘 백트래킹(Backtracking) 정리
그 동안 문제 풀면서 자주 들었던 말.. "이거 백트래킹으로 풀면 돼^^" 찾아야 하는 경우의 수를 줄이는 것은 알았지만, 정확히 어떤 식으로 해결하는 지는 몰랐는데 드디어 오늘 SSAFY 라이브 강의에서 백트래킹 개념을 배웠다. [개념 정리] 백트래킹을 내 식대로 정리하자면, 가장 기본적으로는 '해를 찾는 것'이다. 근데 해를 어떻게 찾느냐 하면, 깊이우선탐색(DFS)와 비슷하게 풀이된다. 이때 다른 점은 깊이우선탐색은 가능한 모든 경우의 수를 탐색하는 것이고, 백트래킹은 조건에 만족한 노드만을 찾아 탐색하다가 해를 찾으면 탐색을 멈추기 때문에 결과적으로 훨씬 적은 경우의 수를 탐색하게 된다. (물론 그렇지 않을 때도 있다.) 즉, 기본적인 뼈대는 DFS지만 만족해야 하는 조건을 넣어주어 탐색하는 경우..
0410_Data Structure /Linked List /Python / 클래스 구현
오랜만에 블로그를 쓴다. 며칠 만인지.. 그 동안 web을 중점적으로 공부하느라 알고리즘에 소홀했는데 (시험 점수는 거짓말 하지 않지ㅠ) 앞으로 하루에 한문제씩은 알고리즘 문제를 풀면서 감을 챙길 생각이다. 어제 오늘 싸피에서 수업했던 내용은 바로 'Linked List'. 말은 쉽지만 코드로 구현해 내기까지 시간이 좀 걸렸다. 처음 과제로 받은 두 개의 문제 중 하나는 단순 리스트로 만들어서 풀었지만, 두 번째는 runtime error... 클래스 피해가려다 더 멀리 돌아가게 됐다ㅎ 사실 처음에는 class 정의해서 푸는 게 생각보다 복잡해 보이고(왜냐,, 나는 객체지향이 아직 낯설기 때문이다.) linked list에 대한 완벽한 이해도 되지 않은 상태라 도전할 엄두가 안 났지만, 과제는 해야겠고 ..
0224_오늘 고생 좀 시킨 그 놈... 'SuperSum'(memoization 활용)
오늘 하루 종일 풀었는데 너무 힘들었다. 재귀미워ㅜ 리뷰는 내일 덧붙여야지 25일 추가, 그렇다 리뷰를 덧붙인다. 이번에 코드업 재귀함수 파트 문제들을 풀면서 재귀의 개념, 어떻게 코드를 작성하는 지에 대한 연습을 했다. 문제 풀다보니 조금은 감이 잡혔는데, 예상치 못한 문제가 나타났다. 바로 런타임 에러. 재귀함수를 쓰면 보통 연산 시간이 늘어나고 비효율적이라는 말을 들어본 적이 있을 것이다. 이 문제를 해결하기 위해서 'Memoization' 개념을 가져와 문제 풀이에 적용했다. Memoization(메모이제이션)은 나도 이번에 처음 알게 됐다. 이는 컴퓨터가 동일한 계산 과정을 반복하지 않도록 이미 계산한 값들을 따로 저장해두고 필요할 때면 그 값들을 불러와 사용하는 것이다. 즉, 계산 반복을 줄여..