전체 글

[백준] 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()..

프롬프트 러닝, Prompt Learning이란?

프롬프트(Prompt)란? ChatGPT를 사용해 과제나 리포트 작성을 할 때, 원하는 방향으로 답변이 나오도록 여러가지 입력을 준 경험이 한 번씩 있다면, "프롬프트를 잘 줘야 ChatGPT가 대답을 잘해줘"라는 말을 들은 경험도 있을겁니다. 여기서 말하는 프롬프트(Prompt)란 무엇일까요? 위의 경험에 빗대어 생각해보면, ChatGPT 즉, 인공지능 모델에 넣어주는 입력값이라 볼 수 있을 것입니다. 조금 더 자세하게 살펴보기위해 프롬프트의 사전적 정의를 확인해보겠습니다. " An act of assisting or encouraging a hesitating speaker." 그대로 번역하자면, "망설이는 화자(Speaker)를 돕거나(Assist) 격려(Encourage)하는 행동"이라는 뜻입니다..

[그래프 탐색] 파이썬으로 구현하는 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 = ..

[NLTK] 자연어 처리를 위한 패키지

자연어처리(NLP, Natural Language Processing)를 위해서는 각 테스크에 맞는 전처리(preprocessing)과정이 필수적으로 필요합니다. 본 게시글에서는 전처리를 위한 패키지인 NLTK를 간단한 예제와 함께 알아보도록 하겠습니다. NLTK에서는 다양한 기능을 제공하지만, 본 글에서는 아래의 기능 위주로 다룹니다 Searching Text Word Statistics Searching Text NLTK에서 제공하는 텍스트 예제로 진행하기 위해, book을 불러오도록 하겠습니다. import nltk from nltk.book import * NLTK에서 book을 불러올 경우 아래의 9개의 책의 텍스트를 불러올 수 있습니다. text1에 저장된 Moby-Dick으로 nltk를 적용..

윈도우 코딩용 폰트 D2Coding 설치하는 방법

네이버에서 개발한 코딩용 폰트 D2Coding은 아래 깃허브 사이트에서 다운로드 할 수 있습니다. https://github.com/naver/d2codingfont/releases Releases · naver/d2codingfont D2 Coding 글꼴. Contribute to naver/d2codingfont development by creating an account on GitHub. github.com 해당 게시물 작성 기준(22.12.19)으로 최신 버전은 Ver 1.3.2입니다. 아래 사진의 노란라인을 쳐둔 D2Coding-Ver1.3.2-20180524.zip 파일만 다운 받으시면 됩니다 zip 파일을 압축해제까지 하면 다음의 경로로 들어가 아해의 .tff 파일 설치를 눌러줍니다. ..