Java - 알고리즘52

• 

  백준 - 1057 토너먼트 https://www.acmicpc.net/problem/1057 1057번: 토너먼트 김지민은 N명이 참가하는 스타 토너먼트에 진출했다. 토너먼트는 다음과 같이 진행된다. 일단 N명의 참가자는 번호가 1번부터 N번까지 배정받는다. 그러고 난 후에 서로 인접한 번호끼리 스타를 www.acmicpc.net 풀이 방법 오랜만에 돌아온 백준 문제 풀이!! 최근에는 알고리즘 잡스 문제를 풀기 때문에 백준 알고리즘 문제 풀이 글이 줄어들었다ㅠㅠ 여튼 이번 문제의 핵심 포인트는 a 와 b 가 같은 라운드에 언제 만나는지 확인하는 것 이다. 따라서 '같은 라운드' 를 확인하는 방법을 알아야한다. 같은 라운드에 있다는 걸 확인하는 방법은 아주 간단하다. (a+1)/2 의 값과 (b+1)/2 의 값이 같은지 여부를 확인.. Java - 알고리즘 2022. 9. 27.

• LIS - 최장 증가 부분 수열 알아보기 최장 증가 부분 수열(LIS, Longest Increasing Subsequence)란? 원소가 n개인 배열의 일부 원소를 골라내서 만든 부분 수열 중, 각 원소가 이전 원소보다 크다는 조건을 만족하고, 그 길이가 최대인 부분 수열을 최장 증가 부분 수열이라고 한다 예를 들어, { 6, 2, 5, 1, 7, 4, 8, 3} 이라는 배열이 있을 경우, LIS는 { 2, 5, 7, 8 } 이다. 이는{ 2, 5 }, { 2, 7 } 등 증가하는 부분 수열은 많지만 그 중에서 가장 긴 것이 { 2, 5, 7, 8 } 때문!! 문제 N개의 자연수로 이루어진 수열이 주어졌을 때, 그 중에서 가장 길게 증가하는(작은 수에서 큰 수로) 원소들의 집합을 찾는 프로그램을 작성하라. 예를 들어, 원소가 2, 7, 5, .. Java - 알고리즘 2022. 9. 24.

• 

  백준 - 1110 더하기 사이클 https://www.acmicpc.net/problem/1110 1110번: 더하기 사이클 0보다 크거나 같고, 99보다 작거나 같은 정수가 주어질 때 다음과 같은 연산을 할 수 있다. 먼저 주어진 수가 10보다 작다면 앞에 0을 붙여 두 자리 수로 만들고, 각 자리의 숫자를 더한다. 그 다음, www.acmicpc.net 풀이 방법 분명히 백준 쉬운 문제 라고 검색해서 찾아서 풀었는데...생각보다 오래걸렸던 문제였다. 그렇다고 어려운 문제는 아니고 다소 생각을 해야했던 문제 이 문제의 핵심 포인트는 아래와 같다. 1. 입력받는 n 이 10 보다 작다면 '뒤' 가 아닌 '앞' 에 0 을 붙여서 2자리로 만드는 것!! => 이 조건 때문에 크기가 2인 배열을 만들어서 문제를 풀었다. 2. 계산해서 만들어.. Java - 알고리즘 2022. 9. 14.

• 

  백준 - 1389 케빈 베이컨의 6단계 법칙 https://www.acmicpc.net/problem/1389 1389번: 케빈 베이컨의 6단계 법칙 첫째 줄에 유저의 수 N (2 ≤ N ≤ 100)과 친구 관계의 수 M (1 ≤ M ≤ 5,000)이 주어진다. 둘째 줄부터 M개의 줄에는 친구 관계가 주어진다. 친구 관계는 A와 B로 이루어져 있으며, A와 B가 친구라는 뜻 www.acmicpc.net 케빈 베이커의 6단계 법칙!! 대충 모든 사람은 6다리 정도 거치면 서로가 서로를 아는 사람으로 이어질 수 있다는 법칙인데 아무래도 나같은 아싸를 계산에 넣지 않고 만든 법칙인듯하다ㅋㅋ 여튼 이 문제는 플로이드 와샬을 사용해서 풀면 된다. 어제 풀었던 플로이드 문제보다 훨씬 쉬운 문제이다. BFS 로도 풀이가 가능하다고 들었으나, 나는 플로이드 와샬.. Java - 알고리즘 2022. 9. 13.

• 

  백준 - 11404 플로이드(feat.플로이드 와샬 알고리즘) https://www.acmicpc.net/problem/11404 11404번: 플로이드 첫째 줄에 도시의 개수 n이 주어지고 둘째 줄에는 버스의 개수 m이 주어진다. 그리고 셋째 줄부터 m+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 버스의 출발 도시의 번호가 www.acmicpc.net 플로이드 와샬 알고리즘 - Floyd Warshall 플로이드 와샬 알고리즘은 모든 정점에서 모든 정점까지 최단 경로를 구하는 것이다. 이때 임의의 노드 S 에서 E 까지 가는데 걸리는 최단 거리를 구하기 위해 S 와 E 사이의 노드인 M 에 대해서 S에서 M 까지 걸리는 최단 거리와 M 에서 E 까지 걸리는 최단 거리를 이용한다. 아래 사진으로 이야기하자면 1에서 2, 3, 4, 5 까지의 최단.. Java - 알고리즘 2022. 9. 12.

• 

  백준 - 10282 해킹 풀이 방법 다익스트라 알고리즘을 공부하기 위해서 찾았던 문제!! 골드임에도 크게 어려운 편은 아니다. 예전에 풀었던 네트워크 문제와 뭔가 비슷하다는 느낌을 많이 받았다. 풀이 포인트는 아래와 같다!! 이 문제의 핵심 포인트는 감염까지 걸리는 최소 시간을 계산하는 것!! 백준 네트워크 문제와 비슷하지만 DFS 나 BFS 로 풀면 시간초과가 나거나 메모리 초과가 발생한다. 이에 다익스트라 알고리즘으로 문제를 풀어야했다. 최소 시간이라는 말은 딱히 없지만...최소 시간이 걸리도록 계산해야함으로 다익스트라 알고리즘을 사용한다. 그나마 주의할 점은 a 가 b 를 의존한다는 점과 전체 입력 받을 때 살짝 복잡하다는 정도? 뭔가 쉬운듯 어려운 다익스트라ㅠㅠ 나머지는 주석 참고!! package baekJoon; im.. Java - 알고리즘 2022. 9. 11.

• 

  백준 - 2579 계단오르기 풀이 방법 실버3 문제이기도 하고, DP 알고리즘 관련해서 공부해보고 싶어서 풀었다가...생각보다 어려워서 고민을 많이했던 문제이다. 물론 엄청 어려웠던 것은 아니고, 뭐랄까...다른 알고리즘 문제보다 수학적인 접근이 필요한? 문제라고 느껴졌다. 마치 그리디 문제나 수학 관련된 문제를 푸는 것처럼 점화식을 찾는 부분도 특히 그랬다. 여튼 이 문제는 아래와 같은 방법으로 접근하면 된다!! // 이 문제의 포인트는 문제를 쪼개서 쉽게 생각하는 것!! // 정확히는 문제중에서 조건을 쪼개고 연결시켜서 다 쉽게 생각하는것이 중요하다. // 조건 1. 현재 계단 i+1 이거나 i+2 가 가능하다. // 조건 2. 단 계단을 i+1, i+2, i+3 순서대로 오를 수 없다. 최대 i+1, i+2 만 가능하다 => .. Java - 알고리즘 2022. 9. 11.

• 

  백준 - 1026 보물 https://www.acmicpc.net/problem/1026 1026번: 보물 첫째 줄에 N이 주어진다. 둘째 줄에는 A에 있는 N개의 수가 순서대로 주어지고, 셋째 줄에는 B에 있는 수가 순서대로 주어진다. N은 50보다 작거나 같은 자연수이고, A와 B의 각 원소는 100보다 작거 www.acmicpc.net 풀이 방법 요번에는 쉬운 문제!! 입력받는 배열 A와 B 에서 각각 i 번째 인덱스끼리 곱한 후 더해서 최소값을 만드는 문제이다 최소값을 어떻게 만들지만 생각하면 굉장히 간단해지는 문제이다. 입력받는 두 배열의 i번째 값들을 곱해서 최소값을 만드려면 A 배열의 최대값과 B 배열의 최소값을 곱하면 될 것이다(혹은 그 반대). 때문에 A 배열을 오름차순으로 정렬하고, B 배열을 내림차순으로 정.. Java - 알고리즘 2022. 9. 6.

• 

  백준 - 2981 검문 https://www.acmicpc.net/problem/2981 2981번: 검문 트럭을 타고 이동하던 상근이는 경찰의 검문을 받게 되었다. 경찰은 상근이가 운반하던 화물을 하나하나 모두 확인할 것이기 때문에, 검문하는데 엄청나게 오랜 시간이 걸린다. 상근이는 시간 www.acmicpc.net 풀이 방법 어떤 문제에 이은 무식하면 용감하다 시리즈 2번째 최근에 유클리드 호제법을 공부하고 관련된 문제를 풀어서 이번에도 쉬울 줄 알고 도전했는데...세상에 이렇게 어려운 문제일 줄은 몰랐다. 물론 풀고 나니까 내가 몰랐었던 혹은 까먹었던 부분들 - 정수론, 나머지 정리 - 을 잘 버무리고 활용하면 쉽게 풀릴만도 했지만 나는 문과였고ㅠㅠ 유클리드 호제법도 정수론도 이제야 보게 되었다ㅠㅠ 여튼 그래도 저런거 다.. Java - 알고리즘 2022. 9. 5.

• 

  백준 - 4485 녹색 옷 입은 애가 젤다지? 풀이 방법 오랜만에 도전한 골드 문제!! 처음에 생각없이 BFS 로 코드를 짰는데 메모리 초과가 발생해서 방향을 다시 잡고 코드를 치기 시작했다. 이 문제의 핵심 포인트는 녹색옷을 입을 애가 젤다라는 점!! 이 아니고ㅋㅋㅋㅋ 2차원 배열로 입력받는다고 하더라도 결국 n-1, n-1 좌표에 도착하는 최소값을 구하는 문제라는 점이다. BFS 나 DFS 로 푸는것이 아니라 다익스트라 알고리즘을 사용해야한다. 다만 우리는 그래프 형식이 아니고 배열로 입력받기 때문에 어떻게 좌표(노드)에서 좌표(노드) 로 넘어갈 수 있는지 고민해야한다. 나는 이 부분을 DFS, BFS 에서 사용하던 dx, dy 배열을 사용해서 풀이를 하였다. 즉, dx, dy 를 통해 계산된 nx, ny 좌표가 배열의 범위 안에 존재하면 이전 .. Java - 알고리즘 2022. 9. 2.

• 

  백준 1193 : 분수찾기 풀이 방법 백준 브론즈의 탈을 쓴 실버 문제...매번 느끼는 것이지만 백준에서 '수학' 이 붙은 애들은 모두 실버 이상의 난이도라고 생각이된다ㅠㅠ 특히나 규칙을 못 찾으면 차라리 BFS, DFS 문제 푸는게 더 쉽다고 느껴질 정도이다. 이 문제가 특히 그랬는데 뭔가 보일듯 말듯 하면서 시간이 정말 오래걸려서 풀었다. 사실 수학 관련 문제가 그렇듯, 이 문제도 점화식을 세우면 혹은 그에 준하는 규칙을 찾으면 해결의 실마리가 보이는 편이다. 짝수 층과 홀수 층에 관한 규칙, n번째 층에 총 몇개의 분수가 오는지 규칙을 찾아서 점화식을 세워야 한다. 나는 문제의 지그재그 순 이라는 것을 하나의 층으로 생각하였다. 즉 1층에는 1/1, 2층에는 1/2, 2/1 ---- 이런 식이다. 여기에 각 층에 몇개의 분수.. Java - 알고리즘 2022. 8. 30.

• 

  백준 - 2839 설탕배달 풀이 방법 스터디에서 곧 풀게될 문제라서 미리 풀어보았던 문제였다. 그런데 그리디 알고리즘이라는 것을 알고 한번 좌절ㅠㅠ 하였다가 몇번이나 틀리고 코드를 완성시켰다. 문제를 풀고나서 보니까 이게 나처럼 무식하게 풀 필요가 없이...규칙을 찾아서 풀면 풀리는 문제라는 것을 알고 한번 더 좌절했다ㅠㅠ 나는 PriorityQueue 와 BFS 를 사용해서 풀었다. queue 에 넣는 값에는 sum 과 cnt 를 사용하였다. cnt 는 n-5 또는 n-3 했을 때 각각 cnt+1 이 되도록 했고, sum 은 n-5 또는 n-3 된 값을 넣어두었다(사실 변수명이 sum 말고 minus 로 설정해야될 것이다). 이후 sum 과 cnt 를 queue에 넣어서 보다 작은 sum 값이 먼저 나오도록 만든다. 이를 통해서.. Java - 알고리즘 2022. 8. 29.