목록분류 전체보기 (95)

히치키치

[백준] 1806번 : 부분합 - Python(파이썬)

문제 www.acmicpc.net/problem/1806 1806번: 부분합 첫째 줄에 N (10 ≤ N < 100,000)과 S (0 < S ≤ 100,000,000)가 주어진다. 둘째 줄에는 수열이 주어진다. 수열의 각 원소는 공백으로 구분되어져 있으며, 10,000이하의 자연수이다. www.acmicpc.net 풀이 투포인터 : start 지점과 end 지점 정해 그 부분의 합 구하기 최소 길이 : end와 start인 index의 차가 작을 수록 최소 길이 기준 값과 비교 : 더 크면 앞의 원소 삭제 / 더 작으면 뒤에 원소 추가 코드 #문제 : https://www.acmicpc.net/problem/1806 import sys N, S = map(int, sys.stdin.readline()...
알고리즘 스터디 2021. 5. 11. 02:39
[백준] 2661번 : 좋은 수열 - Python(파이썬)

문제 www.acmicpc.net/problem/2661 2661번: 좋은수열 첫 번째 줄에 1, 2, 3으로만 이루어져 있는 길이가 N인 좋은 수열들 중에서 가장 작은 수를 나타내는 수열만 출력한다. 수열을 이루는 1, 2, 3들 사이에는 빈칸을 두지 않는다. www.acmicpc.net 풀이 백트래킹 + BFS 가장 작은 수를 나타내는 수열 : 1,2,3 순으로 비교 진행 부분 수열 check 범위 : 전체 수열 길이의 절반 코드 #https://www.acmicpc.net/problem/2661 def back_tracking(idx): for i in range(1, (idx//2) + 1): if s[-i:] == s[-2*i:-i]: #나쁜 순열인 경우 return -1 if idx == n:..
알고리즘 스터디 2021. 5. 11. 01:58
[백준] 11559번 : Puyo Puyo - Python(파이썬)

문제 www.acmicpc.net/problem/11559 11559번: Puyo Puyo 총 12개의 줄에 필드의 정보가 주어지며, 각 줄에는 6개의 문자가 있다. 이때 .은 빈공간이고 .이 아닌것은 각각의 색깔의 뿌요를 나타낸다. R은 빨강, G는 초록, B는 파랑, P는 보라, Y는 노랑이다. www.acmicpc.net 풀이 DFS : 같은 색 & 이어진 뿌요 탐색 que : 현재 위치 중심으로 사라질 뿌요 탐색 set : 색깔 상관없이 사라질 모든 뿌요 집합 (=DFS에서 조건 만족한 모든 뿌요) 뿌요 내리기 : 밑에서부터 시작 / 위에 뿌요 있으면 . 과 바꿔주기 While : flag 켜져 있으면 연쇄 횟수 증가, flag 꺼지면 반복문 탈출 코드 #문제 https://www.acmicpc...
알고리즘 스터디 2021. 5. 3. 16:45
[백준] 14002 : 가장 긴 증가하는 부분수열 - Python(파이썬)

문제 www.acmicpc.net/problem/14002 14002번: 가장 긴 증가하는 부분 수열 4 수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이 www.acmicpc.net 풀이 동적 계획법 길이 : 일차원 배열에 당시 길이 최대값 유지/갱신 : 이전 수+1 수열 출력 : 배열에 최대값 가진 인덱스부터 -1 하며 원래 수열에서 해당 값 가져오기 코드 n = int(input()) arr = list(map(int, input().split())) max_len = [1]*n for i in ra..
알고리즘 스터디 2021. 5. 3. 16:41
Prev 1 ··· 13 14 15 16 17 18 19 ··· 24 Next