# merge sort array = [6,5,3,1,8,7,2,4] def merge_sort(array): if len(array) < 2: # 원소가 하나인 경우 return array merged_array = [] mid = len(array)//2 left_array = merge_sort(array[:mid]) right_array = merge_sort(array[mid:]) l = r = 0 while l < len(left_array) and r < len(right_array): # 여기서는 작은 수 부터 정렬 if left_array[l] < right_array[r]: merged_array.append(left_array[l]) l += 1 else: merged_array.ap..
Algorithm (PS)
https://leetcode.com/problems/fibonacci-number/ Fibonacci Number - LeetCode Level up your coding skills and quickly land a job. This is the best place to expand your knowledge and get prepared for your next interview. leetcode.com 1. 재귀 class Solution: def fib(self, n: int) -> int: if n int: if n int: if n int: x, y = 0, 1 for i in range(n): x, y = y, x+y return x 모든 값을 저장하지 않고 변수 2개만을 이용해서 수열의 ..
https://leetcode.com/problems/longest-palindromic-substring/ Longest Palindromic Substring - LeetCode Level up your coding skills and quickly land a job. This is the best place to expand your knowledge and get prepared for your next interview. leetcode.com class Solution: def longestPalindrome(self, s: str) -> str: def solve(left:int, right:int) -> str: while left >= 0 and right < len(s) and s[l..
https://school.programmers.co.kr/learn/courses/30/lessons/43163 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 핵심 알고리즘 - 단어에서 알파벳은 하나씩만 바꿀 수 있으므로, begin 단어의 길이가 n이라고 했을 때 현재 확인하는 단어의 동일한 알파벳이 n-1 개 인지 체크해야 한다 - bfs 를 이용해서 풀면 최소 단계를 카운트 하기 편하다 !! queue에 step 을 저장하고 새로 업데이트 될때마다 step+1 해주면된다. from collections import deque def solution..
import math n = 1000 # 2 ~ 1000 까지의 모든 소수 array = [True]*(n+1) # 아리스토테네스의 체 for i in range(2, int(math.sqrt(n))+1): # 제곱수까지만 확인한다 if array[i]: j = 2 while i*j < n: # n 보다 작은 모든 i의 배수를 지운다 array[i*j] = False j += 1 for i in range(2, n+1): if array[i]: print(i, end=" ")
class Solution: def isPalindrome(self, s: str) -> bool: # 예외 처리 if s == " ": return True s = s.lower() # 소문자로 변환 new_str = "" for i in s: if i.isalnum(): new_str += i n = len(new_str) for i in range(n // 2): if new_str[i] != new_str[n - i - 1]: return False return True
1. 정직한 나의 dp 풀이 시간초과가 났다 # 1806 부분합 n, s = map(int, input().split()) array = list(map(int, input().split())) INF = int(1e9) dp = [INF] * (n+1) for i in range(n): temp = array[i] count = 1 for j in range(i+1, n): if temp >= s: dp[i] = count continue else: temp += array[j] count += 1 print(min(dp)) 2. 유형을 보니까 투포인터 알고리즘을 사용하는 것이다. 먼저 0번째 인덱스부터 현재 인덱스까지의 원소들의 합을 저장해 놓은 sum_array를 새로 만들어야 한다. 그리고 sum..
위상 정렬만 알면 날먹 가능한 문제이다 https://www.acmicpc.net/problem/2252 학생들을 줄 세워야 하는데 우선순위의 일부분이 m개 주어진다 이를 위상정렬 그래프로 생각하면 반드시 정점 a(학생1) 을 먼저 방문한 이후, 정점 b(학생2) 를 방문해야 한다 라는 순서가 된다. 위상정렬에서는 정점 b를 가기 위해서는 반드시 정점 a를 지나쳐야 하므로, 진입차수(indegree)가 1 증가하게 된다. # 위상 정렬 from collections import deque v, e = map(int, input().split()) indegree = [0]*(v+1) # 진입 차수 graph = [[] for _ in range(v+1)] for _ in range(e): a, b = m..
