algorithm

[백준][파이썬] 2559번 수열

2559번 : 수열 문제 매일 아침 9시에 학교에서 측정한 온도가 어떤 정수의 수열로 주어졌을 때, 연속적인 며칠 동안의 온도의 합이 가장 큰 값을 알아보고자 한다. 매일 측정한 온도가 정수의 수열로 주어졌을 때, 연속적인 며칠 동안의 온도의 합이 가장 큰 값을 계산하는 프로그램을 작성하시오. 입력 첫째 줄에는 두 개의 정수 N과 K가 한 개의 공백을 사이에 두고 순서대로 주어진다. 첫 번째 정수 N은 온도를 측정한 전체 날짜의 수이다. N은 2 이상 100,000 이하이다. 두 번째 정수 K는 합을 구하기 위한 연속적인 날짜의 수이다. K는 1과 N 사이의 정수이다. 둘째 줄에는 매일 측정한 온도를 나타내는 N개의 정수가 빈칸을 사이에 두고 주어진다. 이 수들은 모두 -100 이상 100 이하이다. 출..

[백준][파이썬] 20922번 겹치는건싫어

2161번 : 카드1 문제 홍대병에 걸린 도현이는 겹치는 것을 매우 싫어한다. 특히 수열에서 같은 원소가 여러 개 들어 있는 수열을 싫어한다. 도현이를 위해 같은 원소가 K개 이하로 들어 있는 최장 연속 부분 수열의 길이를 구하려고 한다. 100,000 이하의 양의 정수로 이루어진 길이가 N인 수열이 주어진다. 이 수열에서 같은 정수를 K개 이하로 포함한 최장 연속 부분 수열의 길이를 구하는 프로그램을 작성해보자. 입력 첫째 줄에 정수 N (1≤N≤200,000)과 K(1≤K≤100)가 주어진다. 출력 조건을 만족하는 최장 연속 부분 수열의 길이를 출력한다. 링크 20922번: 겹치는 건 싫어 (acmicpc.net) 20922번: 겹치는 건 싫어 홍대병에 걸린 도현이는 겹치는 것을 매우 싫어한다. 특히..

[알고리즘] 투 포인터(Two Pointers)

투 포인터 (Two Pointers) 리스트에 순차적으로 접근해야 할 때 두 개의 점의 위치를 기록하며 나아가는 알고리즘이다 시작점과 끝점을 그 두개의 점으로 지정한다 특정한 합을 가지는 부분 연속 수열 문제에 적용 가능하다 두 개의 점이므로 투 포인터라 한다 반복문만 사용하는 것보다 메모리와 시간 효율성을 높일 수 있다 시간 복잡도는 O(N) 이다 (반복문 사용시 O(N^2)) 앞에서 시작하는 포인터 & 끝에서 시작하는 포인터 두 포인터 중 start 포인터를 가장 앞 인덱스 0으로 설정하고, 나머지 end 포인터를 가장 마지막 인덱스 n으로 설정한다. 찾아야 하는 값 두 점의 합 → start 포인터를 인덱스 하나 늘려 ..

[백준][파이썬] 6236번 용돈 관리

꽤나 곤란한 문제였다...... 일단 문제 이해부터 막혀 블로그랑 질문 게시판을 많이 참고해야 했다. 그리고도 놓치는 조건들이 있어 열심히 써내려 가보며 문제를 풀었다. 이 포스팅에는 내가 헷갈린 모든 부분들을 담아보려 한다. 6236번 : 용돈 관리 문제 현우는 용돈을 효율적으로 활용하기 위해 계획을 짜기로 하였다. 현우는 앞으로 N일 동안 자신이 사용할 금액을 계산하였고, 돈을 펑펑 쓰지 않기 위해 정확히 M번만 통장에서 돈을 빼서 쓰기로 하였다. 현우는 통장에서 K원을 인출하며, 통장에서 뺀 돈으로 하루를 보낼 수 있으면 그대로 사용하고, 모자라게 되면 남은 금액은 통장에 집어넣고 다시 K원을 인출한다. 다만 현우는 M이라는 숫자를 좋아하기 때문에, 정확히 M번을 맞추기 위해서 남은 금액이 그날 사..

[알고리즘] 이진 탐색(Binary Search) + 매개변수 탐색(Parametric Search)

이진 탐색 반으로 쪼개면서 탐색하는 방법으로, 데이터가 정렬되어 있는 배열에서 사용할 수 있는 알고리즘이다. 탐색 범위를 절반씩 좁혀가며 데이터를 탐색하는 특징을 가지고 있다. 따라서 위치를 나타내는 변수 3개를 사용하는데 탐색하고자 하는 범위의 시작점, 끝점, 중간점을 변수로 가진다. 이진 탐색은 찾으려는 데이터와 중간점에 있는 데이터를 반복적으로 비교하며 탐색해 나간다. 시간 복잡도는 한 단계 거칠 때마다 확인하는 원소가 평균적으로 절반씩 줄어드므로 빅오 표기법에 의해 O(logN)이다. 코딩 테스트에서 단골로 나오는 문제이므로 외우는 것을 추천하며 보통 탐색 범위가 큰 상황에서 사용된다. 탐색 범위가 2000만을 넘어가면 이진 탐색 접근을 권한다고 한다. 구현 방법 1 : 재귀 함수 def bina..

[알고리즘][파이썬] Exhaustive Search / 완전 탐색

2023.07.07... 5학기 여름방학에 다시 시작하는 혼자 하는 알고리즘 레쮸고 !!!!!!!!! 완전 탐색이란 모든 경우의 수를 다 세는 방법 Brute force 직관적이어서 이해하기 쉬운 방법 상대적으로 구현이 간단한 방법 문제의 정확한 결과값을 얻어낼 수 있는 가장 확실하며 기초적인 방법 시간 복잡도가 O(N^2)인 방법 경우의 수에 따라 실행 시간이 비례하기 때문에 입력 값의 범위가 작은 경우 유용 완전 탐색 알고리즘 종류 Brute Force Bitmask (비트마스크) Recursive (재귀) Permutation (순열) BFS (너비우선탐색) & DFS (깊이우선탐색) Brute Force 반복문 or 조건문으로 모든 경우를 체크하여 정답 구하기 (ex) 000~999 사이의 자물쇠..

[알고리즘] 알고리즘 스터디 계획 / Algorithm Study Plan

다시 올리는 알고리즘 스터디 계획 ㅋㅋㅋㅋㅋ 5학기를 마친 여름방학에 ... 저번 겨울방학에 제대로 못한 부분을 채우려 한다 이번에는 나 혼자 !!! 진행할 것이다 목표 : 백준 Gold 달기 사용 언어 : 파이썬(Python) 커리큘럼 : 스택/큐 > 완전탐색 > .. (추후 추가) 일정 : 2023.07 ~ 2023.08 깃헙 레포지토리 : dudrhy12/Baekjoon (github.com) GitHub - dudrhy12/Baekjoon Contribute to dudrhy12/Baekjoon development by creating an account on GitHub. github.com

[알고리즘][파이썬] 그래프 / graph

그래프 (graph) 원소 간의 관계를 표현한 자료구조 그래프의 기본 구조 노드(node)=정점(vertex)와 간선(edge)으로 표현 두 노드가 인접하다 : 두 노드가 간선으로 연결되어 있다 노드1과 노드3은 인접하다 그래프 탐색 : 하나의 노드를 시작으로 다수의 노드를 방문하는 것 그래프의 표현 1. 인접 행렬 (Adjacency Matrix) 2차원 배열로 그래프의 연결관계를 표현하는 방식 2차원 배열에 각 노드가 연결된 형태를 기록하는 방식 연결되어 있지 않은 노드끼리는 무한의 비용으로 작성 (999999999,987654321) 자기자신은 비용이 0 0 1 2 0 0 무한 5 1 무한 0 3 2 5 3 0 INF = 999999999 #무한 graph = [ [0, INF, 5] [INF, 0..

[알고리즘][파이썬] 재귀함수 / Recursive Function

알고리즘 공부하다가.. 한 번 정리해둬야겠다 싶은 재귀함수 레쮸고 재귀함수 (Recursive Function) 자기 자신을 호출하는 함수 프랙털(Fractal) 구조와 흡사 기본 예제 def recursive(): print("재귀 함수 호출") recursive() recursive() 위와 같이 코드 실행 시 "재귀 함수 호출" 문자열이 계속 출력되다가 오류 메세지가 출력된다. "RecursionError: maximum recursion depth exceeded while pickling an object" 재귀의 최대 깊이를 초과했다는 내용으로 파이썬 인터프리터는 호출 횟수 제한이 있기 때문에 생기는 오류이다. (프로그래밍 대회에서는 파이썬의 재귀 호출 제한을 처리하기 위해 라이브러리를 사용하..

[백준][파이썬] 11866번 요세푸스 문제 0

11866번 : 요세푸스 문제 0 문제 요세푸스 문제는 다음과 같다. 1번부터 N번까지 N명의 사람이 원을 이루면서 앉아있고, 양의 정수 K(≤ N)가 주어진다. 이제 순서대로 K번째 사람을 제거한다. 한 사람이 제거되면 남은 사람들로 이루어진 원을 따라 이 과정을 계속해 나간다. 이 과정은 N명의 사람이 모두 제거될 때까지 계속된다. 원에서 사람들이 제거되는 순서를 (N, K)-요세푸스 순열이라고 한다. 예를 들어 (7, 3)-요세푸스 순열은 이다. N과 K가 주어지면 (N, K)-요세푸스 순열을 구하는 프로그램을 작성하시오. 입력 첫째 줄에 N과 K가 빈 칸을 사이에 두고 순서대로 주어진다. (1 ≤ K ≤ N ≤ 1,000) 출력 예제와 같이 요세푸스 순열을 출력한다. 링크 11866번: 요세푸스 ..