본문 바로가기

반응형

Computer

(114)
하드웨어와 네트워크 시스템 기반에서 가장 하위 레이어를 구성하는 요소는 하드웨어와 네트워크입니다. 이번 포스트에서는 온프레미스 시스템 혹은 클라우드 시스템을 구축하기 위한 하드웨어와 네트워크의 기본 지식을 알아보도록 하겠습니다. 서버 장비 CPU (Central Processing Unit) CPU란 프로그램의 처리를 수행하는 시스템의 핵심적인 부품으로 작동 주파수가 크거나 코어가 많아질 수록 연산 능력이 높아집니다. 하드웨어의 발전에 힘입어 최근 대부분의 서버는 멀티 코어를 사용합니다. 또한, CPU는 프로그램의 처리를 위해 메모리에 접근하게 되는데, 메모리와의 처리 속도 차이를 완화할 목적으로 캐시를 사용합니다. CPU는 입출력장치, 기억장치, 연산장치 등의 컴퓨터 리소스를 활용하여 멀티 태스킹을 위한 작업들의 우선순위..
코딩테스트 문제 (26) - 최대 공약수, 최소 공배수 이번 포스트에서는 최소공약수, 최대공배수를 구하는 방법을 알아보겠습니다. 최대 공약수 최대 공약수는 2개의 자연수를 각각 나누어서 나머지가 0이 되는 최대 자연수를 말합니다. 간단하게 2개의 자연수를 받아 2부터 작은 자연수까지 모두 나누어보면 구할 수 있지만 $O(N)$의 시간 복잡도가 소요됩니다. 유클리드 호제법을 사용하면 $O(\log N)$ 에 최대 공약수를 구할 수 있습니다. 유클리드 호제법 유클리드 호제법은 인류사에서 가장 오래된 알고리즘 중 하나로 알려져 있는 알고리즘입니다. 2개의 자연수 a, b (a > b) 에 대해서 a를 b로 나눈 나머지를 r이라 하면 a와 b의 최대 공약수는 b와 r의 최대 공약수와 같습니다. (GCD(a,b) = GCD(b, a%b)) a, b의 최대공약수를 g라..
코딩테스트 문제 (25) - 텀 프로젝트 문제 1. p = [3,1,3,7,3,4,6], N = 7 => 3 2. p = [1,2,3,4,5,6,7,8], N = 8 => 0 풀이 입력을 통해 그래프를 구성하고 사이클에 속하지 않은 정점들의 개수를 출력하는 문제입니다. DFS를 통해 노드를 재귀적으로 방문하면서 리스트를 채워주고 이미 방문한 정점에 도달했을 때, 그 시작점부터의 리스트를 반환하면 사이클에 속한 정점을 구할 수 있습니다. 이를 전체 노드 수에서 빼주면 답을 구할 수 있습니다. kaggle.com의 notebook으로 작성한 풀이는 다음과 같습니다. 홍머스 정리 난이도: 중 DFS를 이용한 그래프 사이클 판별 참조 claude-u.tistory.com/435 www.acmicpc.net/problem/9466
코딩테스트 문제 (24) - 순열 사이클 문제 1. p = [3,2,7,8,1,4,5,6] => 3 2. p = [2,1,3,4,5,6,7,9,10,8] => 7 풀이 입력으로 들어온 순열로 그래프를 구성하고 그래프 내의 사이클의 개수를 출력하는 문제입니다. DFS를 통해 문제를 해결할 수 있습니다. 매 노드에 대해 DFS 함수를 호출하고 방문 노드를 기록합니다. 사이클이라면 DFS가 종료되고 방문하지 않은 다음 노드에 대해 DFS를 호출합니다. 호출한 DFS 횟수마다 카운트 하면 전체 사이클 개수를 얻을 수 있습니다. kaggle.com의 notebook으로 작성한 풀이는 다음과 같습니다. 홍머스 정리 난이도: 중 DFS, 사이클 판별 참조 www.acmicpc.net/problem/10451
코딩테스트 문제 (23) - 방향 그래프에서 사이클 찾기 방향 그래프에서 사이클이란 특정 정점에서 시작해 어떠한 경로를 지나 다시 그 정점으로 돌아오는 경로를 말합니다. 무방향 그래프에서는 서로소 집합으로 사이클을 판별할 수 있습니다. 반면, 방향 그래프에서는 어떻게 사이클이 있는지 판별할까요? DFS는 깊이우선탐색입니다. DFS를 이용해 그래프를 탐색하게 되면 해당 시작 정점에서 갈 수 있는 모든 정점을 방문한 뒤 종료됩니다. 이를 이용해 시작점과 방문점으로 이루어진 DFS 함수를 구성하여 시작점과 방문점이 같은 경우 사이클이 존재한다고 판단할 수 있습니다. 다음 그래프는 4,6,7 노드 간 사이클이 존재합니다. 이 그래프에 대해 사이클이 존재하는지에 대한 코드는 다음과 같습니다. 시간 복잡도 일단 DFS를 수행하는 것은 모든 정점을 방문하고 모든 간선을 방..
코딩테스트 문제 (22) - 랜선 자르기 문제 1. Ks = [802, 743, 457, 539], N = 11 => 200 풀이 K개의 랜선의 길이가 주어졌을 때, N개의 랜선을 만들 수 있는 가장 큰 랜선 자르는 길이를 구하는 문제입니다. 간단히 생각해보면 랜선을 자르기 위한 최대 길이는 배열 중 가장 긴 랜선이고 최소 길이는 1입니다. 즉, 1과 가장 긴 랜선 사이에 N을 만족하는 최대값을 구하면 되는 문제입니다. 이렇게 넓은 범위에서 특정 값을 찾는 문제는 이진 탐색 방법으로 풀 수 있습니다. Left, right를 양 끝으로 정하고 가운데를 탐색해서 그 가운데 값으로 랜선을 잘랐을 때 N보다 작으면 더 작은 값이 필요하니 right를 가운데로 옮기고 반대의 경우는 left를 가운데로 옮깁니다. Left를 가운데로 옮길 때 최대값을 계속..
코딩테스트 문제 (21) - 가장 긴 팰린드롬 부분문자열 문제 가장 긴 팰린드롬 부분문자열 (substring)을 출력하는 문제입니다. 1. 'babad' => 'aba' or 'bab' 2. 'cbbd' => 'bb' 풀이 생각해보면 가장 작은 팰린드롬은 2글자 아니면 3글자가 될 수 있습니다. 그렇다면 2칸, 3칸으로 이루어진 슬라이딩 윈도우를 구성하고 이를 왼쪽에서부터 이동시키면서 팰린드롬이면 양쪽의 칸을 한 칸씩 확장하여 팰린드롬인지 확인합니다. 확장한 후 팰린드롬을 확인할 때, 전체를 볼 필요 없이 양 끝값이 같으면 팰린드롬이라고 간단히 판단할 수 있습니다. 이런 방식으로 확장시키면서 팰린드롬일 경우 계속 저장해서 길이가 긴 문자열을 추출하면 되는 문제입니다. kaggle.com의 notebook으로 작성한 풀이는 다음과 같습니다. 홍머스 정리 난이도..
itertools 모듈 이번 포스트에서는 파이썬의 itertools 내장 모듈에 대해 알아보려고 합니다. itertools는 효율적인 반복을 위한 반복기 빌딩 블록을 generator를 이용한 iterator 형태로 구성하여 빠르고 효율적으로 메모리를 사용할 수 있습니다. itertools 모듈의 자주 쓰이고 중요한 메소드에 대해 알아보겠습니다. 무한 이터레이터 무한으로 반복할 수 있는 메소드입니다. 보통 여기에 속하는 메소드들은 종료 조건을 파라미터로 따로 명시합니다. count(start=0, step=0) 끝나는 지점이 정해지지 않은 range 라 생각하면 편합니다. start와 step만 인수로 주어지기 때문에, 길이가 정해진 다른 리스트와 보통 같이 사용합니다. cycle() 주어진 인자에서 요소를 반환하면서 요소의 ..

반응형