알고리즘41

• [백준 Java] 4195번: 친구 네트워크, union-find 🔗 문제링크 🔗 4195번: 친구 네트워크 첫째 줄에 테스트 케이스의 개수가 주어진다. 각 테스트 케이스의 첫째 줄에는 친구 관계의 수 F가 주어지며, 이 값은 100,000을 넘지 않는다. 다음 F개의 줄에는 친구 관계가 생긴 순서대로 주어진 www.acmicpc.net 🌟 생각 흐름 🌟 두 친구에 대한 이름에 대한 저장이 필요해서 HashMap을 이용해서 이름과 배열에 할당할 index를 저장했다. 배열의 사이즈는 n개의 라인에 모두 서로 다른 친구가 나올 수 있을 것 같아 2*n으로 할당했다. 이후에는 친구의 이름이 해시에 없다면 저장하고 있다면 찾아온다.(만약 그냥 저장하면 index번호가 꼬이므로 저장하지 않는다) 두 친구가 이미 친구 관계인 경우에는 친구의 개수를 리턴하고 친구가 아닌 경우에만.. 알고리즘 2023. 3. 1.

• [백준 Java]15711_환상의 짝궁_수학, 소수 🔗 문제링크 🔗 15711번: 환상의 짝꿍 환상의 나라 디디랜드에서는 인연의 증표로 끈을 하나씩 가지고 있다. 그들은 지극히 평범한 방법으로 이 끈을 이용하여 어떤 두 사람이 환상의 짝꿍인지 판단하는데, 두 사람의 끈을 서로 이 www.acmicpc.net 🌟 생각 흐름 🌟 처음 문제를 보고 짝수와 홀수를 나눠서 생각했다. 1. 홀수의 경우 소수이기 위해서는 한 수가 무조건 2이고 다른 수고 sum-2 이어야 한다. 홀수가 되기 위해서는 짝수 + 홀수 이기 때문에 유일한 짝수이자 소수인 2를 무조건 포함해야 한다고 생각했고 나머지만 소수 판별하면 되겠네라고 생가하고 넘어갔다. 2. 짝수인 경우에는? 여기서 한번 고민을 했다 이걸 다 확인할 수는 없을 거 같은데.. 그래서 구글에 "소수의 합"을 검색하니 .. 알고리즘 2023. 2. 25.

• [백준 Java]1459_걷기_그리디 🔗 문제링크 🔗 1459번: 걷기 세준이는 학교에서 집으로 가려고 한다. 도시의 크기는 무한대이고, 도시의 세로 도로는 모든 정수 x좌표마다 있고, 가로 도로는 모든 정수 y좌표마다 있다. 세준이는 현재 (0, 0)에 있다. 그리고 ( www.acmicpc.net 🌟 생각 흐름 🌟 완탐으로 한다면 x, y의 범위로 인해서 시간 초과가 날 것 같아 그리디로 풀었다 길을 걷는 경우는 3가지로 나눌 수 있다. 모든 블록을 하나씩 다 걸어가는 방법 대각선으로 (n, n)까지 가서 (n, m)이나 (m, n)으로 가는 방법 (n이 더 작다고 가정) 모든 블록을 지그재그로 가는 방법(합이 짝수인 경우에는 모든 경로를 지그재그로 갈 수 있지만 홀수인 경우에는 한 번은 그냥 블록을 걸어가야 한다) 위의 3가지를 계산해.. 알고리즘 2023. 2. 23.

• [백준]1953_팀배분_DFS(BFS도 가능) 🔗 문제링크 🔗 1953번: 팀배분 첫줄에는 청팀의 사람의 수를 출력하고, 그리고 둘째 줄에는 청팀에 속한 사람들을 오름차순으로 나열한다. 그리고 셋째 줄과 넷째 줄은 위와 같은 방법으로 백팀에 속한 인원의 수, 백팀에 속 www.acmicpc.net 🌟 생각 흐름 🌟 우선 문제를 풀기 위해서 싫어하는 사람들과의 표기를 그래프를 통해서 진행했다 그래프를 그린 후 한 노드에서 시작한 경우 현재 노드와 다음노드만 다른 팀이면 가능하다고 생각했다 그리고 그 다음노드에서의 다음노드가 서로 다른 팀이면 가능하다는 식으로 dfs로 구현하였다 그래서 한 노드에서 시작한후 현재 깊이가 짝수이면 청팀, 홀수 이면 백팀에 넣도록 코드를 구현하였다 예를 들어 1,2가 서로를 싫어하고 2,3이 서로를 싫어하는 경우 ↔️ : .. 알고리즘 2023. 2. 22.

• 

  위상정렬 Topology Sort, 백준 1766 문제집(Java) 위상 정렬(Topology Sort) 정렬 알고리즘의 일종으로, 순서가 있는 작업을 차례대로 수행해야 하는 경우 사용할 수 있는 알고리즘이다. 방향 그래프로의 모든 그래프를 방향을 거스르지 않도록 순서대로 나열하는 것이다. 2번을 풀기 전에 1번 3번을 풀기 전에 2번 ,4번 4번을 풀기전에 5번을 푸는 것이 좋다고 하는 상황이 있다면 우리는 다음과 같은 방법들로 문제를 푸는 것이 좋다면 1->2->5->4->3 1->5->2->4->3 과 같이 다양한 경우가 만들어 질수 있다(이 외에도 가능하다) 이렇게 정렬하는것이 위상정렬이다. 추가로 위에 상황에서 쉬운 문제를 먼저 푸는 것을 우선으로 한다고 하면 1->2->5->4->3 같은 순서로 답을 낼 수 있을것이다. [(숫자: 난이도, 1번이 제일 쉬운문제.. 알고리즘 2023. 2. 22.

• 

  [백준 Java] 1238 파티 (다익스트라, 데이크스트라) [문제 링크] boj 1238 자바 dijkstra graph https://www.acmicpc.net/problem/1238 1238번: 파티 첫째 줄에 N(1 ≤ N ≤ 1,000), M(1 ≤ M ≤ 10,000), X가 공백으로 구분되어 입력된다. 두 번째 줄부터 M+1번째 줄까지 i번째 도로의 시작점, 끝점, 그리고 이 도로를 지나는데 필요한 소요시간 Ti가 들어 www.acmicpc.net [생각 흐름] 처음에는 다익스트라 방법으로 문제를 해결하였다. n-1번 다익스트라를 동작시키고, 파티 위치부터 돌아오는 것을 더해 가장 큰 것을 구하는 방법으로 계산하면 된다. 문제에서는 시간상으로 통과하지만 더 좋은 풀이가 있을것 같아 다른 풀이도 확인해본 결과 A -> B로 가는 걸로 돌아가는 걸 계산.. 알고리즘 2023. 2. 21.

• [백준 Java] 2812 크게만들기 그리디 알고리즘 [링크] https://www.acmicpc.net/problem/2812 2812번: 크게 만들기 N자리 숫자가 주어졌을 때, 여기서 숫자 K개를 지워서 얻을 수 있는 가장 큰 수를 구하는 프로그램을 작성하시오. www.acmicpc.net [문제풀이 방법] 가장 큰 숫자를 만들기 위해서는 앞자리가 가장 큰 숫자가 나와야 한다. 따라서 앞자리의 제일 큰 숫자가 오도록 숫자를 찾으면 된다 하지만 문제는 N개중 K개를 지우는 경우이므로 앞에서부터 k까지만 탐색을 해야 뒤에 남은 자리의 숫자를 모두 채울 수 있다 예를 들어 123456의 6자리 숫자에서 4자리를 지우는 경우에는 (0~4범위 [1,2,3,4,5])범위 안에서 탐색하여 5를 선택하고 하나를 선택하였으므로 탐색 가능 범위가 (6~6범위 [6])까.. 알고리즘 2022. 11. 10.

• [백준 Java]1717 집합의 표현 https://www.acmicpc.net/problem/1717 1717번: 집합의 표현 첫째 줄에 n(1 ≤ n ≤ 1,000,000), m(1 ≤ m ≤ 100,000)이 주어진다. m은 입력으로 주어지는 연산의 개수이다. 다음 m개의 줄에는 각각의 연산이 주어진다. 합집합은 0 a b의 형태로 입력이 주어진다. 이는 www.acmicpc.net 크루스칼 알고리즘 풀이에 사용되는 union과 findParent 메서드를 생성하여 해결하였다 먼저 초기에 각 노드들의 부모를 자기 자신으로 초기화한다. 명령으로 union을 하라고 들어온다면 먼저 a, b의 가장 조상 노드를 찾는다 그 후에 두 조상노드 값 중 더 작은 값으로 조상 노드를 갱신하면 union 된다.(마치 트리구조 같이) 명령으로 print.. 알고리즘 2022. 11. 9.

• 

  [백준 JAVA] 2589 보물섬 (BFS,너비 우선 탐색) https://www.acmicpc.net/problem/2589 2589번: 보물섬 보물섬 지도를 발견한 후크 선장은 보물을 찾아나섰다. 보물섬 지도는 아래 그림과 같이 직사각형 모양이며 여러 칸으로 나뉘어져 있다. 각 칸은 육지(L)나 바다(W)로 표시되어 있다. 이 지도에서 www.acmicpc.net input 저장 시 map에 'L'인 경우 true를 저장 , 'W'인 경우 false를 저장하였습니다. 이문제의 포인트는 한 땅에서 가장 멀리 있는 두 육지를 찾고 두 육지의 까지의 시간을 출력하는 것이라 생각했습니다. 하지만 한 지점에서부터 탐색을 한경우에는 땅이 여러 개인 경우, 가장 긴 두 육지의 시작 노드가 아닌 경우 등 최대 값을 보장할 수 없습니다. 따라서 모든 땅인 지점에서부터 너비 우.. 알고리즘 2022. 11. 8.

• [백준 JAVA] 7562 나이트의 이동, BFS(너비 우선 탐색) https://www.acmicpc.net/problem/7562 7562번: 나이트의 이동 체스판 위에 한 나이트가 놓여져 있다. 나이트가 한 번에 이동할 수 있는 칸은 아래 그림에 나와있다. 나이트가 이동하려고 하는 칸이 주어진다. 나이트는 몇 번 움직이면 이 칸으로 이동할 수 www.acmicpc.net https://www.acmicpc.net/problem/2178 미로탐색 문제와 아주 유사하다. 너비우선 탐색을 이용하여 이동위치의 값을 갱신해가면서 이동하여 값을 출력한다 큐에는 이동한 거리가 작은 순으로 들어있으므로 최소값을 만족한다. import java.awt.*; import java.io.BufferedReader; import java.io.IOException; import java.. 알고리즘 2022. 11. 6.

• 

  이진탐색(binary search) 먼저 이진 탐색을 위해서는 내부의 데이터가 정렬되어 있어야 한다. 이진 탐색을 위해서는 시작점 start, end, mid 를 이용하여 탐색한다 찾으려는 데이터와 중간점 위치의 데이터를 비교하며 반복하면서 데이터를 찾는다. 와 같은 과정으로 탐색해 나간다. - python 코드 def binary_search(arr,goal,start,end): if start>end: return None mid = (start+end)//2 if arr[mid]==goal: return mid elif arr[mid]>goal: return binary_search(arr,goal,start,mid-1) else: return binary_search(arr,goal,mid+1,end) def binary_searc.. 알고리즘 2022. 11. 5.

• 

  [백준 JAVA] 16724 피리부는 사나이 백준 자바 16724 피리 부는 사나이 BFS 16724번: 피리 부는 사나이 첫 번째 줄에 지도의 행의 수를 나타내는 N(1 ≤ N ≤ 1,000)과 지도의 열의 수를 나타내는 M(1 ≤ M ≤ 1,000)이 주어진다. 두 번째 줄부터 N개의 줄에 지도의 정보를 나타내는 길이가 M인 문자열이 주 www.acmicpc.net [문제 풀이 방법] 사이클을 따라서 방문 처리되지 않은 원소(0인 원소들) 들을 방문 처리하면서 길을 따라가다가 만약 이전에 방문했던 곳이면 사이클을 따라 safezone이 하나 있어야 하므로 safezone을 하나 증가시켜야 한다 하지만 만약 사이클을 따라가다가 이전에(이번 턴이 아닌) 방문처리가 된 원소라면 이미 이전 턴의 사이클에 safezone이 존재하므로 safezone을 .. 알고리즘 2022. 10. 25.