분류 전체보기

투 포인터 알고리즘은 주로 수열의 연속된 값들의 합을 다룰 때 사용되는 알고리즘이다. 여기서 두 개의 포인터란 말 그대로 시작점과 끝 점을 포인터로 잡아 해당 포인터들이 움직이면서 동작을 수행해준다. 백문이불여일견. 이미지로 한 번 살펴보자 동작 방식 우리가 배열에서 연속된 값의 합이 5가 될 때의 경우를 찾고 싶다고 가정해보자. 물론 반복문을 두 번 중첩시켜 모든 배열의 값들에 대해 완전탐색을 진행할수도 있지만, 그러한 방식은 O(n^2) 만큼의 시간이 소요된다. 배열이 커지면 커질수록 연산시간은 기하급수적으로 증가할 것이다. 따라서 사용되는 방식이 이 글에 포스팅하는 투 포인터 방식이다. 앞서 설명한 것과 마찬가지로, 투 포인터 방식에선 start와 end라는 두 개의 포인터를 정의해준다. 처음엔 두..

예전에 지금보다 더 코린이일 때, 카카오 코딩테스트 기출문제를 호기심에 풀어보다가 첫 문제부터 막힌 기억이 생생하다. 정답률이 무려 80%가 넘는 쉬운 문제였는데, 우리가 흔히 사용하는 10진수의 숫자를 2진수 형태로 바꿔주면 바로 풀 수 있는 간단한 문제였다. 물론 내가 부족하다는 게 가장 주된 이유이지만, 함수를 모른다는 이유로 문제를 풀지 못하면 꽤 억울하다. 그 때의 억울함을 추억하며 이 내용을 정리해보자. 파이썬의 공식 문서에 등록되어 있는 bin()의 사용법은 다음과 같다. 어려운 내용이 아니다. 정수형 숫자를 파라미터로 bin(x)에 넘겨주게 되면, 해당 숫자에 맞는 2진수 숫자를 리턴해준다. print(bin(10)) 10을 2진수로 바꿔주면 다음과 같은 결과가 출력된다. 재미있는 점은 이..

문제 (링크) https://www.acmicpc.net/problem/4948 4948번: 베르트랑 공준 베르트랑 공준은 임의의 자연수 n에 대하여, n보다 크고, 2n보다 작거나 같은 소수는 적어도 하나 존재한다는 내용을 담고 있다. 이 명제는 조제프 베르트랑이 1845년에 추측했고, 파프누티 체비쇼 www.acmicpc.net 나의 풀이 첫 번째 풀이 import sys import math data = [] while True: n = int(sys.stdin.readline()) # 입력값이 0이 아닐때까지 입력값을 data배열에 저장 if n == 0: break else: data.append(n) def is_prime_count(x, y): # x이상 y이하의 수 중 소수인 것의 개수 리..

문제 (링크) https://www.acmicpc.net/problem/1929 1929번: 소수 구하기 첫째 줄에 자연수 M과 N이 빈 칸을 사이에 두고 주어진다. (1 ≤ M ≤ N ≤ 1,000,000) M이상 N이하의 소수가 하나 이상 있는 입력만 주어진다. www.acmicpc.net 나의 풀이 import math m, n = map(int, input().split()) arr = [True for _ in range(n+1)] for i in range(2, int(math.sqrt(n)) + 1): if arr[i] == True: j = 2 while i * j 1: if arr[i] == True: print(i) 접근 방법 및 코드 설명 낮에 공부했었던 에라토스테네스의 체를 사용하는..

알고리즘 문제를 풀다보면 특정 수들이 소수인지 판단하도록 요구하는 문제들이 줄곧 있다. 아예 대놓고 소수찾기라는 문제만 쳐봐도 꽤 많은 문제들이 나올 것이다. 소수는 영어로 Prime Number라고 부르며 1과 자기자신 외에는 어떠한 수로도 나누어 떨어지지 않는 수를 말한다. 특정 수 N이 소수인지 아닌지 구하는 법은 바로 이 특징을 활용하여 2부터 N-1 까지의 수로 해당 수를 나눠보고, 이 과정에서 어떠한 수에 의해 나누어 떨어지는지 확인하는 것이다. 나누어떨어지지 않는다면 해당 수는 소수인 것이고, 도중에 다른 수에 의해 나누어 떨어진다면 그 수는 소수가 아닐 것이다. 이를 코드로 표현하면 다음과 같다. def is_prime_num(n): for i in range(2, n): if n % i ..

힙이란? 힙은 트리 형태로 만들어진 자료구조 중 하나이다. 힙은 트리 중에서도 두 가지 조건을 만족해야 하는데, 첫 번째는 완전이진트리여야 한다는 것 두 번째는 부모 노드의 값이 항상 자신의 자식노드들보다 커야한다는 것이다. (힙의 예시) 위 트리는 트리의 높이 - 1 까지 모두 빈 노드 없이 차 있으며 마지막 높이의 데이터들 역시 왼쪽부터 오른쪽으로 차례대로 채워져있으므로 완전이진트리의 속성을 만족시킨다고 할 수 있다. 또한, 모든 노드들이 자신의 자식노드들보다 큰 값을 가지기 때문에 힙의 성질 역시 만족시킨다고 할 수 있겠다. 힙 자료구조의 구현 힙 자료구조는 기본적으로 완전이진트리이기 때문에, 특정 노드의 위치를 알면 그 노드의 부모 노드의 위치와 두 자식 노드의 위치를 알 수 있다. 이를 활용하면..

1) 이진트리 이진트리는 부모 하나 당 최대 2개까지의 자식노드를 가질 수 있는 트리를 말한다. 따라서 이진트리의 각 노드 인스턴스는 자신의 부모 노드에 대한 레퍼런스와 두 자식노드에 대한 레퍼런스를 가지게 된다. 이진트리의 노드 클래스를 구현하면 다음과 같다. # 이진트리의 노드 class Node: def __init__(self, data): # 파라미터로 받은 데이터를 삽입 self.data = data # None으로 초기값을 지정 후, 노드 생성 후에 지정 self.left_child = None self.right_child = None 이후, 각 데이터를 담은 노드 클래스를 만들어주고 자식 관계를 설정해주고 나면 노드를 통해 그 노드의 부모노드와 자식노드를 모두 호출할 수 있게 된다. 2)..

문제 (링크) https://www.acmicpc.net/problem/1463 1463번: 1로 만들기 첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 정수 N이 주어진다. www.acmicpc.net 나의 풀이 n = int(input()) d = [0] * 1000001 for i in range(2, n+1): d[i] = d[i-1] + 1 if i % 2 == 0: d[i] = min(d[i], d[i//2] + 1) if i % 3 == 0: d[i] = min(d[i], d[i//3] + 1) print(d[n]) 나동빈님의 유튜브 이.코.테 다이나믹 프로그래밍 강의를 들은 후 연습 문제로 풀어보았다. 사실 유튜브에서 제공한 연습문제랑 연산 조건만 다를 뿐 아예 같은 문제라고 봐도 ..