전체 글

전체 글

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

    [java] 백준 1786 (찾기) Gold 1
    Algorithm/Baekjoon Online Judge

    [java] 백준 1786 (찾기) Gold 1

    Problem : https://www.acmicpc.net/problem/1786 1786번: 찾기 첫째 줄에, T 중간에 P가 몇 번 나타나는지를 나타내는 음이 아닌 정수를 출력한다. 둘째 줄에는 P가 나타나는 위치를 차례대로 공백으로 구분해 출력한다. 예컨대, T의 i～i+m-1번 문자와 P의 1～m www.acmicpc.net Approach KMP 알고리즘을 활용한 연습문제이다. KMP 알고리즘에 대한 내용은 여기서 다루지 않고 다음 링크를 참고하면 좋을 것이다. 설명이 정말 명쾌하다. https://bowbowbow.tistory.com/6#comment5168448 KMP : 문자열 검색 알고리즘 문자열 검색이 뭐지? 워드프로세서를 사용할 때 찾기 기능을 사용한적 있을 겁니다. 브라우저에서도..

    [java] 프로그래머스 (보행자 천국) Level 3
    Algorithm/Programmers

    [java] 프로그래머스 (보행자 천국) Level 3

    Problem : https://programmers.co.kr/learn/courses/30/lessons/1832 Approach 2017 카카오코드 예선 문제이다. DP를 이용하되, 두개의 DP를 유지하여야 하는 문제이다. 어느 한 지점 (x, y)에 대하여 그 점에 세로방향 길로 도착했는지, 가로방향 길로 도착했는지, 두개의 DP배열을 유지해야한다. 왜냐하면, 현재 위치 (x, y)에 회전금지 표지판이 있으면, 직진으로만 다음 위치로 갈 수 있기 때문이다. 따라서, 일반적으로 DP를 수행하되, 세로방향 길인지, 가로방향 길인지에 따라 다르게 처리를 해준 후, 목적지 (ex, ey) 를 세로방향 길로 도착할 수 있는 경우의 수와 가로방향 길로 도착할 수 있는 경우의 수를 더한다음 문제에서 요구한것처..

    [java] 프로그래머스 (베스트앨범) Level 3
    Algorithm/Programmers

    [java] 프로그래머스 (베스트앨범) Level 3

    Problem : https://programmers.co.kr/learn/courses/30/lessons/42579 코딩테스트 연습 - 베스트앨범 스트리밍 사이트에서 장르 별로 가장 많이 재생된 노래를 두 개씩 모아 베스트 앨범을 출시하려 합니다. 노래는 고유 번호로 구분하며, 노래를 수록하는 기준은 다음과 같습니다. 속한 노래가 programmers.co.kr Approach 자바에선 HashMap을 이용한 완전탐색으로 풀 수 있는 문제였다. 좀 더 깔끔하게 풀어보고 싶었지만 그럴줄 몰라 아쉬웠다. 문제에서 요구한 출력조건은 다음과 같다. 속한 노래가 많이 재생된 장르를 먼저 수록합니다. 장르 내에서 많이 재생된 노래를 먼저 수록합니다. 장르 내에서 재생 횟수가 같은 노래 중에서는 고유 번호가 낮은..

    [java] 프로그래머스 (순위) Level 3
    Algorithm/Programmers

    [java] 프로그래머스 (순위) Level 3

    Problem : https://programmers.co.kr/learn/courses/30/lessons/49191 코딩테스트 연습 - 순위 5 [[4, 3], [4, 2], [3, 2], [1, 2], [2, 5]] 2 programmers.co.kr Approach 플로이드-와샬 알고리즘을 활용하여 풀 수 있는 의외의 문제이다. 기본적인 메커니즘은 이렇다. result에 {1, 2}, {2, 3}이 있다면, (1, 3)도 결정된다. 경기결과에 없더라도 1과 3사이에 순위를 매길 수 있다. 그런 후, (i, j)와 (j, i)가 모두 갱신이 안되었다면, i 는 순위가 확정되지 않았다고 취급할 수 있다. 먼저 DP배열을 생성한 후, 초기화를 진행한다. (경기결과를 DP배열에 반영) 플로이드-와샬 알고..

    [java] 프로그래머스 (등굣길) Level 3
    Algorithm/Programmers

    [java] 프로그래머스 (등굣길) Level 3

    Problem : https://programmers.co.kr/learn/courses/30/lessons/42898 코딩테스트 연습 - 등굣길 계속되는 폭우로 일부 지역이 물에 잠겼습니다. 물에 잠기지 않은 지역을 통해 학교를 가려고 합니다. 집에서 학교까지 가는 길은 m x n 크기의 격자모양으로 나타낼 수 있습니다. 아래 그림은 m = programmers.co.kr Approach 간단한 DP문제이다. 주의할 점은 문제에서 주어진 예시그림과 주어진 데이터가 불일치한다는 점을 알고 가야한다. 문제의 그림에서는 m = 4, n = 3이지만, 3 x 4 지도가 나와있어 n이 행의 개수, m이 열의 개수라고 생각할 수 있겠지만, 그렇게 푼다면 런타임에러가 계속 뜰 것이다. m을 행의 개수, n을 열의 ..

    [java] 프로그래머스 (여행경로) Level 3
    Algorithm/Programmers

    [java] 프로그래머스 (여행경로) Level 3

    Problem : https://programmers.co.kr/learn/courses/30/lessons/43164 코딩테스트 연습 - 여행경로 [[ICN, SFO], [ICN, ATL], [SFO, ATL], [ATL, ICN], [ATL,SFO]] [ICN, ATL, ICN, SFO, ATL, SFO] programmers.co.kr Approach DFS 를 활용하여 풀이가 가능한 문제이다. 이름의 알파벳 순서가 앞서는 경우부터 방문해야 하므로 방문공항기준 오름차순으로 정렬하고 시작한다. 출발지는 항상 ICN 이므로 ICN을 출발지로 하여 DFS를 수행한다. 티켓을 모두 사용해야 하므로, 시작공항을 제외한 방문공항은 티켓의 개수와 같다.를 이용하여, 티켓을 처음 다 썼을 때의 경로를 ans에 담..

    [java] 프로그래머스 (입국심사) Level 3
    Algorithm/Programmers

    [java] 프로그래머스 (입국심사) Level 3

    Problem : https://programmers.co.kr/learn/courses/30/lessons/43238 코딩테스트 연습 - 입국심사 n명이 입국심사를 위해 줄을 서서 기다리고 있습니다. 각 입국심사대에 있는 심사관마다 심사하는데 걸리는 시간은 다릅니다. 처음에 모든 심사대는 비어있습니다. 한 심사대에서는 동시에 한 programmers.co.kr Approach 이분탐색(이진탐색)을 이용하는 문제였다. 주의할 점은 모든 자료형을 long으로 해줘야 런타임에러가 발생하지 않는다. 일단 이진탐색을 가능하게 하기 위해 정렬을 한다. 그리고 시간을 이분하면서 주어진 시간으로 몇명의 사람을 처리할 수 있는지를 체크한다. 주어진 사람 수 n미만 이면 시간이 더 필요하므로 반으로 나눠진 시간의 오른쪽..

티스토리툴바