본문 바로가기

코딩테스트 문제풀이

1654번 랜선자르기 이분탐색 랜선 자르기 성공 시간 제한메모리 제한제출정답맞힌 사람정답 비율 2 초 128 MB 156532 36560 24658 21.117% 문제 집에서 시간을 보내던 오영식은 박성원의 부름을 받고 급히 달려왔다. 박성원이 캠프 때 쓸 N개의 랜선을 만들어야 하는데 너무 바빠서 영식이에게 도움을 청했다. 이미 오영식은 자체적으로 K개의 랜선을 가지고 있다. 그러나 K개의 랜선은 길이가 제각각이다. 박성원은 랜선을 모두 N개의 같은 길이의 랜선으로 만들고 싶었기 때문에 K개의 랜선을 잘라서 만들어야 한다. 예를 들어 300cm 짜리 랜선에서 140cm 짜리 랜선을 두 개 잘라내면 20cm는 버려야 한다. (이미 자른 랜선은 붙일 수 없다.) 편의를 위해 랜선을 자르거나 만들 때 손실되는 길이는 없다고 가정하며, 기.. 더보기
[python3 ]골드바흐의 추측 골드바흐의 추측 성공다국어 한국어 시간 제한메모리 제한제출정답맞힌 사람정답 비율 0.5 초 256 MB 67052 12207 8363 23.757% 문제 1742년, 독일의 아마추어 수학가 크리스티안 골드바흐는 레온하르트 오일러에게 다음과 같은 추측을 제안하는 편지를 보냈다. 4보다 큰 모든 짝수는 두 홀수 소수의 합으로 나타낼 수 있다. 예를 들어 8은 3 + 5로 나타낼 수 있고, 3과 5는 모두 홀수인 소수이다. 또, 20 = 3 + 17 = 7 + 13, 42 = 5 + 37 = 11 + 31 = 13 + 29 = 19 + 23 이다. 이 추측은 아직도 해결되지 않은 문제이다. 백만 이하의 모든 짝수에 대해서, 이 추측을 검증하는 프로그램을 작성하시오. 입력 입력은 하나 또는 그 이상의 테스트 케.. 더보기
dfs - 알파벳 BackTracking 알파벳 실패다국어 한국어 시간 제한메모리 제한제출정답맞힌 사람정답 비율 2 초 256 MB 87690 28284 17236 29.133% 문제 세로 R칸, 가로 C칸으로 된 표 모양의 보드가 있다. 보드의 각 칸에는 대문자 알파벳이 하나씩 적혀 있고, 좌측 상단 칸 (1행 1열) 에는 말이 놓여 있다. 말은 상하좌우로 인접한 네 칸 중의 한 칸으로 이동할 수 있는데, 새로 이동한 칸에 적혀 있는 알파벳은 지금까지 지나온 모든 칸에 적혀 있는 알파벳과는 달라야 한다. 즉, 같은 알파벳이 적힌 칸을 두 번 지날 수 없다. 좌측 상단에서 시작해서, 말이 최대한 몇 칸을 지날 수 있는지를 구하는 프로그램을 작성하시오. 말이 지나는 칸은 좌측 상단의 칸도 포함된다. 입력 첫째 줄에 R과 C가 빈칸을 사이에 두고 .. 더보기
DP-가장 높은 탑 쌓기 가장 높은 탑 쌓기 밑면이 정사각형인 직육면체 벽돌들을 사용하여 탑을 쌓고자 한다. 탑은 벽돌을 한 개씩 아래 에서 위로 쌓으면서 만들어 간다. 아래의 조건을 만족하면서 가장 높은 탑을 쌓을 수 있는 프 로그램을 작성하시오. (조건1) 벽돌은 회전시킬 수 없다. 즉, 옆면을 밑면으로 사용할 수 없다. (조건2) 밑면의 넓이가 같은 벽돌은 없으며, 또한 무게가 같은 벽돌도 없다. (조건3) 벽돌들의 높이는 같을 수도 있다. (조건4) 탑을 쌓을 때 밑면이 좁은 벽돌 위에 밑면이 넓은 벽돌은 놓을 수 없다. (조건5) 무게가 무거운 벽돌을 무게가 가벼운 벽돌 위에 놓을 수 없다. ▣ 입력설명 입력 파일의 첫째 줄에는 입력될 벽돌의 수가 주어진다. 입력으로 주어지는 벽돌의 수는 최대 100개이다. 둘째 줄부터.. 더보기
Python sort()에서의 key lambda 사용하기 SW마에스트로를 준비하는과정에서 자꾸 문법을 잊어먹는다 ... 그래서 한번 정리를 하고 가는것이 좋다고 생각했다. a라는 리스트가 있다고 가정을 하면, 첫번째 인자를 기준으로 정렬: a.sort(key=lambda x:x[0]) 두번째 인자를 기준을 정렬: a.sort(key=lambda x:x[1]) 첫번쨰 인자를 오름차순으로 정렬하고, 두번쨰 인자를 내림차순으로 정렬하고싶다면 ? a.sort(key=lambda :(x[0],-x[1])) 파이썬에는 sort()라는 내장 함수가 존재해 간단하게 오름차순, 내림차순으로 리스트 정렬이 가능하다. 1. 리스트 정렬하기 - 오름차순으로 정렬하기 arr = [2,3,4,5,1] arr.sort() print(arr) # [1,2,3,4,5] - 내림차순으로 정렬.. 더보기
백준 숨바꼭질 BFS 숨바꼭질 다국어 한국어 시간 제한메모리 제한제출정답맞힌 사람정답 비율 2 초 128 MB 185810 53403 33652 25.253% 문제 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 때 걷는다면 1초 후에 X-1 또는 X+1로 이동하게 된다. 순간이동을 하는 경우에는 1초 후에 2*X의 위치로 이동하게 된다. 수빈이와 동생의 위치가 주어졌을 때, 수빈이가 동생을 찾을 수 있는 가장 빠른 시간이 몇 초 후인지 구하는 프로그램을 작성하시오. 입력 첫 번째 줄에 수빈이가 있는 위치 N과 동생이 있는 위치 K가 주어진다. N과 K.. 더보기
DP 최대선 연결하기 ▣ 출력설명 첫 줄에 겹치지 않고 그을 수 있는 최대선의 개수를 출력합니다. ▣ 입력예제 1 10 4 1 2 3 9 7 5 6 10 8 ▣ 출력예제 1 6 n=int(input()) arr=list(map(int,input().split())) dp=[0]*(n+1) dp[1]=1 res=0 for i in range(2,n): max=0 for j in range(i-1,0,-1): if arr[j] 더보기
DP - Top-Down 방식과 Bottom-up # bottom-top 방식 ''' n=int(input()) dp=[0]*(n+1) dp[1]=1 dp[2]=2 for i in range(3,n+1): dp[i]=dp[i-1]+dp[i-2] print(dp[n]) ''' # TopDown 방식 Dfs사용 def dfs(n): if dp[n]>0: return dp[n] if n==1 or n==2: return n else: dp[n]=dfs(n-1)+dfs(n-2) return dp[n] n=int(input()) dp=[0]*(n+1) print(dfs(n)) 말 그대로 Top-Down방식은 위에서부터 아래로 이동해가면서 최적의 해를 찾아가는방식이고 Bottom-up은 반대이다 다만, Top-Down은 보통 DFS를 많이사용하는것같다.주의하자 더보기

티스토리툴바