본문 바로가기

Algorithm

백준 2606 바이러스 Java 2019. 8. 7. 다양한 방법으로 풀 수 있는 바이러스 문제이다. 대표적인 방법이 DFS, BFS이다. 나도 몇 달전에 BFS로 풀었었던 문제인데 이 문제를 유니온 파인드를 활용해 풀면 DFS보다 실행 속도를 훨씬 빠르게 해결할 수 있다. https://dundung.tistory.com/103 유니온 파인드 유니온 파인드란 어떤 집합을 나타낼 때 사용한다. kruskal 알고리즘에서 사이클 생성 여부를 확인할 때 주로 사용된다. 상호 배타적 집합(Disjoin-set)이라고도 하는데 2가지 연산으로 이루어져 있다. 1. Find :.. dundung.tistory.com 문제의 내용은 1부터 N까지의 컴퓨터들이 연결된 M개의 쌍이 주어지고 1번 컴퓨터가 감염되었을 때 바이러스가 옮는 컴퓨터의 수를 출력하면 된다. 유니온..
백준 1717 집합의 표현 Java 2019. 8. 7. 정답률은 29%이지만 유니온 파인드를 활용한다면 쉽게 해결할 수 있는 문제인 집합의 표현이다. https://dundung.tistory.com/103 유니온 파인드 유니온 파인드란 어떤 집합을 나타낼 때 사용한다. kruskal 알고리즘에서 사이클 생성 여부를 확인할 때 주로 사용된다. 상호 배타적 집합(Disjoin-set)이라고도 하는데 2가지 연산으로 이루어져 있다. 1. Find :.. dundung.tistory.com 문제의 내용은 0부터 N까지 N+1개의 수가 있고 2가지의 명령이 있다. 0번 명령은 x와 y 각각의 집합을 합치는 연산을 하면되고 1번 명령은 x와 y 두 원소가 같은 집합에 포함되어 있는지를 YES or NO로 출력하면 된다. 0번 명령은 유니온 파인드의 union메소드를 ..
유니온 파인드 2019. 8. 7. 유니온 파인드란 어떤 집합을 나타낼 때 사용한다. kruskal 알고리즘에서 사이클 생성 여부를 확인할 때 주로 사용된다. 상호 배타적 집합(Disjoin-set)이라고도 하는데 2가지 연산으로 이루어져 있다. 1. Find : x가 어떤 집합에 포함되어 있는지 찾는 연산 -> 루트를 찾아내는 연산 2. Union : x와 y가 포함되어 있는 집합을 합치는 연산 구현은 간단한 트리를 사용한다. parnet[i]에는 i의 루트가 저장되어 있다. x와 y를 합치는 경우 parent[x] = x, parent[y] = x 형태로 만들어 준다. 1과 2가 같은 집합이고 4와 5가 같은 집합인 경우엔 다음과 같은 형태를 띤다. 만약 2와 5를 합친다면 parnet[i]에는 i의 루트가 저장되어 있기 때문에 par..
백준 3015 오아시스 재결합 Java 2019. 8. 6. 알고리즘 분류에 스택으로 분류되어 있는 오아시스 재결합 문제이다. 문제를 간단히 설명하면 사람 수 N이 주어지고 N명의 사람들의 키가 순서대로 주어진다. 이 순서대로 줄을 서있을 때 A와 B가 마주 볼 수 있는 경우의 수를 출력하면 된다. A와 B 사이에 A 또는 B보다 큰 사람이 있으면 안 된다. N이 500,000이기 때문에 O(N^2)으로 비교해가면서 풀 수 없는 문제이다. 스택을 활용해야 한다는 힌트를 알았기 때문에 주어진 키를 전부 스택에 넣고 어떻게 활용하면 O(N)만에 풀 수 있을까 고민했는데 답이 안 나왔다. 답이 안 나온 이유는 주어진 키를 전부 스택에 넣었기 때문이다. 이 문제는 키를 하나씩 스택에 넣어가며 풀어야 된다. for문을 돌면서 i번째 사람보다 i+1번째 사람이 키가 큰 경우..
백준 14889 스타트와 링크 Java 2019. 8. 5. 삼성 sw 기출문제인 스타트와 링크 문제이다. 정답률을 50%로 sw 기출문제 중에선 쉬운 편인것 같다 알고리즘 분류는 브루트 포스로 분류되어있지만 백트래킹을 활용해서 문제를 풀었다. 문제 내용은 짝수인 사람 수 N이 주어지고 2개의 팀이 N/2명씩 나눠진다. N*N으로 팀원들의 능력치가 주어지면 2개의 팀 사이에 팀원들의 능력치 차이가 최소로 됐을 때 그 능력치 차이를 출력하면 된다. N의 범위가 20으로 작기 때문에 가능한 팀의 구성을 백트래킹으로 전부 구하고 구해질때마다 팀원들의 능력치를 계산해서 그 차이가 최소인 값을 찾아내는 방식으로 구현하였다. 백트래킹으로 team이라는 boolean형 배열에 true가 3개가 되었을 때 계산 메소드를 호출했다. 계산 메소드는 2중 for문으로 능력치가 주어진..
백준 2231 분해합 Java 2019. 7. 29. 단계별로 풀어보기 -> 브루트 포스에서 만난 문제인 분해합이다. 나한테는 문제 자체를 이해하기 힘든 문제였다.. 많은 시간의 고민끝에 이해한 것을 정리하자면 분해합은 숫자 N과 각 자리수의 합을 의미하고 생성자는 그 N을 분해합으로 만들 수 있는 수들을 의미한다. 245가 있다면 245의 분해합은 245+2+4+5 = 256 256의 생성자는 245인 것이다. 문제는 N이 주어졌을 때 가장 작은 생성자를 출력하는 문제이다. 내가 이해하기 어려웠던 것은 분해합들을 생성자라고 이해하고 예제의 216의 분해합은 216+2+1+6 인데 왜 198 출력이지.. 하고 한참을 미궁에 빠졌었다. 다시 한번 말해서 문제의 요지는 입력받은 N을 분해합으로 만들 수 있는 가장 작은 수를 출력하면 되는 것이다. 브루트 포스 ..
백준 1712 손익분기점 Java 2019. 7. 26. 단계별로 풀어보기의 수학 1에서 만난 손익분기점 문제이다. 쉬워 보이는 문제였는데 정답률은 29%로 낮다. 단계별에 있어서 앞으로 더 많은 사람들이 풀고 정답률은 더 낮아질 것 같다. 노트북을 생산하기 위해 필요한 고정비용 A와 가변비용 B, 노트북 가격 C가 주어진다. 고정비용은 말 그대로 변하지 않는 비용이고 가변비용은 한대 생산당 드는 비용이다. 노트북을 N개 생산할 때 A+B*N보다 C*N이 더 커지는 시점이 손익분기점이다. 이때 N의 개수를 출력하면 되는 문제이다. 손익분기점이 존재하지 않으면 -1을 출력해야 하는데 손익분기점이 존재하지 않는 경우는 B보다 C가 작거나 같을 때 이다. B >= C 인 경우엔 몇 대를 팔아도 손익분기점을 넘길 수 없다. 처음엔 쉽게 쉽게 while문으로 1씩 증가..
백준 6549 히스토그램에서 가장 큰 직사각형 Java 2019. 7. 11. 스택으로 풀 수 있는 정답률 24퍼센트의 히스토그램에서 가장 큰 직사각형 문제이다. n개의 직사각형이 있고 n개의 직사각형으로 만들 수 있는 가장 큰 직사각형의 넓이를 출력하면 되는 문제이다. n제한이 100,000이기 때문에 모든 경우를 해보는 O(n^2)의 방법은 시간 초과이다. 스택을 활용한다면 O(n)만에 문제를 풀 수 있다. 문제를 푸는 키포인트는 직사각형의 번호를 스택에 높이를 기준으로 오름차순으로 넣어준다는 점이다. 문제를 푸는 과정을 설명하자면 0부터 n-1까지의 for문을 돌면서 만약 i번째 직사각형의 높이가 스택에 가장 윗부분 직사각형의 높이보다 낮다면 가능한 넓이를 구하면서 가장 큰 값을 찾아낸다. 마지막으로 스택에 남아있는 것들도 처리해준다 i는 현재 위치 즉 오른쪽 위치를 나타내고..

티스토리툴바