[자료구조 복습2] Array List와 Linked List (단순, 원형,이중)
리스트에는 두가지 종류가 있다. 배열리스트와 연결리스트이다. 배열리스트는 말 그대로 '배열'을 이용하여 리스트를 구현한 것이고, 연결리스트는 포인터를 이용하여 리스트를 구현한 것이다. - 배열 리스트의 장점은 원하는 원소를 O(1) 시간으로 찾을 수 있다는 것이다. 하지만 단점은 원소의 개수가 제한되어 있다는 것, 삽입과 삭제가 까다롭다는 점이다. 아무리 탐색에서 O(1)로 효율적이더라도 , 삽입과 삭제에서 O(n)이 걸리므로 그다지 효율적이라 하지 못하겠다. 하지만 그럼에도 불구하고 배열리스트는 리스트 내의 변동 사항이 없고, 리스트의 크기가 클 때 사용하면 효율적일 것이다. 다음은 배열리스트 ADT를 C++로 구현한 것이다. 예외처리는 객체 참조자를 반환해야하는 함수에만 해주었다. 배열리스트 C++ ..
[자료구조 복습1] Array- 다항식 계산 , 희소행렬
자료구조를 처음 배운지 꽤 오래지났다. 그래서 그런지 몇몇 개념들은 희미해졌고 많이 까먹기도 했다. 그 동안 복습을 제대로 안한 문제도 있을 것이라 생각한다. 그래서 2020 상반기의 가장 큰 목표 중 하나를 자료구조 과목을 제대로 복습하는 것이다. 나는 처음 자료구조를 C언어 쓰여진 책으로 배웠지만, 그 책을 바탕으로 이제는 C++로 구현해보고자 한다. C++에 대한 이해도가 높지 않아 실수가 많기때문에 지적이나 조언은 언제나 환영이다! - 다항식 계산 #include using namespace std; #define MAX_ARR 101 int MAX(int a, int b) { if (a > b) return a; else return b; } class polynomial { //coef와 ex..
BOJ 9020 골드바흐의 추측
골드바흐의 추측이란? "2보다 큰 모든 짝수는 두 소수의 합으로 나타낼 수 있다" 는 것이다! 이 문제는 골드바흐의 파티션, 즉 짝수 n이 주어졌을 때 짝수 n을 이루는 '두 소수'를 구하는 문제이다. 단, 파티션이 2개 이상 주어졌을 때는 두 소수간의 차이가 가장 적은 것만을 출력한다 아래가 내가 푼 로직이다. 처음에는 그냥 for문과 if문으로 조건을 만들어서 파티션을 출력하려고 했지만너무 복잡해질 것 같아서 다른 방법을 찾았기에 이 방법을 썼다! (속도는 확실히 좀 느리다) 백준 골드바흐의 추측 소스 #include #include using namespace std; bool prime_num[10001]; //기본값 0 void prime() //에라토스테네스의 체 // 소수 == false /..
