공대생 도전 일지

자료구조와 알고리즘은 컴퓨터 과학에서 가장 핵심적인 주제 중 하나로, 데이터를 효율적으로 저장하고 처리하며 문제를 해결하는 방법을 다룹니다. 아래에 이를 체계적으로 정리했습니다.1. 자료구조 (Data Structures)자료구조는 데이터를 체계적으로 저장하고 관리하는 방법입니다. 자료구조는 사용 목적과 데이터의 특성에 따라 선택되며, 주요 자료구조와 그 특징은 다음과 같습니다.선형 자료구조 (Linear Data Structures)배열 (Array)특징: 고정된 크기의 연속된 메모리 공간에 데이터를 저장.장점: 인덱스를 이용한 빠른 접근 (O(1)).단점: 크기 고정, 삽입/삭제가 비효율적 (O(n)).연결 리스트 (Linked List)특징: 노드(Node)가 데이터와 다음 노드의 주소를 포함.장점..

최소 동전의 수를 구할 때는 그리디 알고리즘으로 해결 가능하다!만약 나누어 떨어지지않을 때 그리디 알고리즘으로 해결이 불가능하다.동적 계획법 = DP - 이전 계산한 값을 재사용하여 하나의 문제를 한 번만 풀게 하는 알고리즘!탑 다운 - 큰 문제부터 풀기 시작하여 작은 문제들을 재귀적으로 호출하여 답을 구하는 방식바텀 업 - 작은 문제들을 먼저 풀기 시작하여 최종적으로 가장 큰 문제들을 해결하는 방식이다.배열에 저장하여 반복 작업을 줄이는 기법이 핵심이다.조건!겹치는 부분(작은) 문제 - 어떠한 문제가 여러 개의 부분(하위) 문제로 쪼갤 수 있을 때 사용한다.최적 부분 구조 - 문제의 정답을 작은 문제의 정답에서 구할 수 있을 때 사용한다.피보나치를 재귀로 구하면 구했던 값을 여러번 구하게 된다.Dp를 ..

재귀 - 자신을 정의할 때 자기 자신을 참조하는 것 함수에서 자기 자신을 호출한다!def fibo(n): if n항상 무한 루프에 빠지지 않도록 잘 설정해야 한다! 정렬 - 데이터를 오름차순 및 내림차순 등 특정한 기준으로 정렬하는 것삽입 - 앞에서부터 차례대로 비교하여 자신의 위치를 찾는다 = 구현 간단, n^2버블 - 두 수를 바꾸는 swap를 많이 사용한다. = 느리지(n^2)만 간단합병 - 퀵 - 피벗을 사용하여 기준으로 정렬한다.힙 - 최대 힙(부모 노드가 자식 노드보다 큰 트리)C++ - intro SortPython - Tim SortJAVA - 병합, 팀 정렬  트리 위의 게임시간 제한: 1 초정점 N개의 트리에서 두 사람이 게임을 진행하려 한다.각 정점은 1번부터 N번 까지 번호가 매겨져..

회문 - 앞뒤 방향으로 볼 때, 같은 순서의 문자로 구성된 문자열ex ) "1234321", "level"def is_palindrime(s): for i in range(len(s)): if s[i]!=s[len(s) -i -1]: return False return Truedef is_palindrome(s): return s == s[::-1]올바른 괄호 문자열 (VPS)스택을 사용해서 해결하는 것으로 )가 입력될 때마다, 스택에 있는 (를 하나씩 지운다!(가 없으면 올바른 괄호 문자열이 아니다.모두 순회한 뒤 스택이 비어있으면 올바른 괄호 문자열이다.분할정복 - 큰 문제를 작은 문제로 분할하여 작은 문제의 답을 모아 큰 문제의 답을 구한다.합병 정렬..

유클리드 호제법 - 최대 공약수를 구할 때 사용한다.N의 약수 찾기1 ~ N까지 나누어서 나머지가 0이 되는 수의 개수 찾기 = 복잡도 N호제법 - 서로 나눈다!두 자연주 a,b에 대해 (a>b) a를 b로 나눈 나머지를 r이라 하면 a,b의 최대 공약수는 b와 r의 최대 공약수와 동일하다.b를 r로 나눈 나머지 r'를 구하고 다시 r을 r'으로 나눈 나머지를 구하는 과정을 반복하여 나머지가 0이 되었을 때 나누는 수가 a와 b의 최대 공약수이다.1071과 1029를 구하자!1071 % 1029 = 421029 % 42 = 21 42는 21로 나누어 떨어지므로 최대 공약수는 21이다! 코드로 구현하자! def GCD(a,b): while b: a,b = b,a%b return aGCD - 최..

시간 복잡도 - 문제를 해결하는 데 걸리는 시간과 입력 사이의 관계빅 오 - 상한 접근 = 최악 경우빅 오메가 - 하한 접근 = 최선의 경우빅 세타 - 둘의 평균빅 오 표기법 종류1 - 일정한 복잡도 = 입력의 크기와 상관 없이 즉시 출력값을 얻어낼 수 있다.log N - N이 커질 수록 N보다 1의 복잡도에 가까워진다. = 중간값을 제시하면서 경우의 수를 절반 씩 나누는 법N - 선형 복잡도 = 입력과 실행시간이 같은 비율로 증가 (입력 값이 커질수록 계수의 의미가 퇴색)N log N -N^2 - 2차 복잡도 = 2중 for문에서 보인다.2^N - 지수 복잡도 = 특별한 경우를 제외하고는 안나오므로 다른 접근 방식을 고민해보는 것이 좋다.N! - 시간 복잡도가 가장 크다.시간 복잡도에 따라 실행 시간이..

https://www.youtube.com/watch?v=nyjFmDUDgO4 길찾기갈 수 있는 지점을 기록할 리스트 생성하고, 시작 위치 넣기1. 리스트[0] 확인하여 그위치 간 뒤 리스트[0] 삭제하고 서있는 지점 -1로 두기 - 더 이상 갈 곳이 없다면 도착지에 갈 수 없다.2. 이동가능한 지점을 리스트에 넣기 - 목적지가 리스트에 있으면 도달 가능한 것이다.3. 1번으로 돌아가기반복하다보면 길을 찾는다.너비 우선 탐색 방식이다! - BFS리스트의 마지막을 꺼내면 깊이 우선 탐색 방식 - DFShttps://www.youtube.com/watch?v=qaiuC3Q73-M다익스트라 - 최단 경로  https://jeong-devlog.tistory.com/entry/%EC%BD%94%EB%94%A9-..

import sys sys.setrecursionlimit(10000) # 재귀 호출 깊이 한계를 10000으로 설정 dp = [[0 for _ in range(m)] for _ in range(n)] # 리스트 행렬 만들기 n * m graph = [[0] * (n + 1) for _ in range(n + 1)] # 올바른 2차원 리스트 초기화 numbers = list(map(int, input().split())) # 한 줄의 숫자들을 입력받음 num = [list(map(int, input().strip().split())) for _ in range(n)] # 행렬 입력받기 import sys # input 함수를 sys.stdin.readline으로 재정의 input = sys.stdin.r..

백준 1927 최소 힙 문제 널리 잘 알려진 자료구조 중 최소 힙이 있다. 최소 힙을 이용하여 다음과 같은 연산을 지원하는 프로그램을 작성하시오. 배열에 자연수 x를 넣는다. 배열에서 가장 작은 값을 출력하고, 그 값을 배열에서 제거한다. 프로그램은 처음에 비어있는 배열에서 시작하게 된다. 입력 첫째 줄에 연산의 개수 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 N개의 줄에는 연산에 대한 정보를 나타내는 정수 x가 주어진다. 만약 x가 자연수라면 배열에 x라는 값을 넣는(추가하는) 연산이고, x가 0이라면 배열에서 가장 작은 값을 출력하고 그 값을 배열에서 제거하는 경우이다. x는 2^31보다 작은 자연수 또는 0이고, 음의 정수는 입력으로 주어지지 않는다. 출력 입력에서 0이 주어진 횟수만큼 답..

백준 2606 바이러스 입력 첫째 줄에는 컴퓨터의 수가 주어진다. 컴퓨터의 수는 100 이하인 양의 정수이고 각 컴퓨터에는 1번 부터 차례대로 번호가 매겨진다. 둘째 줄에는 네트워크 상에서 직접 연결되어 있는 컴퓨터 쌍의 수가 주어진다. 이어서 그 수만큼 한 줄에 한 쌍씩 네트워크 상에서 직접 연결되어 있는 컴퓨터의 번호 쌍이 주어진다. 출력 1번 컴퓨터가 웜 바이러스에 걸렸을 때, 1번 컴퓨터를 통해 웜 바이러스에 걸리게 되는 컴퓨터의 수를 첫째 줄에 출력한다. 예제 입력 1 복사 7 6 1 2 2 3 1 5 5 2 5 6 4 7 예제 출력 1 복사 4 이걸 맨날 구현하면서만 배웠는데 함수로 사용하는 법을 몰라서... 파이썬은 이름만 que, deque라고 하지 자료형을 편하게 사용할 수 있으니까 막 ..