분류 전체보기

오랜만의 bfs, dfs 항상 그렇듯, dfs는 시간초과다. 처음 짠 코드 from collections import deque import sys input=sys.stdin.readline n,m=map(int,input().split()) M=[] for _ in range(n): M.append(list(str(input()))) def bfs(x,y,Mcopy): vismap=[[0 for x in range(m)] for y in range(n)] q=deque() cnt=1 q.append([x,y,cnt]) while q: x,y,cnt=q.popleft() a=[-1,1,0,0] b=[0,0,-1,1] for t in range(4): X=x+a[t] Y=y+b[t] if 0

작은 점프, 큰 점프 그리고 단 한번의 매우 큰 점프를 통해 마지막 돌로 가는 최소 에너지를 구하는 문제. 우선 단 한번의 매우 큰 점프를 제외하고 생각했다. 단 한번은 예외처리를 해주면 되니까 라는 생각에서 그랬다. n까지 가는데 드는 최소 에너지 dp(n)은 dp(n-1)+작은점프, dp(n-2)+큰점프 중 큰 값이다. 코드로 구현하면 n=int(input()) d=[[0,0]] for _ in range(n-1): d.append(list(map(int,input().split()))) dp=[0 for x in range(n+1)] if n==1: print(0) exit() elif n==2: print(d[1][0]) exit() dp[2]=d[1][0] dp[3]=min(d[1][0]+d[2..

다시한번 타일채우기. 이건 좀 특이한 타일채우기이다. 그래도 여타 타일채우기가 그렇듯, 역시 어렵다. 특이한 점은 이건 홀수일때 0이라는 점이다. n=2일때를 보자. n=3일때는 칸을 다 채울수 없으므로 n=4를 보면, 이렇게 쪼개서 생각 할 수 있다. 그리고 여기에 새로운 모양이 생기는데 바로, 이 두가지이다. 그래서 n(4)=3*n(2)+2=11임을 알 수 있다. 다음은 6이다. 마찬가지로 이렇게 볼 수 있다. 그리고 뒤집으면 이렇게 되는데, 여기서 세주면 전부 겹치고, 아까 n(4)에서 새롭게 만들어진 두개만 카운트 된다는 것을 알 수 있다. 그리고 n(6)의 새로운 모양도 생긴다. 그리고 n=8일때, 경우를 나눠보면 이 세가지인데 이를 통해서 n(8)=n(2)*n(6)+2(새로생긴 모양)*(n(4..

타일 싫어... 진짜 엄청 고민했던 문제. 겹치는 경우가 많아서 겹치지 않는 경우로 세야한다. n=3인 경우, 여기서 잘보면 두가지로 분류 할 수 있는데, 처음에 2*1이 온 경우와, 처음에 2*2또는 1*2가 온 경우이다. 처음에 2*1이 온 경우, n=3이므로 1을 뺀, n(2)와 같은 값을 가진다. 처음에 2*2나 1*2가 온 경우, n=3이므로, 2만큼 뺀, n(1)만큼의 값을 가진다. 따라서 일반항은 n(k)=n(k-1)+2*n(k-1)이다. 다시한번 살펴보면, 빨간 박스(2*2)는 처음 세는 값이므로 여기에는 이전 값의 모든 값이 와도 된다. 하지만 두번째, 파란박스에는 ㅣㅣ(2*1 2개)가 오면 빨간 박스와 겹치는 경우가 생긴다. 그래서 파란 박스에 올 수 있는 경우 중 2*2와 1*2 두개..

보통 책을 읽으면 내 생각을 적겠지만, 이 책은 그냥 내용을 기억하는게 더 좋을 것 같아서 내용을 요약해 보았다. 인내심 1. 버티는 것이 가장 중요하다. 인내심이 모든 성공의 시발점이다. 포기하지 않으면 기회는 반드시 찾아온다. 포기를 미화하지마라. 절대 무대에서 사라지지 말고, 문제를 정면돌파하라. 폭풍우를 견딘 나무만이 하늘 높이 성장한다. 기꺼이 대가를 치르고, 가치를 찾아라. 2. 포기가 전략이 될때는 오직 목적이 생존일 때뿐이다. 포기라는 단어에 변명을 매달지 마라. 만약 포기한다면, 깔끔하게 접고 포기했음을 인정하라. 3. 동 트기전이 가장 어둡다. 가파른 경사를 오르느라 숨이 막히고 고통스럽다면, 정상에 가까워졌다는 신호다. 좌절의 순간에는 정확한 인식을 할 수 없다. 이럴땐, 고민하지 말..

개인적으로 굉장히 어려웠던 문제... 첫째로, 최대 수도관 용량으로 dp를 할지, 길이로 dp로 할지 정한다고 해맸다. 두번째로, 입력받아서 배열에서 꺼내쓰려다가 시간초과로 쳐맞았다. 세번째로, 중복사용때문에 고생했다. 아무튼 코드는 아래와 같다. 초기화 방법은 입력값이 1이라고 하면 dp[1]이 들어가는 모든 값의 합을 바꾼다. x가 7이라고 한다면, dp[7]=min(1,dp[7-1])이다. 그리고 만약 dp[7]이 입력이 들어오면 변경 해주는 방식이다. d, p = map(int, input().split()) dp = [0 for _ in range(d+ 1)] for _ in range(p): l, c = map(int, input().split()) for x in reversed(range(..

0부터 n까지의 정수 k개를 더해서 n이 되는 경우의 수를 구하는 프로그램 뭔가 고등학교 시절의 자연수 분할이 떠오른다. 차이점은 0도 포함한다는 점 예를들어 0부터 9까지 2개로 나타내면 0+0 1+0, 0+1 2+0, 1+1, 0+2 3+0, 1+2, 2+1, 0+3 4+0, 1+3, 2+2, 3+1, 4+0 5+0, 1+4, 2+3, 3+2, 4+1, 5+0 ... 와 같이 (n,2)=n+1임을 알 수있다. 그리고 잘 보면, 1+ n-1, 2+n-2꼴로 나타 낼 수 있는데, 이를 잘 보면 (n,k)=(n-1,k-1)+(n-1,k-2)...(n-1,0)으로 나타낼 수 있음을 알 수 있다. 가로는 숫자, 세로는 k개로 나타 낸 것이다 0 1 2 3 4 1 1 1 1 1 1 2 1 2 3 4 5 3 1 ..

모든 인접한 수의 차이가 1인 수의 갯수를 찾는 문제 n=1일때, 1,2,3,4,5,6,7,8,9의 9개이다. (0으로 시작은 안되므로 제외) n=2일때, 10 21 32 12 23 43 54 34 65 45 56 76 67 87 78 98 89 90의 17개이다. 여기서 잘보면, n이 1일때의 두배에서 -1한 것임을 알 수 있다. 이게 n=3일때도 잘 작동해서 일반항이 n(k)=n(k-1)-(k-1)인지 알았으나 5부터 잘 작동하지 않았다. 그렇다면, 일반항을 따로 구할 수 없으니 케이스를 쪼개서 이전값에서 받아오자. 규칙을 찾으면, 어떤 수가 n으로 끝난다면, n으로 끝나는 수의 갯수는 이전 수의 n-1로 끝나는 수와 n+1로 끝나는 수의 갯수의 합이라는 것이다. 여기서 특이 케이스가 보이는데 바로 ..

드디어 dp도 감이 잡혀가는 듯 하다. 물론 다른 문제 풀면 또 아닌걸 느끼겠지만 미로를 오른쪽 아래로 가면서, 가장 사탕을 많이 챙기는 경우의 사탕 수를 구하는 문제 반복문을 돌리면서 현재값=max((x,y-1),(x-1,y),(x-1,y-1))+현재 사탕수 를 해주어 이전값의 최대값+현 사탕수를 구해준다. 다만, 벽 가장자리에 위치한 사탕의 경우 이전값을 구하기가 어려우므로 예외처리 해주었다. 이게 실버 1이라고? 하는 생각이 들었던 문제. import sys input=sys.stdin.readline n,m=map(int,input().split()) ma=[] for x in range(n): ma.append(list(map(int,input().split()))) dp=[[0 for x in..

이 글은 개인적인 생각으로, 사실과 다를 수 있습니다. SNS, 소셜 네트워크 서비스는 시간과 공간을 뛰어넘어 우리가 서로 소통할 수 있게 해주었다. 물론 장점이 매우 많다. 우리는 먼 거리의 친구들과 실시간으로 연락 할 수 있고, 오랜 친구들의 팔로우나, 친구추가로 끊어진 연이 다시 연결되기도 한다. 그러나, SNS는 분명하게 사회를 망치고 있다. 물론 지금 당장 SNS를 지우고 혼자 살라는 뜻은 아니다. 또한 분명 SNS로 행복을 얻는 사람들도 있을 것이다. 행복하다고 느낀다면 됐다. 내가 그런 사람들에게 개입할 권리는 없다. 그러나 그렇지 않다면, 이런 면이 분명하게 있고, 경계하면서 살아야 한다는 취지에서 이런 글을 적는다. 시각의 극대화 SNS, 특히 인스타그램의 게시글은 사진에 너무 집중되어 ..