본문 바로가기

알고리즘

 (6)
[코스모스 4주차] 이분탐색 알고리즘 1. 이분탐색? 이분 탐색은 정렬되어 있는 리스트에서 탐색 범위를 절반씩 좁혀가며 데이터를 탐색하는 방법 이분 탐색은 배열 내부의 데이터가 정렬되어 있어야만 사용할 수 있음 변수 3개(start, end, mid)를 사용하여 탐색 찾으려는 데이터와 중간점 위치에 있는 데이터를 반보적으로 비교해서 원하는 데이터를 찾는 것이 이진탐색의 과정 시간 복잡도 : O(log₂N) 예를들어, 처음 데이터의 개수가 32개라면, 이론적으로 1단계를 거치면 약 16개의 데이터가 남고, 2단계에서 약 8개, 3단계에서 약 4개의 데이터만 남게됨 이진 탐색은 탐색 범위를 절반씩 줄이고, O(log₂N)의 시간복잡도를 보장 2. 이분탐색 알고리즘 https://www.acmicpc.net/problem/1920 1920번: 수..
[코스모스 4주차] 이분 탐색 알고리즘 "import sys" sys = system, stdin = standard input, readline = 한 줄씩 입력받기 input : 무조건 문자열로 입력받음 정수를 입력해도 따로 int(input()) 해 줘야 함 → input 함수는 매 호출마다 한 줄씩 읽고 문자열로 반환하는데, sys.stdin.readline()은 개행 문자를 포함한 한 줄을 읽고 문자열로 반환하여 대규모 입력 처리 시 효율적임 이분 탐색 (Binary Search)이란 내 코드 import sys # system specific parameters and functions -> 파이썬 인터프리터를 제어할 수 있는 방법 제공 n = int(sys.stdin.readline()) nums = list(map(int, sy..
[코스모스 4주차] 이분탐색 알고리즘 이분탐색 알고리즘이란? 정렬되어 있는 리스트에서 탐색 범위를 절반씩 좁혀가면서 데이터를 탐색하는 방법!배열 내부의 데이터가 정렬되어 있어야만 사용할 수 있는 알고리즘이다. 푸는 방식은?1. 집합을 정렬시킨다. 2. 시작과 끝 지점의 index를 지정한다. 3. 시작과 끝 인덱스를 사용해서 중간 인덱스를 구한다. 4. 중간 지점의 값과 element를 비교한다. 여기에서!두 값이 동일하다면 값을 찾은 것이다.element > 중간 이면 중간 보다 윗부분에서 탐색을 진행한다.element 위 과정을 성공할 때까지 반복하게 된다.  위 풀이 방법을 사용해 백준 1920번 수 찾기를 푼 코드from sys import stdin, stdoutn = stdin.readline()N = sorted(map(int,..
[코스모스 2주차] 브루트포스 알고리즘 1. 브루트포스? 완전 탐색 알고리즘 가능한 모든 경우의 수를 모두 탐색하면서 요구조건에 충족되는 결과만을 가져옴 예외 없이 100% 확률로 정답만 출력 알고리즘을 설계하고 구현하기 매우 쉬움 복잡한 알고리즘 없이 빠르게 구현 가능 알고리즘의 실행 시간이 매우 오래 걸림 메모리 효율면에서 매우 비효율적 단계 모든 가능한 해 검사 해 검증 최적 해 선택 또는 모든 해 반환 2. 브루트포스 알고리즘 https://www.acmicpc.net/problem/19532 19532번: 수학은 비대면강의입니다 정수 $a$, $b$, $c$, $d$, $e$, $f$가 공백으로 구분되어 차례대로 주어진다. ($-999 \leq a,b,c,d,e,f \leq 999$) 문제에서 언급한 방정식을 만족하는 $\left(x..
[코스모스 2주차] 브루트 포스 알고리즘 https://www.acmicpc.net/problem/19532 19532번: 수학은 비대면강의입니다 정수 $a$, $b$, $c$, $d$, $e$, $f$가 공백으로 구분되어 차례대로 주어진다. ($-999 \leq a,b,c,d,e,f \leq 999$) 문제에서 언급한 방정식을 만족하는 $\left(x,y\right)$가 유일하게 존재하고, 이 때 $x$와 $y$가 각각 $- www.acmicpc.net 나만의 해결 방안!! a, b, c, d, e, f = map(int, input().split()) # 위 입력 방식은 너무... 기본적인 것... split으로 띄어쓰기하여 받은 스트링을 잘라서 인트로 받아 온 후 각 변수에 할당해 줌!! for i in range(-999, 1000): ..
[코스모스 2주차] 브루트포스 알고리즘 Brute Force Algorithm 브루트 포스 알고리즘이란 이름 그대로 무식한 힘으로 가능한 모든 경우의 수를 탐색하면서 요구조건에 충족되는 결과만을 가져오게 된다. 따라서 무조건 정답만을 출력하게 된다는 장점이 있다. 아는 구현도 매우 간단하고 복잡한 알고리즘 없이 빠른 구현이 가능하나, 실행시간이 매우 오래걸리고 메모리 효율 측면에서 매우 비효율적이라는 단점이 있다. 푸는 방법의 대부분은 반복문과 조건문을 통해서 답을 도출하게 된다. 재귀도 사용할 수 있다. 문제의 조건은 문제를 해결할 수 있는 풀이의 수가 제한이 되어있어야 한다. 다음은 이번 주 브루트포스 과제였던 '수학은 비대면강의입니다'이다. 이는 연립방정식, 브루트 포스 방식으로 풀 수 있으나 브루트 포스 문제로 풀게 된다면 다음과 같은 코드로 짤 수 있다. 가능한 i와 j의..

티스토리툴바