본문 바로가기
728x90

알고리즘42

[cs 스터디] 운영체제 후기 5주차동안의 운영체제 스터디 후기를 작성하게 되었습니다! 1~3주차는 모두 열심히 참여했지만.. 4주차 ~ 5주차는 개인 이슈때문에 참석하지 못했습니다. 우선, 운영체제 스터디를 참여하면서 가장 좋았고 기억에 남는 것은 면접에 대한 피드백과 개발을 공부하는 사람들과의 소통을 할 수 있었다는 점입니다. 저는 개인적으로 면접을 체계적으로 준비해본 경험이 없었습니다. 제가 공부한 것들에 대해서 그저 정리만 하고 면접관이 질문하면 답만 하는 면접을 준비했었습니다. 하지만, 스터디를 통해서 면접관이 원하는게 무엇일까? 에 대해서 다시 한번 생각하게 되었고 다른 분들의 면접 시 장점, 저의 면접시 단점에 대해서도 알게 되었습니다. 이를 기반으로 면접을 볼 때 한층 더 높아진 자신감으로 접할 수 있을 거라는 확신이 .. 2024. 2. 15.
레드블랙트리 레드-블랙트리 - 이진탐색트리의 일종 - 균형잡힌 트리 : 높이가 o(logn) - search, insert, delete연산을 최악의 경우에도 o(logn)시간에 지원 - 각 노드는 하나의 키, 왼쪽 자식, 오른쪽 자식, 부모노드의 주소를 저장 - 자식노드가 존재하지 않을 경우 NIL노드라고 부르는 특수한 노드가 있다고 가정 - 결국 모든 리프노드는 NIL노드 - 루트의 부모도 NIL노드라고 가정 - 노드들은 내부노드와 NIL노드로 분류 * 실제로 구현할 때 NIL노드를 구현하지는 않음 레드-블랙 트리 -> 기본적으로는 이진탐색트리 1. 각 노드는 red 혹은 black 2. 루트노드는 black 3. 모든 리프노드는 black 4. red노드의 자식노드들은 전부 black -> red노드는 연속되어.. 2021. 5. 12.
멱집합 멱집합 : 주어진 집합의 모든 부분 집합들로 구성된 집합 data = {a,b,c,d} => 원소의 개수 : 2^4 = 16 ex) a,b,c,d,ab,ac.... *{a,b,c,d,e,f}의 모든 부분집합을 나열하려면 - a를 제외한 {b,c,d,e,f}의 모든 부분집합들을 나열하고 - {a,b,c,d,e,f}의 모든 부분집합에 {a}를 추가한 집합들을 나열한다. => {b,c,d,e,f}의 모든 부분집합에 {a}를 추가한 집합들을 나열하려면 - {c,d,e,f}의 모든 부분집합들에 {a}를 추가한 집합들을 나열하고 - {c,d,e,f}의 모든 부분집합들에 {a,b}를 추가한 집합들을 나열한다. 수도코드 - 처음에 p는 공집합, s는 전체 집합 - s가 공집합이 되면 끝난다 - s의 원소들을 하나씩 꺼.. 2021. 5. 5.
순환의 응용 : n queens problem - queen이 같은 행이나 열에 있으면 안됌 Backtracking - 진행하다가 막다른 길에 도달할 때 왔던 길을 되돌아가는 방법 *상태공간트리 - 상태공간트리란 찾는 해를 포함하는 트리 - 해가 존재한다면 그것은 반드시 이 트리의 어떤 한 노드에 해당함 -> 이 트리를 체계적으로 탐색하면 해를 구할 수 있음 * 상태공간 트리의 모든 노드를 탐색해야 하는 것은 아님 ex) 1번 말이 1,1에 있다면 2번말은 2,1과 2,2에는 갈 수가 없으므로 그 밑은 찾아볼 필요가 없다. => backtracking 기법 - 꽝인지 확인 -> 밑으로 내려갈 필요 x - 정답이라면 리턴 - 꽝이 아닌데 정답도 아니라면 -> queen함수를 다시 호출 - 성공인지 확인하는 방법 : 매개변수 값이 내가 놓고 싶은 말의 .. 2021. 5. 5.
순환의 응용 - 미로찾기 순환적 사고 - 현재 위치에서 출구까지 가는 경로가 있으려면 1. 현재 위치가 출구이거나 혹은 2. 이웃한 셀들 중 하나에서 현재 위치를 다시 오지 않고 출구까지 가는 경로가 있거나 미로찾기(Decision Problem) - 현재 위치가 출구이면 true 리턴 - 출구가 아니면 이웃한 셀들을 찾아보고 이훗한 셀들이 갈 수 있는 길이라면 셀들을 갖고 findPath 다시 호출 - 하지만 위의 코드로 구현하면 지금 방문한 셀이 왔던 곳인지 모르기 때문에 무한루프에 빠질 수 있음 따라서 방문했는지 안했는지를 알려줘야함 - 처음에 방문했다고 표시 - 이웃한 셀들 중 검사할 셀이 이미 방문했는지 확인한다. - 지금 셀이 벽인지와 방문했는지를 체크 - 지금 셀이 출구면 true리턴 - 출구가 아니면 방문한걸로 체.. 2021. 5. 5.
[백준 1654] 랜선 자르기 [java] 이분 탐색 문제로 풀었다. 이 문제에서 두 가지 주의할 점이 있는데 하나는 범위가 커서 long형으로 선언해야하는 점과 문제에서 랜선의 길이는 자연수라는 점이다. 우선 랜선의 길이는 1부터 주어진 랜선들 중 가장 긴 랜선의 길이가 될 수 있다. 따라서 1과 가장 긴 랜선의 길이의 평균 값을 기준으로 위아래로 찾아보면 된다. 코드 package baekjoon; import java.util.Scanner; public class cut_lanwire { public static void main(String[] args) { Scanner scan = new Scanner(System.in); int k = scan.nextInt(); long n = scan.nextLong(); long arr[] =.. 2021. 5. 4.
728x90

티스토리툴바