제일 왼쪽은 고정해놓고 그 오른쪽만 투포인터로 계산한다. O(n^2) 정렬해놓고 합이 작으면 더 큰 곳으로 이동하고 크면 오른쪽 포인터를 왼쪽으로 이동시킨다 같은 원소가 있는 부분은 넘어가면서 구한다 1. python class Solution: def threeSum(self, nums: List[int]) -> List[List[int]]: nums.sort() res=[] for i in range(len(nums)-2): if i>0 and nums[i]==nums[i-1]: continue # 중복인 경우 넘어간다 left,right=i+1,len(nums)-1 while left
각 왼쪽, 오른쪽 끝에서 시작한다. 왼쪽의 벽이 더 높으면 오른쪽에서 안쪽으로 이동하고 (더 큰 벽을 찾아서) 오른쪽 벽이 더 높다면 왼쪽에서 안쪽으로 이동한다. 만약 현재 왼쪽에서 안쪽으로 이동하는데 지금까지 왼쪽에서 만난 벽 중 가장 높은 위치 lh 보다 작은 곳이라면 물이 고이므로 lh-height[l] 이런 식으로 더해준다. 1. python class Solution: def trap(self, height: List[int]) -> int: if not height: return 0 left,right=0,len(height)-1 l_max,r_max=height[left],height[right] amount=0 while left
연속된 집은 털 수 없다. 바로 이전 집의 dp값이나 두 번째 전 집에서 현재 집을 턴 합 중 더 큰 값이 현재 위치의 집에서 가장 큰 값이 된다 from collections import defaultdict class Solution: def rob(self, nums: List[int]) -> int: if not nums: return 0 if len(nums)
계단 오르기 문제 메모이제이션으로 재귀로 풀어도 되고 반복문으로 풀어도 된다 1계단에 오르는 방법 1로 가는거 한 가지, 2 계단에 오르는 법은 1에서 1칸 가는 방법, 0에서 2칸 가는 방법 2가지로 초기화한다. 나머지만 현재 위치보다 1칸 아래에서 오는 방법과 2칸 아래에서 오는 방법을 더해주면 된다 from collections import defaultdict class Solution: def climbStairs(self, n: int) -> int: dp=defaultdict(int) dp[1]=1 dp[2]=2 for i in range(3,n+1): dp[i]=dp[i-1]+dp[i-2] return dp[n]
수학적인 풀이가 대부분이라 수학적으로 풀었는데 그렇게 풀기 위한게 맞는 건지 모르겠다 알고리즘 능력 기르려고 대표 문제 풀때는 수학적인 문제 나오면 좀 싫다 ㅠㅠ 배열이 2개인 경우와 3개인 경우로 나눠서 풀면 되는데 4개인 경우에는 배열 2개인 경우보다 절대로 작을 수 없기 때문이다. (수학 공식) # you can write to stdout for debugging purposes, e.g. # print("this is a debug message") def solution(A): # write your code in Python 3.6 min_value=sum(A[:2])/2 ans=0 # 3개인 배열을 위해서 인덱스 제한 for i in range(1,len(A)-2): # 원소 2개인 배열 ..
음수 경우를 생각하면서 풀어야 되는 문제 1. 가장 작은 수들이 음수인 경우 가장 작은 음수 2개 (절대값은 크다) * 가장 큰 원소를 곱할 경우 가장 큰 원소가 나올 수 있다. 가장 큰 원소도 음수인 경우는 자연스럽게 작은 수가 된다 2. 한 경우는 모든 것이 양수이고 세 개 곱한 것이 가장 큰 수인 경우이다 def solution(A): # write your code in Python 3.6 A.sort(); a=A[-1]*A[-2]*A[-3] b=A[0]*A[1]*A[-1] if a>b: return a else: return b
합이 최대인 부분 배열을 찾는다 현재 값 혹은 현재값 + 이전까지의 합이 큰지 비교해서 더 큰 값을 dp배열에 넣고 최대 값을 리턴하면 된다. O(n)이 걸린다 class Solution: def maxSubArray(self, nums: List[int]) -> int: answer=[nums[0]] for i in range(1,len(nums)): answer.append(nums[i]+(answer[i-1] if answer[i-1]>0 else 0)) return max(answer) * 카데인 알고리즘 (가끔 알고리즘이나 자료구조 공부할 때 항상 등장하는 부분배열 최대값 구하기 알고리즘이다 O(n)에 구할 수 있다 현재의 부분 배열 합과 리턴해줄 최대값을 비교해 더 큰 값으로 계속 갱신해준다 ..
www.acmicpc.net/problem/15685 15685번: 드래곤 커브 첫째 줄에 드래곤 커브의 개수 N(1 ≤ N ≤ 20)이 주어진다. 둘째 줄부터 N개의 줄에는 드래곤 커브의 정보가 주어진다. 드래곤 커브의 정보는 네 정수 x, y, d, g로 이루어져 있다. x와 y는 드래곤 커� www.acmicpc.net from collections import deque from collections import defaultdict dict=defaultdict(int) n=int(input()) dy,dx=[0,-1,0,1],[1,0,-1,0] # 북서남동 0 1 2 3 => 서남동북 1 2 3 0 def dragon(x,y,d,g): direct=[d] dict[(x, y)] = 1 # 시작..
www.acmicpc.net/problem/14889 14889번: 스타트와 링크 예제 2의 경우에 (1, 3, 6), (2, 4, 5)로 팀을 나누면 되고, 예제 3의 경우에는 (1, 2, 4, 5), (3, 6, 7, 8)로 팀을 나누면 된다. www.acmicpc.net from collections import deque from itertools import combinations import math n=int(input()) a=[list(map(int,input().split())) for _ in range(n)] p=[i for i in range(n)] allcase=combinations(p,n//2) ans=math.inf def check(start): global ans lin..
www.acmicpc.net/problem/14502 14502번: 연구소 인체에 치명적인 바이러스를 연구하던 연구소에서 바이러스가 유출되었다. 다행히 바이러스는 아직 퍼지지 않았고, 바이러스의 확산을 막기 위해서 연구소에 벽을 세우려고 한다. 연구소는 크� www.acmicpc.net from collections import deque import math from itertools import combinations import copy n,m=map(int,input().split()) a,blank,virus=[],[],[] dy,dx=[1,-1,0,0],[0,0,1,-1] for y in range(n): tmp=list(map(int,input().split())) a.append(tmp) ..