알고리즘 (136) 썸네일형 리스트형 [백준] 16932번 모양만들기 https://www.acmicpc.net/problem/16932 16932번: 모양 만들기 N×M인 배열에서 모양을 찾으려고 한다. 배열의 각 칸에는 0과 1 중의 하나가 들어있다. 두 칸이 서로 변을 공유할때, 두 칸을 인접하다고 한다. 1이 들어 있는 인접한 칸끼리 연결했을 때, 각각의 연결 요소를 모양이라고 부르자. 모양의 크기는 모양에 포함되어 있는 1의 개수이다. 배열의 칸 하나에 들어있는 수를 변경해서 만들 수 있는 모양의 최대 크기를 구해보자. www.acmicpc.net 1. 이해하기 0과 1로 이뤄진 배열에서 1을 하나 놓음으로 1로 이뤄진 가장 큰 영역을 찾는 문제이다. 모든 0에 1을 놔보면서 크기를 비교한다. 하지만 1을 놓고 그때마다 dfs를 수행한다면 시간 초과가 일어난다. .. 특정 구간에 0~9의 숫자 갯수 찾기 start%10 가 0이 될때까지 start++를 한다. 이 과정에서 start에 나오는 숫자의 갯수를 세준다. end%10가 9가 될때까지 end--를 한다. 이 과정에서 end에 나오는 숫자의 갯수를 세준다. 0~9 모두에 (end-start+1)*t를 더해준다. 이때 t의 값은 어떤 자리수를 세는지에 따라 다르다. 예를 들어 일의 자리를 센다면 t=1이고 십의 자리를 센다면 t=10이다. 십의 자리를 셀때는 일의 자리를 셀 동안 계속해서 반복적으로 나오기 때문이다. start > end 혹은 start == 0, end == 0일때 반복을 종료한다. ans = 0; long mul = 1; while(A next permutation 다음 순열에 해당하는 배열을 찾는 방법. 처음부터 순서대로 배열을 보면서 arr[i] = arr[i] 인 마지막 i를 찾는다. 만약 그러한 i가 없다면 이미 마지막 순열이다. 다음은 끝에서 시작하면서 arr[j] > arr[i] 인 첫번째 j를 찾는다. 이후에 swap(i,j)한다. 그 이후에 i+1부터 끝까지 정렬을 해준다. 정렬을 할 때는 앞뒤만 바꾸는 작업을 해주면 된다. 그 이유는 i+1부터 끝까지는 이미 내림차순이기 때문이다. 이 배열을 예로 들면 1번을 만족하는 i는 숫자 1을 가지고 있는 arr[2]이다. 또한 3번을 만족하는 j는 숫자 7을 가지고 있는 arr[4]이다. 따라서 i .. [SWEA] 7699번 수지의 수지 맞는 여행 https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AWqUzj0arpkDFARG&categoryId=AWqUzj0arpkDFARG&categoryType=CODE SW Expert Academy SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요! swexpertacademy.com 1. 이해하기 상하좌우로 이동이 가능하지만 같은 명물을 보지 않고 가장 많은 명물을 보는 방법을 찾는 것이다. dfs로 풀 수 있다. 2. 구현하기 dfs(x,y,depth) 현재 위치를 받고 얼마나 많은 명물을 봤는 지를 갱신해준다. 현재 위치의 명물은 본 것이므로 봤다고 표시를 해준다. 함수가 종료될 때는 다시 보.. 바이너리 카운팅을 통해 부분집합 생성 public class subset { public static void main(String[] args) { char[] arr = {'a','b','c'}; for(int i = 0; i < (1 Permutation & Combination import java.util.Arrays; public class Permutation { static int[] arr = {1,2,3}; public static void main(String[] args) { perm(arr.length,0); } static void perm(int n, int k) { if(k == n) { System.out.println(Arrays.toString(arr)); return; } for(int i = k; i < arr.length; i++) { swap(k,i); perm(n,k+1); swap(k,i); } } static void swap(int i, int j) { int tmp = arr[i]; arr[i] = arr[j]; arr[j] = tmp.. [백준] 7662번 이중 우선순위 큐 1. 이해하기 자료구조 트리를 사용하는 법을 물어보는 문제이다. java에서 TreeMap을 사용한다. HashMap은 정렬이 되지 않기 때문에 Key값으로 정렬이 되는 TreeMap을 사용한다. 이때, 값이 int값을 벗어날 수 있으므로 long을 key값으로 저장해준다. 2. 전체코드 package algo; import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.StringTokenizer; import java.util.TreeMap; public class Acm7662_이중우선순위큐 { static TreeMap map; public static void.. DISJOINT-SETS, MST MST(최소 신장 트리) MST의 목적 낭비를 줄이고 최적의 비용으로 모두를 연결하기 위함 그리디한 기법을 쓴다. 팩토리얼 보다 적게 만들기 위해서 쓴다. 모든 경로의 합이 최소를 찾기 위해서 쓴다.(나중에 나올 다익스트라와 용도가 다르다.) MST를 만들기 위한 기법은 두가지 프림, 크루스칼 프림 disjoint-sets을 기반으로 깔고 들어간다. 크루스칼 크루스칼에서 다음 노드를 선택했을 때 그 노드를 union한다. 또한 사이클이 발생할 수 있는 경우를 방지한다. 트리이기 때문에 사이클이 발생하지 않아야 한다. 간선이 많으면 터진다. 간선이 적으면 크루스칼, 간선이 많으면 프림 DISJOINT-SETS 서로소 집합을 의미한다. 각 집합의 부모 노드를 가지고 있고 부모 노드가 다르면 다른 집합을 의미.. 이전 1 2 3 4 5 6 ··· 17 다음
