전체 글

전체 글

    [java] 프로그래머스 (거스름돈) Level 3
    Algorithm/Programmers

    [java] 프로그래머스 (거스름돈) Level 3

    Problem : https://programmers.co.kr/learn/courses/30/lessons/12907 코딩테스트 연습 - 거스름돈 Finn은 편의점에서 야간 아르바이트를 하고 있습니다. 야간에 손님이 너무 없어 심심한 Finn은 손님들께 거스름돈을 n 원을 줄 때 방법의 경우의 수를 구하기로 하였습니다. 예를 들어서 손님께 5 programmers.co.kr Approach 백준 온라인 저지에서도 DP 카테고리의 문제를 풀어봤다면, 비슷한 문제를 보았을 것이다. 꽤나 유명한 DP문제이고, 아마 나는 KnapSack 문제로 풀었던 것 같다. 하지만 여기서는 KnapSack처럼 2차원배열을 가지고 풀면 효율성테스트에서 시간초과가 발생하므로, 1차원배열로 풀이하여야 한다. DP[i] 를 i ..

    Head First: Design Patterns - 데코레이터 패턴(Decorator Pattern)
    Book/Design Patterns

    Head First: Design Patterns - 데코레이터 패턴(Decorator Pattern)

    디자인 패턴: 데코레이터 패턴(Decorator Pattern) 이 포스팅은 Head First: Design Patterns 책을 보고, 개인적으로 정리한 포스팅입니다. Decorator Pattern 이란? 데코레이터 패턴(Decorator Pattern)에서는 객체에 추가적인 요건을 동적으로 첨가한다. 데코레이터는 서브클래스를 만드는 것을 통해서 기능을 유연하게 확장할 수 있는 방법을 제공한다. 데코레이터의 슈퍼클래스는 자신이 장식하고 있는 객체의 슈퍼클래스와 같다. 한 객체를 여러 개의 데코레이터로 감쌀 수 있다. 데코레이터는 자신이 감싸고 있는 객체와 같은 슈퍼클래스를 가지고 있기 때문에 원래 객체(싸여져 있는 객체)가 들어갈 자리에 데코레이터 객체를 집어넣어도 상관없다. 데코레이터는 자신이 장..

    [Java] 백준 3344 (N-Queen) Platinum 5
    Algorithm/Baekjoon Online Judge

    [Java] 백준 3344 (N-Queen) Platinum 5

    Problem : https://www.acmicpc.net/problem/3344 3344번: N-Queen 첫째 줄에 N이 주어진다. N은 8, 26, 213, 2012, 99991, 99999중 하나이다. www.acmicpc.net Approach 일반적인 Backtracking 으로 풀면 시간초과가 난다. 입력의 크기가 최대 99999이고, 백트랙킹 기법은 시간복잡도가 O(N^2)이기 때문이다. 나도 구글링 중에 알아낸 풀이법으로, N-Queens의 규칙을 찾아 그대로 구현하는 문제였다. 솔직히 아직 완벽히 이해하진 못했다. 자세한 알고리즘은 밑의 링크에 Existence of solutions 탭을 확인하시면 좋을 것 같다. https://en.wikipedia.org/wiki/Eight_qu..

    [java] 프로그래머스 (리틀 프렌즈 사천성) Level 3
    Algorithm/Programmers

    [java] 프로그래머스 (리틀 프렌즈 사천성) Level 3

    Problem : https://programmers.co.kr/learn/courses/30/lessons/1836 코딩테스트 연습 - 리틀 프렌즈 사천성 리틀 프렌즈 사천성 언제나 맛있는 음식들이 가득한 평화로운 푸드 타운. 푸드 타운에서 행복하게 사는 리틀 프렌즈들은 마을에 있는 매직 스푼을 보물처럼 보관하고 있다. 매직 스푼은 재료만 programmers.co.kr Approach 2017 카카오코드 본선문제이다. 구현에 필요한 별다른 테크닉은 필요없고, 여러 경우에 대해 조건 검사를 많이 해야되는 문제였다. 두 타일 사이가 최대 한번의 꺾임만으로 서로 도달할 수 있는지에 대한 문제이다. 동시에 없앨 수 있는 타일이 여러개이면, 알파벳이 작은 순부터 처리해야하므로, 정렬은 사용해야 되겠다는 점만 ..

    [java] 프로그래머스 (블록 이동하기) Level 3
    Algorithm/Programmers

    [java] 프로그래머스 (블록 이동하기) Level 3

    Problem : https://programmers.co.kr/learn/courses/30/lessons/60063 코딩테스트 연습 - 블록 이동하기 [[0, 0, 0, 1, 1],[0, 0, 0, 1, 0],[0, 1, 0, 1, 1],[1, 1, 0, 0, 1],[0, 0, 0, 0, 0]] 7 programmers.co.kr Approach 2020 KAKAO BLIND RECRUITMENT 문제이다. 약간 어려운 DP문제라고 생각한 문제이지만, 백준 온라인 저지에서도 비슷한 류의 DP 문제를 보았기에 크게 어렵지는 않았다. 일단 DP 배열을 구성함에 있어 로봇이 가로방향일 때와 세로방향일 때를 나누어 구성하였다. 그리고 자유롭게 이동을 할 수 있다는 가정에서의 총 움직임 개수는 8개이다.(상하..

    [java] 프로그래머스 (외벽 점검) Level 3
    Algorithm/Programmers

    [java] 프로그래머스 (외벽 점검) Level 3

    Problem : https://programmers.co.kr/learn/courses/30/lessons/60062 코딩테스트 연습 - 외벽 점검 레스토랑을 운영하고 있는 스카피는 레스토랑 내부가 너무 낡아 친구들과 함께 직접 리모델링 하기로 했습니다. 레스토랑이 있는 곳은 스노우타운으로 매우 추운 지역이어서 내부 공사를 하는 programmers.co.kr Approach 2020 KAKAO BLIND RECRUITMENT 문제였다. (해당 코딩테스트에서 가장 낮은 정답률을 기록하는... 0.6%) 순열을 이용한 탐색 유형의 문제이다. 처음 문제를 접했을 땐, dist 배열을 오름차순으로 정렬하여 무언가를 해보려고 했으나, 조금 생각한 결과 간단하게도 많은 반례가 생각이나서 고민 차에, 카카오 테크..

    [java] 프로그래머스 (기둥과 보 설치) Level 3
    Algorithm/Programmers

    [java] 프로그래머스 (기둥과 보 설치) Level 3

    Problem : https://programmers.co.kr/learn/courses/30/lessons/60061 코딩테스트 연습 - 기둥과 보 설치 5 [[1,0,0,1],[1,1,1,1],[2,1,0,1],[2,2,1,1],[5,0,0,1],[5,1,0,1],[4,2,1,1],[3,2,1,1]] [[1,0,0],[1,1,1],[2,1,0],[2,2,1],[3,2,1],[4,2,1],[5,0,0],[5,1,0]] 5 [[0,0,0,1],[2,0,0,1],[4,0,0,1],[0,1,1,1],[1,1,1,1],[2,1,1,1],[3,1,1,1],[2,0,0,0],[1,1,1,0],[2,2,0,1]] [[ programmers.co.kr Approach 2020 KAKAO BLIND RECRUITMEN..

    Head First: Design Patterns - 옵저버 패턴(Observer Pattern)
    Book/Design Patterns

    Head First: Design Patterns - 옵저버 패턴(Observer Pattern)

    디자인 패턴: 옵저버 패턴(Observer Pattern) 이 포스팅은 Head First: Design Patterns 책을 보고, 개인적으로 정리한 포스팅입니다. Observer Pattern 이란? 옵저버 패턴(Observer Pattern)에서는 한 객체의 상태가 바뀌면 그 객체에 의존하는 다른 객체들한테 연락이 가고 자동으로 내용이 갱신되는 방식으로 일대다(one-to-many) 의존성을 정의한다. 일대다 관계는 주제(Subject)와 옵저버(Observer)에 의해 정의된다. 옵저버 패턴을 구현하는 방법에는 여러가지가 있지만, 대부분 주제(Subject) 인터페이스와 옵저버(Observer) 인터페이스가 들어있는 클래스 디자인을 바탕으로 한다. 일대다 관계 옵저버 패턴에서 상태를 저장하고 지배..

    Head First: Design Patterns - 스트래티지(전략) 패턴(Strategy Pattern)
    Book/Design Patterns

    Head First: Design Patterns - 스트래티지(전략) 패턴(Strategy Pattern)

    디자인 패턴: 스트래티지 패턴(Strategy Pattern) 이 포스팅은 Head First: Design Patterns 책을 보고, 개인적으로 정리한 포스팅입니다. Strategy Pattern 이란? 스트래티지 패턴(Strategy Pattern)에서는 알고리즘군을 정의하고 각각을 캡슐화하여 교환해서 사용할 수 있도록 만든다. 스트래티지 패턴을 활용하면 알고리즘을 사용하는 클라이언트와는 독립적으로 알고리즘을 변경할 수 있다. 간단한 SimUDuck 애플리케이션 이 애플리케이션에서는 헤엄을 치거나, 꽥꽥거리는 소리도 내는 매우 다양한 오리 종류를 보여준다. 처음 이 시스템을 디자인한 사람들은 표준적인 객체지향 기법을 사용하여 Duck이라는 슈퍼클래스를 만든 다음, 그 클래스를 확장하여 다른 모든 종..

    [java] 프로그래머스 (가장 긴 팰린드롬) Level 3
    Algorithm/Programmers

    [java] 프로그래머스 (가장 긴 팰린드롬) Level 3

    Problem : https://programmers.co.kr/learn/courses/30/lessons/12904 코딩테스트 연습 - 가장 긴 팰린드롬 앞뒤를 뒤집어도 똑같은 문자열을 팰린드롬(palindrome)이라고 합니다. 문자열 s가 주어질 때, s의 부분문자열(Substring)중 가장 긴 팰린드롬의 길이를 return 하는 solution 함수를 완성해 주세요. 예를들 programmers.co.kr Approach 처음 생각한 풀이는 문자열의 왼쪽 끝과 오른쪽 끝을 각각 left와 right로 정해놓고, 범위를 점점 줄여나가는 식으로 풀이를 생각했지만, 결과적으로 시간초과가 나는 코드가 됐다. 문자열의 모든 위치를 기준으로 시작하여, 팰린드롬이면 계속해서 범위를 늘려 팰린드롬 문자열인지..

티스토리툴바