코딩스뮤:)

[Python] BOJ 9663. N-Queen

https://www.acmicpc.net/problem/9663 9663번: N-Queen N-Queen 문제는 크기가 N × N인 체스판 위에 퀸 N개를 서로 공격할 수 없게 놓는 문제이다. N이 주어졌을 때, 퀸을 놓는 방법의 수를 구하는 프로그램을 작성하시오. www.acmicpc.net NxN 체스판에 퀸 N개를 서로 공격할 수 없게 놓는 경우의 수를 출력하는 문제로 N=4일때를 예시로 들면 다음과 같이 설명할 수 있다 4x4 체스판에 퀸 4개가 아래와 같이 있다 상태 공간 트리(State-Space Tree)로 1~4번 퀸의 위치를 표현할 수 있다 아래는 4개의 퀸들이 서로 공격할 수 없게 놓은 경우의 수 중 하나로, 상태 공간 트리로 표현했을 때는 다음과 같은 경로를 거치게 된다 - 퀸은 현..

이진 탐색(Binary Search)과 매개변수 탐색(Parametric Search)

이진탐색이란? 이진 탐색이란 정렬된 배열에서 타겟의 존재 여부와 존재한다면 해당 위치를 알려주는 알고리즘이다. 중요한 점은 정렬된 배열에서만 사용할 수 있다는 것이다 기존의 단순 비교를 통한 탐색을 한다면 최악의 경우 배열 안에 있는 N개의 데이터 모두와 비교해야하므로 시간복잡도가 O(N)인 반면, 이진탐색은 재귀적으로 탐색범위를 반으로 줄여나가서 시간복잡도가 O(logN)까지 줄일 수 있다 이진탐색과 매개변수 탐색 매개변수 탐색(parametric search)이란? *최적화 문제를 *결정 문제로 풀 수 있는 기술로 다음과 같은 상황에 이용할 수 있다. *최적화 문제(Optimization Problem): 가능한 해들 중 가장 좋은 해를 찾는 것 *결정 문제(Decision Problem): 답이 이..

파이썬으로 구현하는 퀵 정렬(Qucik Sort)

Concept 병합 정렬(Merge Sort)과 마찬가지로, 퀵 정렬은 분할 정복(Divide and Conquer) 기법과 재귀 알고리즘을 이용한 정렬 알고리즘으로, 시간복잡도는 $O(nlogn)$이다 하나의 리스트에서 피봇(pivot)이라고 불리는 임의의 기준값을 사용하여 pivot 값을 기준으로 pivot 보다 작은 값의 그룹과 큰값의 그룹으로 나눈다. 이 때 두 그룹의 각 요소들은 정렬된 상태는 아니지만, pivot은 정렬된 위치로 들어가게되며 이를 재귀호출을 통해 정렬하게 된다. 전체적인 동작 과정은 다음과 같다 구현 코드 (아래 코드는 pivot을 arr의 첫번째 요소로 잡은 코드입니다; pivot = arr[0]) 1) 정렬되지 않은 데이터 -> 리스트로 입력 받기 >>>3 2 4 6 9 1..

파이썬으로 구현하는 병합정렬(Merge Sort)

Concept 병합정렬은 분할 정복(Divide and Conquer) 기법과 재귀 알고리즘을 이용한 정렬 알고리즘으로, 시간복잡도는 O(nlogn)이다 하나의 리스트를 두 개의 균등한 크기로 분할하고 분할된 부분 리스트를 정렬한 다음, 두 개의 정렬된 부분 리스트를 합하여 전체가 정렬된 리스트를 얻는 정렬방법이다. 이때 병합 정렬은 아래와 같은 분할 정복 메커니즘을 따르게 된다 - 분할(Divide): 입력 리스트를 같은 크기의 2개의 부분 리스트로 분할한다 - 정복(Conquer): 부분 리스트를 정렬한다 - 결합(Combine): 정렬된 부분 리스트를 하나의 리스트에 통합한다 *이 때 그림에서 표현은 생략되었으나 부분 리스트의 크기가 1이 될 때까지 분할 후 정렬 후 합병과정을 거치게 된다 구현 코..

[SWEA] 분할 정복(Divide and Conquer)

본 글은 [SW Expert Academy]의 파이썬 SW문제 해결 응용-구현2 분할 정복 강의를 보고 정리한 글입니다 https://swexpertacademy.com/main/learn/course/subjectDetail.do?courseId=AVuPDYSqAAbw5UW6&subjectId=AWUYFsQq11kDFAVT SW Expert Academy SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요! swexpertacademy.com 분할 정복(Divide and Conquer) 목차 01 분할 정복 기법 02 병합 정렬 03 퀵 정렬 04 이진 검색 05 분할 정복 사례 01 분할 정복 기법 분할 정복(DnQ)이란? 탑다운 접근(Top-down approac)으로, 문제..

[SWEA] 완전 검색(Brute-force search)

본 글은 [SW Expert Academy]의 파이썬 SW문제 해결 응용-구현2 완전 검색 강의를 보고 정리한 글입니다 https://swexpertacademy.com/main/learn/course/subjectDetail.do?courseId=AVuPDYSqAAbw5UW6&subjectId=AWUYDrI61lYDFAVT# SW Expert Academy SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요! swexpertacademy.com 완전 검색(Brute-force search, 브루트 포스 서치) 목차 01 완전 검색 기법 02 조합적 문제 01 완전 검색 기법 완전 검색(Brute-force search)이란? 문제의 해(Solution)를 얻기 위해 가능한 모든 경..

[LM 평가지표] Perplexity, PPL

유원준님의 딥러닝을 이용한 자연어 처리 입문의 펄플렉서티(Perplexity, PPL) 글을 요약한 게시글입니다 언어모델의 평가 방법(Evaluation metric of Language Model), Perplexity PPL은 문장의 길이로 정규화된 문장 확률의 역수로, 문장 W의 길이가 N이라고 했을 때, PPL은 아래와 같다 $PPL(W)=P(w_1,w_2, \cdots, w_N)^{-\frac{1}{N}} = \sqrt{\frac{1}{P(w_1,w_2, \cdots, w_N)}}^N$ 문장의 확률에 체인룰(chain rule)을 적용하면 아래와 같다 $PPL(W)=\sqrt{\frac{1}{P(w_1,w_2, \cdots, w_N)}}^N=\sqrt{\frac{1}{\Pi_{i=1}^N P(w..

[그래프 이론] 플로이드-워셜(Floyd-Warshall) 알고리즘

플로이드-워셜(Floyd-Warshall) 알고리즘이란? 모든 두 노드 u,v 사이에서 가장 최단 거리를 찾는 알고리즘 시간복잡도 $O(n^3)$으로 그래프의 크기가 작을 때만 사용 가능 음의 에지(negative edge)가 있어도 계산이 가능한 알고리즘 단, 음의 사이클(negative cycle)이 있을 경우 불가능 기본 개념: $A^k$[i][j] 노드 i에서 j까지의 최단거리 비용에는 $index