본문 바로가기

CS

 (93)
[프로그래머스] 뒤에 있는 큰 수 찾기 https://school.programmers.co.kr/learn/courses/30/lessons/154539 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 배열의 각 원소에 대해 자기보다 1) 뒤에 있고 2) 크면서 3) 가장 가까운 숫자를 "뒷 큰 수"라고 정의한다. 현재 문제는 배열이 주어졌을 때 뒷 큰 수를 구하는 문제다. 단순히 생각해서 특정 인덱스에서 자기보다 인덱스가 높은 모든 배열 원소와 값을 비교한다면 결과를 구할 수 있다. 예를 들어 인덱스가 1이라면, 인덱스 2 ~ n-1의 원소를 모두 비교하다 보면 언젠가 답이 나오는 것이다. ..
[디자인패턴] Bridge 패턴 설명 구현과 추상을 분리하여 독립적으로 존재하게 만든다. 확장성과 유연성이 좋다. 추상적 개념을 구체화하는 경우 상속을 이용할 수 있다. 이때 상속의 경우 하면 할수록 클래스가 구체적인 구현 사항에 종속되기 때문에 수정 및 확장이 어려워진다. 위 그림의 Paint를 생각해 보자. Paint는 도형들에 대한 가장 추상적인 인터페이스로, 도형을 화면에 그리는 draw 메서드를 정의한다. 구체적인 도형을 의미하는 Circle, Rectangle은 Paint 인터페이스를 구현함으로써 화면에 표현될 수 있으며, 이를 통해 모든 도형을 draw( )라는 일관된 메서드를 통해 그릴 수 있게 된다. 여기서 문제점이 되는 부분은 각 도형을 구체적으로 그리는 구현과 밀접하게 관계되는 OpenGL__, DirectX__ 클..
[디자인패턴] Singleton 패턴 설명 어떤 클래스는 프로그램 상에서 정확히 하나의 인스턴스만 존재하여, 해당 인스턴스가 자신과 관련된 모든 작업을 감독해야 하는 경우가 있다. 이 상황에서 단순히 static 전역변수를 하나 둬서 처리할 수도 있지만 싱글톤 패턴을 이용하여 클래스 자신이 static 변수를 관리하면서 단일 인스턴스를 보장할 수 있다. 일반적인 사용 방식은 다음과 같다. 생성자를 private ( 특이한 경우에는 protected ) 로 설정하여 클래스 외부에서 호출할 수 없게 만든다. 클래스 내부에 static private 인스턴스인 instance을 선언한다. public getInstance 함수를 통해 instance에 대한 접근 권한을 부여한다. 초기에 instance가 없다면 null 체크 후 instance을..
[디자인패턴] Adapter 패턴 설명 특정 클래스의 동작을 클라이언트가 원하는 형태로 변환, 인터페이스를 일치시킨다. 위 그림에서, 클라이언트는 Target 인터페이스 형태로 기존 기술인 Adaptee 클래스의 기능을 사용하고 싶다. 이때 Adaptee을 직접 Target에 맞게 수정하는 것은 매우 고단한 작업이며, 만약 레거시 기술이라면 여러 이유로 수정이 불가능할 수도 있다. 이러한 상황에서 외부 모듈 자체를 수정하는 대신 Adapter 클래스를 구현하여 Adaptee의 인터페이스를 Target의 인터페이스에 적응시킨다. Adapter 패턴은 기존 클래스 Adaptee을 사용하고 싶지만 인터페이스가 맞지 않는 경우, 이 상황에서 Adaptee 자체를 Target 인터페이스에 맞출 수는 없을 때 사용한다. 잘 유지보수 되고 있는 모듈..
[프로그래머스] 숫자 블록 https://school.programmers.co.kr/learn/courses/30/lessons/12923# 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 길이가 1,000,000,000(10억) 인 블록 각각에 숫자를 부여하되, 다음 조건을 만족한다. 숫자의 범위는 1 ~ 10,000,000(1천만) 이다. 숫자 N은 2 * N, 3 * N ... 블록에 부여될 수 있으며, 작은 숫자에서 큰 숫자 순서로 블록을 덮어쓸 수 있다. 예를 들어 4번째 블록에 숫자 1이 부여되더라도, 이후 숫자 블록 2에 의해 갱신될 수 있다. 즉, 조건을 만족하는 경..
[디자인패턴] Composite 패턴 설명 클라이언트 입장에서 개별적인 객체와 복합적인 객체를 동일하게 처리할 수 있도록 한다. Composite는 복합 객체로, 내부에 Component 추상 클래스를 상속하는 다른 객체들을 배열 등의 형태로 관리할 수 있다. 클라이언트는 복합 객체와 단일 객체의 구분 없이 동일하게 취급하며, 추상적인 Component라는 단위로 접근하게 된다. 구성 요소 Component: 모든 객체에 대한 인터페이스(추상 클래스)로, 객체들이 공통적으로 가지는 동작인 op 및 복합 객체에게 필요한 Add, Remove 등의 연산을 모두 정의하고 있다. 리프 노드들 입장에서는 Add, Remove 등 연산이 필요하지 않지만, 리스코프 교체 원리를 따라 단일 객체와 복합 개체 모두가 Component라는 인터페이스 아래에서..
[백준] 랜선 자르기 https://www.acmicpc.net/problem/1654 1654번: 랜선 자르기 첫째 줄에는 오영식이 이미 가지고 있는 랜선의 개수 K, 그리고 필요한 랜선의 개수 N이 입력된다. K는 1이상 10,000이하의 정수이고, N은 1이상 1,000,000이하의 정수이다. 그리고 항상 K ≦ N 이다. 그 www.acmicpc.net 발상에 도움이 된 영상: https://www.youtube.com/watch?v=94RC-DsGMLo 문제 설명 기존에 있던 랜선 K개를 동일한 양의 정수 길이 L 단위로 잘라 N개 이상의 동일한 랜선을 얻을 때, L의 최대값을 구하는 문제다. 일단 L의 후보 L'을 찾으면 ∑ ( Ki // L' ) >= N인지 판단할 수 있는데, 해당 조건을 만족하는 경우 L'을 ..
[백준] 계단 오르기 https://www.acmicpc.net/problem/2579 2579번: 계단 오르기 계단 오르기 게임은 계단 아래 시작점부터 계단 꼭대기에 위치한 도착점까지 가는 게임이다. 과 같이 각각의 계단에는 일정한 점수가 쓰여 있는데 계단을 밟으면 그 계단에 쓰여 있는 점 www.acmicpc.net 최근에 동적 계획법 문제를 접했는데 개인적으로 너무 어렵다고 느꼈다. 다만 계속 삽질하면서 얻은 경험적 지식 중 하나는 특정 동적 계획법 문제들은 뒤에서 앞 방향으로 식을 반대로 생각하면 쉬울 수 있다는 것이다. 현재 문제는 이러한 경우 중 하나로, 도착지 입장에서 점화식을 전개하는 방식으로 식을 작성했다. N번째 계단에 도달할 수 있는 경우는 크게 2가지가 존재할 수 있다. N-1번째 계단을 밟는 경우 N-..

티스토리툴바