전체 글

전체 글

    [java] 백준 11047 (동전 0) Silver 1
    Algorithm/Baekjoon Online Judge

    [java] 백준 11047 (동전 0) Silver 1

    Problem : https://www.acmicpc.net/problem/11047 11047번: 동전 0 첫째 줄에 N과 K가 주어진다. (1 ≤ N ≤ 10, 1 ≤ K ≤ 100,000,000) 둘째 줄부터 N개의 줄에 동전의 가치 Ai가 오름차순으로 주어진다. (1 ≤ Ai ≤ 1,000,000, A1 = 1, i ≥ 2인 경우에 Ai는 Ai-1의 배수) www.acmicpc.net Approach 주어지는 동전의 가치가 항상 배수관계이므로, 동전의 개수가 최소가 되게끔 동전을 사용하려면 동전의 가치가 큰 것부터 동전을 구성해나가면 된다. 예를들어, 500원 2개보단 1000원 1개 사용하는게 개수가 더 적다.(주어지는 동전의 가치들이 항상 배수관계이므로 가능함) 다른 테크닉은 필요하지 않는 간..

    [java] 백준 17298 (오큰수) Gold 4
    Algorithm/Baekjoon Online Judge

    [java] 백준 17298 (오큰수) Gold 4

    Problem : https://www.acmicpc.net/problem/17298 17298번: 오큰수 첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000,000)이 주어진다. 둘째에 수열 A의 원소 A1, A2, ..., AN (1 ≤ Ai ≤ 1,000,000)이 주어진다. www.acmicpc.net Approach 배열에서 자신 기준 오른쪽에 있는 큰 값들 중 가장 가까운 값을 찾는 문제이다. 간단하게 생각할 수 있는 naive한 방법은 자신보다 큰 값이 나올 때까지 자신 기준 오른쪽 요소들을 모두 탐색하는 것이다. 하지만 이런 접근법은 최대 O(n^2)의 시간복잡도를 가지므로 효율성이 떨어진다. 다른 풀이법으로는 스택을 이용한 풀이법이 있다. 처음 시작점을 스택에 push 한다. 스택의..

    [java] 백준 2629 (양팔저울) Gold 2
    Algorithm/Baekjoon Online Judge

    [java] 백준 2629 (양팔저울) Gold 2

    Problem : https://www.acmicpc.net/problem/2629 2629번: 양팔저울 첫째 줄에는 추의 개수가 자연수로 주어진다. 추의 개수는 30 이하이다. 둘째 줄에는 추의 무게들이 자연수로 가벼운 것부터 차례로 주어진다. 같은 무게의 추가 여러 개 있을 수도 있다. 추의 무 www.acmicpc.net Approach 주어진 추들의 무게로 구슬의 무게를 확인할 수 있는지를 판단하는 문제였다. 구슬을 목적지라고 가정한다면, 목적지를 갈 수 있는지를 판단하는 문제다. 따라서 필자는 깊이우선탐색을 이용하여 풀이를 하였다. 일단, 탐색 진행 방법에는 3가지 방법이 있다. 무게를 확인할 구슬은 항상 저울의 왼쪽에 놓는다고 가정하였을 때, 다음 구슬을 저울의 오른쪽에 올리는 경우(w + w..

    [java] 백준 1707 (이분 그래프) Gold 4
    Algorithm/Baekjoon Online Judge

    [java] 백준 1707 (이분 그래프) Gold 4

    Problem : https://www.acmicpc.net/problem/1707 1707번: 이분 그래프 입력은 여러 개의 테스트 케이스로 구성되어 있는데, 첫째 줄에 테스트 케이스의 개수 K(2≤K≤5)가 주어진다. 각 테스트 케이스의 첫째 줄에는 그래프의 정점의 개수 V(1≤V≤20,000)와 간선의 개수 www.acmicpc.net Approach 풀이에 시작하기 앞서 주의할 점을 소개한다. 이 문제는 은근히 반례를 찾는 유저들이 많았는데 대부분 다음과 같은 이유로 오답이 생겼을 것이다. 질문 게시판에 있는 djm03178님의 게시글을 인용하겠다. 테스트 케이스마다 초기화를 해야 한다. 똑같은 입력을 주었을 때 다른 출력을 내놓는다면 초기화가 되지 않은 상태일 것이다. 1번 정점에서만 탐색을 하..

    [java] 프로그래머스 (구명보트) Level 2
    Algorithm/Programmers

    [java] 프로그래머스 (구명보트) Level 2

    Problem : https://programmers.co.kr/learn/courses/30/lessons/42885 코딩테스트 연습 - 구명보트 무인도에 갇힌 사람들을 구명보트를 이용하여 구출하려고 합니다. 구명보트는 작아서 한 번에 최대 2명씩 밖에 탈 수 없고, 무게 제한도 있습니다. 예를 들어, 사람들의 몸무게가 [70kg, 50kg, 80kg, 5 programmers.co.kr Approach N kg의 하중을 견디는 보트를 최소로 사용하여 모든 사람을 구출하는 문제이다. 일단 사람들의 몸무게를 오름차순으로 정렬한다. 그리고 밑의 단계를 반복한다. 구출하지 못한 사람들 중, 몸무게가 가장 큰 사람과 작은 사람의 합이 보트의 하중 기준치를 넘긴다면, 가장 큰 사람만 태운다. 구출하지 못한 사람..

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

    [java] 프로그래머스 (위장) Level 2

    Problem : https://programmers.co.kr/learn/courses/30/lessons/42578 코딩테스트 연습 - 위장 programmers.co.kr Approach 조합의 수학적 규칙을 알고 있다면 쉽게 풀 수 있는 문제이다. N개의 옷이 있을 때, 옷을 고를 수 있는 경우의 수(입지 않는 경우도 포함)는 N+1가지다. 그래서 M종류의 옷이 각각 N1, N2, ... , Nm개씩 있을 때, 옷을 고를 수 있는 경우의 수(입지 않는 경우도 포함)는 (N1 + 1) * (N2 + 1) * ... * (Nm + 1) - 1(옷을 하나도 안입는 경우) 이다. 위 규칙만 안다면 각각 옷의 개수가 몇개인지만 판별하면 된다. 필자는 HashMap을 사용하여 옷의 개수를 카운팅하기가 편했다..

    [java] 백준 1956 (운동) Gold 4
    Algorithm/Baekjoon Online Judge

    [java] 백준 1956 (운동) Gold 4

    Problem : https://www.acmicpc.net/problem/1956 1956번: 운동 첫째 줄에 V와 E가 빈칸을 사이에 두고 주어진다. (2 ≤ V ≤ 400, 0 ≤ E ≤ V(V-1)) 다음 E개의 줄에는 각각 세 개의 정수 a, b, c가 주어진다. a번 마을에서 b번 마을로 가는 거리가 c인 도로가 있다는 의 www.acmicpc.net Approach 최단경로 사이클을 찾는 문제이다. 따라서 플로이드 와샬(Floyd Warshall) 알고리즘을 사용하여야 한다. 참고로 1:N 최단경로 문제는 다익스트라 알고리즘을, 음수사이클을 찾을 때엔 벨만-포드 알고리즘을, N:N 최단경로 문제는 플로이드 와샬 알고리즘으로 접근하면 용이하다. 이 문제에서는 각 노드 A에 대하여 A에서 시작하..

    [java] 백준 10217 (KCM Travel) Gold 1
    Algorithm/Baekjoon Online Judge

    [java] 백준 10217 (KCM Travel) Gold 1

    Problem : https://www.acmicpc.net/problem/10217 10217번: KCM Travel 각고의 노력 끝에 찬민이는 2014 Google Code Jam World Finals에 진출하게 되었다. 구글에서 온 초대장을 받고 기뻐했던 것도 잠시, 찬찬히 읽어보던 찬민이는 중요한 사실을 알아차렸다. 최근의 대세 www.acmicpc.net Approach 이 문제는 다익스트라 알고리즘과 DP를 같이 사용해서 풀어야했다. 인접리스트를 이용하여 그래프를 구성하였으며, 시간순 오름차순(시간이 같으면 비용순 오름차순)으로 구성하였다. 그런 후, 시작점 1부터 다익스트라 알고리즘을(BFS: PriorityQueue 이용) 적용하여, 비용을 초과하지 않는 선에서 모두 갱신해주었다. 다익스..

    [java] 프로그래머스 (전화번호 목록) Level 2
    Algorithm/Programmers

    [java] 프로그래머스 (전화번호 목록) Level 2

    Problem : https://programmers.co.kr/learn/courses/30/lessons/42577 코딩테스트 연습 - 전화번호 목록 전화번호부에 적힌 전화번호 중, 한 번호가 다른 번호의 접두어인 경우가 있는지 확인하려 합니다. 전화번호가 다음과 같을 경우, 구조대 전화번호는 영석이의 전화번호의 접두사입니다. 구조 programmers.co.kr Approach 처음엔 임의의 문자열 하나 A를 나머지 문자열(B, C, D, ...)에서 찾는 indexOf() 를 활용하여 반환값이 0인 것을 찾는 naive한 방법을 사용했었다. (indexOf()의 반환값이 0이면, 그 문자열로 시작한다는 뜻이므로) 그래서 Set 에 주어진 문자열을 모두 넣은 후, 하나씩 검사하는 방식을 썼었다. 이..

    [java] 백준 11404 (플로이드) Gold 4
    Algorithm/Baekjoon Online Judge

    [java] 백준 11404 (플로이드) Gold 4

    Problem : https://www.acmicpc.net/problem/11404 11404번: 플로이드 첫째 줄에 도시의 개수 n이 주어지고 둘째 줄에는 버스의 개수 m이 주어진다. 그리고 셋째 줄부터 m+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 버스의 출발 도시의 번호가 www.acmicpc.net Approach 1 대 N 최단 경로를 구할 때에는 다익스트라(Dijkstra) 알고리즘을 사용하면 된다. N 대 N 최단 경로를 구할 때에는 플로이드 와샬(Floyd Warshall) 알고리즘을 사용하면 된다. 다익스트라 알고리즘은 가장 적은 비용을 하나씩 선택하며 최단경로를 구성해 나갔다면, 플로이드 와샬 알고리즘은 거쳐가는 정점을 기준으로 알고리즘을 수행한다. 다음과 같은 ..

티스토리툴바