본문 바로가기

전체 글

 (261)
[다이나믹 프로그래밍] 피보나치 수열, 개미 전사, 1로 만들기, 효율적인 화폐 구성, 금광, 병사 배치하기 python 다이나믹 프로그래밍(Dynamic Programming, 동적 계획법) 메모리를 적절히 사용하여 수행 시간 효율성을 비약적으로 향상시키는 방법 계산한 결과를 메모리에 저장해(Memoization) 다시 계산하는 일이 없게 함 구현 방식은 일반적으로 탑다운방식과 보텀업방식이 있음 탑다운방식-큰 문제를 잘게 쪼개어 푸는 것 보텀업방식-작은 문제들을 해결해 큰 문제를 해결하는 것 다이나믹 프로그래밍의 조건 주어진 문제가 다음의 조건들을 만족할 때 다이나믹 프로그래밍을 사용할 수 있음 최적 부분 구조 (Optimal Substructure) 큰 문제를 작은 문제로 나누고 작은 문제의 답을 모아 큰 문제를 해결할 수 있을 때 중복되는 부분 문제 (Overlapping Subproblem) 동일한 작은 문제를 반복..
[백준] 16928 : 뱀과 사다리 게임 python 1. 사다리와 뱀을 만나면 무조건 이동한다. 2. 사다리와 뱀이 있는 칸은 여러 번 방문할 수도 있으니, 주사위 던진 횟수가 최소가 되게 신경써야 한다. 이 두 가지만 신경쓰면 크게 어렵지 않은 문제였다. from collections import deque import sys input = sys.stdin.readline def bfs(start): q = deque() # 시작점을 큐에 넣고 방문체크 q.append(start) visited[start] = True while q: # 현재 위치를 cur에 저장 cur = q.popleft() # 주사위를 굴려서 갈 수 있는 곳을 확인함 for i in range(1,7): ncur = cur+i # 100번 칸에 도달했다면 주사위 던진 횟수를+1..
[백준] 1012 : 유기농 배추 python 배추들이 상하좌우로 인접해있는 곳에는 배추흰지렁이가 한 마리만 있어도 되기 때문에 모든 배추들이 탐색완료가 될 때까지 BFS나 DFS를 수행하고 그 횟수를 세주면 되는 간단한 문제다. 평소엔 행을 x로 열을 y로 두고 푸는 경우가 많은데 이 문제에선 반대라서 그게 좀 헷갈렸다. from collections import deque import sys input = sys.stdin.readline def bfs(ay,bx): q = deque() q.append((ay,bx)) visited[ay][bx] = True while q: y,x = q.popleft() for i in range(4): ny = y+dy[i] nx = x+dx[i] if 0
JLPT N1 163점 합격 후기 (공부팁은 하나도 없습니다) 제목에도 적혀있듯이 이건 시험합격 후기이긴하지만 이 글을 읽음으로써 JLPT 준비에 대한 팁을 받아가는 사람은 거의 없을 것이라고 생각한다. 시험준비에 대한 정보를 받고 싶어서 들어오셨다면 유감입니다. 그렇지만 일본문화에 아주 익숙한 오타쿠라면...도움이 될지도 모른다. 아무튼 합격후기를 빙자한 내 일본어공부 연대기(?)를 써보겠다. https://www.youtube.com/watch?v=7462CNWWwdQ 일본밴드지만 영어가사가 훨씬 많은 엘르가든. 그냥 내가 좋아함 우리집안엔 오타쿠가 많다. 그래서 어릴 때부터 온갖 만화, 애니메이션을 보고 들으며 자랐다. (일본드라마는 언내추럴 하나밖에 안봤음) 초등학생 때는 형제의 영향으로 내 세대에는 모르는 게 당연한 동방신기 일본노래를 들었다. 그래서 흔히..
[백준] 12015 : 가장 긴 증가하는 부분 수열 2 python https://velog.io/@ledcost/%EB%B0%B1%EC%A4%80-12015-%ED%8C%8C%EC%9D%B4%EC%8D%AC-%EA%B0%80%EC%9E%A5-%EA%B8%B4-%EC%A6%9D%EA%B0%80%ED%95%98%EB%8A%94-%EB%B6%80%EB%B6%84-%EC%88%98%EC%97%B4-2-%EA%B3%A8%EB%93%9C2-%EC%9D%B4%EB%B6%84-%ED%83%90%EC%83%89 위 포스트를 참고해서 문제를 풀었다. 우선 arr라는 리스트에 입력받은 값들을 저장한다. 그리고 res라는 리스트를 만들고 arr[0]를 저장한 뒤에, arr에 저장된 값과 res의 마지막값을 비교하며 더 클 경우에는 res에 추가하고 작거나 같을 경우에는 res안에서 적절한 ..
[백준] 2110 : 공유기 설치 python 이분탐색 문제들은 어떤 값을 이분탐색할 것인지 결정하는 게 가장 어려운 것 같다... 이 문제는 공유기 사이의 거리값으로 이분탐색을 해서 풀어야 하는 문제였다. # 집의 개수와 공유기의 개수를 입력받음 n,c= map(int,input().split()) # 집의 좌표들을 입력받고 정렬한 리스트 house를 생성 house = sorted([int(input()) for _ in range(n)]) # 공유기 사이의 거리값들을 이분탐색 하는 것이기 때문에 # 최소거리인 1과 최대거리인 house[-1]-house[0]을 start와 end로 지정함 start,end = 1, house[-1]-house[0] # 인접한 공유기의 거리의 최대값을 저장할 변수 answer = 0 # 이분탐색이 가능할 동안 반..
[백준] 10816 : 숫자 카드 2 python N개의 카드를 오름차순으로 정렬한 리스트 card에서 bisect라이브러리의 내장함수인 bisect_right와 bisect_left를 이용해서 각각의 숫자가 몇개씩 있는지 세고, 딕셔너리에 추가한 뒤 출력하는 방식을 생각했는데 자꾸 시간초과가 나왔다. bisect_right(list, value)는 list에서 value가 들어갈 가장 오른쪽 위치를 알려주고 bisect_left(list, value)는 왼쪽 위치를 알려줘서 정렬된 list에 사용하면 오른쪽위치-왼쪽위치=list내에서 그 숫자의 개수가 된다. 그런데 생각해보니 굳이 다시 저장하고 끄집어낼 필요가 없는 거다. 그래서 딕셔너리를 쓰지 않고 그냥 바로 출력해버리니까 정답판정을 받았다. import bisect n = int(input()) ..
[백준] 17086 : 아기 상어 2 python 그래프를 입력받을 때 상어가 있는 위치의 행,열 위치를 큐에 삽입한다. 큐에서 상어의 위치를 하나씩 꺼내면서 주변에 0(아직 탐색하지 않은 물)이 있으면 거리값을 1 증가시키고 그걸 그래프에 저장한 뒤 BFS 탐색을 하는 식으로 문제를 풀었다. from collections import deque import sys input = sys.stdin.readline def bfs(): while shark: x,y = shark.popleft() for i in range(8): nx = x+dx[i] ny = y+dy[i] if 0

티스토리툴바