본문 바로가기

전체 글

 (397)
S-algo10 동적프로그래밍(1) cansum 보호되어 있는 글입니다.
백준(BOJ) 1010번 다리놓기 https://www.acmicpc.net/problem/1010 조합을 사용하여 정말 간단히 풀리는 문제다. 내가 조합을 공부할 때는 이보다 훨씬 복잡했다. 조합을 재귀트리로 구현할때 어떻게 구현하는지와 아래와 같이 dp를 써서 구현할 때 어떻게 저런 수식이 나오는지 그리고 시중의 다른 풀이법에 대하여 공부하자. import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.StringTokenizer; public class Main{ public static int solution(int r, int n){ int[][]dp=new int[n+1][r+1]; for(..
백준(BOJ) 27112 시간외 근무 멈춰!!! https://www.acmicpc.net/problem/27112 문제의 특성! -"주말에는 정규근무를 할수 없다." 이러한 조악한 조건들이 들어가면 문제가 지저분해 진다. 다만, 단순히 지저분해 진다고 해서 그 지저분한 것을 어떻게 구현하나로 방향을 잡지 말고 그 조악한 것을 문제에서 주워진 조건을 변형하고 어떻게 상쇄시켜버릴지, 없애버릴지 생각해 내는 것은 참 훌륭한 것같다. 실제 예를들면 아래와 같다. 해결코드를 보면 주워진 deadline을 새롭게 갱신해 준다(renewedDeadline). 이렇게 주워진 마감일을 앞당김으로써 주중에도 정규근무(regularWork)가 가능하게 해준것이다. 즉, 주말에는 regularWork가 불가능하다는 조악한 상황설정을 문제에서 주워진 값에 변형을 가해줌으로..
소프트웨어 공학시간에 살펴본 몇몇 디자인 패턴의 간단한 정리 기존에 사용중인 입력장치(이미있는것)와의 인터페이스 작동 방식이 호환되지(자신이 원하는것) 않아 이를 변환할 수 있는 변환기 역할의 중간 매개체 클래스를 만들어야 한다. =어댑터패턴(=이미 있는 것을 자신이 원하는 방식으로 바꾸어 쓸 수 있게 해주는 패턴) 도로를 통제하기 위해서는 기본적으로 신호등 기능이 필요하지만 그 외에 변경 차선, 차로의 등, 횡단보도 신호, 교통량 등을 모두 조합하여 통제할 수 있는 클래스를 만들어야 한다. =데코레이션 패턴 데이터집합에 순차적인 접근 또는 순회를 지원하여 기본표현(리스트, 스택, 트리등)이 노출되지 않으면서 행동할 수 있도록 접근기능과 자료구조를 분리한다 =반복자 패턴 현재 상태를 파악하고 그에 따른 객체의 동작이 달라야 하기 때문에 맥락과 상태를 별도로 구현하..
[UML] 클래스 다이어그램 (Class Diagram) 출처: https://brownbears.tistory.com/577 클래스 다이어그램은 구조 다이어그램으로 클래스 내부 구성요소 및 클래스 간의 관계를 도식화하여 시스템의 특정 모듈이나 일부 및 전체를 구조화 합니다. 개발 하기 전, 클래스 다이어그램을 그리게 되면 시스템 내 클래스 간의 의존성 파악과 팀원들 간 의사소통이 편리합니다. 클래스 다이어그램의 목적에 따라 개념, 명세, 구현 단계로 나눌 수 있습니다. 개념 단계에서는 클래스만 도출하고 관계를 단순화하는 것이 목적입니다. 명세와 구현 단계에서는 개발 직전 설계나 구현 이후 설명 목적으로 사용되고 이 다이어그램을 기반으로 코드로 구현하거나 코드를 기반으로 다이어그램을 그리기 때문에 코드와 연관이 깊습니다. 요소 (element) 클래스 클래스 ..
백준(BOJ) 13164번 행복 유치원 문제를 읽고 "어떻게 이 문제를 탐욕적 알고리즘과 연관시켜 멋지게 해결할 수 있을까?"라고 생각했다. 도저히 염두가 나지 않아 바로 답을 보았다. 해결의 키는 주워진 수의 조로 분할 한다는 것이고 이는 각각의 원생들 사이 중에서 어느곳에다 분별의 막대기를 둘지 선택하는 문제임을 인지하는데 있다. 어디다 막대기를 두어야 하는가? 원생들은 서로 인접해야 한다고 했으므로(이게 정말 중요함) 원생들의 키차이가 가장 많은 곳에 막대기를 두어 다른조로 구분해 내면 된다. 그렇게 되면 그 큰 키차이가 없어진다. 즉, 원생들의 키의 차이를 모두 구한 자료구조 리스트를 구하고 그 리스트를 오름차순 정렬한다.그 후 height.length-(groups-1)를 구한후 그보다 1더 작은 위치까지 모두 더해 주면 된다(아래코..
백준(BOJ) 11000: 강의실 배정 문제를 다시 풀때마다 새로운 회의를 이미 강의실을 차지하고 있는 모든 회의들의 마감시간과 비교해야하는 것 아니냐는 게으른 사고에 빠지곤 한다!!! 아래는 이에 대한 답이다! 모든 것과 비교해야 하는 경우 이러한 번거로움을 없애줄 수 있는 것이 우선순위 큐이다. 왜 그런가? 사실은 모든 것과 비교할 필요가 없고 그 중 가장 크거나 혹은 가장 작은 것과의 비교만 이루어 지면 되기때문이다. 배열에 시작시간이 가장 이른 순서로 배열을 정렬하고 그 배열의 첫번째 인자의 마감시간을 우선순위 큐에 넣는다. 그리고 두번째인자부터 그 시작시간을 우선순위큐의 인자와 비교만 하면 되는 것이다. 만약 우선순위 큐의 값이 더 작다면 pop하고 2번째 회의의 마감시간을 큐에 넣으면 되고 만약 우선순위 큐의 값이 더 크다면 pop..
School algo08 탐욕적(Greedy) 알고리즘(&자바복수비교문법) 복습. 탐욕적 알고리즘이란? 매 반복시 최선의 것을 선택하는 알고리즘 A. 마감시간이 있는 최적 스케줄링 문제 마감시간 있는 최적 스케줄 문제는 일에 대한 마감시간과 그에따른 이익이 함께 주워 진다. 그리고 구하는 것은 이익이 최대가 되는 스케줄이다. 우선 문제에 들어가기 앞서 참고하면 좋은 영상과 그 영상으로부터의 코드를 소개한다. https://www.youtube.com/watch?v=x9iDSJHV8F8 크루스칼에서는 feasible 과정이 있지만 같은 MST를 구하는 프림알고리즘에서는 feasible과정이 없다. 그 이유는 프림 알고리즘은 정점을 선택하는 것이기 때문이다. 프림 알고리즘에서 for문 사용으로 매번 다른 정점을 선택하는 코드 구조이다. 그렇다면 마감시간있는 프로젝트에서는 왜 fea..

티스토리툴바