Algorithm

    [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 ..

    [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..

    [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로 정해놓고, 범위를 점점 줄여나가는 식으로 풀이를 생각했지만, 결과적으로 시간초과가 나는 코드가 됐다. 문자열의 모든 위치를 기준으로 시작하여, 팰린드롬이면 계속해서 범위를 늘려 팰린드롬 문자열인지..

    [java] 백준 10266 (시계 사진들) Platinum 5
    Algorithm/Baekjoon Online Judge

    [java] 백준 10266 (시계 사진들) Platinum 5

    Problem : https://www.acmicpc.net/problem/10266 10266번: 시계 사진들 상근이는 보통의 시계와는 다른 독특한 시계 사진 두장이 있습니다. 시계는 n개의 동일한 길이와 목적을 가진 시계 바늘들을 가지고 있습니다. 애석하게도 시계의 숫자들은 희미해져 각 시계 바 www.acmicpc.net Approach KMP 알고리즘의 실패함수(Failure Function)를 연습할 수 있는 문제이다. KMP 알고리즘의 자세한 내용은 다음 링크를 참조하면 좋을것이다. https://bowbowbow.tistory.com/6#comment5168448 KMP : 문자열 검색 알고리즘 문자열 검색이 뭐지? 워드프로세서를 사용할 때 찾기 기능을 사용한적 있을 겁니다. 브라우저에서도 ..

    [java] 백준 1305 (광고) Platinum 5
    Algorithm/Baekjoon Online Judge

    [java] 백준 1305 (광고) Platinum 5

    Problem : https://www.acmicpc.net/problem/1305 1305번: 광고 세준이는 길 한가운데에서 전광판을 쳐다보고 있었다. 전광판에는 광고가 흘러나오고 있었다. 한참을 전광판을 쳐다본 세준이는 이 광고가 의미하는 것이 무엇인지 궁금해지기 시작했다. 전광 www.acmicpc.net Approach KMP 알고리즘의 실패함수(Failure Function)를 연습할 수 있는 문제이다. KMP 알고리즘의 자세한 내용은 다음 링크를 참조하면 좋을것이다. https://bowbowbow.tistory.com/6#comment5168448 여기서 사용할 내용은 실패함수(Failure Function) pi를 활용한다. 실패함수 pi는 간단히 말하면, i길이의 문자열 p 에서 접두사와..

    [java] 백준 4354 (문자열 제곱) Platinum 5
    Algorithm/Baekjoon Online Judge

    [java] 백준 4354 (문자열 제곱) Platinum 5

    Problem : https://www.acmicpc.net/problem/4354 4354번: 문자열 제곱 알파벳 소문자로 이루어진 두 문자열 a와 b가 주어졌을 때, a*b는 두 문자열을 이어붙이는 것을 뜻한다. 예를 들어, a="abc", b="def"일 때, a*b="abcdef"이다. 이러한 이어 붙이는 것을 곱셈으로 생각한다 www.acmicpc.net Approach KMP 알고리즘의 실패함수(Failure Function)를 연습할 수 있는 문제이다. KMP 알고리즘의 자세한 내용은 다음 링크를 참조하면 좋을것이다. https://bowbowbow.tistory.com/6#comment5168448 여기서 사용할 내용은 실패함수(Failure Function) pi를 활용한다. 실패함수 p..

티스토리툴바