[생각의 흐름] 1. 쿼드 트리의 이해 아래 순서로 흑/백 압축을 한다. 1 2 3 4 2. 쿼드트리 상하 반전 어떻게 처리할까? -> 뭔가 규칙이 있을 것 같다 3. 문제의 example을 보니 1, 2, 3, 4 를 3, 4, 1, 2로 바꾸면 상하반전이 된다. 4. 현재 level에서 노드를 4개로 묶어서 상하반전 시키면 되겠다. 5. x는 어떻게 처리하나? -> 분할정복으로 처리하고 올라온다. /* 쿼드 트리 뒤집기 https://www.algospot.com/judge/problem/read/QUADTREE */ #include #include char str[1001]; int len; void inverseNode(int nodeStart[], int nodeEnd[]) { char tmpS..
[생각의 흐름] 1. 모든 스위치를 무한대로 누르는건 답이 없음 2. [12, 3, 6, 9] 시간의 특성을 보면 어짜피 스위치를 4번 누르면 원래 상태로 돌아옴(한 바퀴 돔) and 한 바퀴 돌았을 때 다른 연산에 영향을 주지 않음 3. 0번째 스위치부터 0번 누르고 -> 1번째 스위치 -> .... , 1번 누르고 1번째 스위치 -> ... , 2번 누르고 1번째 스위치... 하나의 스위치당 총 4개의 경우를 통해 최소한으로 스위치를 누를 수 있는 경우의 수를 구함. 4. 시간 복잡도는 각각의 스위치가 선택할 수 있는 경우의 수는 4가지 이기 때문에 4(개)^10(개의 스위치)로 시간안에 들어올 것으로 판단 /* https://www.algospot.com/judge/problem/read/CLOCK..
[생각의 흐름] 1. 보드의 왼쪽 위에서 부터 블록을 채운다. 2. 블록 타입의 경우의수는 4개 -> 기준 점 x, y에서 블록 모양을 만들어보면 4가지 나옴 3. 왼쪽 위에서부터 가능한 모든 블록을 넣어본다. 4. 보드 범위를 넘어가지 않고 흰색이 아닌 칸을 예외처리 5. 기저사례(모든 블록이 채워지는 경우) 1을 리턴한다. /* BOARDCOVER 게임판 덮기 https://www.algospot.com/judge/problem/read/BOARDCOVER */ #include const int MAX_BOARD_SIZE = 22; const int BLOCK_TYPE = 4; char board[MAX_BOARD_SIZE][MAX_BOARD_SIZE]; int H, W; // L자 모양 블록을 회전..
https://www.algospot.com/judge/problem/read/PICNIC [생각의 흐름] 1. 완전탐색으로 짝을 구한다. 2. 친구 관계를 2차원 vector로 추상화 한다. 3. 짝이 지어졌는지 확인하기 위해 boolean타입 isPiar배열로 체크한다. 4. (1,0) (0,1)과 같은 중복케이스를 제거하기 위해 순차적으로 짝을 정해준다 (0, 1)만 가능하게 /* 소풍 PICNIC https://www.algospot.com/judge/problem/read/PICNIC */ #include #include #include using namespace std; const int MAX_CHILDREN = 10; bool isPair[MAX_CHILDREN]; int C, n, m,..
https://www.algospot.com/judge/problem/read/BOGGLE algospot.com :: BOGGLE 보글 게임 문제 정보 문제 보글(Boggle) 게임은 그림 (a)와 같은 5x5 크기의 알파벳 격자인 게임판의 한 글자에서 시작해서 펜을 움직이면서 만나는 글자를 그 순서대로 나열하여 만들어지는 영어 www.algospot.com [생각의 흐름] 1. 시작 위치를 정한뒤 8방향으로 완전 탐색을 해보자 -> 완전탐색 시 timeout 발생 2. DP문제임을 고려해보고 중복되는(연산) 부분 고민 -> 단어의 현재 알파벳위치와 x, y의 값을 이용하면 캐싱 가능? -> 경우의 수는 항상 같기 때문에 캐싱 가능 -> 메모이제이션으로 시간초과 해결 /* BOGGLE 보글 게임 htt..
Software Development 정의 : sw를 활용하여 현실의 어떤 문제를 해결하는 것. 개발 방법론 프로그래밍 언어의 철학에 따라 크게 두가지 방식과 방법론이 존재 1. Procedural Programming ex) C -> SASD(Structure Analysis and Structured Design) 2. Object-Oriented Programming ex)C++, Java -> OOAD(Object-Oriented Analysis and Design) Procedural Programming은 Algorigthm(Procedure)과 Data Structure에 중점을 둠 따라서 Algorithm과 Data Structure는 서로 독립적이다. (함수 시그니처만 맞으면 사용 가능)..
GRASP: General Principles in Assigning Responsibilities 란? 객체 설계와 책임 할당의 9가지 원칙을 설명한다. 도메인 내에서 어떻게 하면 적절하게 모듈을 나누고 책임을 할당할지에 대한 설계 철학이라고 할 수 있다. 1. Creator 문제 인식 : 누가 객체 A를 생성할 책임을 가질 것인가? 해결책 : 아래의 조건을 만족하는 클래스가 그 책임을 가져갈 후보가 된다. - A 객체를 포함하고 있다.(contain, aggregate) - A 객체의 정보를 기록(Record)하고 있다. - A 객체를 사용하고 있다. - A 객체가 초기화에 필요한 정보를 가지고 있다. 예를들어 아래와 같은 관계인 경우 SmartPhoneFactory가 SmartPhone객체를 생성할..
Dependency Inversion Principle 의존관계 역전 원칙 정의 : 상위 모듈이 하위 모듈에 의존하는게 아니라 상위모듈과 하위모듈 모두 인터페이스(추상화)에 의존해야 한다. 의존관계 역전이란 말이 처음에는 와닿기 힘들다. 따라서 아래의 그림을 비교해서 보면 이해가 조금더 쉬울것 같다. 아래의 그림과 같이 상위모듈이 하위모듈에 의존하는 경우 하나의 하위모듈만 수정을 해도 상위모듈은 영향을 받게 되는 문제점이 있다. 따라서 인터페이스(추상화)를 통해 의존성을 상위모듈->하위모듈 에서 하위모듈->인터페이스 로 역전시켜준다. 이런 식으로 디자인을 변경하면 상위모듈에서 인터페이스를 가지고 있기 때문에 ownership도 가지게 된다. 왜냐하면 인터페이스란 "변하지 않는 것"의 다른말이기 때문에 하..
Interface Segregation Principle 인터페이스 분리 원칙 정의 : 클라이언트는 자신이 사용하지 않는 메소드에 의존하지 않아야 한다. 즉, 인터페이스를 구체적으로 잘게 짤라서 만들어야 한다. 아래와 같이 디자인 된 시스템을 보면 ISP원칙을 적용하면 좋을것 같다. InfoApplication은 getName(), getID()메소드만 사용하고 나머지는 필요 없으며 CareereApplication은 getJobLevel()메소드만 사용한다. 이러한 상황에서 getAge()라는 메소드를 추가하게 되면 Employee클래스에 연관된 모든 클래스가 영향을 받는다. 따라서 아래와 같이 인터페이스를 분리해보자 EmployeeInfo와 EmplyeeCareere로 인터페이스를 분리함으로써 서로간..
Liskov Substitution Principle 리스코프 치환 원칙 정의 : Derived class는 Base class로 반드시 대체 될 수 있어야 한다. 예를 들어 아래와 같은 관계의 클래스가 있을 때 Base myBase = new Derived(); myBase.funcA(); myBase.funcB(); myBase.funcC(); myBase.funcD(); 리스코프 치환 원칙을 위반한 예 Base로 치환된 new Derived가 코드가 문제 없이 모든 메소드를 호출할 수 있어야 한다. 위의 코드가 안되는 경우가 있을까? 아마 java나 c++에서는 컴파일 에러를 발생시키기 때문에 코드 실행이 안되는 경우는 없을 것이다. 그러나 논리적으로 안되게 하는 방법이 있는데 그 예는 java.u..
