분류 전체보기
-
연결리스트의 개념자료구조 2022. 7. 10. 13:47
📌 연결리스트의 개념 💡 자기참조 구조체 동일한 타입의 구조체에 대한 포인터를 속성으로 포함하는 구조체 Link Node 구조체에 대한 포인터 -> 메모리의 주소를 가리키는 자료형 여러 개의 Node 구조체를 연결하는 역할 💡 연결리스트 단순 연결리스트(Singly Linked List) 자기 참조 구조체(Node)들의 연결 천번째 노드에 대한 포인터만 유지 리스트의 이름 = 첫번째 노드의 수조 이후 노드들은 구조체의 Link 포인터를 통해 참조 마지막 노드의 Link 포인터는 NULL로 설정한다. 다른 연결리스트 이중 연결 리스트(Doubly Linked List) 앞 뒤의 노드들의 정보를 가지고 있다. 원형 연결 리스트(Circular Linked List) 마지막 노트와 첫노드를 연결 연결리스트 연..
-
배열을 이용한 희소행렬의 표현자료구조 2022. 7. 10. 13:46
📌 배열을 이용한 희소행렬의 표현 💡 희소행렬 행렬의 표현 2차원 배열 : Array[MaxRows][MaxCols] 0이 많이 포함된 경우, 희소행렬이라고 한다. 0이 아닌 데이터의 수 배열 맨 처음에 행렬의 정보기록 = (행, 열, 0이 아닌 데이터의 수) 💡 행렬의 전치 전치연산 (Transposing a Matrix) row & column 을 교환 를 희소행렬 M의 어디에 저장하는가? -> -> -> 전치연산을 위한 연속적인 삽입으로 인해 기존에 저장된 항목들..
-
배열을 이용한 다항식의 표현자료구조 2022. 7. 10. 13:44
📌 배열을 이용한 다항식의 표현 💡 순서리스트 (Orderd List) 데이터들의 순서가 유지되는 집합 집합이란, 원소들의 모임, 순서를 중요시 하지 않음. 한 주의 요일들 섞여진 카드들 미국의 2차 세계 대전 참전 연도 스위스의 2차 세계 대전 참전 연도 (원소가 없는 집합도 순서리스트에 포함된다.) 💡 순서리스트의 연산 순서리스트에 적용 가능한 연산들 리스트 길이 연산 리스트의 모든 데이터들을 왼쪽에서 오른쪽으로 읽기 리스트로부터 i번째 데이터를 검색 리스트로부터 i번째 데이터를 교체 리스트의 i번째 위치에 새로운 데이터 추가 (i번째 이후에 있던 데이터는 한 칸씩 밀림) 리스트의 i번째 위치에 있는 데이터를 삭제 (i번째 이후에 있던 데이터는 한 칸씩 당겨짐) 💡 다항식 소개 순서리스트를 구현하는 ..
-
배열과 구조체의 정의자료구조 2022. 7. 10. 13:42
📌 배열과 구조체의 정의 💡 배열의 정의 배열이란? 동일한 데이터 타입의 데이터들을 묶는 구조 메모리의 연속된 위치에 차례대로 저장(Index, Data) 쌍의 집합 배열에 적용 가능한 연산 인덱스 i 번째에 저장된 데이터를 출력 인덱스 i 번째에 데이터 d 를 저장 배열의 저장된 데이터의 수는 얼마인가? 💡 구조체 구조체의 정의 하나 이상의 기본 자료형을 기반으로 사용자 정의 자료형을 만들 수 있는 문법요소 다양한 자료형을 포함한다. 구조체 비교 구조체의 내용이 동일한지를 검사하는 방법은 모든 속성이 같은지 하나씩 비교하는 것이다. 💡 자기 참조 구조체 정의 : 자기 자신을 가리키는 포인터를 속성으로 갖는 구조체 연결리스트에 많이 사용된다.
-
[백준] 1068 트리 with PythonPS 2022. 7. 7. 22:19
📌 BOJ 1068 트리 💡 조건 트리에서 리프 노드란, 자식의 개수가 0인 노드를 말한다. 트리가 주어졌을 때, 노드 하나를 지울 것이다. 그 때, 남은 트리에서 리프 노드의 개수를 구하는 문제. 노드를 지우면 그 노드와 노드의 모든 자손이 트리에서 제거된다. 다음과 같은 트리가 있다고 하자. 현재 리프 노드의 개수는 3개이다. (초록색 색칠된 노드) 이때, 1번을 지우면, 다음과 같이 변한다. 검정색으로 색칠된 노드가 트리에서 제거된 노드이다. 이제 리프 노드의 개수는 1개이다. 첫째 줄에 트리의 노드의 개수 N이 주어진다. N은 50보다 작거나 같은 자연수이다. 둘째 줄에는 0번 노드부터 N-1번 노드까지, 각 노드의 부모가 주어진다. 만약 부모가 없다면 (루트) -1이 주어진다. 셋째 줄에는 지울..
-
[백준] 17103 골드바흐 파티션 with PythonPS 2022. 7. 6. 16:55
📌 BOJ 17103 골드바흐 파티션 💡 조건 골드바흐의 추측: 2보다 큰 짝수는 두 소수의 합으로 나타낼 수 있다. 짝수 N을 두 소수의 합으로 나타내는 표현을 골드바흐 파티션이라고 한다. 짝수 N이 주어졌을 때, 골드바흐 파티션의 개수를 구해보자. 두 소수의 순서만 다른 것은 같은 파티션이다. 첫째 줄에 테스트 케이스의 개수 T (1 ≤ T ≤ 100)가 주어진다. 각 테스트 케이스는 한 줄로 이루어져 있고, 정수 N은 짝수이고, 2 < N ≤ 1,000,000을 만족한다. 정수론, 소수판별, 에라토스테네스의 체 유형의 문제 🖥 소스 코드 from sys import stdin def prime_list(n): sieve = [False, False] + [True] * n m = int(n ** 0..
-
알고리즘의 복잡도 계산자료구조 2022. 7. 6. 15:07
📌 알고리즘의 복잡도 계산 💡 성능분석 주어진 문제를 해결 정확성 문서화 얼마나 주석을 잘 달았는가? / 관련 문서가 얼마나 잘 작성되었는가? 모듈화 함수를 얼마나 체계적으로 잘 나누었는가? 가독성 변수 또는 함수의 이름이 얼마나 의미있게 쓰였는가? 공간 효율성 시간 효율성 필수적인 요소 - 1, 2 좋은 프로그래밍의 습관 - 3, 4, 5 성능과 관련 - 6, 7 💡 성능 분석 VS 성능 측정 성능 분석 시뮬레이션, 복잡도 성능 측정 실제로 실행시켜서 실행 시간을 측정 💡 복잡도의 정의 공간 복잡도 : 프로그램 실행에 사용되는 메모리 시간 복잡도 : 프로그램 실행에 걸리는 시간 💡 시간복잡도 실행에 걸리는 시간(T[p]) = 컴파일 시간 + 실행 시간 컴파일 시간은 고정 and 한번만 필요 T[p]는 ..
-
자료구조의 정의와 알고리즘의 정의 및 표현자료구조 2022. 7. 5. 16:57
📌 자료구조 💡 정의 문제해결을 위해 데이터를 조직하여 표현하는 방법 전화번호부 - List, Linked List, Tree 수강신청, 대기열 - Queue 지하철 노선도 - Graph 💡 중요성 주어진 문제의 특성에 맞는 자료구조를 선택한다. 프로그램의 개발이 쉽고 성능이 향상한다. 💡 추상 데이터 타입 (Abstract Data Type) 자료구조를 기술할 때 사용하는 방법 데이터 객체 및 연산명세와 데이터 객체 내부 표현양식 / 연산의 구현 내용을 분리 사용자가 원하는 서비스를 표현하는 부분과 서비스를 내부적으로 구현하는 부분을 분리하겠다. Ada Package, C++ Class ADT에서 연산의 명세 구성요소 : 함수 이름, 인자들의 타입 함수의 호출 방법 및 결과물이 무엇인지를 설명 함수의 ..
-
[백준] 16956 늑대와 양 with PythonPS 2022. 7. 2. 01:20
📌 BOJ 16956 늑대와 양 💡 조건 크기가 R×C인 목장이 있고, 목장은 1×1 크기의 칸으로 나누어져 있다. 각각의 칸에는 비어있거나, 양 또는 늑대가 있다. 양은 이동하지 않고 위치를 지키고 있고, 늑대는 인접한 칸을 자유롭게 이동할 수 있다. 두 칸이 인접하다는 것은 두 칸이 변을 공유하는 경우이다. 목장에 울타리를 설치해 늑대가 양이 있는 칸으로 갈 수 없게 하려고 한다. 늑대는 울타리가 있는 칸으로는 이동할 수 없다. 울타리를 설치해보자. 목장의 크기 R, C가 주어진다. R개의 줄에 목장의 상태가 주어진다. '.'는 빈 칸, 'S'는 양, 'W'는 늑대이다. 1 ≤ R, C ≤ 500 늑대가 양이 있는 칸으로 갈 수 없게 할 수 있다면 첫째 줄에..
-
[백준] 12920 평범한 배낭 2 with PythonPS 2022. 7. 1. 21:13
📌 BOJ 12920 평범한 배낭 2 💡 조건 민호는 BOJ 캠프에 가기 위해 가방을 싸려고 한다. 가방에 어떠한 물건들을 넣냐에 따라 민호의 만족도가 달라진다. 집에 있는 모든 물건들을 넣으면 민호가 느낄 수 있는 만족도는 최대가 될 것이다. 하지만 민호가 들 수 있는 가방의 무게는 정해져 있어 이를 초과해 물건을 넣을수가 없다. 민호가 만족도를 최대로 느낄 수 있는 경우를 찾아보자. 단, 집에 동일한 물건들이 여러개가 있을 수 있기 때문에 한 물건을 두개 이상 챙기는 것도 가능하다. 첫 번째 줄에 N, M (1 ≤ N ≤ 100, 1 ≤ M ≤ 10,000) 이 빈칸을 구분으로 주어진다. N은 민호의 집에 있는 물건의 종류의 수이고 M은 민호가 들 수 있는 가방의 최대 무게다. 두 번째 줄부터 N개의..