알고리즘

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

문제 (링크) 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 ..

문제 (링크) 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]) 나동빈님의 유튜브 이.코.테 다이나믹 프로그래밍 강의를 들은 후 연습 문제로 풀어보았다. 사실 유튜브에서 제공한 연습문제랑 연산 조건만 다를 뿐 아예 같은 문제라고 봐도 ..

문제 (링크) https://www.acmicpc.net/problem/1978 1978번: 소수 찾기 첫 줄에 수의 개수 N이 주어진다. N은 100이하이다. 다음으로 N개의 수가 주어지는데 수는 1,000 이하의 자연수이다. www.acmicpc.net 나의 풀이 n = int(input()) data = list(map(int, input().split())) count = 0 for x in data: for i in range(2, x+1): if x % i == 0: if x == i: count += 1 break print(count) 백준에서 틀린 문제를 살펴보다가 발견한 문제다. 왜 그랬는지는 모르겠는데 꽤 많이 틀려놨었고, 발견하자마자 풀어봤는데 바로 풀렸다. 알고리즘 문제 중 소수와..

문제 (링크) https://www.acmicpc.net/problem/1920 1920번: 수 찾기 첫째 줄에 자연수 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 줄에는 N개의 정수 A[1], A[2], …, A[N]이 주어진다. 다음 줄에는 M(1 ≤ M ≤ 100,000)이 주어진다. 다음 줄에는 M개의 수들이 주어지는데, 이 수들 www.acmicpc.net 나의 풀이 from sys import stdin n = stdin.readline() # 이진탐색을 진행해야하므로 탐색을 할 리스트를 sorted 처리 해준다 group_n = sorted(list(map(int, stdin.readline().split()))) m = stdin.readline() group_m = list(map..

대부분의 프로그래밍 언어에 내장된 정렬 함수들은 이 퀵 정렬 알고리즘과 병합 알고리즘을 기반으로 만들어졌다. 그 중 하나인 퀵 정렬 알고리즘에 대해 학습해보자. 선택 정렬, 삽입 정렬이 데이터들을 순차적으로 비교하는 것과 다르게, 퀵 정렬 알고리즘에선 기준 데이터(Pivot)를 설정해 해당 값보다 큰 데이터와 작은 데이터의 위치를 바꾸는 방식으로 정렬을 수행한다. 퀵 정렬 알고리즘이 작동하는 방식의 순서도는 다음과 같다. 1. 비교 기준이 될 pivot 인덱스를 설정한다. (기본적인 퀵 정렬 알고리즘에선 배열의 맨 처음 값을 pivot으로 설정한다.) 2. arr[pivot]부터 왼쪽부터 +1 씩 순차적으로 이동하며 arr[pivot]보다 큰 값을 찾는다. 3. 배열의 맨 뒤 값부터 순차적으로 -1 씩 ..