알고리즘

상당히 어려웠다. 합을 기록해서 뺀 것과 비교한다는 것을 떠올리기 너무 힘들었다. a+b+c=d라는 식에서 a+b=d-c를 유도해서 풀어야 했다. 그러면 수를 3개만 골라도 되기때문에 O(N^3)으로 풀 수 있다. #https://www.acmicpc.net/problem/2295 n = int(input()) u = set() ans=[] for i in range(n): u.add(int(input())) sums = set() for i in u: for j in u: sums.add(i + j) for i in u: for j in u: if (i - j) in sums: ans.append(i) ans.sort() print(ans[-1])

생각보다 많이 어려웠던... 상상도 못했던 방법으로 해결했던 문제 처음 풀이는 재귀로 했더니 시간복잡도때문에 시간초과가 발생했다. def do(rest,ans,start): mmax=0 ch=0 if rest==0: return ans else: for x in range(start,len(num)): if x+rest

복잡하지만 꼼꼼히 잘 작성해 주면 됐던 문제 마지막에 good을 추가로 출력해주면서, 반례를 잡아주었다. import heapq from collections import deque n=int(input()) line=deque() heap=[] stack=[] #대기줄 for _ in range(n): l=list(map(str,input().split())) for x in l: a,b=x.split('-') b=int(b) heapq.heappush(heap,[a,b]) line.append([a,b]) while heap: target=heapq.heappop(heap) while line: x=line.popleft() if x!=target: if stack: y=stack.pop() if y..

사과와 뱀은 matrix와 visited(덱)에 기록하고, 시간은 힙에 넣어서 보관했다. 방향 계산을 떠올리기 힘들었던 문제 from collections import deque import heapq def change(d, c): if c == "L": d = (d - 1) % 4 else: d = (d + 1) % 4 return d def start(): direction = 1 time = 1 y, x = 0, 0 visited = deque([[y, x]]) matrix[y][x] = 2 if times: ftime=heapq.heappop(times) else: ftime=[] while True: y, x = y + dy[direction], x + dx[direction] if 0

뒤에 들어온 문장부터 확인해서 문자열 리스트에 추가해부고, 겹치는게 하나도 없다면 c만큼 출력하고, 겹치는게 있을때마다 c값을 하나씩 깎아내면 된다. 중복 유무는 딕셔너리로 확인해주었다. r,c=map(int,input().split()) table=[] for _ in range(r): l=list(input()) table.append(l) cnt=r-1 strlist=['' for _ in range(c)] while table: li=table.pop() ch={} k=0 for x in range(c): if ch.get(strlist[x]+li[x]) is None: strlist[x]=strlist[x]+li[x] ch[strlist[x]]=1 else: strlist[x]=strlist[x..

생각보다 까다로웠던 문제 import heapq n=int(input()) m=[] for _ in range(n): m.extend(list(map(int,input().split()))) reverse_sign = lambda x: x*-1 m=list(map(reverse_sign,m)) heapq.heapify(m) for _ in range(n-1): heapq.heappop(m) print(-heapq.heappop(m)) 이렇게 모든 수를 힙에 집어넣고, 출력했더니 메모리 초과가 났다. 이유는 int가 32비트이기 때문이다. 32*1500*1500/1000000 = 72MB이기때문이다. 그래서 힙을 n개로 유지했다. import heapq n=int(input()) heap=[] for _ ..

꽤나 중요한 것을 배웠던 문제 아래는 시간초과 났던 코드이다. n=int(input()) l=list(map(int,input().split())) result=[0 for x in range(n)] for x in range(len(l)): stack=l[:x+1] now=stack.pop() t=0 cnt=0 while tl[x]: result[x]=stack[-1][0]+1 break else: stack.pop() stack.append([x,l[x]]) result=map(str,result) print(" ".join(result)) 코드 구조와 별개로 시간복잡도가 달라질 수 있다는 것을 배웠다. 조금더 파봐야 하겠지만 꽤나 흥미롭다.

처음에는 dfs로 해결하려 했지만, 시간 초과에 부딪혔다. 답은 우선순위 큐였다. 하나만 쓸려다가 계속 막혔는데 두개를 써보니 해결됐다. 우선순위 큐에서 꺼내면서 그 값의 end값을 q안에 push한다. 그리고 end값과 q[0]을 비교하고, 만족했을 때 그값을 빼내면 된다. 비교했을때 만족하지 못해도 그냥 q에 넣는다. 마지막엔 q에 남아있는 값의 수를 출력해주면 된다. #https://www.acmicpc.net/problem/1374 import sys import heapq input=sys.stdin.readline n=int(input()) lecture=[] q=[] for _ in range(n): l=list(map(int,input().split())) heapq.heappush(lec..

조건 정리 1. 이름이 중복되면 더이상 값을 안받음 2. 겹치는 시간대의 수가 가장 많은 장소를 골라냄 3. 많은 경우 사전순으로 배열 4. 그 중에서 가장 빠른 시간대를 골라냄 풀이 메모리 제한이 512MB인데, 시간대 제한인 50000으로 계산하면 총 제출수 10(각각 다른 장소 일 수 있으므로)*50000*4(int)가 되겠다. 총 2MB이므로 매우 널널하게 잡아 줄 수 있다. 그래서 장소마다 딕셔너리로 50000따리 리스트를 할당했다. 그리고 제출 받을때, 시작점과 끝점까지 반복시키며 시간대를 증가시켜준다. 가장 큰 숫자가 찍힌 부분이 겹치는 부분이다. 그리고 동시에 겹치는 부분이 가장 큰 장소를 maxplace에 저장했다. maxplace의 숫자가 크다면, maxpace를 비워주고, 그것만 추가..

stack을 사용해 해결했다. 사실 zip부분은 큐를 쓰면 좀 더 빠를 것 같지만... 그냥 stack으로 해봤다. 문자와 숫자를 동시에 받아서 처리하는데 예외상황이 나와서 처리하는데 애먹었다. #https://www.acmicpc.net/problem/23300 def doforward(now): if forward: backward.append(now) now=forward.pop() return now def dobackward(now): if backward: forward.append(now) now=backward.pop() return now def connect(where,now): if now=='first': now=where else: backward.append(now) now=wh..