전체 글

전체 글

    [java] 백준 11657 (타임머신) Gold 4
    Algorithm/Baekjoon Online Judge

    [java] 백준 11657 (타임머신) Gold 4

    Problem : https://www.acmicpc.net/problem/11657 11657번: 타임머신 첫째 줄에 도시의 개수 N (1 ≤ N ≤ 500), 버스 노선의 개수 M (1 ≤ M ≤ 6,000)이 주어진다. 둘째 줄부터 M개의 줄에는 버스 노선의 정보 A, B, C (1 ≤ A, B ≤ N, -10,000 ≤ C ≤ 10,000)가 주어진다. www.acmicpc.net Approach 도시 to 도시 의 최단경로비용을 구하는 문제인데, 음수 사이클이 존재할 수도 있는 문제이다. 음수사이클이 존재할 수 있으므로, 다익스트라 알고리즘은 사용이 불가능하다. 문제에서 의도한 바는 벨만-포드(Bellman-Ford) 알고리즘이므로 필자도 그 방법을 이용했다. 벨만-포드 알고리즘은 최단거리로 목..

    [java] 프로그래머스 (H-Index) Level 2
    Algorithm/Programmers

    [java] 프로그래머스 (H-Index) Level 2

    Problem : https://programmers.co.kr/learn/courses/30/lessons/42747 코딩테스트 연습 - H-Index H-Index는 과학자의 생산성과 영향력을 나타내는 지표입니다. 어느 과학자의 H-Index를 나타내는 값인 h를 구하려고 합니다. 위키백과1에 따르면, H-Index는 다음과 같이 구합니다. 어떤 과학자가 발표 programmers.co.kr Approach 이 문제에 있어서 주의할 점은 답이 citations에 없는 요소가 될 수 있다는 점이다. 예를 들어 citations = {6, 6, 6, 6} 이라면 답은 4가 된다. 필자는 citations 배열을 오름차순 정렬 한 후, 배열안에 i보다 크거나 같은 수가 i개 있는지를 검사하여, 가장 큰 i..

    [java] 프로그래머스 (큰 수 만들기) Level 2
    Algorithm/Programmers

    [java] 프로그래머스 (큰 수 만들기) Level 2

    Problem : https://programmers.co.kr/learn/courses/30/lessons/42883 코딩테스트 연습 - 큰 수 만들기 programmers.co.kr Approach (Wrong) 처음엔 주어진 문자열로 만들 수 있는 모든 수를 만들어 가장 큰 값을 저장해서 풀면 된다고 생각했다. 그러나 주어진 문자열의 길이가 최대 1,000,000자리 이하인 숫자이므로 당연하게 TLE, RTE를 받았다. Approach (Correct) 주어진 문자열에서 K개를 지워 가장 큰 수를 만들려면 앞자리 수가 클수록 좋다. 그렇다면 앞자리가 커질 수 있게, 앞의 수가 뒤의 수보다 작으면 삭제하면 된다. ​ -> 언제까지? K개까지만 (K개만 지울 수 있으니까) 작지 않다면 그 뒤에 붙인다...

    [java] 백준 9370 (미확인 도착지) Gold 2
    Algorithm/Baekjoon Online Judge

    [java] 백준 9370 (미확인 도착지) Gold 2

    Problem : https://www.acmicpc.net/problem/9370 9370번: 미확인 도착지 (취익)B100 요원, 요란한 옷차림을 한 서커스 예술가 한 쌍이 한 도시의 거리들을 이동하고 있다. 너의 임무는 그들이 어디로 가고 있는지 알아내는 것이다. 우리가 알아낸 것은 그들이 s지점에서 www.acmicpc.net Approach 다익스트라 알고리즘을 이용하여 푸는 문제이다. 처음 문제를 이해할 때 g나 h로부터 갈 수 있는 노드들을 구하는 문제라고 이해를 했었다. 문제에서 요구한 것을 간단히 쉽게 말하면, 시작점 s에서 임의의 노드 X로 최단거리로 가는 길에 무조건 g-h 혹은 h-g가 있는 노드들을 구하는 것이다. 예를 들어, s = 1, g = 3, h =4 라고 할 때, 1에서..

    [java] 백준 1504 (특정한 최단 경로) Gold 4
    Algorithm/Baekjoon Online Judge

    [java] 백준 1504 (특정한 최단 경로) Gold 4

    Problem : https://www.acmicpc.net/problem/1504 1504번: 특정한 최단 경로 첫째 줄에 정점의 개수 N과 간선의 개수 E가 주어진다. (2 ≤ N ≤ 800, 0 ≤ E ≤ 200,000) 둘째 줄부터 E개의 줄에 걸쳐서 세 개의 정수 a, b, c가 주어지는데, a번 정점에서 b번 정점까지 양방향 길이 존 www.acmicpc.net Approach 가중치가 음수가 아니므로 다익스트라 알고리즘을 이용하여 문제 풀이가 가능하다. 하지만 특정 루트를 반드시 지나가면서 최단거리를 구해야한다. A 부터 B까지 가는 최단경로를 구해야 할 때, V1-V2 경로를 무조건 지나야 한다면, A - V1 - V2 - B A - V2 - V1 - B 위의 두 경로가 존재한다. 따라서 ..

    [java] 프로그래머스 (소수 찾기) Level 2
    Algorithm/Programmers

    [java] 프로그래머스 (소수 찾기) Level 2

    Problem : https://programmers.co.kr/learn/courses/30/lessons/42839 코딩테스트 연습 - 소수 찾기 한자리 숫자가 적힌 종이 조각이 흩어져있습니다. 흩어진 종이 조각을 붙여 소수를 몇 개 만들 수 있는지 알아내려 합니다. 각 종이 조각에 적힌 숫자가 적힌 문자열 numbers가 주어졌을 때, 종이 programmers.co.kr Approach 이 문제는 머릿속으로는 풀이가 생각나지만 구현이 쉽지 않았다. 크게 두개의 단계가 필요하다. 1: 주어진 숫자로 만들 수 있는 모든 숫자를 만들어야 한다. 2: 만들어진 숫자가 소수인지를 판별해야 한다. 1번을 수행하려면 최대 nP1 + nP2 + ... + nPn-1 + nPn 번의 연산이 필요하다. 2번을 수행..

    [java] 프로그래머스 (더 맵게) Level 2
    Algorithm/Programmers

    [java] 프로그래머스 (더 맵게) Level 2

    Problem : https://programmers.co.kr/learn/courses/30/lessons/42626 코딩테스트 연습 - 더 맵게 매운 것을 좋아하는 Leo는 모든 음식의 스코빌 지수를 K 이상으로 만들고 싶습니다. 모든 음식의 스코빌 지수를 K 이상으로 만들기 위해 Leo는 스코빌 지수가 가장 낮은 두 개의 음식을 아래와 같 programmers.co.kr Approach '이렇게 풀어도 되나?' 싶었지만 어쨌든 모든 테케를 다 통과했다. 우선순위 큐를 사용하여 큐에 요소가 2개 미만이라면 -1을 리턴한다. 큐에 요소가 2개 이상이라면, 가장 작은 두개 요소를 빼내 섞은 후, 다시 큐에 집어넣었다. 큐의 모든요소가 K 이상일 때까지 혹은 큐의 요소개수가 2개 미만이 될 때까지 반복했다..

    [java] 백준 1753 (최단경로) Gold 5
    Algorithm/Baekjoon Online Judge

    [java] 백준 1753 (최단경로) Gold 5

    Problem : https://www.acmicpc.net/problem/1753 1753번: 최단경로 첫째 줄에 정점의 개수 V와 간선의 개수 E가 주어진다. (1≤V≤20,000, 1≤E≤300,000) 모든 정점에는 1부터 V까지 번호가 매겨져 있다고 가정한다. 둘째 줄에는 시작 정점의 번호 K(1≤K≤V)가 주어진다. www.acmicpc.net Approach 최단거리를 구하는 문제이다. 1. 단방향 그래프 2. 가중치는 항상 자연수 위의 조건으로 인해 다익스트라(O(Elog(V))를 이용하여 문제 풀이가 가능하다. 다익스트라 알고리즘은 현재 연결된 노드에서 이어진 모든 곳을 일단 방문하여 거리를 계산하여 저장한 후, 새로운 노드와 새로운 간선들이 추가되면, 도달할수 있는 ..

    [java] 백준 2206 (벽 부수고 이동하기) Gold 4
    Algorithm/Baekjoon Online Judge

    [java] 백준 2206 (벽 부수고 이동하기) Gold 4

    Problem : https://www.acmicpc.net/problem/2206 2206번: 벽 부수고 이동하기 N×M의 행렬로 표현되는 맵이 있다. 맵에서 0은 이동할 수 있는 곳을 나타내고, 1은 이동할 수 없는 벽이 있는 곳을 나타낸다. 당신은 (1, 1)에서 (N, M)의 위치까지 이동하려 하는데, 이때 최단 경로 www.acmicpc.net Approach 조건이 달려있는 경로 최소비용 문제이다. 필자는 BFS를 사용했다. 경우의 수를 따지기 전에, 현재 위치에서 벽을 부시고 왔는지에 대한 brokenWall[x][y] 배열이 필요하다. brokenWall[x][y] 의 값이 2이면, 해당 (x, y)를 아직 방문하지 않았다는 뜻이고, 1이라면, 해당 (x, y)를 방문했는데 방문하기전에 경..

    [java] 백준 7569 (토마토2) Silver 1
    Algorithm/Baekjoon Online Judge

    [java] 백준 7569 (토마토2) Silver 1

    Problem : https://www.acmicpc.net/problem/7569 7569번: 토마토 첫 줄에는 상자의 크기를 나타내는 두 정수 M,N과 쌓아올려지는 상자의 수를 나타내는 H가 주어진다. M은 상자의 가로 칸의 수, N은 상자의 세로 칸의 수를 나타낸다. 단, 2 ≤ M ≤ 100, 2 ≤ N ≤ 100, www.acmicpc.net Approach 백준 7576번 토마토 문제와 같은 문제이지만, 3차원 배열로 구성된 문제이다. 7576번 문제의 풀이는 밑의 링크에 있다. 2020/12/30 - [Algorithm/Baekjoon Online Judge] - [java] 백준 7576 (토마토1) Silver 1 [java] 백준 7576 (토마토1) Silver 1 Problem : ..

티스토리툴바