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

www.acmicpc.net/problem/1077510775번: 공항예제 1 : [2][?][?][1] 형태로 도킹시킬 수 있다. 3번째 비행기는 도킹시킬 수 없다. 예제 2 : [1][2][3][?] 형태로 도킹 시킬 수 있고, 4번째 비행기는 절대 도킹 시킬 수 없어서 이후 추가적인 도킹은 불www.acmicpc.net 백준 공항 문제를 풀어봤습니다. 백준 유형별문제에서 유니온파인드 문제를 골라푼거라 접근을 쉽게 할 수 있었습니다. 해결방법을 요약하면,1. Gi 비행기는 자신과 같거나 작은 게이트번호에만 도킹할 수 있다.2. 그러므로 최대한 많은 비행기를 도킹시키려면 자신이 현재 도킹될 번호 -1 로 union을 해주며 추가 도킹한다. (이때 도킹될 번호는 find를 사용하면 된다.) 도킹이 가능했..

그동안 시간관계상 알고리즘 풀이를 못하였는데 약 두달만에 풀어봤네요. 오랜만의 풀이라 안그래도 없던 알고리즘 실력도 다 떨어졌는데 주요 알고리즘과 스탠다드한 문제 풀이로 감도 되찾고 실력을 쌓으려고합니다.. ㅎㅎ 시간 여유도 생겼으니 열심히 해야겠습니다. 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/11779 11779번: 최소비용 구하기 2 첫째 줄에 도시의 개수 n(1≤n≤1,000)이 주어지고 둘째 줄에는 버스의 개수 m(1≤m≤100,000)이 주어진다. 그리고 셋째 줄부터 m+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 버스 www.acmicpc.net 백준 다익스트라 분류 문제에 있는 최소비용 구하기 2 입니다. 지나간 도시의 개수와 경로도 출력해야하는 특징이 있는 문제였습니다. 나머지는 원래 다익스트라 풀던대로 풀이했습니다. P.S 그리고 미리 말하면 예제에서는 출력이 1 3 5 가 나오는데 제 갈 수 있는 최단경로가 여러개가 생길 수 있기 떄문에 1 4 5 도 맞습니다. //역추적 Stack stack = new Stack..

www.acmicpc.net/problem/2887 2887번: 행성 터널 첫째 줄에 행성의 개수 N이 주어진다. (1 ≤ N ≤ 100,000) 다음 N개 줄에는 각 행성의 x, y, z좌표가 주어진다. 좌표는 -109보다 크거나 같고, 109보다 작거나 같은 정수이다. 한 위치에 행성이 두 개 이 www.acmicpc.net 백준 최소신장트리 문제인 행성 터널 문제를 풀어봤습니다. ㅎㅎ 처음에 평소대로 푼 후 제출을 하였는데 메모리 초과가 일어났습니다. //모든 행성 관계 연결(엣지 초기화) for (int i = 0; i < N - 1; i++) { Space space = spaces[i]; for (int j = i + 1; j < N; j++) { Space space2 = spaces[j];..

보호되어 있는 글입니다.

www.acmicpc.net/problem/4195 4195번: 친구 네트워크 첫째 줄에 테스트 케이스의 개수가 주어진다. 각 테스트 케이스의 첫째 줄에는 친구 관계의 수 F가 주어지며, 이 값은 100,000을 넘지 않는다. 다음 F개의 줄에는 친구 관계가 생긴 순서대로 주어진 www.acmicpc.net 백준 유니온 파인드 단계별 풀기의 마지막 문제 친구 네트워크 문제입니다. ㅎㅎ 이전에 풀어온 유니온 파인드 문제와 다르게 노드가 숫자가 아닌 문자열이 주어졌습니다. 이를 해결하기 위해 HashMap을 사용하여 이름(문자열)을 노드번호(Int)로 변환함으로써 기존의 숫자 노드를 활용한 문제처럼 바꿔줍니다. 또한 친구의 수를 구해야하므로 추가적으로 count 배열도 사용해주도록 합니다. 이 부분 빼고는 ..

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/step/15 최소 신장 트리 단계 신장 트리가 중요한 이유는, 가장 적은 개수의 간선으로 모든 정점을 연결할 수 있기 때문입니다. 이 문제를 통해 확인해 봅시다. www.acmicpc.net 백준 최소신장트리 단계별풀기의 4번째 문제입니다. ㅎㅎ 이전 단계문제들과 거의 비슷합니다. N개의 나의 위치와 우주신들의 좌표가 주어집니다. 그다음 M개의 이어진 좌표들이 주어 집니다. 이 이후에 최소비용으로 모두 연결해서 가장 낮은 비용으로 나와 우주신들이 모두 건너건너 최소신장트리로 연결되게 하면 끝입니다. 기존의 크루스칼 알고리즘을 사용하면 풀립니다. 추가로 Math.round() 를 사용하면 4.00일 경우 0이 잘려서 4.0으로 출력이 되서 이럴때는 String.foramt()..

www.acmicpc.net/problem/4386 4386번: 별자리 만들기 도현이는 우주의 신이다. 이제 도현이는 아무렇게나 널브러져 있는 n개의 별들을 이어서 별자리를 하나 만들 것이다. 별자리의 조건은 다음과 같다. 별자리를 이루는 선은 서로 다른 두 별을 일 www.acmicpc.net 백준 최소신장트리 단계별 풀기 3번째 문제입니다. 이전 단계 문제와 마찬가지로 크루스칼 알고리즘과 유니온-파인드를 사용합니다. 입력값하고 가중치 넣는 방식만 변형된 문제였습니다. [Java] import java.util.ArrayList; import java.util.Collections; import java.util.Scanner; class Main { private static int[] parent;..

www.acmicpc.net/problem/1197 1197번: 최소 스패닝 트리 첫째 줄에 정점의 개수 V(1 ≤ V ≤ 10,000)와 간선의 개수 E(1 ≤ E ≤ 100,000)가 주어진다. 다음 E개의 줄에는 각 간선에 대한 정보를 나타내는 세 정수 A, B, C가 주어진다. 이는 A번 정점과 B번 정점이 www.acmicpc.net 백준 최소신장트리 단계별풀기의 두번째 문제입니다. ㅎㅎ 최소신장트리는 크르수칼 알고리즘을 사용하는 문제입니다. 노드개수를 V, 변의 개수를 E라고 하면 O(ElogV)의 시간복잡도를 가집니다. 저는 풀기전 영상을 통해 개념을 먼저 복습하고 봤습니다. www.youtube.com/watch?v=LQ3JHknGy8c 풀이방법은 다음과 같습니다. 1. 노드의 연결요소들을..

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

www.acmicpc.net/problem/11726 11726번: 2×n 타일링 2×n 크기의 직사각형을 1×2, 2×1 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오. 아래 그림은 2×5 크기의 직사각형을 채운 한 가지 방법의 예이다. www.acmicpc.net 백준 11726 2xn 타일링 문제입니다. dp 문제인데 그려보니까 간단한 점화식이였습니다. ㅎㅎ dp[n] = dp[n-1] + dp[n-2] 그려보면 바로 풀리는 문제였습니다. n=1 일 때 처리만 조심..! 여기서 인덱스아웃에러 떴었습니다. 풀이는 다음과 같습니다 [Java] import java.util.Scanner; class Main { public static void main(String[] args) { Scann..

www.acmicpc.net/problem/16236 16236번: 아기 상어 N×N 크기의 공간에 물고기 M마리와 아기 상어 1마리가 있다. 공간은 1×1 크기의 정사각형 칸으로 나누어져 있다. 한 칸에는 물고기가 최대 1마리 존재한다. 아기 상어와 물고기는 모두 크기를 가 www.acmicpc.net 귀요미 아기상어 문제입니다. 옛날에 나중에 풀어야지 했다가 이번에 solved 클래스에 있길래 풀어봤습니다. 처음에 잘 푼줄 알고 테케돌려보는데 4,5,6 만 틀려서 디버깅 하나하나 다 돌려보며 확인했는데도 맞아서 삽질을 좀 했는데 원인은 모든 물고기 상대로 지나갈 수 있는 건지 알았는데 자신보다 작거나 같은 크기의 물고기만 지나갈 수 있던 거였습니다. 문제를 잘못읽는 습관이 많은데 조심해야겠습니다. ㅠ..