빠르고 꾸준하게

자료구조 & 알고리즘/백준(Baekjoon)

[백준] 1477(파이썬) - 휴게소 세우기

https://www.acmicpc.net/problem/1477 1477번: 휴게소 세우기 첫째 줄에 현재 휴게소의 개수 N, 더 지으려고 하는 휴게소의 개수 M, 고속도로의 길이 L이 주어진다. N은 100보다 작거나 같으며, M도 100보다 작거나 같다. L은 100보다 크거나 같고, 1000보다 작거나 www.acmicpc.net 이 문제를 읽고 처음 든 생각은 이분 탐색으로 풀어야겠다 였다. 처음에는 입력받은 휴게소위치에 0과 l 값을 넣어줘서 각각 휴게소 사이의 거리들을 구해서 오름차순 정렬한 뒤, 각각 거리들의 차 만큼과 이분 탐색한 값을 비교해주면서 구현하였다. 이분 탐색으로 풀어야 하는데 카운트를 어떻게 할지가 문제였는데, 거리에 맞게 지어야 하므로 거리를 mid 값으로 나눈 값을 카운트..

자료구조 & 알고리즘/백준(Baekjoon)

[백준] 1182(파이썬) - 부분수열의 합

https://www.acmicpc.net/problem/1182 1182번: 부분수열의 합 첫째 줄에 정수의 개수를 나타내는 N과 정수 S가 주어진다. (1 ≤ N ≤ 20, |S| ≤ 1,000,000) 둘째 줄에 N개의 정수가 빈 칸을 사이에 두고 주어진다. 주어지는 정수의 절댓값은 100,000을 넘지 않는다. www.acmicpc.net 이 문제는 다양한 방법이 있을 거 같지만 일단은 직관적으로 풀어봤다. 그냥 주어진 입력값의 조합을 다 구해서 그 조합들의 합이 S가 될 때 cnt를 1씩 올려서 구현했는데 시간 초과가 날줄 알았는데 시간 초과 없이 통과했다. 두 번째 구현은 dfs로 구현했다. idx값과 Sum 변수를 함수 변수로 넘겨주고, idx는 1씩 더해서 재귀를 사용했고 Sum을 통해서 ..

자료구조 & 알고리즘/프로그래머스(programmers)

[programmers] 가장 긴 팰린드롬

https://programmers.co.kr/learn/courses/30/lessons/12904 코딩테스트 연습 - 가장 긴 팰린드롬 앞뒤를 뒤집어도 똑같은 문자열을 팰린드롬(palindrome)이라고 합니다. 문자열 s가 주어질 때, s의 부분문자열(Substring)중 가장 긴 팰린드롬의 길이를 return 하는 solution 함수를 완성해 주세요. 예를들 programmers.co.kr 이 문제는 문자열을 어떻게 쪼개고 비교할 것인가에 대한 문제였다. 처음에는 괄호 만들기처럼 스택에 넣고 하나하나 꺼내주면서 비교해주려고 했는데 그렇게 되면 가장 긴 팰린드롬을 구하기가 까다로워질 거 같아서 그냥 2중 for문으로 비교했다. 첫 번째 for문으로는 i를 주어진 문자열 길이 만큼 돌려주면서 j로는..

자료구조 & 알고리즘/프로그래머스(programmers)

[programmers] 멀리뛰기

https://programmers.co.kr/learn/courses/30/lessons/12914 코딩테스트 연습 - 멀리 뛰기 효진이는 멀리 뛰기를 연습하고 있습니다. 효진이는 한번에 1칸, 또는 2칸을 뛸 수 있습니다. 칸이 총 4개 있을 때, 효진이는 (1칸, 1칸, 1칸, 1칸) (1칸, 2칸, 1칸) (1칸, 1칸, 2칸) (2칸, 1칸, 1칸) (2칸, 2 programmers.co.kr 이 문제는 백준에서 풀었었던 계단 오르기와 비슷한 문제라고 생각했고 같은 방식은 DP로 풀기 시작했다. 간단하게 점화식을 세울 수 있었고, Bottom-up방식을 사용했고 2차원DP배열에 메모이제이션으로 구현했다. # 이문제는 dp문제이다. def solution(n): answer = 0 dp =[[0]..