본문 바로가기

알고리즘

 (60)
백준(BOJ) 20040: 사이클 게임 https://www.acmicpc.net/problem/20040 자료구조 문제로 Union-find집합자료구조를 묻고 있다. "사이클=집합" 이라는 것을 항상 기억하고 사이클에 관한 문제라면 어떻게든 Union-find를 사용하려고 해야한다. 사이클은 다른 말로 집합을 형성하는 것이다. 같은 집합에 속해있는 정점들만 선택하면 하나의 사이클을 만든다. import java.io.BufferedReader; import java.io.InputStreamReader; import java.util.Arrays; import java.util.StringTokenizer; public class Main { public static class Edge { int from; int to; public Edg..
백준(BOJ) 11286 : 절댓값 힙 https://www.acmicpc.net/problem/11286 import java.io.BufferedReader; import java.io.InputStreamReader; import java.util.Comparator; import java.util.PriorityQueue; public class Main{ public static class Element{ int original; int ab; public Element(int original){ this.original=original; this.ab=Math.abs(original); } public int getAbsValue(){ return ab; } public int getOriginal(){ return original..
백준(BOJ) 1912: 연속합 https://www.acmicpc.net/problem/1912 점화식등 다해놓고 안타깝게도 아래 max변수의 초기값을 생각없이 -1로 무턱대고 잡았다가 오답이 떳다. 초기화을 함부로 주지 말자. import java.io.BufferedReader; import java.io.InputStreamReader; import java.util.Arrays; import java.util.StringTokenizer; public class Testing3{ public static void solution(int n, int[]arr){ int[]dp=new int[n]; dp[0]=arr[0]; for(int i=1;i
백준(BOJ) 2407: 조합 https://www.acmicpc.net/problem/2407 기초문제로 BigInteger타입과 그 연산( dp[i][j]=dp[i-1][j-1].add(dp[i-1][j]); )방식에 대해 알아두기. BigInteger에 대하여https://coding-factory.tistory.com/604#google_vignette ==>> int는 메모리 크기는 4byte로 표현할 수 있는 범위는 -2,147,483,648 ~ 2,147,483,647이고 long은 메모리 크기는 8byte로 표현할 수 있는 범위는 -9,223,372,036,854,775,808 ~ 9,223,372,036,854,775,807입니다. 그 범위를 넘어서게 되면 모두 0으로 출력이 됩니다. 숫자의 범위가 저 범위를 넘을 경..
백준(BOJ) 12849: 본대 산책 https://www.acmicpc.net/problem/12849 매우 상징성이 강한 문제다. 내가 그동안 왜 안나오나... 하고 생각했던 그런문제다. 문제가 조건을 명확하게 주지 않은 면이 있는데, 출발점도 정보관이고 도착점도 정보관으로 놓고 푸는 문제다. 문제에서 묻는것은 출발점에서 시작해 D분이 지났을때 다시 출발점으로 돌아올수 있는 경로의 수이다. 이렇게 총 경로의 수를 구할때 Dynamic programming으로 해결할 수 있음을 유의하자! 정석은 2차원배열을 이용하는 것이지만 배열을 하나더 추가로 두는 조건으로 1차원 배열 2개로도 해결이 가능하다. 두 풀이 모두 소개한다. import java.io.BufferedReader; import java.io.InputStreamReader; ..
S-algo02 3자리 짝수찾기 빈도수 배열과 size변수를 이용하여 100의 자리에는 0이 올수 없도록 하고 1의 자리를 뽑을 때는 오로지 짝수만을 뽑도록 한다. 수학문제 푸는 거랑 똑같다. 머릿속으로 재귀트리 모형이 그려지면서 재귀함수 호출전 --frequency[i], 재귀함수 호출후 ++frequency[i]를 하는 것은 기계적으로 그려진다. 다만 이 문제만이 가지는 고유한 특성인 백의 자리에는 0이 들어가지 않고 오직 짝수인 100의 자리수를 어떻게 생성해 낼 것인지가 이 문제만이 가지는 특이점이다. 풀이법은 크게 두 가지이다. 1. 재귀를 이용한 풀이 2. 100~998까지의 숫자를 모두 탐색해 보기. import java.io.BufferedReader; import java.io.InputStreamReader; impo..
백준(BOJ) 2655: 가장높은 탑쌓기 https://www.acmicpc.net/problem/2655 가장높은 탑쌓기: 최장증가 부분수열(LIS, Longest Increaing Subsequence) 문제의 변형 기존과 비슷한 문제여서 기존의 방법으로 뭔가 해결될 수 있을 것 같으면 해보면 된다. 다만 용납해서는 안되는 경우가 같은 문제임에도 불구하고 전혀 다른 풀이를 쓰고 기존의 해결방법을 적용할 줄 모르는 것이다. 만약 기존의 풀이법으로는 안된다면 왜 안되는지 파악해야 한다. 그것이 기존의 문제와 다른 차이점이기 때문이라면 차이점은 명확히 정리해서 알고있어야 한다. 그게 문제를 정리해 가는 것이므로. 대체 어떻게 했길래 dp[i]가 i번째 벽돌을 가장 아래에 뒀을때의 최대높이를 의미하게 할 수 있었던 것인가? (0-1배낭문제)대체 어..
백준(BOJ) 1932: 정수 삼각형 정수삼각형: https://www.acmicpc.net/problem/1932 기타리스트: https://www.acmicpc.net/problem/1495 정수삼각형문제는 최종 결과값들을 조회할 수 있는 틀이 있다. 하지만 기타리스트 문제는 최종 결과값들을 조회할 수 있는 정수삼각형 문제에서말하는 그 틀이 없고 입력으로 주워지는 최댓값이 있어 제한될 수 있는 범위라는 것이 있고 그 범위를 조회하면 답이 구해진다. 위에서 말하는 정수 삼각형 문제에서 틀이라는 것은 아래 그림과 같이 1,2,3,4,5...n 행을 거치는 누적 값들이 결국은 최하위행의 열중 어느 하나의 열에 결국은 들어가게 된다는 것이다. 기타리스트 문제는 이런 틀이 없다. 다만 결과로 얻을 수 있는 값을 제한하고 그로부터 조회할 수 있는 ..

티스토리툴바