#INFO#SOLVE인접리스트 방식을 사용한 재귀 DFS 알고리즘을 사용해 풀이했다.main 함수에서 nodeList에 정점 (컴퓨터 정보) 과 연결된 간선 정보를 입력한다. 또한 문제의 요구사항은 1번 컴퓨터와 연결된 컴퓨터 노드의 수 이기에, 1번 컴퓨터만 DFS 로직을 실행한다. int main(){ // Input Logic ios::sync_with_stdio(0); cin.tie(0); cin >> computer_num >> computer_line; for (int i = 0; i > node1 >> node2; nodeList[node1].push_back(node2); nodeList[node2].push_back(node1); ..
#info#Solve최빈값 처리에서 상당히 애를 먹었던 문제이다. 각 변수의 역할은 다음과 같다. int N :입력받을 정수의 개수이다. (Max : 500,000)int sum : 입력받은 정수의 총 합을 저장할 변수이다. (산술평균 계산 시 사용)int arr[N] : 입력받은 정수의 정보를 저장할 배열이다. (중앙값 계산 시 사용)vector mode_candidates : 최빈값 후보를 저장할 베겉이다. 문제 조건 중 최빈값이 여러개 존재하는 경우 최빈값 중 두 번쨰로 작은 값을 출력하라는 조건이 있었기에 따로 후보 벡터를 선언해 두었다.int bindo[8001] : 정수가 몇 번 등장하는지 저장할 배열이다. 입력되는 정수의 절댓값은 4000을 넘지 않기에 -4000 ~ +4000 사이의 정수..
#Memory Visibility 메모리 가시성 (Memory Visibility) 문제는 멀티 스레드 환경에서 발생하는 특정 스레드에서 변경한 정보가 바로 다른 스레드에 보이지 않는 현상이다.이는 CPU 아키텍쳐 구조로 인해 발생한다. 메인 메모리로부터 직접 데이터를 불러오는 것은 CPU로부터의 거리가 멀리 떨어져 있기에 상대적으로 속도가 느리다. 따라서 CPU는 속도 향상을 위해 CPU 근처에 작은 크기의 캐시 메모리를 배치하여 속도를 향상시키는 구조를 채택한다. 자바 멀티 스레드 환경에서 또한 각 스레드는 고유의 캐시 메모리를 가진다. CPU 아키텍쳐와 동일하게 스레드는 메인 메모리로부터 직접 값을 읽는 대신, 스레드의 캐시 메모리로 값을 복사한 뒤 사용한다. #Memory Visibility E..
* STL 내부의 이진탐색 관련 메서드 사용법에 관해 정리한 글 입니다.→About Binary Search#1binary_search method#include bool binary_search(first, last, value); parameter Infofirst : 탐색 시작 위치 (시작 이터레이터) * 배열의 경우 시작 주소 last : 탐색 종료 위치 (종료 이터레이터) * 배열의 경우 마지막 주소value : 탐색 타깃 데이터 ▶ first ~ last 범위 내부에 타깃 데이터 (value) 가 존재하는지 O(LogN) 시간 복잡도로 탐색한다. ▶ 만약 타깃 데이터가 존재한다면 true를 반환하고, 타깃 데이터가 존재하지 않는다면 false를 반환한다.▶ 단, 원소가 정렬된 상태에서만 탐색..
#Infohttps://www.acmicpc.net/problem/1654#Logic만들 수 있는 최대 랜선의 길이를 구하는 문제이다.처음으로 가장 단순한 알고리즘인 브루트포스 방식으로 접근해 보았다. 1cm부터 랜선의 최대 길이만큼 반복문을 돌려서, 가능한 모든 경우를 계산하는 로직이다. 하지만 해당 방식은 시간 복잡도가 최소 O(N) 만큼 소모되며,랜선의 최대 길이는 2^31 - 1 이기에 절대로 시간제한 2초 안에 통과할 수 없다. 다음으로 이분탐색 풀이로 접근해 보았다.About Binary Search이분탐색 알고리즘은 시간 복잡도가 O(LogN) 만큼 걸리기에, 충분히 통과 가능하다. 우선, 랜선의 개수 K, 필요한 랜선의 개수 N을 입력 받은 뒤랜선의 길이 정보를 lines vector에 ..