본문 바로가기

CS/Algorithm

(52)
패스트캠퍼스 챌린지 27일차 [강의] 다음은 패스트 캠퍼스 알고리즘 / 기술면접 완전 정복 올인원 패키지를 통해 학습 및 정리한 내용입니다. 기본 탐색 알고리즘 오늘은 기본 탐색 알고리즘에서 기초 문제풀이를 진행했다. 단순히 정렬만하면 되는 문제들이어서 가볍게 풀어냈다. 내일은 핵심 유형 문제풀이와 고급 탐색 기초 및 핵심 유형 문제풀이를 진행할 예정이다. 1668번 문제를 풀어야했는데 1688번 문제를 풀었다. 시간도 오래걸리고 어려워서 이게 맞나 다시 봤더니 1688번 문제를 풀어야했다. 결국 풀지는 못했지만 난이도 높은 문제여서 재밌게 삽질하고 끝마쳤다. CCW 알고리즘이라고 하던데 내일은 이 알고리즘을 공부해보고 한번 다시 풀어봐야겠다. 알고리즘은 배워도 배워도 끝이 없다. 정말 재밌다😥 그리고 어느새 백준 실버 3까지 올라..
패스트캠퍼스 챌린지 26일차 [강의] 다음은 패스트 캠퍼스 알고리즘 / 기술면접 완전 정복 올인원 패키지를 통해 학습 및 정리한 내용입니다. 재귀 호출 함수 재귀 호출 알고리즘 문제는 풀어도 풀어도 언제나 새롭다. 이제 어느정도 감을 잡았다 싶다가도 새로운 유형의 문제를 만나면 다시 감을 잃어버리는 느낌이다. 그래도 다행인 것은 재귀 함수를 사용하다보면 예전보다는 훨씬 빠르게 이해하고 적용할 수 있다는 것이다. 이번 알고리즘 문제에서는 내장 함수인 eval 함수를 통해 문자형 자료형을 숫자형으로 변환하지 않고 그대로 연산시킬 수 있었다. 하지만 왠만해서는 사용을 자제하는게 좋다고 한다. 코드의 가독성을 떨어뜨릴 뿐만 아니라 디버깅도 어려워질 수 있고, 일부 로컬에만 의존하는 환경 의존성까지 생길 수 있기 때문이라고 한다. 그리고 서..
패스트캠퍼스 챌린지 25일차 [강의] 다음은 패스트 캠퍼스 알고리즘 / 기술면접 완전 정복 올인원 패키지를 통해 학습 및 정리한 내용입니다. 디테일 잡기 백준 문제를 풀다보면 시간과 메모리가 제한되어 있는 경우가 있다. 지금까지 나는 그게 왜 중요한지도 모르고 무턱대고 문제를 풀었는데, 알고리즘을 더욱 효율적으로 작성해야하는 상황에 부딪히니 꽤나 당황스러웠다. 당시 사용했던 알고리즘이나 기본 라이브러리 운좋게 맞아 떨어졌던 것 같다. 자료구조와 알고리즘을 공부한 지 약 한달정도 되어가는데, 몇몇 알고리즘과 시간 복잡도에 대한 개념을 어느 정도 잡아가고 있다고 생각했지만, 더욱 효율적으로 작성해야하는 상황에 부딪히며 다시금 디테일의 중요성을 깨닫게 됐다. 알고리즘을 공부하다보면 실력이 향상되고 있음을 느끼는 순간들이 있다. 평소에는 ..
패스트캠퍼스 챌린지 24일차 [강의] 다음은 패스트 캠퍼스 알고리즘 / 기술면접 완전 정복 올인원 패키지를 통해 학습 및 정리한 내용입니다. 기본 알고리즘 복습 어제 자료구조 문제 풀이에 이어 오늘은 기본 알고리즘에 해당하는 정렬 알고리즘에 대해 문제 풀이와 복습을 진행하였다. 오늘 복습한 정렬 알고리즘은 bubble sort, insert sort, merge sort, quick sort, selection sort로 지난 강의에서 배웠던 내용이지만 대부분 잊어먹어 최대한 보지 않고 구현하려고 노력했다. 물론 효율성만 놓고 봤을 때 정렬 알고리즘을 모두 구현할 필요까지 있겠냐 싶겠지만, 구현하는 과정에서 파이썬 언어에 대한 이해도도 높아졌고 무엇보다 알고리즘을 코드로 구현하는 능력이 점점 좋아지고 있음을 느끼고 있어 자료구조와 ..
패스트캠퍼스 챌린지 23일차 [강의] 다음은 패스트 캠퍼스 알고리즘 / 기술면접 완전 정복 올인원 패키지를 통해 학습 및 정리한 내용입니다. 오늘은 기본 자료구조와 관련된 핵심 유형 문제풀이를 진행했다. 강의가 있었지만 스스로 풀어보는 게 도움이 될 것이라 생각해서 강의를 듣기 전 직접 문제를 풀어보았고, 헷갈리는 부분만 강의를 참고하였다. 문제 유형은 큐, 스택, 그리디로 총 세 문제였는데 자료구조에 대한 개념은 알고있었음에도 문제를 해석하고 적용하는 과정에서 꽤나 어려움이 따랐다. 그럼에도 자료 구조에 대한 개념이 이해가 되어있는 상태여서 구조를 그려가며 알고리즘을 구현할 수 있었다. 예전에는 무턱대고 문제를 풀면서 의식의 흐름대로 작성했었는데 유형별로 풀이를 하니 조금 더 수월하게 문제 풀이를 할 수 있었다. 물론 유형별 문제..
패스트캠퍼스 챌린지 22일차 [강의] 다음은 패스트 캠퍼스 알고리즘 / 기술면접 완전 정복 올인원 패키지를 통해 학습 및 정리한 내용입니다. 자료구조 및 알고리즘 기초 강의 수강 완료 오늘부터 기초 문제 풀이를 시작했는데 그 전에 자료구조와 알고리즘을 복습하는 시간을 가졌다. 복습을 하면서 느꼈던 것은 자료구조와 알고리즘에 대한 내용을 몰랐었을 땐 코딩 테스트를 어떻게 풀어야할지, 자료구조와 알고리즘이 무엇인지 막연했었지만 지금은 부담감도 많이 해소되었고 어느정도 자신감이 붙어있는 상태이다. 물론 파이썬 언어를 사용하면서 감이 익혀진 것도 있지만 강의를 통해 자신감을 얻게된 것이 6~7할 정도 되는 것 같다. 아직은 자료구조와 알고리즘을 능숙하게 사용하는 단계는 아니지만, 끈기를 갖고 계속해서 활용해나간다면 파이썬을 비롯해서 다른 ..
패스트캠퍼스 챌린지 21일차 [강의] 다음은 패스트 캠퍼스 알고리즘 / 기술면접 완전 정복 올인원 패키지를 통해 학습 및 정리한 내용입니다. 백 트래킹 백 트래킹(back tracking) 또는 퇴각 검색(back track)이라고 부른다. 이는 알고리즘이라고 하기 보다는 제약 조건을 만족하는 문제에서 정답을 찾기 위한 기법이라 볼 수 있다. 정답을 찾기 위해 후보 군에서 제약 조건을 체크하다가, 해당 후보군이 제약 조건을 만족하지 않을 경우 back track하여 이 후보군과 관련된 경우의 수를 더이상 찾지않고 다음 후보군으로 넘어가며 제약 조건을 만족하는 경우를 찾는 방법이다. 실제 구현하게 되면 고려할 수 있는 모든 경우의 수를 상태 공간 트리(State Space Tree)로 표현한다. 그리고 이러한 트리에서 DFS 알고리즘..
패스트캠퍼스 챌린지 20일차 - 보충 학습 [강의] 다음은 패스트 캠퍼스 알고리즘 / 기술면접 완전 정복 올인원 패키지를 통해 학습 및 정리한 내용입니다. Prem's Algorithm 상세 구현 Prem's Algorithm을 구현한 함수와 인수이다. 시간 복잡도는 최악의 경우로, while 구문에서 모든 간선에 대해 반복하고, 최소 힙 구조를 사용하기 때문에 O(E logE)의 시간 복잡도를 가진다. 코드별로 자세히 알아보자. prim 함수의 매개변수는 start_node와 edges다. 인수로 전달받을 땐 start_node는 string 값이며 edges는 list 형태로 전달받게 된다. 이때 변수 2개가 선언되어지는데 이 중 첫번째 mst는 Minimum Spanning Tree의 약자로 prim 함수를 통해 출력될 값이다. 먼저 변수 ..