백준 / 연구소 / 14502번 / Python
·
코딩테스트(프로그래머스 & 백준)/백준-Python
*문제 출처는 백준에 있습니다. 문제 제목: 연구소 / 14502번 (골드 4단계)문제 사이트: https://www.acmicpc.net/problem/14502 문제 설명 나의 풀이from collections import dequedef bfs(): q = deque() vc = [row[:] for row in virus] for i in range(N): for j in range(M): if vc[i][j] == 2: q.append((i, j)) while q: y, x = q.popleft() for iy, ix in [(0, 1), (0, -1), (1, 0), (-1, 0)]: ..
백준 / 좋다 / 1253번 / Python
·
코딩테스트(프로그래머스 & 백준)/백준-Python
*문제 출처는 백준에 있습니다. 문제 제목: 좋다 / 1253번 (골드 4단계)문제 사이트: https://www.acmicpc.net/problem/1253 문제 설명 나의 풀이N = int(input())A = list(map(int, input().split()))A.sort()# 좋은 수를 셀 배열s = set()for i in range(0, len(A) - 1): for j in range(i + 1, len(A)): result = A[i] + A[j] if result 중복을 고려하지 못한 풀이 방법이다. 그래서 틀렸다.N = int(input())A = list(map(int, input().split()))A.sort()# 개수를 셀 변수cnt = 0for..
[알고리즘] 투 포인터(Two Pointer)
·
컴퓨터 과학/알고리즘
투 포인터 기법은 배열이나 리스트를 탐색하는 데 매우 효율적인 알고리즘 기법입니다. 두 개의 포인터를 사용하여 문제를 해결하는 이 기법은 주로 정렬된 데이터에서 특정 조건을 만족하는 쌍을 찾는 데 유용합니다. 이 기법은 많은 경우에 O(N) 또는 O(N^2)의 시간 복잡도를 가지며, 최적화된 솔루션을 제공합니다. 투 포인터(Two Pointer) 기본 개념투 포인터 기법은 다음 두 가지 주요 방식으로 사용됩니다:양 끝에서 시작하기적용 예: 정렬된 배열에서 두 수의 합이 목표 값과 일치하는 쌍을 찾는 문제방법: 배열의 시작과 끝에 각각 포인터를 두고, 두 포인터가 가리키는 값의 합을 계산합니다. 합이 목표 값과 같으면 쌍을 찾은 것이고, 그렇지 않으면 포인터를 조정합니다.같은 방향으로 이동하기적용 예: 특..
백준 / 가장 긴 증가하는 부분 수열 4 / 14002번 / Python
·
코딩테스트(프로그래머스 & 백준)/백준-Python
*문제 출처는 백준에 있습니다. 문제 제목: 가장 긴 증가하는 부분 수열 4 / 14002번 (골드 4단계)문제 사이트: https://www.acmicpc.net/problem/14002 문제 설명 나의 풀이n = int(input())data = list(map(int, input().split()))dp = [1] * (n + 1)for i in range(len(data)): for j in range(i): if data[j] ※ 알아야 할 것https://www.acmicpc.net/problem/12015 이 문제랑 다르다.이 풀이는 1번째 코드에서 수열이 증가하면 증가하는 길이만큼 출력한다.그리고 그 최대 증가하는 수들은 x 값을 가지고 있을 테니깐 뒤에서부터 x 값과 같..
백준 / 회의실 배정 / 1931번 / Python
·
코딩테스트(프로그래머스 & 백준)/백준-Python
*문제 출처는 백준에 있습니다. 문제 제목: 회의실 배정 / 1931번 (실버 1단계)문제 사이트: https://www.acmicpc.net/problem/1931 문제 설명 나의 풀이def solution(m): count = 0 # end는 현재 회의 끝나는 시간 end = -1 # s는 다음 회의 시작, e는 다음 회의 끝 for s, e in m: if end 이 문제의 핵심은 회의 끝나는 시간을 오름차순(이게 우선적으로 와야함), 회의 시작하는 시간을 오름차순을 통해서 가장 많이 사용할 수 있는 회의 시간을 찾는 것이 중요하다. 하지만 위 풀이는 정답과 비슷하지만 반례가 발생한다. 회의 끝나는 시간을 오름차순을 했지만 회의 시작하는 시간을 오름차순을 하지..
백준 / 그룹 단어 체커 / 1316번 / Python
·
코딩테스트(프로그래머스 & 백준)/백준-Python
*문제 출처는 백준에 있습니다. 문제 제목: 그룹 단어 체커 / 1316번 (실버 5단계)문제 사이트: https://www.acmicpc.net/problem/1316 문제 설명 나의 풀이def solution(s): stack = [] alpha = {chr(i + 96) : 0 for i in range(1, 27)} for word in s: if not stack: stack.append(word) continue if stack[-1] == word: continue elif stack[-1] != word: stack.append(word) for ..
[알고리즘] 이분 탐색(Binary Search)
·
컴퓨터 과학/알고리즘
이분 탐색(Binary Search)은 정렬된 배열에서 특정 값을 빠르게 찾기 위한 효율적인 알고리즘입니다. 이 알고리즘은 배열을 반복적으로 반으로 나누면서 원하는 값을 찾는 방식으로 동작하며, 시간 복잡도가 O(logn)입니다. 이는 선형 탐색(Linear Search)의 O(n)과 비교할 때 훨씬 더 효율적입니다. 이분 탐색 알고리즘의 동작 원리시작과 끝 설정: 배열의 시작점(low)과 끝점(high)을 설정합니다.중간점 계산: 시작점과 끝점의 중간 인덱스(mid)를 계산합니다.중간값 비교: 배열의 중간 값(arr[mid])과 찾고자 하는 값(target)을 비교합니다.만약 arr[mid]가 target과 같으면, 해당 인덱스를 반환합니다.만약 arr[mid]가 target보다 크면, target은 ..
피사노 주기(Pisano Period)
·
컴퓨터 과학/수학
피사노 주기란 피보나치 수열을 어떤 수 m으로 나눈 나머지들의 수열이 반복되는 주기를 말합니다. 피보나치 수열의 각 항을 m으로 나눈 나머지들을 구하다 보면, 이 나머지들이 주기적으로 반복되는 패턴을 갖게 됩니다. 이 패턴이 반복되기 시작하는 주기의 길이를 피사노 주기라고 합니다. 예시예를 들어, 피보나치 수열을 3으로 나눈 나머지의 피사노 주기를 살펴보겠습니다:피보나치 수열: 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, ...피보나치 수열을 3으로 나눈 나머지: 0, 1, 1, 2, 0, 2, 2, 1, 0, 1, 1, ...여기서 나머지의 수열을 보면 0, 1, 1, 2, 0, 2, 2, 1 이후부터 다시 0, 1, 1, 2, 0, 2, 2, 1이 반복되기 시작합니다. 이 주기는..
백준 / 최솟값 찾기 / 11003번 / Python(PyPy3 제출)
·
코딩테스트(프로그래머스 & 백준)/백준-Python
*문제 출처는 백준에 있습니다. 문제 제목: 최솟값 찾기 / 11003번 (플래티넘 5단계)문제 사이트: https://www.acmicpc.net/problem/11003 문제 설명 나의 풀이import heapqfrom collections import dequedef solution(lis, l): # 결과 result = [] # L를 계산할 deque() q = deque() for number in lis: q.append(number) if len(q) == l + 1: q.popleft() # 최소 값을 구할 힙 heap = list(q) heapq.heapif..
백준 / 토마토 / 7576번 / Python
·
코딩테스트(프로그래머스 & 백준)/백준-Python
*문제 출처는 백준에 있습니다. 문제 제목: 토마토 / 7576번 (골드 5단계)문제 사이트: https://www.acmicpc.net/problem/7576 문제 설명 나의 풀이from collections import dequedef solution(B): m = len(B[0]) n = len(B) move = [(0, 1), (0, -1), (1, 0), (-1, 0)] queue = deque() # 먼저 익은 토마토를 모두 큐에 넣어준다. for y in range(n): for x in range(m): if B[y][x] == 1: queue.append((y, x, 0)) # (y, x, 시간)..
[알고리즘] 최소 공배수(LCM, Least Common Multiple)
·
컴퓨터 과학/알고리즘
최소공배수(LCM, Least Common Multiple)를 구하는 여러 가지 방법이 존재하며, 이 중에서도 유클리드 호제법을 활용한 방법이 가장 효율적입니다. 아래에서는 여러 방법을 비교하고, 각 방법의 특징과 효율성을 설명하겠습니다. 1. 완전 탐색 기반 방법 (Brute Force)이 방법은 두 수의 배수를 계산하고, 가장 작은 공통 배수를 찾는 매우 직관적인 방법입니다. 알고리즘a와 b의 배수를 각각 계산합니다.두 수의 배수 중에서 가장 작은 공통 배수를 찾습니다.def lcm_brute_force(a, b): max_ab = max(a, b) lcm_value = max_ab while lcm_value % a != 0 or lcm_value % b != 0: lc..
[알고리즘] 최대 공약수(GCD, Greatest Common Divisor)
·
컴퓨터 과학/알고리즘
이번에는 최대공약수(GCD, Greatest Common Divisor)를 구하는 여러 알고리즘을 소개하겠습니다. 각 방법은 효율성이나 구현 방식에 차이가 있습니다. 1. 완전 탐색 방법 (Brute Force)첫 번째는 완전 탐색 방법을 이용한 최대 공약수를 구하는 방법 입니다.가장 직관적인 방법으로, 두 수의 공통된 약수 중에서 가장 큰 값을 찾는 방법입니다. 알고리즘두 수 중 작은 수를 선택합니다.그 수로부터 1까지 모든 수에 대해 두 수 모두를 나눌 수 있는지 확인합니다.두 수를 모두 나눌 수 있는 가장 큰 수가 최대공약수입니다.def gcd_brute_force(a, b): min_num = min(a, b) for i in range(min_num, 0, -1): if ..
김치바보
'분류 전체보기' 카테고리의 글 목록 (10 Page)
상단으로

티스토리툴바