본문 바로가기

전체 글

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 게임 맵 최단거리 문제 설명 ROR 게임은 두 팀으로 나누어서 진행하며, 상대 팀 진영을 먼저 파괴하면 이기는 게임입니다. 따라서, 각 팀은 상대 팀 진영에 최대한 빨리 도착하는 것이 유리합니다. 지금부터 당신은 한 팀의 팀원이 되어 게임을 진행하려고 합니다. 다음은 5 x 5 크기의 맵에, 당신의 캐릭터가 (행: 1, 열: 1) 위치에 있고, 상대 팀 진영은 (행: 5, 열: 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를 많이사용하는것같다.주의하자 더보기
[python3]2146번:다리만들기 다리 만들기 성공 시간 제한메모리 제한제출정답맞힌 사람정답 비율 2 초 192 MB 34525 12576 7824 33.328% 문제 여러 섬으로 이루어진 나라가 있다. 이 나라의 대통령은 섬을 잇는 다리를 만들겠다는 공약으로 인기몰이를 해 당선될 수 있었다. 하지만 막상 대통령에 취임하자, 다리를 놓는다는 것이 아깝다는 생각을 하게 되었다. 그래서 그는, 생색내는 식으로 한 섬과 다른 섬을 잇는 다리 하나만을 만들기로 하였고, 그 또한 다리를 가장 짧게 하여 돈을 아끼려 하였다. 이 나라는 N×N크기의 이차원 평면상에 존재한다. 이 나라는 여러 섬으로 이루어져 있으며, 섬이란 동서남북으로 육지가 붙어있는 덩어리를 말한다. 다음은 세 개의 섬으로 이루어진 나라의 지도이다. 위의 그림에서 색이 있는 부분이.. 더보기
AOP 전처리와 후처리 공통로직,핵심로직을 분리. AOP 용어 Aspect 여러 객체에 공통으로 적용되는 공통 관심 사항을 Aspect라고 한다. Target 우리가 위빙할 대상을 Target이라고 한다. Pointcut JoinPoint를 적용할 영역을 지정한다. JoinPoint 클래스의 인스턴스 생성 시점', '메소드 호출 시점(앞, 뒤 등)', '예외 발생 시점'과 같이 특정 시점을 조인포인트라고 한다. 1) @Around 2) @Before 3) @After 4) @AfterThrowing 5) @AfterReturning Advice 조인 포인트에 삽입되어져 실질적으로 동작하는 코드를 Advice라고 한다. /@Configuration Controller전에 쓰고 @Component Controller 가 뜨고난 후 @Component @As.. 더보기

티스토리툴바