PurplePurple

보호되어 있는 글입니다.

보호되어 있는 글입니다.

# 14002 1699 2225 1149 1309 11057 9465 1932 11055 11722 # task num = int(input()) seq = [int(i) for i in input().split()] dp = [1]*num # 0부터 5까지 6개의 원소 tracker = [-1]*num for i in range(1,num): #1부터 5까지 5개의 원소 for j in range(0,i): if seq[j]=dp[i]: dp[i] = dp[j]+1 tracker[i]= j max_value = max(dp) # 어레이에서 가장 큰 값 idx = dp.index(max_value) print(max_value) answer=[] while True: answer.append(seq[id..

# 잡소리 이놈의 굼뱅이같은 언어 파이썬은 작성하기는 편한데 속도가 느려터졌다. 뭐 백준 실버문제가지고 뭔 속도타령이냐 할 수도 있겠지만 실행속도를 빠르게 만들고 싶다는 욕구가 충만해진다. 그런의미에서 지금 타이밍에 배우는 다이나믹 프로그램은 이런 욕망을 해갈해보라고 던져준 좋은 개념일 것이다. 백준의 기초 알고리즘 1/2을 듣고나서부터 본격적으로 뭔가 알고리즘스러운 것을 배우기 시작한 기분이 든다. [1] 동적 계획법의 고안자인 벨만(Richard E. Bellman)은(벨만-포드 알고리즘의 그 벨만 맞다.) dynamic이라는 단어가 멋있어서(...) 선택했다고 한다. Programming이란 단어는 최적화 연구 분야에서 최적의 프로그램을 찾아낸다는 의미로 사용된다. - 프로그래밍 대회에서 배우는 알..

from sys import stdin from math import sqrt while True: n=int(stdin.readline()) # n 입력 if n==0: break prime_list = [True]*(n+1) # n까지 소수여부 # 에라토스테네스의 체 maxroot = int(sqrt(n)) for i in range(3,maxroot+1,2): # 3부터 n의 최대약수가 될 수 있는 루트n까지 2씩 뛰면서 체크(짝수는 배제) if prime_list[i]: #i가 True라면=소수라면, for j in range(3*i, n+1, 2*i): prime_list[j] = False # 3i부터 m까지 2i씩 뛰면서 i의 배수는 다 소수아님. # 소수쌍 판별기 for i in range..

백준의 기초알고리즘 수학1 강의를 들었다. 아무래도 계절학기로 이산수학을 들었기 때문에, 개념자체는 어려울 게 없었다. 유클리드 호제법을 통한 최대공약수, 최소공배수 구하는 알고리즘 (시간복잡도 O(logn) ) 소수판별 알고리즘(시간복잡도 O(sqrt(n))이지만, sqrt(n)할바에 n/2 ) 범위가 제한된 환경에서 사용하는 에라스토테네스의 체 ( 시간복잡도 O( log(log(n)) ) 이렇게 세가지를 배워보았다. 뭐 유클리드 호제법이랑, 소수판별 알고리즘은 프로그래머스 기초100제에서도 이미 풀어봤고 그리 복잡할게 없었으나 에라스토테네스의 체는 개념으로는 이해가 가면서도 실제로 구현을 위해서는 코드의 구성이 O(n^2)이 안되도록 설계해야 하는데, 상당히 당황스러울 수 밖에 없다. 에라스토테네스의..

보호되어 있는 글입니다.

https://plzrun.tistory.com/entry/%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-%EB%AC%B8%EC%A0%9C%ED%92%80%EC%9D%B4PS-%EC%8B%9C%EC%9E%91%ED%95%98%EA%B8%B0

백준 알고리즘 기초 (1/2)를 본격적으로 풀어보자. 자료구조수업에서 배웠던 stack이다. 파이썬 역시 list 자료형이 기본적으로 주어지기에, 쉽게 구현하였다. 스택을 포함한 자료구조를 구현할 때 조심해야 할 점은 아래의 기초연산을 제외한 다른 연산을 막 사용했다가 알고리즘의 시간복잡도를 더 늘려버릴 수도 있기에 최대한 기초연산을 생각하며 구현할 수 있도록 노력하는 것이 아닐까? 물론 append가 O(1)의 연산이기는 하지만, C언어에서 배운 array 구조의 원초적인 접근은 따로 어레이의 길이를 추적하는 length에 해당하는 변수를 만들어서 꾸준히 추적하는 것이 핵심이라고 생각을 했었다. 다만 후술할 시간초과의 문제는 append나 pop을 막 썼다고 생기는 문제는 아니고 input함수가 그만큼..

문자열을 다루는 법 ---------------------------- 1. 특정 문자의 제거 (https://school.programmers.co.kr/learn/courses/30/lessons/120826) - 내가 사용한 방법 C언어 맹쿠로 문자열을 나타내기 위해 list(my_string)을 한 후 for문을 돌려서 새 리스트를 append로 만든 후 ' '.join() 하기. -> 파이썬의 문자열을 다루는 방법에 대해 익숙해질 필요가 있다. def solution(my_string, letter): answer = [] str_list = list(my_string) for letter_list in str_list: if letter_list != letter: answer.append(l..