분류 전체보기

백트래킹 문제. dfs로 돌려서 경로를 s에 튜플 형태로 모두 저장했다. 그 후에 s를 set으로 바꿔서 중복을 제거하고 갯수를 세어주면 오케이 #https://www.acmicpc.net/problem/17255 from collections import deque def dfs(start,end,res): vis=deque(res[-1]) if len(vis)==len(l): s.append(tuple(res)) return if start-1>=0: vis.appendleft(l[start-1]) res.append(tuple(vis)) dfs(start-1,end,res) vis.popleft() res.pop() if end+1

상당히 어려웠다. 합을 기록해서 뺀 것과 비교한다는 것을 떠올리기 너무 힘들었다. 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])

First rule of fight club is "You do not talk about fight club". 파이트클럽을 봤다. 사실 그냥 다 줘 패는 영환줄 알고 봤는데... 전혀 아니었다 ㅋㅋ 사실 쉬려고 본 영환데 오히려 많은 생각을 하게 만드는 영화였다. 어쨌든 너무 좋았던 영화. 상당히 감명 깊게 봤다. 이런 주제를 자극적이면서도 아주 참신한 방식으로 표현할 수 있구나를 굉장히 많이 느꼈던 영화였다. 이게 99년도 영화라니 믿을 수가 없다. 그리고 타일러 더든이 없애버리려고 했던, 초토화시켜버리려고 했던 소비지상주의는 심해졌으면 심해졌지 정말 나아진 것은 없구나란 생각을 많이 했다. 아 이거 스포리뷰니까 안 본 사람들은 알아서 잘 피하기 바란다. 주인공은 반복되는 일을 하고, 일에 대한 스..

생각보다 많이 어려웠던... 상상도 못했던 방법으로 해결했던 문제 처음 풀이는 재귀로 했더니 시간복잡도때문에 시간초과가 발생했다. 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..

보통의 경우엔 도파민은 인생의 최대 적이라고 생각할 수 있다. 도파민 중독은 삶을 피폐하게 하고, 만족할 수 없는 삶으로 만들기 때문이다. 게임중독이었던 사람의 극복 경험담 https://www.youtube.com/watch?v=H25yb5RBzW0&t=702s 그러나 이 중독이라는 것은 과잉 공급되었을때, 뇌가 도파민 감수성이 떨어져서 일어나는 현상이다. 그래서 더 많은 양을 공급해야하고, 공급하면 공급할 수록 더 많은 양을 얻어야 한다. 근데 이 논리라면 약 20년간 온갖 도파민에 다 노출되어 있는 나는 도파민 중독인가? 나는 누구보다 음주를 즐기고, 게임을 즐기고, 코인 선물 거래, 주식 거래를 하면서 정말 굉장히 많은 도파민에 노출되었었다. 잠도 못자고 거래할 정도로 피폐하기 지내보기도 했었다...

생각보다 까다로웠던 문제 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)) 코드 구조와 별개로 시간복잡도가 달라질 수 있다는 것을 배웠다. 조금더 파봐야 하겠지만 꽤나 흥미롭다.