본문 바로가기

📊 Algorithm91

🧚‍♂️알고리즘🧚‍♂️ - 정수론1(소수,오일러 피) 🌊정수론 - 수의 성질을 탐구하고 공부하는 분야 🌊 🔢소수 구하기🔢 소수: 자신보다 작은 2개의 자연수를 곱해 만들 수 없는 1보다 큰 자연수. (1과 자기 자신 외에 약수가 존재하지 않는 수) 소수 구하기의 핵심 이론 에라토스테네스의 체 1. 구하고자 하는 소수의 범위만큼 1차원 리스트 생성 2. 2부터 시작하여 지워지지 않은 현재 선택된 숫자의 배수에 해당하는 수를 리스트에서 끝까지 탐색하면서 지운다. 3. 리스트의 끝까지 2번을 반복한 후 리스트에 남아 있는 수를 출력한다. 에라토스테네스의 체 시간복잡도 O(N^2) 같겠지만 일반적으로 O(Nlog(logN))이라고 한다. 왠지 이해가 안 돼서 검색해봤더니 Sieve of Eratosthenes - Wikipedia From Wikipedia, th.. 2023. 5. 9.
🧚‍♂️알고리즘🧚‍♂️ - 이진탐색 이진 탐색(이분 탐색) 데이터가 정렬되어 있는 상태에서 원하는 값을 찾아내는 알고리즘 대상 데이터의 중앙값과 찾고자 하는 값을 비교해 데이터의 크기를 절반씩 줄이면서 대상을 찾음 기본 틀 1. 데이터 오름차순(내림차순) 정렬하기 2. 현재 데이터셋의 중앙값(mid) 선택 3. 중앙값 > 타깃 데이터일 때 중앙값 기준으로 왼쪽 데이터셋을 선택한다. (mid값을 바꾸는 방법 사용) 4. 중앙값 이진탐색 알고리즘 사용 중간값 = 블루레이의 크기 블루레이의 크기가 될 수 있는 최솟값 = 최대 길이의 레슨시간 = 시작인덱스 블루레이의 크기가 될 수 있는 최댓값 = 최대 길이의 레슨시간 = 종료인덱스 중앙값(블루레이) 크기로 모든 레슨을 저장할 수 있다면 종료인덱스 = 중앙값-1 중앙값(블루레이) 크기로 모든 레슨.. 2023. 3. 1.
🔰U-pper 이화여대 프로그래밍 대회- 한번에합격!🔰 이화여자대학교 프로그래밍 대회 [E-PPER경진대회]참가신청_기본안내 🤷‍♀️응시대상 : SW학부 컴퓨터공학/사이버보안주전공, 학년제한없음 www.notion.so 아직 1학년이지만.. 경험삼아 한번 ㄱㄱ 스터디 :: Ewha CyberCampus :: cyber.ewha.ac.kr 기출문제 - 이화퀸프 네이버카페 EWHA QueenP : 네이버 카페 이화여자대학교 컴퓨터공학과 EWHA QueenP 입니다 cafe.naver.com 으므흐어엥 합격했다! 뭐지! 망했다고 생각했지만! 한번에 합격! 와 22학번 나밖에 없따! 나머지 남은 기회 3번 다 출전해서 상금을 촵촵 노리도록 하겠다. 2023. 2. 6.
💠SUAPC🎆 신촌지역 대학교 프로그래밍 대회 2023 winter 경험삼아 출전 결심! 노션 스터디 일정/ 기출 / 개인기출풀이장 / 블로그후기글.용어정리글 등 참고자료 Dev for SUAPC’23 내게 파이 한 조각을 조 north-lilac-170.notion.site 지금 이씨크루 팀원들 중 하고싶은 친구들이랑 팀 결성 다 파이썬이라서 파이 한 조각만 조!🥧 30등 짝짝 목표인 솔프드 얻기/ 꼴찌 안하기는 성공했으므로 만족 2문제 풀었다 또 푼 2문제가 시간 초과 나서 너무 답답했다. 정말 알고리즘 공부의 부족함을 느꼈고.. 앞으로 더 정진하겠다 1학기 때 알고리즘 공부 열심히 해서 (책 끝내기!)(스터디 결성!) SUPAC summer를 다시 나갈 생각이다. 홧탱 얻은 솔브드 뱃지~ 얻은 솔브드 배경~ 2023. 2. 5.
🧚‍♂️알고리즘🧚‍♂️ - 완전탐색 - 너비 우선 탐색(BFS) 너비 우선 탐색(BFS) 탐색 시작 노드와 가까운 노드를 먼저 방문하여 완전 탐색하는 방법 최단 경로 찾기 - 큐 자료구조 이용 -> 선입선출 특성 필요 -노드 방문 여부를 체크할 리스트 필요 1260 실버 2 1260번: DFS와 BFS 첫째 줄에 정점의 개수 N(1 ≤ N ≤ 1,000), 간선의 개수 M(1 ≤ M ≤ 10,000), 탐색을 시작할 정점의 번호 V가 주어진다. 다음 M개의 줄에는 간선이 연결하는 두 정점의 번호가 주어진다. 어떤 두 정점 사 www.acmicpc.net - 노드 번호가 작은 것을 먼저 방문-> 오름차순 정렬하기 ⭐️DFS BFS 기초 모양! ⭐️ import queue from sys import stdin N,M,V = map(int,stdin.readline()... 2023. 2. 1.
🧚‍♂️알고리즘🧚‍♂️ - 동적 계획법(DP) 1 DP / 다이나믹 프로그래밍/ 동적 계획법 하나의 큰 문제를 여러 개의 작은 문제로 나누어서 그 결과를 저장하여 다시 큰 문제를 해결할 때 사용하는 것 큰 문제를 작은 문제로 쪼개서 그 답을 저장해두고 재활용 - 큰 문제를 작은 문제로 나눌 수 있어야 함 - 동일한 작은 문제들이 반복하여 나타나는 경우/ 이 문제들의 결괏값이 항상 같은 경우 사용 가능 - 메모이제이션 기법: 작은 문제들은 한 번만 계산해 저장해 놓고 재사용 - 톱 다운 방식 / 바텀 업 방식 (Ex: 피보나치 수열) 동적 계획법으로 풀 수 있는지 확인 (n번째 피보나치 수열을 구하는 문제는 n-1,n-2번째 피보나치 수열을 구하는 작은 문제로 나눌 수 있음 / 수열의 값은 항상 같음) -> 점화식 세우기 ( D[N] = D[N-1]+ D.. 2023. 1. 30.
🧚‍♂️알고리즘🧚‍♂️ - 완전탐색 - 깊이 우선 탐색(DFS) 깊이 우선 탐색(DFS) 루트 노드(혹은 다른 임의의 노드)에서 시작해서 다음 분기로 넘어가기 전에 해당 분기를 완벽하게 탐색(최대 깊이까지)하는 방법 - 재귀 함수 이용 - 스택 자료구조 이용 ->후입선출 특성 필요 -노드 방문 여부를 체크할 리스트 필요 인접 리스트로 그래프 표현 ->방문리스트 초기화->시작노드 스택에 삽입->대상 노드의 인접 노드 스택 삽입->스택에 값이 없을 때까지 반복 단절점 찾기, 단절선 찾기, 사이클 찾기, 위상 정렬 등에 이용 🥈실버 2 11724 연결요소의 개수 구하기 11724번: 연결 요소의 개수 첫째 줄에 정점의 개수 N과 간선의 개수 M이 주어진다. (1 ≤ N ≤ 1,000, 0 ≤ M ≤ N×(N-1)/2) 둘째 줄부터 M개의 줄에 간선의 양 끝점 u와 v가 주.. 2023. 1. 27.
🏆솔브드 클래스 2++ 달성하기! 🧧 설연휴에(맨날 놀긴 하지만) 클래스솔브드 도장깨기 목표는 클래스 2++ 달성! 7문제! 2231 분해합 브론즈 2 #브루트 포스 알고리즘 from sys import stdin N = int(stdin.readline()) #자릿수에 따라서 생성자후보 최솟값 구하고 되는지 다 돌기 # 생성자 후보 최솟값은 원래수-(원래수의자릿수*9)로 #자릿수 구하기 M = N length = 1 while(1): if M/10 >= 1: M /= 10 length += 1 else: break reresult = 0 for cha in range( N - (length * 9), N): result = cha K = cha for j in range(length-1,-1,-1): result += K //(10**.. 2023. 1. 21.
🧚‍♂️알고리즘🧚‍♂️ - 완전탐색 - 브루트 포스 브루트 포스 완전탐색 알고리즘. 즉, 가능한 모든 경우의 수를 모두 탐색하면서 요구조건에 충족되는 결과 찾기 이용 도구 선형 구조를 전체적으로 탐색하는 순차 탐색 비선형 구조를 전체적으로 탐색하는 깊이 우선 탐색(DFS, Depth First Search)/너비 우선 탐색(BFS, breadth first search) 1. 브론즈2 백준 2858 기숙사 바닥 2858번: 기숙사 바닥 첫째 줄에 상근이네 방의 크기 L과 W을 공백으로 구분하여 출력한다. 만약, 두 수가 다르다면, 큰 수가 L이 되고 작은 수가 W이 된다. 항상 정답이 유일한 경우만 입력으로 주어진다. www.acmicpc.net - 빨간색 타일의 최대 수, 갈색 타일의 최대 수를 확인해서 적당한 수를 반복문에 넣는다. from sys i.. 2023. 1. 16.
🧚‍♂️알고리즘🧚‍♂️ - 정렬 - 기수 정렬 / 계수 정렬 기수 정렬 값을 바로 비교하지 않는 특이한 정렬 값을 놓고 비교할 자릿수를 정한 다음 해당 자릿수만 비교함 시간복잡도 O(kN) K는 데이터의 자릿수 10개의 큐 사용 ( 0,1,2,3,4,5,6,7,8,9 담당) 일의 자릿수 -> 십의 자릿수 -> 백의 자릿수 ... 순으로 정렬돤 데이터들을 계속 재정렬 (이전 자릿수에서 정렬된 순서 기준으로 다음 자릿수에 저장!) 계수 정렬 데이터의 최댓값 크기의 배열에 각 요소의 배열 등장 횟수를 count해 저장한 후 작은 인덱스값 순서대로 출력 O(n + k) (k는 Input 요소의 최댓값)( k가 작은 수라면 O(n), k가 무한으로 커질 때는 O(무한)) 실버 5 10989번 수 정렬하기3 10989번: 수 정렬하기 3 첫째 줄에 수의 개수 N(1 ≤ N .. 2023. 1. 16.

티스토리툴바