버러범의 개발이야기

알고스팟 문제 링크: https://www.algospot.com/judge/problem/read/BRACKETS2

( ) { } [ ] 이렇게 세 종류의 괄호를 나열한 문자열이 주어졌을때 해당 문자열이 짝이 맞는지를 확인하는 문제이다.

여기서 짝이 맞는다는 표현은 다음 세가지 조건을 모두 지켰을 경우를 말한다.

- ( 는 ) 와, { 는 } 와, [ 는 ]와 짝을 이루어야만 한다.

- 모든 괄호 쌍은 먼저 열린 뒤 닫힌다.

- 한 괄호 쌍이 다른 괄호쌍과 서로 '교차해' 있으면 안된다. 이 정의에 의하면 [ ( ] ) 는 짝이 맞지 않는 경우이다.

스택을 이용하면 다음과 같은 방식으로 문제를 풀 수 있다.

문자열을 순회하면서 열린괄호면은 스택에 넣는다.

닫힌 괄호면 현재 스택의 탑에 있는것과 대응한다면 스택의 탑을 pop하고 대응하지 않는다면 false를 리턴한다.

코드 원본: https://github.com/sbl133/JongmanBook/blob/main/19.%20QueueStackDeque/BRACKETS2.cpp

댓글을 통한 코드리뷰, 질문, 지적 언제든 환영입니다!

reference: 프로그래밍 대회에서 배우는 알고리즘 문제해결전략2

알고스팟 문제 링크: https://www.algospot.com/judge/problem/read/JOSEPHUS

조세푸스를 포함해서 병사들이 원형으로 앉아 순서대로 죽는다.

첫번째 병사가 처음으로 죽으면, 시계방향으로 k번째 사람이 죽기를 반복하다가 조세푸스를 포함한 병사 하나만 살아 남았을때 죽는것을 멈춘다고 한다.

이렇게 조세푸스가 마지막 두명중 하나가 되기 위해서는 조세푸스는 첫번째 병사로부터 몇자리 떨어진 곳에 있어야 하는지 구하는 문제이다.

이 문제를 풀려면 요소들을 순회하면서 삭제하는 작업을 반복적으로 해야한다.

이때 우리는 다양한 곳에서 요소를 추가/삭제할때 상수시간복잡도를 가지는 연결리스트( list )를 활용할 수 있다.

배열( vector, int[] )의 경우 맨 뒤 이외의 위치에서 원소 추가/삭제를 수행할때 선형시간복잡도를 가진다.

코드 원본: https://github.com/sbl133/JongmanBook/blob/main/18.%20linearDS/JOSEPHUS.cpp

댓글을 통한 코드리뷰, 질문, 지적 언제든 환영입니다!

reference: 프로그래밍 대회에서 배우는 알고리즘 문제해결전략2

알고스팟 문제 링크: https://algospot.com/judge/problem/read/CHRISTMAS

상자마다 인형이 담겨있는 갯수가 각각 다르게 주어졌을때, 아이들k명에게 똑같은 갯수의 인형을 남는 인형 없이 나누어 주려 한다.

주문을 할때 'h번 상자부터 t번 상자까지 다 주세요'(h<=t)라고만 할 수있다.

한번 만 주문할 수 있는 경우 가능한 주문 방법,

한 상자가 주문에 중복으로 포함 되지 않게끔 여러번 주문 할수 있는 경우 최대 주문 횟수, 이렇게 두가지를 구하는 문제이다.

h에서 t까지 구입했을때 남기지 않고 나눠줄 수 있는 경우는 (psum[t]-psum[h-1])%k==0인 경우다.

한번 만 주문할 수 있는 경우 가능한 주문방법 = 나머지가 같은 것들끼리 묶고, 각 묶음에서 두개를 뽑는 조합의 경우

0번부터 i번까지의 상자가 있고, 여러번 주문 할때 최대 주문 횟수를 maxBuys(i)라 할때

maxBuys(i) = max( maxBuys(i-1), maxBuys(j)+1) (이때 j는 psum[i]==psum[j]인 i보다 작은 최댓값)

코드 원본: https://github.com/sbl133/JongmanBook/blob/main/17.%20partial%20sum/CHRISTMAS.cpp

댓글을 통한 코드리뷰, 질문, 지적 언제든 환영입니다!

reference: 프로그래밍 대회에서 배우는 알고리즘 문제해결전략2

BOJ 문제 링크: https://www.acmicpc.net/problem/15686

집과 치킨가게의 좌표가 N*N배열 형태로 주어진다.

m개의 치킨집을 남기고 구할 수 있는 각 집에서 가장 가까운 치킨 집과의 거리 합의 최솟값을 구하는 문제이다. 

집들과 치킨집들의 좌표를 각각의 벡터로 관리해준다.

좌표로 주어진 치킨집들중에 m개의 치킨집을 남겨야되는 작업은 재귀를 통해서 치킨집을 전체 순회하면서 구할 수 있다.

현재 치킨집을 남기는 경우와 폐업시키는 경우를 각각 재귀호출해서 더 작은 값을 반환 하는 쪽의 도시 치킨 거리를 반환한다.

코드 원본: https://github.com/sbl133/BOJ/blob/main/%2315686.cpp

댓글을 통한 코드리뷰, 질문, 지적 언제든 환영입니다!

BOJ 문제 링크: https://www.acmicpc.net/problem/12865

배낭에 담을 수 있는 무게가 제한 되있고, 각 물건들의 가치와 무게가 주어진다.

이때 배낭에 담을 수 있는 물건들의 가치의 최댓값을 구하는 문제이다.

주어진 물건들을 차례대로 순회하면서 담을지 안담을지를 결정한다. 담았을 경우 현재 배낭에 무게에 담고자 하는 물건의 무게를 추가하여 다음 물건을 결정하는 재귀를 호출하고, 안담았을 경우 현재배낭에 무게 그대로 다음 물건을 결정하는 재귀를 호출한다. 이 두 재귀중 큰 값을 반환하는 경우의 값을 return하면 된다.

코드 원본: https://github.com/sbl133/BOJ/blob/main/%2312865.cpp

댓글을 통한 코드리뷰, 질문, 지적 언제든 환영입니다!

객체 지향 프로그래밍에서 정말 중요하게 여겨지는 5가지 원칙이 있다. 

프로그래머들의 필독서로 유명한 클린코드의 저자 로버트 마틴이 객체 지향에서 중요한 5가지 개념을 정리한 것인데

SOLID원칙 이라고도 많이 알려져있다.

이번에는 이 객체 지향의 5가지 원칙 SOLID에 대해 얘기하고자 한다.

      SOLID

1. SRP: 단일 책임 원칙 (single responsibility principle)
2. OCP: 개방-폐쇄 원칙 (open/closed principle)
3. LSP: 리스코프 치환 원칙 (Liskov substitution principle)
4. ISP: 인터페이스 분리 원칙 (Interface segregation principle)
5. DIP: 의존관계 역전 원칙 (Dependency inversion principle)

1. SRP - 단일 책인 원칙 (single responsibility principle)

한 클래스는 하나의 책임만 가져야 한다는 뜻이다.

하나의 책임이라는 것은 문맥과 상황에 따라 달라지므로 모호할 수 있지만, 중요한 기준은 변경에 있다.

변경이 있을 때 파급 효과가 크면 단일 책임 원칙을 잘 못 지킨 것이고, 작으면 단일 책임 원칙을 잘 지켰다고 할 수 있다.

예를 들어 보고서를 편집하고 출력하는 모듈을 생각해 보자.

이 모듈은 두 가지 이유로 변경될 수 있는데, 하나는 보고서의 내용 때문일 수 있고, 다른 하나는 보고서의 형식 때문일 수 있다.

이 두가지 변경은 하나는 보고서의 내용(텍스트) 측면, 다른 하나는 보고서의 디자인 측면이라는 서로 매우 다른 원인에서 비롯된다.

따라서 단일 책임 원칙관점에서 보고서를 편집하고 출력하는 모듈은 잘못된 설계이고,

해당 모듈은 두 가지 책임이 서로 분리된 모듈로 나뉘어야 한다.

2. OCP - 개방-폐쇄 원칙 (open/closed principle)

SOLID 5가지 원칙 중 DIP와 더불어 가장 중요하게 여겨지는 원칙이다.

개방-폐쇄 원칙이란 소프트웨어 요소는 확장에는 열려 있으나 변경에는 닫혀 있어햐 한다는 원칙이다.

중요한 개념인 만큼 그림을 참고하여 설명하려 한다.

운전자는 자동차면허만 있다면 자동차 종류에 상관없이 운전을 할 수 있다.

이를 프로그래밍 관점에서 보자면 인터페이스는 자동차, 구현체는 전기자동차, 경유자동차, 수소자동차라고 할 수 있다.

이때 운전자가 휘발유자동차를 운전해야하는 상황이 생긴다면 단순히 휘발유자동차 구현체만 추가해 주면 되고

자동차 인터페이스를 가르키는 운전자가 해야할 일은 없다.

하지만 만약 운전자가 자동차 인터페이스가 아니라 전기자동차나 수소자동차등 특정 구현체를 가르킨다면

다르게 말해 자동차의 종류에 따라 운전법이 다르고 운전면허가 따로 있다면,

운전자는 운전해야 하는 자동차의 종류가 달라질때마다 새로운 운전면허를 따야되는 불쌍한 일이 벌어지게 된다.

따라서 자동차의 종류는 필요에 따라 추가할 수 있지만, 운전자는 운전만 할줄 알면 어떤 종류에 차를 운전하든 변경할 필요가 없는것

즉, '확장에는 열려 있으나 변경에는 닫혀 있는것' 이것이 개방-폐쇄 원칙이다.

3. LSP - 리스코프 치환 원칙 (Liskov substitution principle)

프로그램의 객체는 프로그램의 정확성을 깨뜨리지 않으면서 하위 타입의 인스턴스로 바꿀 수 있어야 한다는 원칙이다.

다형성에서 하위 클래스는 인터페이스 규약을 다 지켜야 한다는 뜻으로 다형성을 지원하기 위한 원칙이다.

사용자가 인터페이스를 믿고 사용하려면 인터페이스를 구현한 구현체는 이 원칙을 지켜야 한다.

이것은 단순히 컴파일에 성공하는 것을 넘어서는 이야기다.

예를 들어 자동차 인터페이스에서 밣으면 앞으로 가는것을 의도하고 추상메서드로 엑셀을 만들었다고 하자.

만약 자동차 종류중 하나가 엑셀메서드에서 자동차가 멈추는 기능을 구현한다면 확장은 정상적으로 될것이다.

하지만 운전자가 멋모르고 이 자동차를 운전하면 대형사고로 이어질 수 있다.

따라서 객체는 프로그램의 정확성을 깨뜨리지 않으면서 하위 타입의 인스턴스로 바꿀 수 있어야한다.

4. ISP - 인터페이스 분리 원칙 (Interface segregation principle)

특정 클라이언트를 위한 인터페이스 여러 개가 범용 인터페이스 하나보다 낫다는 원칙이다.

예를들면 자동차 인터페이스는 운전 인터페이스와 정비 인터페이스로 분리할 수 있고,

사용자는 운전자와 정비사로 분리할 수 있다.

이렇게 분리하면 정비 인터페이스 자체가 변해도 운전자 클라이언트에는 영향을 주지 않게 된다.

즉, 인터페이스가 명확해지고, 대체 가능성이 높아지게 된다.

5. DIP - 의존관계 역전 원칙 (Dependency inversion principle)

앞서 말했듯이 이 원칙은 OCP와 더불어서 객체 지향 5원칙 중 가장중요한 원칙이다.

DIP란 프로그래머는 "추상화에 의존해야지, 구체화에 의존하면 안된다." 라는 원칙이다.

쉽게 이야기해서 구현 클래스에 의존하지 말고, 인터페이스에 의존하라는 뜻이다.

위에 있는 그림을 예를 들자면, 운전자는 자동차를 운전할 수 있다면 전기자동차, 수소자동차, 경유 자동차 모두 운전할 수 있게 설계해야한다.

만약 운전자가 전기자동차'만', 수소자동차'만' 운전할 수 있게 설계한다면 프로그램은 확장하기 어렵고 변경 또한 어렵게 된다.

참고: 인프런 -  '스프링 핵심 원리 - 기본편'

알고스팟 문제 링크: https://algospot.com/judge/problem/read/GRADUATION

각 학기마다 열리는 전공과목을 선수과목과 학기당 들을 수 있는 최대 과목수를 고려하여 알맞게 수강했을때

졸업요건을 충족시키는 최소 이수 학기를 구하는 문제이다. 

현재 학기와 이제까지 들은 과목들이 주어졌을때 앞으로 들어야 하는 최소 학기를 반환하는 함수를 만들고

메모이제이션을 사용하는 다이나믹 프로그래밍기법을 이용하면 문제를 풀 수 있다.

이때 각 과목의 선수과목과 각 학기에 열리는 과목들을 비트마스크 기법을 사용하여 표현한 것에 주목하자.

코드 원본: https://github.com/sbl133/JongmanBook/blob/main/16.%20bitmask/GRADUATION.cpp

댓글을 통한 코드리뷰, 질문, 지적 언제든 환영입니다!

reference: 프로그래밍 대회에서 배우는 알고리즘 문제해결전략2

객체 지향 프로그래밍에서 빼놓을 수 없는 특징 3가지 있는데, 사람들은 이것을 객체 지향 프로그래밍의 3요소라고 합니다.

이번에는 이 객체 지향 프로그래밍의 3요소에 대해서 얘기하고자 합니다.

객체 지향 프로그래밍의 3요소

• 캡슐화 (Encapsulation)
• 상속 (Inheritance)
• 다형성 (Polymorphism)

먼저 캡슐화 (Encapsulation) 입니다.

캡슐화란 객체의 속성(data)과 행위(메서드)를 하나로 묶고, 실제 구현 내용 일부를 외부에 감추어 은닉하는걸 뜻합니다.

캡슐화는 중요한 데이터(예를 들면 비밀번호)를 보호하거나, 외부에는 불필요한 즉 내부적으로만 사용되는 부분을 감춰서 복잡성을 줄이기위해 사용됩니다.

자바에서는 다음과 같은 접근 제어자를 이용하여 캡슐화를 구현할 수 있습니다.

private:  같은 클래스 내에서만 접근이 가능

default:  같은 패키지 내에서만 접근이 가능

protected:  같은 패키지 내에서, 그리고 다른 패키지의 자손클래스에서 접근이 가능

public:  접근 제한이 전혀 없음

주의할 점은 대상에 따라 사용할 수 있는 접근 제어자가 다르다는 것이다.

클래스: public, default 접근 제어자만 사용 가능

메서드, 멤버변수: public, protected, default, private 모두 사용가능

지역변수: 사용 할 수 있는 접근 제어자 없음

다음으로 상속 (Inheritance) 입니다.

상속이란 기존의 클래스를 재사용하여 새로운 클래스를 작성하는 것입니다.

상속을 이용하면 보다 적은 양의 코드로 새로운 클래스를 작성할 수 있고 코드를 공통적으로 관리할 수 있기 때문에 코드의 추가, 변경이 용이합니다.

상속의 이러한 특징은 코드의 재사용성을 높이고 코드의 중복을 제거하여 프로그램의 생산성과 유지보수에 크게 도움이 됩니다.

자바에서 상속을 구현하는 방법은 클래스 또는 인터페이스의 이름을 키워드 'extends', 'implements'와 함께 써 주기만 하면 됩니다.

// Parent클래스를 상속받는 Child클래스

class Child extends Parent {

         //...

}

class 클래스이름 implements 인터페이스이름{

        // 인터페이스에 정의된 추상메서드를 구현

}

주의할 점은 extends와 implements를 사용할때는 다음과 같은 규칙들이 있다는 것입니다.

1. 클래스가 클래스를 상속받을땐 extends 사용
2. 클래스가 인터페이스를 상속받을땐 implements 사용
3. 인터페이스가 인터페이스를 상속받을땐 extends 사용
4. 인터페이스를 다중 상속받는것은 가능하지만, 클래스를 다중 상속받는것은 불가능

마지막으로 다형성 (polymorphism) 입니다.

다형성은 객체 지향 프로그래밍의 3요소중 가장 중요하다고 여겨지는 것입니다.

다형성이란 여러 가지 형태를 가질 수 있는 능력을 의미합니다.

예를들어, 자바에서는 한 타입의 참조변수로 여러 타입의 객체를 참조할 수 있도록 하거나,

똑같은 이름으로 서로 다르게 동작하는 메서드를 정의하고 호출할 수 있도록 하면서 다형성을 실현할 수 있게 합니다.

다형성을 취하므로 얻을 수 있는 이익으로는 메서드나 객체 설계시 역할(메서드 이름, 인터페이스)을 먼저 부여하고,

그  후에 해당 역할을 수향하는 구현체를 만듦으로써

사용자는 구현체의 내부 구조를 몰라도 사용가능하고, 구현체의 내부 구조가 변경되어도 영향을 받지 않으며, 구현대상을 변경해도 영향을 받지 않게 된다는 점이 있습니다.

구체적인 예로는 업캐스팅, 오버로딩, 오버라이딩 정도가 있습니다.

위 3가지는 하나하나가 포스팅 주제로 다뤄질 만큼 중요하고 설명할 양이 적지않아 여기서는 정의와 이것들이 어떤 방식으로 다형성을 이루는지 정도만 설명하겠습니다.

업캐스팅: 조상클래스 타입의 참조변수로 자손클래스의 인스턴스를 참조할 수 있도록 하는 것으로,

한가지 타입의 참조 변수가 여러 타입의 인스턴스를 참조 할 수 있다는 점에서 다형성을 실현하였다 할 수 있습니다.

오버로딩: 한 클래스 내에 같은 이름의 메서드를 여러 개 정의하는 것으로,

똑같은 이름으로 여러가지 메서드들을 나타낼 수 있다는 점에서 다형성을 실현하였다 말할 수 있습니다.

오버라이딩: 조상 클래스로부터 상속받은 메서드의 내용을 변경하는 것으로,

이 역시 같은 이름으로 다르게 구현하는 메서드를 호출하므로 다형성을 실현하였다 할 수 있습니다.

참조: Java의 정석 3rd Edition(남궁 성 지음)