막내의 막무가내 프로그래밍 & 일상

www.acmicpc.net/problem/10971 10971번: 외판원 순회 2 첫째 줄에 도시의 수 N이 주어진다. (2 ≤ N ≤ 10) 다음 N개의 줄에는 비용 행렬이 주어진다. 각 행렬의 성분은 1,000,000 이하의 양의 정수이며, 갈 수 없는 경우는 0이 주어진다. W[i][j]는 도시 i에서 j www.acmicpc.net 백준 백트래킹 유형에서 외판원 순회2 라는 문제를 풀어봤습니다. ㅎㅎ N개의 도시를 특정 시작 도시에서 출발하여 다시 첫 도시로 순회하는 최단 경로를 구하는 문제입니다. 방문한 도시는 다시 못가고요. 백트래킹을 사용하면 되고 매개변수로 깊이, 시작도시, 이전방문도시, 총 경로비용, 방문 여부를 사용해주면 됩니다. 풀이는 다음과 같습니다. [Java] import ja..

programmers.co.kr/learn/courses/30/lessons/1844?language=java 코딩테스트 연습 - 게임 맵 최단거리 [[1,0,1,1,1],[1,0,1,0,1],[1,0,1,1,1],[1,1,1,0,1],[0,0,0,0,1]] 11 [[1,0,1,1,1],[1,0,1,0,1],[1,0,1,1,1],[1,1,1,0,0],[0,0,0,0,1]] -1 programmers.co.kr 오랜만에 프로그래머스 문제를 풀어봤습니다. ㅎㅎ 단순한 BFS 문제입니다. 그러므로 풀이생략 !! [Java] import java.util.LinkedList; import java.util.Queue; class Solution { private static boolean[][] isVisite..

www.acmicpc.net/problem/2665 2665번: 미로만들기 첫 줄에는 한 줄에 들어가는 방의 수 n(1≤n≤50)이 주어지고, 다음 n개의 줄의 각 줄마다 0과 1이 이루어진 길이가 n인 수열이 주어진다. 0은 검은 방, 1은 흰 방을 나타낸다. www.acmicpc.net 백준 다익스트라 유형에서 한 문제를 골라 풀어봤는데 BFS에 가까운 문제였습니다. ㅎㅎ 문제에 대해 간략히 설명하면, 검은색방은 지나갈 수 없고 흰색방은 지나갈 수 있는데, (0,0)에서 (N,N) 까지 가는데 최소한의 검은색-> 흰색 방으로 변경해야 하는 개수를 구하는 문제였습니다. 해당 지점까지 오는데 색을 바꾼 값을 담는 배열인 distances - distances는 가장 큰 값(INF)로 초기화를 해줍니다. ..

www.acmicpc.net/problem/2589 2589번: 보물섬 보물섬 지도를 발견한 후크 선장은 보물을 찾아나섰다. 보물섬 지도는 아래 그림과 같이 직사각형 모양이며 여러 칸으로 나뉘어져 있다. 각 칸은 육지(L)나 바다(W)로 표시되어 있다. 이 지도에서 www.acmicpc.net 백준 2589 보물섬 문제를 풀어봤습니다. ㅎㅎ 백준 브루트포스 유형에서 한 문제를 골라풀었는데 BFS 기본 문제였습니다. 땅끼리 거리가 가장 큰 곳이 보물이 숨어있는 땅이므로 땅인 곳을 모두 BFS 탐색돌려서 가장 먼 경로를 출력하면됩니다. 코틀린의 coerceAtLeast() 라는 함수를 알 수 있던 문제였습니다. 자바에서는 최대값 = Math.Max( 최댓값, 숫자2 ) 이렇게 최댓값을 갱신하지만 코틀린에서는..

www.acmicpc.net/problem/15663 15663번: N과 M (9) 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해 www.acmicpc.net 백트랙킹 시리즈문제 중 하나인 백준 15663 N과 M (9)를 풀었습니다. 오름차순으로 숫자들을 나열하되 중복된 숫자는 두 번 출력하면 안되었습니다. 그래서 오름차순으로 정렬하고 set을 이용해 중복된 숫자는 안나오게 백트랙킹을 구현했습니다. 풀이는 다음과 같습니다. [Java] import java.util.Arrays; import java.util.HashSet; import java.util.Scan..

보호되어 있는 글입니다.

www.acmicpc.net/problem/1182 1182번: 부분수열의 합 첫째 줄에 정수의 개수를 나타내는 N과 정수 S가 주어진다. (1 ≤ N ≤ 20, |S| ≤ 1,000,000) 둘째 줄에 N개의 정수가 빈 칸을 사이에 두고 주어진다. 주어지는 정수의 절댓값은 100,000을 넘지 않는다. www.acmicpc.net 백준 알고리즘 분류에서 백트랙킹 한 문제를 풀어봤습니다. ㅎㅎ 수열이 있는데 해당 수열들의 조합의 합이 S가 되는 경우의 수를 찾는 문제입니다. 보통의 백트랙킹 문제와 다르게 DFS()에서 for문이 필요하진 않았습니다. 풀이는 주석을 달아놨습니다. [JAVA] import java.util.Scanner; class Main { static int[] num; private..

www.acmicpc.net/problem/2146 2146번: 다리 만들기 여러 섬으로 이루어진 나라가 있다. 이 나라의 대통령은 섬을 잇는 다리를 만들겠다는 공약으로 인기몰이를 해 당선될 수 있었다. 하지만 막상 대통령에 취임하자, 다리를 놓는다는 것이 아깝다 www.acmicpc.net 백준 BFS 유형의 백준 2146 다리만들기 문제입니다. 여러개의 섬이(1) 있는데 바다에(0) 최소의 다리 개수를 설치하여 여러개의 섬들 중 두 개의 섬을 이을 수 있게 하려는 문제 입니다. BFS를 살짝 응용한 문제입니다. 처음에 너무 비효율적으로 자원을 소비하는건가 했는데 통과되었습니다. 풀이를 간략히 설명하면, 1. 섬마다 번호가 똑같으므로 바로 BFS로 다른 섬을 찾아 연결하기가 힘듭니다. 그러므로 섬에 각..

www.acmicpc.net/problem/2468 2468번: 안전 영역 재난방재청에서는 많은 비가 내리는 장마철에 대비해서 다음과 같은 일을 계획하고 있다. 먼저 어떤 지역의 높이 정보를 파악한다. 그 다음에 그 지역에 많은 비가 내렸을 때 물에 잠기지 않는 www.acmicpc.net 백준 그래프 유형분류에서 푼 안전영역이라는 문제입니다. ㅎㅎ 지역마다 높이가 다른데 해당 높이보다 같거나 큰 비가 오면 지역이 물에 잠기게 됩니다. 모든 비오는 경우의 수에서 물에 안잠긴 지역들의 구역이 최대일때 몇 구역인지 구하는 기본적인 BFS 유형의 문제였습니다. 비에와서 잠긴 부분을 벽(isUnderWatered)라고 생각하고 풀면 됩니다. 풀이는 주석으로 충분하며 다음과 같습니다. [Java] import j..

그동안 시간관계상 알고리즘 풀이를 못하였는데 약 두달만에 풀어봤네요. 오랜만의 풀이라 안그래도 없던 알고리즘 실력도 다 떨어졌는데 주요 알고리즘과 스탠다드한 문제 풀이로 감도 되찾고 실력을 쌓으려고합니다.. ㅎㅎ 시간 여유도 생겼으니 열심히 해야겠습니다. youngest-programming.tistory.com/382 [알고리즘] 스터디 계획표 현재 하고있는것들이 있어 좀 밀렸지만 최대한 계획 맞춰서 공부 youngest-programming.tistory.com 예전 공부 계획표 참고하면서 분류당 한문제씩 풀어볼까 생각중입니다. www.acmicpc.net/problem/2023 2023번: 신기한 소수 수빈이가 세상에서 가장 좋아하는 것은 소수이고, 취미는 소수를 가지고 노는 것이다. 요즘 수빈이가..

programmers.co.kr/learn/courses/30/lessons/49189 코딩테스트 연습 - 가장 먼 노드 6 [[3, 6], [4, 3], [3, 2], [1, 3], [1, 2], [2, 4], [5, 2]] 3 programmers.co.kr 최근 백준만 풀다가 오랜만에 프로그래머스 문제를 풀어본 것 같습니다. 예전에는 프로그래머스에 적응이 되어 백준의 입력값을 직접 받아야한다는점이 거부감이 있었는데 이제 프로그래머스가 뭔가 어색하네요. ㅎㅎ 프로그래머스 고득점 kit 그래프 종류에 있던 Level 3 문제입니다. 최단경로 문제인가 했는데 최단 경로가 아닌 최장 경로의 개수가 몇개인지 묻는 문제이고 간선의 가중치는 1로 모두 동일하다는 특징을 갖고 있습니다. 저는 평소 최단경로 문제푸..

보호되어 있는 글입니다.

www.acmicpc.net/problem/13549 13549번: 숨바꼭질 3 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 www.acmicpc.net BFS문제로 이전에 푼 숨바꼭질 문제와 비슷하나 순간이동시 0초가 걸리게 바꼈습니다. youngest-programming.tistory.com/379 [알고리즘] 백준 1697 숨바꼭질 -bfs, dfs- 자바 코틀린 www.acmicpc.net/problem/1697 1697번: 숨바꼭질 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,00..

www.acmicpc.net/problem/2644 2644번: 촌수계산 사람들은 1, 2, 3, …, n (1≤n≤100)의 연속된 번호로 각각 표시된다. 입력 파일의 첫째 줄에는 전체 사람의 수 n이 주어지고, 둘째 줄에는 촌수를 계산해야 하는 서로 다른 두 사람의 번호가 주어진 www.acmicpc.net 간단한 BFS를 사용하는 문제였습니다. 풀이는 다음과 같습니다. 1. 찾아햘 관계 num1, num2 가 있다. 2. num1을 시작으로 BFS 탐색을 하여 가족 관계를 찾기 시작한다. 3. 가족관계인 번호를 찾으면 촌수를 1 증가시키고 계속해서 2번을 반복한다. 4. 2~3을 num2를 찾을때까지 반복한다. [Java] import java.util.LinkedList; import java.u..

www.acmicpc.net/problem/17144 17144번: 미세먼지 안녕! 미세먼지를 제거하기 위해 구사과는 공기청정기를 설치하려고 한다. 공기청정기의 성능을 테스트하기 위해 구사과는 집을 크기가 R×C인 격자판으로 나타냈고, 1×1 크기의 칸으로 나눴다. 구사 www.acmicpc.net 백준 17144 미세먼지 안녕! 문제를 풀어봤습니다. ㅎㅎ 처음에 다음과 같이 큰 그림만 정해놓고 풀이했습니다. 1. 미세먼지 퍼트림(0으로된 새로운 맵에 더해서 저장) 2. 새로운맵을 공기청정기 규칙대로 밀어줌( 새 맵에 저장) 풀이를 좀 더 자세히 적으면 1. 미세먼지를 퍼트릴 수 있는 것은(5이상의 크기가짐) bfs()로 퍼트립니다. 퍼진 미세먼지와 퍼진 후의 원래 위치의 미세먼지를 계산 후 newMap..