공부공간

https://www.acmicpc.net/problem/15812 1717번: 집합의 표현 첫째 줄에 n(1 ≤ n ≤ 1,000,000), m(1 ≤ m ≤ 100,000)이 주어진다. m은 입력으로 주어지는 연산의 개수이다. 다음 m개의 줄에는 각각의 연산이 주어진다. 합집합은 0 a b의 형태로 입력이 주어진다. 이는 www.acmicpc.net 맵의 모든 1의 개수가 정복되는 최소 시간을 구하는 것이므로 모든경우를 살펴야한다 ( 완전탐색 ) BFS를 이용하여, 1을 만날때마다 카운트를 증가시켜 전체의 1의 개수와 같아질때의 시간을 구한다. 모든경우의 수에서 최소시간이 정답이다 ! import java.io.BufferedReader; import java.io.IOException; import..

www.acmicpc.net/problem/11003 1717번: 집합의 표현 첫째 줄에 n(1 ≤ n ≤ 1,000,000), m(1 ≤ m ≤ 100,000)이 주어진다. m은 입력으로 주어지는 연산의 개수이다. 다음 m개의 줄에는 각각의 연산이 주어진다. 합집합은 0 a b의 형태로 입력이 주어진다. 이는 www.acmicpc.net 배열을 O(n)탐색하면서 현재 값보다 큰 값은 빼주고, index가 범위 밖에 있는것도 빼준다. import java.io.BufferedReader; import java.io.BufferedWriter; import java.io.IOException; import java.io.InputStreamReader; import java.io.OutputStreamWr..

최근에 알고리즘 문제를 풀다가 조금 신기한 경우를 발견했다.. ( 사실 내가 기초가 없어 자바는 new만 해주면 서로다른 Hashcode를 가지고 관리되는 줄 알았다) 내가 넣어준적 없는 List_B가 HashMap에 있다고 나온다.. 그렇다면 HashMap은 객체의 어떤 값을 Key로 설정하여 Value 들을 관리할까 ?? 1 ) HashMap Class 내부에서 자료들을 어떻게 관리할까 ? 먼저, get은 hashmap에서 특정 객체를 뽑아올때, 특정 객체를 hash()의 인자로 넣고 그 결과를 getNode()를 호출시켜서 value가있으면 반환하는 로직으로 구성되어있다. put도 마찬가지로 hash함수에 key를 통과시켜서 putVal한 결과를 반환하는 식이였다. 그렇다면 Hashmap.hash(..

2020년은 SSAFY 3기를 이수하면서 시간을 보냈다. 수많은 면접을 보았다. 네이버, 삼성전자, SK C&C, 우리FIS, 신한 DS, 김앤장 ... 그때 받았던 질문들, 어순, 단어 등을 잘 정리해두고 외우다시피 노력한게 최종합격의 성취가 된거같다. 아직 남은 곳도 있지만 일단 하나 합격했으니 다행이다. 전국에 취준생분들 화이팅.. 2020 취업기 끝!

www.acmicpc.net/problem/9205 9205번: 맥주 마시면서 걸어가기 송도에 사는 상근이와 친구들은 송도에서 열리는 펜타포트 락 페스티벌에 가려고 한다. 올해는 맥주를 마시면서 걸어가기로 했다. 출발은 상근이네 집에서 하고, 맥주 한 박스를 들고 출발한다. www.acmicpc.net 각 정점에서 최대거리 ( x + y = 1000칸 움직임 ) 에 편의점이있거나 현재 정점에서 페스티벌위치까지 갈수있는지 판단하기 위해서 재귀함수를 이용하여 매 정점을 체크해준다. import java.io.BufferedReader; import java.io.InputStreamReader; import java.util.StringTokenizer; public class Main { public st..

www.acmicpc.net/problem/18870 18870번: 좌표 압축 수직선 위에 N개의 좌표 X1, X2, ..., XN이 있다. 이 좌표에 좌표 압축을 적용하려고 한다. Xi를 좌표 압축한 결과 X'i의 값은 Xi > Xj를 만족하는 서로 다른 좌표의 개수와 같아야 한다. X1, X2, ..., XN에 좌 www.acmicpc.net 좌표 압축 (Coordinate Compress)은 말그래도 좌표를 압축하여 사용하는 것이다. 단독으로 이것만 나오지 않고 보통 세그먼트트리나 구현문제에서 좌표를 압축해도 문제상황이 달라지지 않는 경우에 사용한다. 배열을 정렬해주고 작은 값에 인덱스를0을 부여하며 증가시켜서 압축시키는 방식이다. 아래는 구현코드 hashmap을 이용하여 압축하였다. 배열을 써도될..

www.acmicpc.net/problem/10211 10211번: Maximum Subarray 크기 N인 정수형 배열 X가 있을 때, X의 부분 배열(X의 연속한 일부분) 중 각 원소의 합이 가장 큰 부분 배열을 찾는 Maximum subarray problem(최대 부분배열 문제)은 컴퓨터 과학에서 매우 잘 알려져 있 www.acmicpc.net 수열에서 연속된 부분배열의 최댓값을 구하는 문제.. 양수면 계속더하면 최댓값이 되지만 중간에 음수가있는경우, 음수의 덧셈으로 0보다 크면 계속 더해준다. N^2 / NlogN의 풀이도 있지만, O(N)에 해결가능하다 package algorithm; import java.io.BufferedReader; import java.io.InputStreamRea..

www.acmicpc.net/problem/4386 4386번: 별자리 만들기 도현이는 우주의 신이다. 이제 도현이는 아무렇게나 널브러져 있는 n개의 별들을 이어서 별자리를 하나 만들 것이다. 별자리의 조건은 다음과 같다. 별자리를 이루는 선은 서로 다른 두 별을 일 www.acmicpc.net 별자리를 클래스로 묶고 별자리 간 거리를 계산해서 우선순위 큐에 넣는다. 거리가 짧은 별자리들의 쌍이 항상 나오므로, 크루스칼 알고리즘으로 MST를 완성한다. import java.io.BufferedReader; import java.io.InputStreamReader; import java.util.Comparator; import java.util.PriorityQueue; import java.util...