[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 위의 두 경로가 존재한다. 따라서 ..

→2021.01.01

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번을 수행..

→2020.12.31

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개 미만이 될 때까지 반복했다..

→2020.12.31

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))를 이용하여 문제 풀이가 가능하다. 다익스트라 알고리즘은 현재 연결된 노드에서 이어진 모든 곳을 일단 방문하여 거리를 계산하여 저장한 후, 새로운 노드와 새로운 간선들이 추가되면, 도달할수 있는 ..

→2020.12.31

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)를 방문했는데 방문하기전에 경..

→2020.12.30

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

→2020.12.30

Algorithm/Baekjoon Online Judge

[java] 백준 7576 (토마토1) Silver 1

Problem : https://www.acmicpc.net/problem/7576 7576번: 토마토 첫 줄에는 상자의 크기를 나타내는 두 정수 M,N이 주어진다. M은 상자의 가로 칸의 수, N은 상자의 세로 칸의 수를 나타낸다. 단, 2 ≤ M,N ≤ 1,000 이다. 둘째 줄부터는 하나의 상자에 저장된 토마토 www.acmicpc.net Approach 시작점이 여러개인 최단경로 문제이다. 문제에서 배열의 요소가 1인 모든 곳이 시작점이다. (따라서 요소가 1인 모든 좌표를 큐에 넣고 BFS를 수행한다.) 벽이 -1 로 막혀있지 않고, 범위를 벗어나지 않으며, 방문하지 않았다면, 방문하면서 직전 위치의 값 + 1을 방문하는 곳에 저장한다. BFS가 완전히 모두 수행된 후, 최단경로 배열을 검사하여..

→2020.12.30

Algorithm/Programmers

[java] 프로그래머스 (가장 큰 수) Level 2

Problem : https://programmers.co.kr/learn/courses/30/lessons/42746 코딩테스트 연습 - 가장 큰 수 0 또는 양의 정수가 주어졌을 때, 정수를 이어 붙여 만들 수 있는 가장 큰 수를 알아내 주세요. 예를 들어, 주어진 정수가 [6, 10, 2]라면 [6102, 6210, 1062, 1026, 2610, 2106]를 만들 수 있고, 이중 가장 큰 programmers.co.kr Approach 처음엔 사전정렬을 생각했었다. 그런데 사전검색으로는 반례가 생긴다. 사전 순 정렬이면 공통된 부분이 같으면 짧은 것이 먼저다. 예를들어, 333과 33같은 경우 33이 333보다 우선이다. 그러나 문제의 요구대로라면 33, 332는 33+332가 되어야하고, 33,..

→2020.12.29

Algorithm/Programmers

[java] 프로그래머스 (괄호 변환) Level 2

Problem : https://programmers.co.kr/learn/courses/30/lessons/60058 코딩테스트 연습 - 괄호 변환 카카오에 신입 개발자로 입사한 콘은 선배 개발자로부터 개발역량 강화를 위해 다른 개발자가 작성한 소스 코드를 분석하여 문제점을 발견하고 수정하라는 업무 과제를 받았습니다. 소스를 컴 programmers.co.kr Approach 2020 KAKAO BLIND RECRUITMENT 문제이다. 딱히 접근법이 없다. 문제에 나와있는 조건들을 순서대로 구현하면 된다. 주의할 점은 4-4 의 괄호방향을 뒤집는다 이다. 단지 괄호방향만 뒤집을 뿐 문자열의 역순을 취하면 안된다. 1. 입력이 빈 문자열인 경우, 빈 문자열을 반환합니다. 2. 문자열..

→2020.12.29

Algorithm/Baekjoon Online Judge

[java] 백준 2178 (미로 탐색) Silver 1

Problem : https://www.acmicpc.net/problem/2178 2178번: 미로 탐색 첫째 줄에 두 정수 N, M(2 ≤ N, M ≤ 100)이 주어진다. 다음 N개의 줄에는 M개의 정수로 미로가 주어진다. 각각의 수들은 붙어서 입력으로 주어진다. www.acmicpc.net Approach (1, 1)에서 (n, n)까지의 최소 이동거리를 구하는 문제이다. BFS를 사용하여, 범위를 벗어나지 않고, 요소가 1이며, 방문하지 않았다면, 큐에 집어넣는 식으로 진행하였다. 방문할 곳에 직전 곳에 있는 값+1 을 저장해주면 (n, n)에 최소 비용이 저장될 것이다. BFS를 구현만 할줄 안다면, 쉬운 문제가 될 것이다. Code import java.io.*; import java.uti..

→2020.12.29

티스토리툴바