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

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

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/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 만 틀려서 디버깅 하나하나 다 돌려보며 확인했는데도 맞아서 삽질을 좀 했는데 원인은 모든 물고기 상대로 지나갈 수 있는 건지 알았는데 자신보다 작거나 같은 크기의 물고기만 지나갈 수 있던 거였습니다. 문제를 잘못읽는 습관이 많은데 조심해야겠습니다. ㅠ..

www.acmicpc.net/problem/9375 9375번: 패션왕 신해빈 첫 번째 테스트 케이스는 headgear에 해당하는 의상이 hat, turban이며 eyewear에 해당하는 의상이 sunglasses이므로 (hat), (turban), (sunglasses), (hat,sunglasses), (turban,sunglasses)로 총 5가지 이다. www.acmicpc.net 해시맵을 사용하면 간단하게 풀리는 문제입니다. 단 다음 공식을 알아야합니다. 옷 종류별로 (옷 개수+1) * (옷 개수 + 1 ) * ... * (옷 개수 + 1 ) -1 이 총 알몸이 아닌 상태로 의상을 입을 수 있는 경우의 수 입니다. 풀이는 다음과 같습니다. [Java] import java.util.HashMap..

www.acmicpc.net/problem/9465 9465번: 스티커 첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스의 첫째 줄에는 n (1 ≤ n ≤ 100,000)이 주어진다. 다음 두 줄에는 n개의 정수가 주어지며, 각 정수는 그 위치에 해당하는 스티커의 www.acmicpc.net 처음 완전탐색으로 접근했다가 삽질만 했습니다. 제출 시 60초가 걸리는 테스트케이스와 100,000개의 n 때문에 완전탐색으로 푼다고 해도 시간초과가 날 것 같당.. 이후 서칭 후 DP 문제인 것을 알고 dp로 풀었습니다. 다음 그림으로 점화식을 세우면 됩니다. [Java] import java.util.Scanner; class Main { public static void main(String[]..

www.acmicpc.net/problem/1504 1504번: 특정한 최단 경로 첫째 줄에 정점의 개수 N과 간선의 개수 E가 주어진다. (2 ≤ N ≤ 800, 0 ≤ E ≤ 200,000) 둘째 줄부터 E개의 줄에 걸쳐서 세 개의 정수 a, b, c가 주어지는데, a번 정점에서 b번 정점까지 양방향 길이 존 www.acmicpc.net 백준 최단경로 단계별풀기 두 번째 문제를 풀어봤습니다. 시작점에서 도착점까지의 최단 경로를 구해야하는데 반드시 거쳐야 할 정점 두 개를 조건으로 추가되었습니다. 반드시 지나야하는 정점이 v1, v2 인데 start -> v1 -> v2 -> end start -> v2 -> v1 -> end 두 가지 로직이 가능합니다. 이를 적용한 풀이입니다. [Java] impor..

[2021-05-16 업데이트] 오랜만에 안드로이드 관련 포스팅입니다. 복습도 할겸 이전에 했던 프로젝트를 보던 중 전화번호 인증 구현에 대해 포스팅을 해보려고합니다. 안드로이드와 코틀린을 요즘 못하고있네요 ㅠㅠ 공식문서를 참고했습니다. firebase.google.com/docs/auth/android/phone-auth?hl=ko Android에서 전화번호로 Firebase에 인증 Firebase 인증을 사용하면 사용자의 전화로 SMS 메시지를 전송하여 로그인하는 것이 가능합니다. 사용자는 SMS 메시지에 포함된 일회용 코드를 사용하여 로그인합니다. 앱에 전화번호 로그인을 추 firebase.google.com 추가로 제가 여기서 구현한 전화번호인증을 구현하려면 이미 파이어베이스 인증이 된 상태여야 ..

www.acmicpc.net/problem/15655 15655번: N과 M (6) N개의 자연수와 자연수 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오. N개의 자연수는 모두 다른 수이다. N개의 자연수 중에서 M개를 고른 수열 www.acmicpc.net 주석에 풀이를 적어놓았습니다. [Java] import java.util.Arrays; import java.util.Scanner; class Main { static int[] nums; static int[] arr; static boolean[] isVisited; static int N; static int M; static StringBuilder sb = new StringBuilder()..

www.acmicpc.net/problem/1874 1874번: 스택 수열 1부터 n까지에 수에 대해 차례로 [push, push, push, push, pop, pop, push, push, pop, push, push, pop, pop, pop, pop, pop] 연산을 수행하면 수열 [4, 3, 6, 8, 7, 5, 2, 1]을 얻을 수 있다. www.acmicpc.net 단계별 풀기 스택 마지막 문제입니다. 스택에 push하는 순서는 반드시 오름차순을 지키도록 한다고 하자에 유의해야합니다. 풀이는 다음과 같습니다. [Java] import java.util.Scanner; import java.util.Stack; public class Main { private static Stack stack..