Algorithm

[백준] 12865번: 평범한 배낭 - 파이썬(Python)

https://www.acmicpc.net/problem/12865 해당 문제의 주어진 입력과 목표를 먼저 살펴봅시다.  1. 문제 입력 & 목표해당 문제의 주어진 입력과 목표를 먼저 살펴봅시다. 문제 입력 N: 물품의 수 (1 ≤ N ≤ 100)K: 버틸 수 있는 최대 무게 (1 ≤ K ≤ 100,000)w,v : 물건의 무게, 물건의 가치 (1 ≤ W ≤ 100,000 / 0 ≤ V ≤ 1,000)  문제 목표배낭이 버틸 수 있는 최대 무게인 K가 넘지 않는 선에서, 담을 수 있는 물건의 최대 가치를 구해라  2. 접근 방식문제의 첫 번째 예제를 시각화하면 다음과 같습니다.  편의상 물건의 인덱스를 1부터 시작한다고 할 때,왼쪽의 배열은 i번째 물건의 무게(w), 가치(v)이며, 오른쪽은 최대 배낭이..

파이썬으로 구현하는 세그먼트 트리(Segment Tree)

https://codingsmu.tistory.com/175 파이썬으로 구현하는 구간합과 누적합(Prefix sum)구간합이란?구간합이란, 나열된 숫자에서 특정 구간의 합을 말합니다. 만약 위의 arr에서 1~3번째 구간합을 구하고 싶다면, arr[1]+arr[2]+arr[3] = 4+3+2 = 9 입니다. 가장 기본적인 구간합 알고리즘을codingsmu.tistory.com 이전 글에서 먼저, 배열에서의 특정 구간의 합을 구할 때 O(N) 시간안에 구할 수 있는 누적합(Prefix Sum)알고리즘을 알아보았습니다. 이번 글에서는 더 개선된 시간인 O(logN)으로 구간합을 구할 수 있는 자료구조인 세그먼트 트리(Segment Tree)에 대해 알아보도록 하겠습니다.    세그먼트 트리(Segment T..

파이썬으로 구현하는 구간합과 누적합(Prefix sum)

구간합이란?구간합이란, 나열된 숫자에서 특정 구간의 합을 말합니다. 만약 위의 arr에서 1~3번째 구간합을 구하고 싶다면, arr[1]+arr[2]+arr[3] = 4+3+2 = 9 입니다. 가장 기본적인 구간합 알고리즘을 생각해보면, 단순히  i~j번째까지의 값을 더하면 되고 이때 시간복잡도는 O(N)입니다.하지만, 배열의 크기인 N이 매우 크고 구간합을 물어보는 쿼리가 N번이라면,다음과 같이 O(N)*O(N) ≈  O(N^2)이라는 거듭제곱의 높은 시간복잡도를 가지는 알고리즘이 됩니다.arr = list(map(int, input().split())) # 크기가 n개인 arrfor _ in range(N): # N 번의 쿼리 : O(N) i, j = map(int, input().split()..

[그래프 탐색] 파이썬으로 구현하는 DFS, BFS

그래프 탐색이란?그래프의 각 노드를 방문하는 것으로, 크게 깊이 우선탐색(Depth First Search, DFS)과 너비 우선 탐색(Bredth-First Search, BFS) 알고리즘이 있습니다.  DFS는 주로 재귀 혹은 스택으로 구현하게 되며, 백트래킹 문제에서 주로 사용됩니다. BFS의 경우 주로 큐로 구현하며, 최단 경로를 구하는 문제에서 자주 사용됩니다.  파이썬으로 그래프 입력받기그래프 탐색 방법을 구현하기 전, 파이썬에서 그래프를 입력받는 방법에 대해서 알아보도록 하겠습니다. 파이썬에서 제공하는 List, deque등 다양한 자료형으로 저장할 수 있지만, 개인적으로 파이썬의 Dictionary 자료형으로 입력받는 것을 가장 선호해 이 방법을 소개하고자 합니다. 앞의 그림과 같이 노드 ..

[문자열] 파이썬으로 구현한 유효한 팰린드롬(Palindrome)

팰린드롬(Palindrome)이란? 앞뒤가 똑같은 단어나 문장으로, 뒤집어도 같은 말이 되는 단어 또는 문장을 팰린드롬, 우리말로는 회문이라고 부릅니다. 영어의 회문으로는 "No lemon, no melon"처럼 뒤집어도 같은 알파벳 순서를 가지는 문장을 예시로 들 수 있습니다. 예시와 같이 회문은 보통 대소문자와 공백, 특수문자를 구별하지 않습니다. (단, 문제마다 정의하는 회문이 다를 수 있습니다) 파이썬으로 유효한 팰린드롬 검사하기 자료형에 따른 구현 방법 1. 리스트로 구현 2. 덱(deque)으로 구현 각 방법을 보기 전, 입력으로 들어오는 strs은 다음의 정규식을 통해 대소문자/특수문자/공백 구분 없이 유효성을 검사할 수 있도록 처리되었습니다 strs = strs.lower() strs = ..

[SWEA] 그래프의 최소 비용 문제

본 글은 [SW Expert Academy]의 파이썬 SW문제 해결 응용-구현2 완전 검색 강의를 보고 정리한 글입니다 https://swexpertacademy.com/main/learn/course/subjectDetail.do?courseId=AVuPDYSqAAbw5UW6&subjectId=AWUYHO7a2JoDFAVT# SW Expert Academy SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요! swexpertacademy.com 그래프의 최소 비용 문제 목차 01 최소 신장 트리 02 프림 알고리즘 03 크루스칼 알고리즘 04 최단 경로 05 다익스트라 알고리즘 01 최소 신장 트리 그래프에서 최소 비용 문제 유형 1. 최소 *신장 트리 문제 가중치 그래프에서 모든..

[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): 답이 이..