반응형 전체 글 목록571 [분할 정복/ 파이썬] 백준 11444번 : 피보나치 수 6 / 골드 3 https://www.acmicpc.net/problem/11444 11444번: 피보나치 수 6 첫째 줄에 n이 주어진다. n은 1,000,000,000,000,000,000보다 작거나 같은 자연수이다. www.acmicpc.net dp로 잘 알려진 피보나치 문제지만, 이 문제에선 n이 정말 큰 수로 주어지기 때문에 조금 다른 방법을 써야한다. 도가뉴 항등식이라고 있다. n번째 피보나치 수를 a(n)이라 하면, a(2n) = a(n)[a(n) + 2a(n-1)] a(2n-1) = a(n)**2 + a(n-1)**2 가 성립한다. 따라서 n이 아무리 커도 log(n) 시간에 문제를 해결할 수 있기 때문에 이 문제를 풀 수가 있다. import collections n = int(input()) m = 1.. 2021. 12. 6. [최단 경로] 백준 11779번 : 최소비용 구하기 2 / 골드 3 https://www.acmicpc.net/problem/11779 11779번: 최소비용 구하기 2 첫째 줄에 도시의 개수 n(1≤n≤1,000)이 주어지고 둘째 줄에는 버스의 개수 m(1≤m≤100,000)이 주어진다. 그리고 셋째 줄부터 m+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 버스 www.acmicpc.net 다익스트라 + 경로 직접 구하기 문제이다. 힙에 cost + w, next 뿐만 아니라 cur 노드도 넣어준다. 그리고 힙에서 하나씩 꺼내면서 처음 방문한 노드에 도착하면 딕셔너리 구조에 이전 노드, 현재 노드를 저장해준다. 다익스트라가 끝난 후 딕셔너리를 이용해 목적지부터 역순으로 경로를 추적하면 된다. 웰노운 문젠데 좀 오래 걸렸다.. 정신차리자. import .. 2021. 12. 3. [다이나믹 프로그래밍] 백준 11054번: 가장 긴 바이토닉 부분 수열 / 골드 3 https://www.acmicpc.net/problem/11054 11054번: 가장 긴 바이토닉 부분 수열 첫째 줄에 수열 A의 크기 N이 주어지고, 둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ N ≤ 1,000, 1 ≤ Ai ≤ 1,000) www.acmicpc.net well-known problem인 LIS를 조금 응용하면 풀 수 있는 문제! n = int(input()) nums = list(map(int, input().split())) dp_asc = [0 for _ in range(n)] dp_desc = [0 for _ in range(n)] for i in range(n): max_val = 0 for j in range(i): if nums[j] < nums[i]:.. 2021. 12. 3. [스프링] (윈도우) 스프링 빌드와 실행 빌드 방법 1. cmd 실행 2. 프로젝트 경로 찾아가기 ex) 3. dir 명령어는 디렉토리 내 파일들을 볼수 있게 해줌 4. gradlew build 명령어로 프로젝트를 빌드 빌드 완료 후 실행하려면?? 1. 빌드 후에는 build 디렉토리가 생성되기 때문에 이곳으로 들어가서 libs 폴더로 들어감. dir 명령어로 파일들 확인. 이때 hello-spring-0.0.1-SNAPSHOT.jar로 실행시킬 수 있음 2. 실행하려면 아래와 같이 java -jar 파일명.jar 해주면 된다. 이때 파일명은 hello까지만 입력하고 탭을 누르면 자동완성이 됨. 3. 실행을 확인해보자. 성공! 2021. 12. 1. [디자인 패턴] Proxy Pattern 프록시 패턴 Proxy Pattern Definition 프록시 패턴은 어떤 객체에 대한 접근을 제어하기 위한 용도로 대리인이나 대변인에 해당하는 객체를 제공하는 패턴입니다. Structure Types 프록시 패턴은 다양하게 활용이 될 수 있습니다. 원격 프록시는 원격 객체에 대한 접근을 제어할 수 있습니다. 가상 프록시는 생성하기 힘든 자원에 대한 접근을 제어할 수 있습니다. 보호 프록시는 접근 권한이 필요한 자원에 대한 접근을 제어할 수 있습니다. Source Code 이번 예제에서는 가장 간단한 프록시 패턴 형태만을 살펴보겠습니다. 가장 먼저 Subject 인터페이스를 만들어줍니다. 여기선 IService가 Subject 인터페이스에 해당합니다. package proxy_pattern; public inter.. 2021. 12. 1. [디자인 패턴] State Pattern 스테이트 패턴 State Pattern Introduction 게시물의 좋아요/싫어요 버튼 기능을 만들어봅시다! Definition 스테이트 패턴을 이용하면 객체의 내부 상태가 바뀜에 따라서 객체의 행동을 바꿀 수 있습니다. 마치 객체의 클래스가 바뀌는 것과 같은 결과를 얻을 수 있습니다. Structure 스테이트 패턴은 전략 패턴과 동일한 구조를 가집니다. Source Code 게시물에 좋아요/싫어요 기능을 만들어봅시다. 우선 게시물 클래스를 만들어줍니다. 스테이트 패턴의 Context 클래스에 해당합니다. package state_pattern; public class Article { State state = new IdleState(); public void setState(State state) { this.. 2021. 12. 1. 이전 1 ··· 33 34 35 36 37 38 39 ··· 96 다음 반응형
