코딩테스트 연습 - 전력망을 둘로 나누기 문제 바로가기 문제 설명 전체 전력망을 2개의 전력망으로 나눴을 때, 두 전력망(그래프)의 노드 개수 차이가 가장 최소가 되는 값을 반환해야 합니다. 따라서 그래프에 이어진 노드 개수 를 빠르게 파악하는 것이 중요하기 때문에 그래프 탐색 중 너비 우선 탐색(BFS)를 사용했습니다. 그리고 전력...

자료형을 변환할 때, C 언어는 암시적 형변환과 명시적 형변환 2가지가 존재합니다. 간략하게 설명하면 암시적 형변환은 컴파일러가 대신 수행하는 형변환이고 명시적 형변환은 반대로 프로그래머가 직접 형변환을 수행하는 것입니다. int i_num = 3.14; // 암시적 double d_num_01 = double(i_...

백준의 Sort 마스터 배지훈의 후계자라는 문제는 정렬과 탐색으로 간단히 풀 수 있는 문제였습니다. 저는 algorithm 라이브러리의 sort, find 함수를 통해 문제를 풀고자 하였습니다. 첫 번째 시도 (실패) #include <iostream> #include <algorithm> using namespace s...

코딩테스트 연습 - 퍼즐 게임 챌린지 문제 바로가기 문제 설명 해결 방법 숙련도의 최솟값을 찾아야 하므로 탐색 알고리즘을 이용하고자 하였습니다. 처음 사용한 탐색 알고리즘은 순차 탐색이였습니다. 순차 탐색은 \(O(N)\) 이라는 시간 복잡도를 갖지만, diffs 의 원소는 100’000 이하이므로 제한 시간 내 풀이가 가능하다고 ...

그래프는 다른 포스트에서 설명했던 트리처럼 노드와 간선을 사용하는 자료구조입니다. 그러나 트리와 전혀 다른 자료구조로 몇 가지 명확한 차이점이 존재합니다. 따라서 이번 포스트에서는 그래프가 무엇이고 그래프의 특징은 무엇이 있으며, 어디에서 사용하는지 알아보겠습니다. 그래프 (Graph) 그래프는 노드(Node, 혹은 버텍스(Vertex))와 ...

저번 포스트에서는 네트워크 통신을 위한 국제 통신 모델인 OSI 7 계층에 대해서 알아보았습니다. 이번 포스트에서는 OSI 7 계층의 3, 4 계층에 대해 조금 더 자세히 알아보겠습니다. 통신규약 모음 (Internet Protocol Suite) 인터넷에서 컴퓨터들이 서로 정부를 주고받는 데 쓰이는 통신규약(프로토콜) 모음 을 인터넷 프로토콜...

이 포스트는 백준 사이트의 로봇 청소기 문제 풀이입니다. 문제 코드 구현 문제에 주어진 로봇 청소기의 작업 순서를 코드에 그대로 표현하고자 하였습니다. 먼저, 현재 위치에서 is_dirty_tiles_left() 함수를 실행하여 지금 해야하는 작업을 실행합니다. 그리고 변경된 위치를 작업 큐에 넣는 것을 반복하여 큐가 빌 때 까지 반복...

자료형을 변환할 때, C 언어는 암시적 형변환과 명시적 형변환 2가지가 존재합니다. 간략하게 설명하면 암시적 형변환은 컴파일러가 대신 수행하는 형변환이고 명시적 형변환은 반대로 프로그래머가 직접 형변환을 수행하는 것입니다. int i_num = 3.14; // 암시적 double d_num_01 = double(i_...

코딩테스트 연습 - 여행 경로 문제 바로가기 문제 해결 방법 문제 조건에서 주어진 티켓을 모두 사용할 수 있다고 보장하였으므로 완전 탐색 중 깊이 우선 탐색(DFS)를 사용해 문제를 해결하고자 하였습니다. 탐색을 진행하기 전, 티켓을 중복해서 사용할 수 없으므로 이용한 공항을 기록하고자 하였습니다. 문자열을 key 값으로 한 해시 ...

이진 트리의 약점 이전 포스트에서 이진 트리에 대해 설명했었습니다. 그리고 이진 트리의 약점으로 모든 노드가 1개의 자식만 갖게되어 일렬로 만들어진 트리가 있었습니다. 이 트리의 이름은 편향 이진 탐색 트리라고 부릅니다. [편향 이진 탐색 트리] 이러한 트리를 개선하고자 만들어진 자료 구조가 균형 이진 탐색 트리 입니다. 이진 트리가 균...