Java - 알고리즘52

• 

  다익스트라 알고리즘 데이크르스라 알고리즘 Dijkstra Algorithm 일명 다익스트라 알고리즘이라고도 한다. - 보통 음의 가중치가 없는 가주치 방향 그래프를 기준으로 최소 비용으로 노드를 방문하거나 노드를 이어가는 문제들에 많이 쓰인다 => 가중치 방향 그래프란 노드에서 다른 노드로 갈 때 일정한 비용이 드는 그래프를 의미한다. - 기본적으로 O(V^2) 의 시간복잡도를 가지나 PriorityQueue 나 sort 를 사용해서 O(VlogV) 의 시간 복잡도를 만들어서 계산하게 된다. 다익스트라 알고리즘 코드 보통 아래와 같은 순서로 코드 작성한다. 0. 정점과 비용을 위한 Edge class 를 만들어둔다 1. n번째 노드에서의 최소 cost 로 방문할 수 있는 도로를 찾기위해 PriorityQueue 를 사용한다.. Java - 알고리즘 2022. 8. 27.

• 

  백준 - 1647 도시 분할 계획 https://www.acmicpc.net/problem/1647 1647번: 도시 분할 계획 첫째 줄에 집의 개수 N, 길의 개수 M이 주어진다. N은 2이상 100,000이하인 정수이고, M은 1이상 1,000,000이하인 정수이다. 그 다음 줄부터 M줄에 걸쳐 길의 정보가 A B C 세 개의 정수로 주어지는데 A번 www.acmicpc.net 풀이 방법 이전에 풀었던 1922 네트워크 연결 문제와 아주아주아주 동일한 문제 사실 가장 큰 차이점은 마을을 두개로 분리했을 때 도로 최소 유지비용을 찾는 것이다. 이 문제에서 가장 고민했던 부분이 바로 저 부분이었다. 최소 신장 트리를 만들어서 하는 것은 알겠는데...대체 어떻게 두개로 나누지...? 그리고 두개로 나눈 후 어떻게 최소 유지비용을 찾지..?.. Java - 알고리즘 2022. 8. 27.

• 

  백준 - 1922 네트워크 연결(feat. 크루스칼 알고리즘) https://www.acmicpc.net/problem/1922 1922번: 네트워크 연결 이 경우에 1-3, 2-3, 3-4, 4-5, 4-6을 연결하면 주어진 output이 나오게 된다. www.acmicpc.net 풀이 방법 내가 무식해서 때문에 용감해져서 도전했던 문제ㅠ.ㅠ 사실 그래프 문제고 탐색하는 문제이기 때문에 DFS 나 BFS 로 하면 되는 문제겠네 하면서 풀었는데 당연히 다르게 푸는 문제였고, 메모리 초과만 5번은 뜬 것 같다. 2시간쯤 지나서 뭔가 이상하다고 느꼈고, 찾아보니 DFS 도 아니고, BFS 도 아니고 크루스칼 알고리즘과 이를 위한 union-find 구현을 통해 푸는 문제라는것을 알았다. 오늘도 새로운 것을 알아간다ㅋㅋㅋㅋ 이 문제는 최소 신장 트리를 찾는 문제이고, 이.. Java - 알고리즘 2022. 8. 24.

• 

  백준 - 1712 손익분기점 풀이 방법 매번 느끼는건데 백준에서의 수학 관련된 문제들은 옳곧이 수학적인 계산을 하는 것보다는 일종의 '꼼수'를 발견하는게 중요하다고 느낀다. 저번 A->B 문제도 그렇고, 이 문제도 그렇다. 오히려 수학 계산을 정말 하면 시간초과가 터지는 그런...? 사실 문제를 계산한다 라는 느낌보다는 '순수익이 어떻게 기준점을 넘길까?' 를 생각해보면 쉬워지는 문제이다. 예컨데 순수익을 먼저 계산한 후 순수익을 기준으로 고정비용을 몇일만에 넘길 수 있는가? 를 생각하면 되는 문제이다. A = 1000, B = 70, C = 170 인 경우 1일차 : 1000+70*1 , 170*1 을 비교 2일차 : 1000+70*2 , 170*2 을 비교 n일차 : 1000+70*n , 170*n 을 비교 이때 고정비용인 A .. Java - 알고리즘 2022. 8. 23.

• 

  백준 - 5397 키로거 https://www.acmicpc.net/problem/5397 5397번: 키로거 첫째 줄에 테스트 케이스의 개수가 주어진다. 각 테스트 케이스는 한줄로 이루어져 있고, 강산이가 입력한 순서대로 길이가 L인 문자열이 주어진다. (1 ≤ L ≤ 1,000,000) 강산이가 백스페이스를 입 www.acmicpc.net 풀이 방법 실버 2 문제라서 그래도 할만할 줄 알고 편하게 도전했다가 망해버린 문제 처음에는 ArrayList 로 접근해서 풀어보려고 했는데 문제를 읽다보니까 이렇게 풀어서는 안되는구나...를 끝없이 느끼고 LinkList 로 전환하여서 풀었다. 솔직히 LinkList 를 Queue 구현할때만 사용하고, 심지어 List 의 다양한 기능을 위해 사용하는 ListIterator 는 처음 써보는.. Java - 알고리즘 2022. 8. 22.

• 

  백준 - 2798 블랙잭 https://www.acmicpc.net/problem/2798 2798번: 블랙잭 첫째 줄에 카드의 개수 N(3 ≤ N ≤ 100)과 M(10 ≤ M ≤ 300,000)이 주어진다. 둘째 줄에는 카드에 쓰여 있는 수가 주어지며, 이 값은 100,000을 넘지 않는 양의 정수이다. 합이 M을 넘지 않는 카드 3장 www.acmicpc.net 문제 카지노에서 제일 인기 있는 게임 블랙잭의 규칙은 상당히 쉽다. 카드의 합이 21을 넘지 않는 한도 내에서, 카드의 합을 최대한 크게 만드는 게임이다. 블랙잭은 카지노마다 다양한 규정이 있다. 한국 최고의 블랙잭 고수 김정인은 새로운 블랙잭 규칙을 만들어 상근, 창영이와 게임하려고 한다. 김정인 버전의 블랙잭에서 각 카드에는 양의 정수가 쓰여 있다. 그 다음, .. Java - 알고리즘 2022. 8. 21.

• 

  백준 - 11652 카드 https://www.acmicpc.net/problem/11652 11652번: 카드 준규는 숫자 카드 N장을 가지고 있다. 숫자 카드에는 정수가 하나 적혀있는데, 적혀있는 수는 -262보다 크거나 같고, 262보다 작거나 같다. 준규가 가지고 있는 카드가 주어졌을 때, 가장 많이 가지 www.acmicpc.net 문제 준규는 숫자 카드 N장을 가지고 있다. 숫자 카드에는 정수가 하나 적혀있는데, 적혀있는 수는 -2^62보다 크거나 같고, 2^62보다 작거나 같다. 준규가 가지고 있는 카드가 주어졌을 때, 가장 많이 가지고 있는 정수를 구하는 프로그램을 작성하시오. 만약, 가장 많이 가지고 있는 정수가 여러 가지라면, 작은 것을 출력한다. 입력 첫째 줄에 준규가 가지고 있는 숫자 카드의 개수 N (1 .. Java - 알고리즘 2022. 8. 20.

• 백준 - 3055 탈출 https://www.acmicpc.net/problem/3055 3055번: 탈출 사악한 암흑의 군주 이민혁은 드디어 마법 구슬을 손에 넣었고, 그 능력을 실험해보기 위해 근처의 티떱숲에 홍수를 일으키려고 한다. 이 숲에는 고슴도치가 한 마리 살고 있다. 고슴도치는 제 www.acmicpc.net 문제 사악한 암흑의 군주 이민혁은 드디어 마법 구슬을 손에 넣었고, 그 능력을 실험해보기 위해 근처의 티떱숲에 홍수를 일으키려고 한다. 이 숲에는 고슴도치가 한 마리 살고 있다. 고슴도치는 제일 친한 친구인 비버의 굴로 가능한 빨리 도망가 홍수를 피하려고 한다. 티떱숲의 지도는 R행 C열로 이루어져 있다. 비어있는 곳은 '.'로 표시되어 있고, 물이 차있는 지역은 '*', 돌은 'X'로 표시되어 있다. 비버의.. Java - 알고리즘 2022. 8. 19.

• 백준 - 20291 파일 정리 https://www.acmicpc.net/problem/20291 20291번: 파일 정리 친구로부터 노트북을 중고로 산 스브러스는 노트북을 켜자마자 경악할 수밖에 없었다. 바탕화면에 온갖 파일들이 정리도 안 된 채 가득했기 때문이다. 그리고 화면의 구석에서 친구의 메시지를 www.acmicpc.net 문제 친구로부터 노트북을 중고로 산 스브러스는 노트북을 켜자마자 경악할 수밖에 없었다. 바탕화면에 온갖 파일들이 정리도 안 된 채 가득했기 때문이다. 그리고 화면의 구석에서 친구의 메시지를 확인할 수 있었다. 바탕화면의 파일들에는 값진 보물에 대한 정보가 들어 있어. 하나라도 지우게 된다면 보물은 물론이고 다시는 노트북을 쓸 수 없게 될 거야. 파일들을 잘 분석해서 보물의 주인공이 될 수 있길 바랄게. .. Java - 알고리즘 2022. 8. 19.

• 백준 - 10825 국영수 https://www.acmicpc.net/problem/10825 10825번: 국영수 첫째 줄에 도현이네 반의 학생의 수 N (1 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 한 줄에 하나씩 각 학생의 이름, 국어, 영어, 수학 점수가 공백으로 구분해 주어진다. 점수는 1보다 크거나 같고, 1 www.acmicpc.net 문제 도현이네 반 학생 N명의 이름과 국어, 영어, 수학 점수가 주어진다. 이때, 다음과 같은 조건으로 학생의 성적을 정렬하는 프로그램을 작성하시오. 국어 점수가 감소하는 순서로 국어 점수가 같으면 영어 점수가 증가하는 순서로 국어 점수와 영어 점수가 같으면 수학 점수가 감소하는 순서로 모든 점수가 같으면 이름이 사전 순으로 증가하는 순서로 (단, 아스키 코드에서 대문자는 소.. Java - 알고리즘 2022. 8. 18.

• 백준 - 7568 덩치 https://www.acmicpc.net/problem/7568 7568번: 덩치 우리는 사람의 덩치를 키와 몸무게, 이 두 개의 값으로 표현하여 그 등수를 매겨보려고 한다. 어떤 사람의 몸무게가 x kg이고 키가 y cm라면 이 사람의 덩치는 (x, y)로 표시된다. 두 사람 A 와 B의 덩 www.acmicpc.net 문제 우리는 사람의 덩치를 키와 몸무게, 이 두 개의 값으로 표현하여 그 등수를 매겨보려고 한다. 어떤 사람의 몸무게가 x kg이고 키가 y cm라면 이 사람의 덩치는 (x, y)로 표시된다. 두 사람 A 와 B의 덩치가 각각 (x, y), (p, q)라고 할 때 x > p 그리고 y > q 이라면 우리는 A의 덩치가 B의 덩치보다 "더 크다"고 말한다. 예를 들어 어떤 A, B 두 .. Java - 알고리즘 2022. 8. 18.

• 

  백준 - 14226 이모티콘 https://www.acmicpc.net/problem/14226 14226번: 이모티콘 영선이는 매우 기쁘기 때문에, 효빈이에게 스마일 이모티콘을 S개 보내려고 한다. 영선이는 이미 화면에 이모티콘 1개를 입력했다. 이제, 다음과 같은 3가지 연산만 사용해서 이모티콘을 S개 만 www.acmicpc.net 문제 영선이는 매우 기쁘기 때문에, 효빈이에게 스마일 이모티콘을 S개 보내려고 한다. 영선이는 이미 화면에 이모티콘 1개를 입력했다. 이제, 다음과 같은 3가지 연산만 사용해서 이모티콘을 S개 만들어 보려고 한다. 화면에 있는 이모티콘을 모두 복사해서 클립보드에 저장한다. 클립보드에 있는 모든 이모티콘을 화면에 붙여넣기 한다. 화면에 있는 이모티콘 중 하나를 삭제한다. 모든 연산은 1초가 걸린다. .. Java - 알고리즘 2022. 8. 15.