Disjoint Set 특징 그룹이 있다. 각 그룹은 공통된 요소들이 없다. (상호 배타적) 원소가 어떤 그룹에 속해있는가? (Find) 2개의 그룹을 어떻게 합칠 것인가? (Union) 특징에 대한 구체화 그룹이 있다 = 그룹을 특정할 수 있는 "그룹명"은 무엇으로 할까? = 그룹의 창시자 OR 임의 지정으로 (특정 원소 = 그룹의 상징 = Root)을 만든다. 각 그룹은 공통된 요소들이 없다. (상호 배타적) = 복잡도가 낮다. = 오직 하나의 Root를 가지고 있다. 원소가 어떤 그룹에 속해있는가? (Find) = Root를 찾으면 된다. How? = 최상위 부모까지 올라간다. = 따로 Root를 저장할 수도 있다. 2개의 그룹을 어떻게 합칠 것인가? (Union) = 그룹의 Root를 찾는다. =..
코딩 테스트를 풀 때 생각해야 하는 것들 STL를 적극적으로 활용하자 Vector를 당연하고 set이나 map, queue, stack 등의 자료구조를 사용할 방법이 있는지 생각해보자 보통 사용하면 문제가 쉽게 풀리도록 만들어 놓는다. 그리드 문제일 수도 있다는 생각을 하자 문제를 보고 바로 정렬이나 완전 탐색으로 풀 수 있겠다고 생각이 들어도 1번 더 생각하자. 탐욕법으로 보다 간단하게 풀 수 있는 방법이 존재할 수 있다. 있다면 그게 맞는 방법일 테니까
큰 수 만들기 고려할 점 1,000,000 이하라는 큰 수 입력으로 준다. = 효율을 확인한다는 의미 순서가 섞이지 않는다. = 최적화를 할 수 있는 부분 내가 만든 코드 #include #include using namespace std; string solution(string number, int k) { string answer = ""; int size = number.size() - k; int maxIndex = 0; char maxNum = '\0'; for(int i = 0; i < size; i++){ maxNum = '\0'; for(int j = maxIndex; j maxNum){ maxNum = number[j]; maxIndex = j; } } answer += maxNum; ..
모음사전 고려할 점 규칙이 뭔지 생각하는 게 유일한 포인트 반복문만으로도 만들 수 있을 것 같지만 복잡함 출제 의도가 있을거란 생각에 그려보니 트리구조와 동일하다는 특징! 내가 만든 코드 #include #include #include using namespace std; string origin = "AEIOU"; string strAnswer = ""; int count = 0; int num = 0; void dfs(int length, string str){ if(length >= 5) return; for(int i = 0; i < 5; i++){ str += origin[i]; count++; if(str == strAnswer){ num = count; } dfs(length + 1, str..
전력망을 둘로 나누기 고려할 점 각 간선이 끊어졌을 때를 생각해야 함 개수만 알면 되니까 dfs를 1번 노드에 1번만 해도 가능 내가 만든 코드 #include #include #include using namespace std; void dfs(int here, vector& visited, vector& checked, vector& wires){ int size = wires.size(); checked[here-1] = true; visited[here-1] = true; for(int i = 0; i < size; i++){ if(wires[i][0] == here){ int there = wires[i][1]; if(visited[there-1] == false){ dfs(there, visi..
소수 찾기 고려할 점 소수를 찾아야 한다 = 소수 찾기 함수 제작 숫자를 문자로 준다 = 직접 해보니 문자로 받는 게 더 편했다 = stoi 함수 사용 총 N개의 숫자에서 1~R 개의 숫자를 뽑아서 순열을 어떻게 만들 것인가? = 재귀함수와 Set 자료구조를 같이 사용해 해결 내가 만든 코드 #include #include #include #include #include #include using namespace std; set mySet; bool IsPrime(string str_num) { if(str_num[0] == '\0'){ return false; } int num = stoi(str_num); int index = (int)sqrt(num) + 1; if(num < 2){ return ..
next_permutation 함수 순열이란 n개 중에서 r개를 선택해 나열하는 모든 경우의 수이다. (순서 상관있음) nPr = n! / (n - r)! 예를 들어 5개 중에 5개를 뽑아서 나열하는 모든 경우의 수는 5! = 120이다. template bool next_permutation ( BidirIt first, BidirIt last ); #include 해야 함 현재 순열에 대하여 다음 순열을 반환한다. 다음 순열을 어디로 반환하는가? = 원본을 바꿔버린다. 현재 순열 값을 확인하고 다음 순열을 반환하기 때문에 처음부터 끝까지의 순열을 가지고 싶다면 정렬된 상태에서 시작해야 한다. BidirIt는 아마 Bidirectional Iterator를 의미하는 듯 2번째 인자로 비교 함수를 넣을 ..
EQS Node Test와 Context Test란 환경 쿼리 시스템(EQS)에서 Generator로 생성된 여러 아이템 중 Context를 참고해 Test를 수행하여 가장 최적의 아이템을 선정할 수 있다. 여러 Test를 같이 사용하여, 아이템의 범위를 효과적으로 줄여 아이템을 선정할 수 있다. Test는 2가지 사용 방법이 있는데, Score와 Filter 또는 둘다 선택할 수 있다. 아이템에 가중치를 부여하거나 필터링하는 2가지 사용 방법이다. Common Test - Distance 거리를 측정하는 Context + Text Mode(1차원, 2차원, 3차원) 각각의 Item과 선택한 위치의 거리를 반환한다. Common Test - Trace 내용Trace Channel + Context 트레이..
네트워크 계층 모델 계층 모델 표현 7계층, 5계층, 4계층 등 여러개가 있는 것 같지만 모두 같음 각 계층들은 같은 계층끼리만 통신가능 상위 계층에서 하위 계층으로 내려갈 때, 계층마다 고유한 헤더를 붙인다. (캡슐화) OSI 7 계층 모델 5계층 모델 TCP/IP 모델 Application Layer Application Layer Application Layer Presentation Layer Session Layer Transport Layer Transport Layer Transport Layer Network Layer Network Layer Network Layer DataLink Layer DataLink Layer Network Access Layer Physical Layer Ph..
통신과 네트워크, LAN, IP 통신과 네트워크 통신 = 데이터를 다른 쪽으로 전달하는 것 ex) 모스부호, 무전기, 전화, TV등 네트워크 = 여러대의 컴퓨터가 데이터를 주고 받을 수 있는 통신 시스템 네트워크 구성 = 물리적인 연결(통신 연결) + 통신 약속(프로토콜) 거리에 따른 네트워크 분류 인터넷이라 말하는 것 = WAN WiFi같은 작은 지역 네트워크 = LAN 초근거리 통신 = NFC (짧다) NFC < PAN < LAN < MAN < WAN (길다) 통신 대상에 따른 네트워크 분류 1 대 1 = Unicast 1 대 다수 (불특정 다수) = Broadcast 1 대 다수 (특정 다수) = Multicast LAN Topology (구조) LAN 네트워크를 구성하는 여러 배치 구조가 존재 e..
