알고리즘49

• [백준 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.

• [백준 JAVA] 11561 N과 M(3) 백트랙킹 https://www.acmicpc.net/problem/15651 15651번: N과 M (3) 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해 www.acmicpc.net dfs로 m만큼의 깊이만큼 반복한다. 각 깊이에 arr[d]의 값을 가능한 범위 (1~N)까지의 값을 모두 넣고 만약 깊이가 만족되면 stringbuilder에 저장하여 마지막에 출력한다. import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.String.. 알고리즘 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.

• 

  [백준 java] 2166 다각형의 면적 백준 boj 2166 다각형의 면적 골드 5 🔗 문제링크 🔗 2166번: 다각형의 면적 첫째 줄에 N이 주어진다. 다음 N개의 줄에는 다각형을 이루는 순서대로 N개의 점의 x, y좌표가 주어진다. 좌표값은 절댓값이 100,000을 넘지 않는 정수이다. www.acmicpc.net 🌟 생각 흐름 🌟 문제를 읽고 다각형의 면적을 구하는 방법이 있을 것 같아 구글링을 했다 아래 페이지를 참조하여 구현하였다. 다각형 넓이 구하기: 15 단계 (이미지 포함) - wikiHow 다각형의 넓이를 계산하는 일은 정삼각형 넓이를 구하는 것처럼 간단하기도 하지만 각 변의 길이가 다른 11각형의 넓이를 구하는 것처럼 복잡하기도 합니다. 다양한 다각형의 넓이를 구하는 방 ko.wikihow.com 위에 페이지에서 참조한 부분.. 알고리즘 2022. 10. 25.

• 

  [백준 java] 2225번 합분해 DP https://www.acmicpc.net/problem/2225 2225번: 합분해 첫째 줄에 답을 1,000,000,000으로 나눈 나머지를 출력한다. www.acmicpc.net [문제 풀이] arr[a][b] -> a개의 숫자를 이용해서 b를 만들수 있는 경우의 수 1개의 숫자를 이용해서 b를 만들수 있는 경우는 무조건 1개 임으로 1로 초기화 한다. arr[a][b]=arr[a-1][b]+arr[a][b-1] arr[3][2] = 002,020,200,110,101,011 (6) arr[4][1] = 0001,0010,0100,1000 (4) arr[4][2] = 0002,0020,0200, 0110,0101,0011,1001,1010,1100, 2000 (10) arr[3][2]의 앞에 0을 .. 알고리즘 2022. 10. 23.

• 

  [백준 Java]9466_텀프로젝트 [문제 링크] 9466 텀 프로젝트 자바 백준 https://www.acmicpc.net/problem/9466 9466번: 텀 프로젝트 이번 가을학기에 '문제 해결' 강의를 신청한 학생들은 텀 프로젝트를 수행해야 한다. 프로젝트 팀원 수에는 제한이 없다. 심지어 모든 학생들이 동일한 팀의 팀원인 경우와 같이 한 팀만 있을 www.acmicpc.net [생각 흐름] 처음에는 for문으로 i에서 모든 경로를 확인하여 사이클을 확인하려 하였는데 시간 초과가 났다. 그래서 O(n)으로 통과할 수 있는 방법을 찾다가 i번째부터 연결된 경로를 따라가다가 사이클이 생기면 처리하는 방식으로 해결하였다. 1) 1->2->3->4->2 와같은 상황이라면 사이클이 생겨서 2번 사람의 전 사람은 혼자 해야 한다. 각 노드를.. 알고리즘 2022. 10. 22.

• 

  [백준 JAVA] 14889 스타트와 링크, 합 이용 [문제링크] 스타트와 링크 실버2 https://www.acmicpc.net/problem/14889 14889번: 스타트와 링크 예제 2의 경우에 (1, 3, 6), (2, 4, 5)로 팀을 나누면 되고, 예제 3의 경우에는 (1, 2, 4, 5), (3, 6, 7, 8)로 팀을 나누면 된다. www.acmicpc.net 팀원이 되는경우 계산하는 부분을 두 가지로 나누어 코딩하였다. [1번 풀이] vistied 되었다면 A팀으로 생각하여 백트랙킹후 이중포문으로 계산 import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.StringTokenizer; public .. 알고리즘 2022. 10. 19.

• 

  [백준 Java] 2638 치즈 [문제 링크] boj 2638 치즈 골드 3 자바 https://www.acmicpc.net/problem/2638 2638번: 치즈 첫째 줄에는 모눈종이의 크기를 나타내는 두 개의 정수 N, M (5 ≤ N, M ≤ 100)이 주어진다. 그 다음 N개의 줄에는 모눈종이 위의 격자에 치즈가 있는 부분은 1로 표시되고, 치즈가 없는 부분은 0으로 www.acmicpc.net [생각 흐름] init 함수에서 배열에서 바깥쪽을 모두 -1로 초기화하고 안쪽에 있는 것과 다르게 표기한다. 이때 만약 치즈가 있는 칸이 하나도 없다면 true를 리턴하여 더 이상 진행하지 않도록 해준다. 이후에 remove 함수에서 치즈가 있는 칸이라면 4면 중 2면이 -1로 노출되어 있는 치즈 인지 확인하고 노출되어있다면 본 배열의.. 알고리즘 2022. 10. 17.

• 

  [백준 JAVA] 1644 소수의 연속합 [문제 링크] 자바 1644 소수의 연속합 https://www.acmicpc.net/problem/1644 1644번: 소수의 연속합 첫째 줄에 자연수 N이 주어진다. (1 ≤ N ≤ 4,000,000) www.acmicpc.net [생각 흐름] 먼저 에라토스테네스의 체를 이용하여 목표하는 값 이하까지의 소수 배열을 구한다. 이후에 투 포인터를 활용하여 만약 goal 값보다 현재값이 커지면 left를 오른쪽으로 옮기고 , goal 보다 작아지면 right를 오른쪽으로 옮겨 가면서 계산한다.(현재 sum에는 left~right까지의 배열의 합이 들어있다) 만약 목표값과 같으면 cnt를 하나 증가시키고 오른쪽을 증가시키도록 한다 종료시점은 right가 끝에 닿을 때까지 진행하도록 하였다. left를 확인하.. 알고리즘 2022. 10. 14.