Elisom

백트래킹은 문제 해결 기법으로, 제약 조건 만족 문제에서 해를 찾기 위한 전략이다. 고려할 수 있는 모든 경우의 수를 상태 공간 트리(State Space Tree)를 통해 표현하여 각 후보군을 DFS 방식으로 탐색한다. Promising: 해당 루트가 조건에 맞는지 검사하는 기법 Pruning: 조건에 맞지 않으면 제거하고 다른 루트로 바로 넘어가 탐색 시간 절약하는 기법(가지치기) N Queen 문제 가장 대표적인 백트래킹 문제 유형. NxN 체스판에 N개의 Queen을 서로 공격할 수 없도록 배치하는 문제 ...체스에서 퀸은 가장 강력한 말인데, 수직/수평/대각선으로 이동 및 공격 가능함. 이 체스판 문제를 앞서 말한 대로 상태 공간 트리로 표현하고, Promising 및 Pruning을 하려면 아..

Prim's Algorithm은 먼저 다루었던 크루스칼 알고리즘과 같은 대표적인 최소 신장 트리 알고리즘이다. 프림 알고리즘이 크루스칼 알고리즘보다 조금 더 복잡하다. 두 알고리즘 모두 탐욕 알고리즘을 기반으로 하는데, Kruskal's algorithm은 단순히 가중치를 기준으로 sorting하여 작은 것부터 선택하며 MST를 구하지만, Prim's algorithm은 특정 정점에서 시작하여, 이 정점에 연결된 가장 작은 가중치의 간선을 선택하며 MST를 구한다. 하나의 정점을 정하고, 이 정점에 연결되어 있는 간선들을 리스트에 담은 후, 이 리스트에서 weight가 가장 작은 간선을 선택하여 cycle이 이루어지지 않는지 확인하고 연결한다. 이 때 간선들을 담는 리스트의 자료형으로 최소힙을 사용하면 ..

지난 Python 강의 기록에서 작성했던 Kruskal's algorithm에 대해 더 작성해보고자 한다. 패스트캠퍼스 Python 코딩테스트 강의 4주차 패스트캠퍼스 Python 코딩테스트 강의 [개발자 취업 합격 패스 with 코딩테스트, 기술면접]를 수강하며 정리한 글입니다🤓 Content 이번에는 앞서 배운 내용들을 바탕으로 고급 정렬 알고리즘을 배 elisom.tistory.com Kruskal's algorithm은 대표적인 최소 신장 트리 알고리즘이다. 신장 트리, Spanning tree. : 그래프의 모든 노드가 연결되어 있으며 트리의 속성을 만족하는 그래프 1. 모든 노드를 포함해야 함 2. 모든 노드가 서로 연결 3. 트리의 속성을 만족 (사이클x) 당장 눈앞의 최소 비용을 선택하여 ..

패스트캠퍼스 Python 코딩테스트 강의 [개발자 취업 합격 패스 with 코딩테스트, 기술면접]를 수강하며 정리한 글입니다🤓 Content 벌써 이번 강의 환급 챌린지의 마지막 미션 시기가 되었다니,, 어떠했는지 한 번 돌아보도록 하겠습니다 우선 환급 챌린지에 대해서 말해보자면, 패스트캠퍼스에 보면 종종 환급 챌린지를 진행한다. 강의도 열심히 듣고 돈도 아낄 수 있는 좋은 기회인 것 같아서 어떤 강의를 듣고 싶은지, 할 수 있는 상황인지 기회를 보고 있었다. 지난번에 확인해 볼 때에는 2-3달 정도의 장기 챌린지였던 것으로 기억하는데, 이번에는 1달뿐이어서 고민 않고 바로 수강 등록했다😀 결론적으로는 1달 챌린지 아주 만족한다. 이 이상이면 빼놓지 않고 잘할 수 있을지 자신이 없따ㅎㅎ 내가 수강했던 강..

패스트캠퍼스 Python 코딩테스트 강의 [개발자 취업 합격 패스 with 코딩테스트, 기술면접]를 수강하며 정리한 글입니다🤓 Content 이번에는 앞서 배운 내용들을 바탕으로 고급 정렬 알고리즘을 배웠다 퀵 정렬 정렬 알고리즘의 꽃이라고도 불림. 강사도 퀵 정렬을 보고 나서, 알고리즘을 효과적으로 작성할 수 있다는 것을 생각하였다고 함 python으로 특히 코드가 아름다움 기준점 pivot을 정하여 기준보다 작은 것을 왼쪽, 큰 것을 오른쪽으로 모으는 함수 왼쪽과 오른쪽은 각각 재귀용법을 사용하여 다시 동일함수 호출하며 반복함. 함수에서는 왼쪽+기준점+오른쪽을 리턴 퀵 정렬을 위와 같이 일반적으로 구현해 보았다. 이를 Python의 list comprehension을 사용하여 더 깔끔하게 구현해 보면..

패스트캠퍼스 Python 코딩테스트 강의 [개발자 취업 합격 패스 with 코딩테스트, 기술면접]를 수강하며 정리한 글입니다🤓 Content Part 2부터는 알고리즘 이론이 나온다. 알고리즘 이론 버블정렬 등 유명한 정렬 알고리즘들은 이미 다 구현이 되어 적용되어 있는데 왜 공부해야 할까? 지금까지 만들어진 알고리즘들 중에 가장 잘 만들어진 것을 익히고 배우는 과정이기 때문. 미술에서의 모사처럼 알고리즘도 따라 하며 배워야 할 필요가 있다. 이를 기반으로 알고리즘을 풀어나가면 더 잘 만들 수 있을 것이다. 알고리즘을 구현을 연습할 때에는 바로 코드를 작성하지 않고, 연습장에 쓰며 알고리즘을 고안한 다음에, 에디터에 옮겨 동작하는지 확인하는 방식으로 하면 좋다. 그래야 효율적인 알고리즘을 고안하기 좋다...

패스트캠퍼스 Python 코딩테스트 강의 [개발자 취업 합격 패스 with 코딩테스트, 기술면접]를 수강하며 정리한 글입니다🤓 Content 지난주에 수강한 기초 자료구조 배열, 큐, 스택, 링크드리스트에 이어 시간 복잡도가 나온다. 알고리즘 복잡도 다양한 알고리즘들 중 어떤 알고리즘이 더 좋은지 판단하기 위한 복잡도 계산 - 시간 복잡도 (중요) - 공간 복잡도 시간 복잡도 반복문이 지배함 종류 - Big O 표기법: 최악의 실행 시간 표기 아무리 최악의 상황이어도 이 정도의 성능은 보장한다는 의미를 가져 많이 사용됨 O(1) < O(logN) < O(NlogN) < O(n^2) < O(2^N) < O(N!) - 오메가 표기법: 최상의 실행 시간 표기 - 세타 표기법: 평균 실행 시간 표기 빅오 표기법..

패스트캠퍼스 Python 코딩테스트 강의 [개발자 취업 합격 패스 with 코딩테스트, 기술면접]를 수강하며 정리한 글입니다🤓 Content 1주차 수강한 내용을 정리하기에 앞서, 이 강의를 수강하기로 결정한 이유를 말해보자면 6개의 챕터의 다양한 내용으로 구성되어 있기 때문이었다. Chapter 1. 자료구조 이론 - 10h Chapter 2. 알고리즘 이론 - 12.5h Chapter 3. 코딩테스트 문제 풀이 - 21h Chapter 4. 실전 코딩테스트 문제 풀이 - 9h Chapter 5. 기술 면접 & CS 지식 - 19h Chapter 6. 네카라쿠배 합격자 노하우 - 11h 대략 총 83시간이다.. 하루에 3시간씩 성실히 듣는다면 1달이 걸리겠어요., 강의 내용도 풍부하길 기대합니다🥺 1주..