전체 글
-
[백준 7568번] 덩치Coding Test/백준 2021. 3. 19. 03:16
# 문제 내 풀이 n = int(input()) # 사람들의 덩치 정보 입력 받기 people = [tuple(map(int, input().split())) for _ in range(n)] # 현재 사람의 덩치를 다른 모든 사람들과 비교하여 for i in range(n): rank = 1 # 만일 현재 사람보다 덩치가 큰 사람이 있다면, rank를 1 증가시킴 for j in range(n): if people[i][0] < people[j][0] and people[i][1] < people[j][1]: rank += 1 # 현재 사람의 등수 출력 print(rank, end=' ') 생각해볼 점 처음엔 입력 수가 많지 않아 조건에 맞춰 bubble sort를 한 후, 정렬된 정보대로 차례차례 비..
-
[백준 1806번] 부분합Coding Test/백준 2021. 3. 16. 23:20
# 문제 내 풀이 n, s = map(int, input().split()) data = list(map(int, input().split())) min_len = int(1e5) # 구하고자 하는 부분 수열 중 가장 짧은 것의 길이 interval_sum = 0 # 현재 부분 수열의 부분합 end = 0 # 투 포인터 알고리즘 수행 # start를 차례대로 증가시키며 반복 for start in range(n): # end를 가능한 만큼 이동시키기 while interval_sum = s and end - star..
-
[백준 2470번] 두 용액Coding Test/백준 2021. 3. 13. 01:49
# 문제 내 풀이 n = int(input()) data = list(map(int, input().split())) min_val = 2 * int(10e9) # 혼합 용액의 최소 특성값 left = 0 right = n - 1 data.sort() # 오름차순 정렬 # 양 끝의 포인터가 엇갈리기 전까지 while left < right: # 현재 가리키는 두 용액의 특성값 합이 최소 특성값이라면 최솟값 갱신 if abs(data[left] + data[right]) < min_val: min_val = abs(data[left] + data[right]) min_pair = (data[left], data[right]) # right가 가리키는 특성값의 절대값이 더 크다면 right를 1 감소시킴 i..
-
[백준 3273] 두 수의 합Coding Test/백준 2021. 3. 10. 20:53
# 문제 내 풀이 - 문제 풀이 실패, 수정 답안 n = int(input()) nums = list(map(int, input().split())) x = int(input()) cnt = 0 # (ai, aj) 쌍의 갯수 left = 0 # 왼쪽 인덱스 right = n - 1 # 오른쪽 인덱스 nums.sort() # 오름차순으로 정렬 수행 # 두 포인터가 교차할 때까지 while left x: right -= 1 continue l..
-
[알고리즘] 투 포인터 (Two Pointers)Computer Science/자료구조 & 알고리즘 2021. 3. 8. 00:33
# 투 포인터 (Two Pointers) 알고리즘 투 포인터(Two Pointers) 알고리즘은 리스트에 순차적으로 접근해야 하는 경우에, 두 개의 점의 위치를 기록하면서 처리하는 방식을 말한다. 시작점과 끝점을 사용해 순차적으로 접근할 데이터의 범위를 표현할 수 있다. 투 포인터를 활용하면 유용한 다음 문제를 살펴보자. 위 문제는 전체 수열이 주어지면, 그 수열의 부분 수열 중 특정한 합을 가지는 연속하는 부분 수열을 찾는 문제이다. 이 문제를 해결하는 가장 심플한 방법은 완전탐색으로 각 인덱스마다 해당 인덱스로 시작하는 부분 연속 수열을 모두 찾아보는 방법이다. 다만, 이 완전탐색은 시간 복잡도가 O(N²)이 걸리므로 비효율적이다. 이 때, 투 포인터 알고리즘을 활용하면 선형 시간 복잡도 O(N)으로..
-
[백준 4948번] 베르트랑 공준Coding Test/백준 2021. 3. 6. 22:09
# 문제 내 풀이 - 시간 초과, 수정 답안 n = 123456 * 2 # 2부터 (2 * 123456)까지의 모든 수에 대하여 소수 판별 # 처음엔 모든 수를 소수(True)인 것으로 초기화(0, 1은 제외) array = [True for _ in range(2 * n + 1)] # 에라토스테네스의 체 알고리즘 수행 # 2부터 2n의 제곱근까지의 모든 수에 대하여 for i in range(2, int((2 * n) ** 0.5) + 1): if array[i] == True: # i를 제외한 i의 모든 배수를 지우기 j = 2 while i * j 1 and array[i]: cnt += 1 # 개수 출력 print(cnt) 생각해볼 점 에라토스테네스의 체의 시간복잡도가 매우 빠르긴 하지만, 테스트..
-
[백준 1929번] 소수 구하기Coding Test/백준 2021. 3. 4. 23:43
# 문제 내 풀이 m, n = map(int, input().split()) # 처음엔 모든 수를 소수(True)인 것으로 초기화(0, 1은 제외) array = [True for i in range(n + 1)] # 에라토스테네스의 체 알고리즘 수행 # 2부터 n의 제곱근까지의 모든 수를 확인하며 for i in range(2, int(n ** 0.5) + 1): if array[i] == True: # i를 제외한 i의 모든 배수를 지우기 j = 2 while i * j 1 and array[i]: print(i) 생각해볼 점 마지막 출력에서 1을 거르는 조건을 생각하지 못해 오래 걸렸다. 예외 케이스를 항상 염두하자.
-
[OS] 9-2. Virtual MemoryComputer Science/운영체제 2021. 3. 4. 02:05
# Page replacement - 다양한 캐슁 환경 - 캐슁 기법 한정된 빠른 공간(=캐쉬)에 요청된 데이터를 저장해 두었다가 후속 요청시 캐쉬로부터 직접 서비스하는 방식이다. 즉, 한 번 썼던 데이터는 빠른 접근이 가능한 캐쉬 메모리에 저장해두었다가 가까운 시기에 해당 데이터에 대한 접근이 요청되면 빠르게 제공해준다. Paging system과 더불어 cache memory, buffer caching, Web caching 등 다양한 분야에서 사용되는 방식이다. - 캐슁 기법의 운영상 시간 제약 다만, 이러한 캐슁 기법은 운영상 시간 제약이 존재한다. 교체 알고리즘이 삭제할 항목을 결정하는 일에 지나치게 많은 시간을 소요하지 않아야 한다. 예를 들어, Buffer caching이나 Web cach..