전체 글

전체 글

    [java] 백준 14226 (이모티콘) Gold 5
    Algorithm/Baekjoon Online Judge

    [java] 백준 14226 (이모티콘) Gold 5

    문제 원문 링크 : https://www.acmicpc.net/problem/14226 14226번: 이모티콘 영선이는 매우 기쁘기 때문에, 효빈이에게 스마일 이모티콘을 S개 보내려고 한다. 영선이는 이미 화면에 이모티콘 1개를 입력했다. 이제, 다음과 같은 3가지 연산만 사용해서 이모티콘을 S개 만 www.acmicpc.net Approach DFS 를 이용한 DP문제이다. 문제의 조건 화면에 있는 이모티콘을 모두 복사해서 클립보드에 저장한다. 클립보드에 있는 모든 이모티콘을 화면에 붙여넣기 한다. 화면에 있는 이모티콘 중 하나를 삭제한다. 이 문제를 풀려면 이모티콘의 길이가 X일 때, 현재 클립보드에 저장된 이모티콘의 길이가 몇인지를 저장해 놓아야 한다. 그래야 X보다 큰 길이Y의 이모티콘을 만들 때..

    [java] 백준 1949 (우수 마을) Gold 1
    Algorithm/Baekjoon Online Judge

    [java] 백준 1949 (우수 마을) Gold 1

    문제 원문 링크 : https://www.acmicpc.net/problem/1949 1949번: 우수 마을 N개의 마을로 이루어진 나라가 있다. 편의상 마을에는 1부터 N까지 번호가 붙어 있다고 하자. 이 나라는 트리(Tree) 구조로 이루어져 있다. 즉 마을과 마을 사이를 직접 잇는 N-1개의 길이 있으며, www.acmicpc.net Approach(Wrong: TLE) 트리에서의 DP문제로, 2213번 트리의 독립집합과 유사한 문제이다. DFS를 이용하여 트리 끝까지 내려가면 함수가 차례차례 종료되는 것을 이용하여 값을 갱신했지만 시간초과(TLE)가 떴다. 질문 글을 올려 답변을 받자면 내 잘못된 코드는 DP를 수행하지 않고 그냥 탐색만 하는 것이므로 각 호출에서 구한 답을 메모이제이션 해보라는 ..

    [java] 백준 2533 (사회망 서비스(SNS)) Gold 3
    Algorithm/Baekjoon Online Judge

    [java] 백준 2533 (사회망 서비스(SNS)) Gold 3

    문제 원문 링크 : https://www.acmicpc.net/problem/2533 2533번: 사회망 서비스(SNS) 페이스북, 트위터, 카카오톡과 같은 사회망 서비스(SNS)가 널리 사용됨에 따라, 사회망을 통하여 사람들이 어떻게 새로운 아이디어를 받아들이게 되는가를 이해하는 문제가 중요해졌다. 사회망 www.acmicpc.net Approach (Wrong) 내가 처음 생각했던 잘못된 접근법 처음에는 아무 노드나 루트로 잡고 level을 매겨서 min(홀수레벨 총 노드개수, 짝수레벨 총 노드개수)로 구현하면 될 줄 알았다. 질문 게시판에 있는 대부분의 반례 또한 통과되어 맞는 풀이법이라고 생각했으나, 다음과 같은 반례가 있었다. Approach (Correct) 자신이 얼리어답터인지, 아닌지 일때..

    [java] 백준 15681 (트리와 쿼리) Gold 5
    Algorithm/Baekjoon Online Judge

    [java] 백준 15681 (트리와 쿼리) Gold 5

    문제 원문 링크 : https://www.acmicpc.net/problem/15681 15681번: 트리와 쿼리 트리의 정점의 수 N과 루트의 번호 R, 쿼리의 수 Q가 주어진다. (2 ≤ N ≤ 105, 1 ≤ R ≤ N, 1 ≤ Q ≤ 105) 이어 N-1줄에 걸쳐, U V의 형태로 트리에 속한 간선의 정보가 주어진다. (1 ≤ U, V ≤ N, U ≠ V) www.acmicpc.net Approach 트리에서의 DP문제다. 트리를 만들 때는 루트를 지정하고 시작하는 것이 편하다. 이 문제의 경우에는, 트리를 만들면서 배열에 자신의 서브노드 개수를 기록하면 된다. 함수를 재귀적으로 호출하면 Terminal Node부터 함수가 종료되기 때문에 쉽게 구현할 수 있다. Code import java.io..

    [Java] TreeSet<E>
    Language/Java

    [Java] TreeSet<E>

    슈퍼클래스 Set 에 대해 알고 싶으면 다음 포스팅을 참고하세요. 본 포스팅 내용 중 Set 주요 메소드에 관한 내용은 밑의 포스팅에 정리하였습니다. 2020/11/11 - [Language/Java] - [Java] Set 정리 [Java] Set 정리 Set의 서브클래스에 대해 알고 싶으면 다음 포스팅을 참고하세요. 2020/12/12 - [Language/Java] - [Java] HashSet, LinkedHashSet 정리 , LinkedHashSet 정리" data-og-description="HashSet의 상속관계 Module j.. gre-eny.tistory.com TreeSet의 상속관계 Module java.base Package java.util Class TreeSet java...

    [Java] HashSet<E>, LinkedHashSet<E>
    Language/Java

    [Java] HashSet<E>, LinkedHashSet<E>

    슈퍼클래스 Set 에 대해 알고 싶으면 다음 포스팅을 참고하세요. HashSet 의 주요 메소드는 대부분 Set 클래스와 동일하므로 밑의 포스팅에 정리하였습니다. 2020/11/11 - [Language/Java] - [Java] Set 정리 [Java] Set 정리 Set의 서브클래스에 대해 알고 싶으면 다음 포스팅을 참고하세요. 2020/12/12 - [Language/Java] - [Java] HashSet, LinkedHashSet 정리 , LinkedHashSet 정리" data-og-description="HashSet의 상속관계 Module j.. gre-eny.tistory.com HashSet의 상속관계 Module java.base Package java.util Class HashSe..

    [java] 백준 17070 (파이프 옮기기 1) Gold 5
    Algorithm/Baekjoon Online Judge

    [java] 백준 17070 (파이프 옮기기 1) Gold 5

    문제 원문 링크 : https://www.acmicpc.net/problem/17070 17070번: 파이프 옮기기 1 유현이가 새 집으로 이사했다. 새 집의 크기는 N×N의 격자판으로 나타낼 수 있고, 1×1크기의 정사각형 칸으로 나누어져 있다. 각각의 칸은 (r, c)로 나타낼 수 있다. 여기서 r은 행의 번호, c는 열의 www.acmicpc.net Approach DP문제이다. 위 그림과 같이 파이프를 놓을 수 있고, 첫 파이프가 (1, 1) 과 (1, 2)를 차지할 수 있으므로 처음 놓을 수 있는 파이프는 3열부터 놓을수 있다. DP[i][j][1] = 파이프의 끝이 가로방향으로 (i, j) 에 놓여 있는 경우, DP[i][j][1] = DP[i][j - ..

    [java] 백준 17404 (RGB거리 2) Gold 4
    Algorithm/Baekjoon Online Judge

    [java] 백준 17404 (RGB거리 2) Gold 4

    문제 원문 링크: https://www.acmicpc.net/problem/17404 17404번: RGB거리 2 첫째 줄에 집의 수 N(2 ≤ N ≤ 1,000)이 주어진다. 둘째 줄부터 N개의 줄에는 각 집을 빨강, 초록, 파랑으로 칠하는 비용이 1번 집부터 한 줄에 하나씩 주어진다. 집을 칠하는 비용은 1,000보다 작거나 www.acmicpc.net 비슷한 문제 백준 1149 (RGB거리) Silver 1 1149번: RGB거리 첫째 줄에 집의 수 N(2 ≤ N ≤ 1,000)이 주어진다. 둘째 줄부터 N개의 줄에는 각 집을 빨강, 초록, 파랑으로 칠하는 비용이 1번 집부터 한 줄에 하나씩 주어진다. 집을 칠하는 비용은 1,000보다 작거나 www.acmicpc.net Approach DP문제이다..

    [java] 백준 1149 (RGB거리) Silver 1
    Algorithm/Baekjoon Online Judge

    [java] 백준 1149 (RGB거리) Silver 1

    문제 원문 링크: https://www.acmicpc.net/problem/1149 1149번: RGB거리 첫째 줄에 집의 수 N(2 ≤ N ≤ 1,000)이 주어진다. 둘째 줄부터 N개의 줄에는 각 집을 빨강, 초록, 파랑으로 칠하는 비용이 1번 집부터 한 줄에 하나씩 주어진다. 집을 칠하는 비용은 1,000보다 작거나 www.acmicpc.net Approach DP문제이다. DP[i][j] = i번째 집을 j색으로 칠했을 때의 최소비용값이라 할 때, Min(DP[N][빨강], DP[N][초록], DP[N][파랑]) 을 구하면 되는 문제이다. 연속된 집을 같은 색깔로 칠할 수는 없으므로 밑의 점화식을 적용시킬 수 있다. DP[i][j] = Min(DP[i - 1][(j + 1) % 3], DP[i -..

    [java] 백준 12852 (1로 만들기 2) Silver 1
    Algorithm/Baekjoon Online Judge

    [java] 백준 12852 (1로 만들기 2) Silver 1

    문제 원문 링크: https://www.acmicpc.net/problem/12852 Approach DP 문제이다.DP[i] = i를 만들 수 있는 최소 연산 수. 라고 하였을 때,i 를 만들 수 있는 가짓 수는 다음 3가지이다. 이 중 최소 연산 수를 DP[i]에 저장하면 된다. i - 1 숫자에서 +1 을 하여 i를 만드는 경우 i / 2 숫자에서 *2 를 하여 i를 만드는 경우 i / 3 숫자에서 *3 을 하여 i를 만드는 경우위의 규칙으로 밑의 점화식을 도출할 수 있다. DP[i] = min(DP[i - 1], DP[i / 2], DP[i / 3]) 위의 식은 Bottom-up 방식의 점화식이다.i가 2나 3으로 나누어 떨어질 경우에만 나눠야 하므로 위의 식에 조건을 추가하여야 한다.추가로 N을..

티스토리툴바