노는 게 제일 좋아

사실 그래프의 연결 상태를 표현할 때 우리는 배열로 많이 하곤 한다. 하지만 행렬을 이용했을 때 가장 큰 문제점은 노드의 개수의 제곱에 비례하는 메모리를 사용하기 때문이다. 노드의 개수 범위가 만약 100000이라면 십만의 제곱은... 우선 0이 10개다. 10억이다. int로 저장했다면 10억 * 4byte = 40억 byte 다. 그러면.. 약 3기가 바이트.. 그래서 우리는 굳이 연결되지 않은 부분까지 저장하기는 그래서 인접리스트로 저장하기로 했다. 그렇게 되면 실제로 연결된 부분만 저장할 수 있다. 즉, vector을 원소로 하는 vector 또는 array를 만들어 해당 인덱스랑 연결된 노드들의 정보를 넣는 것이다. 실제로 이는 문제풀이할 때 노드의 수로 초과하는 것을 막아주기 때문에 유용하다고..

어렵다기 보다.. 엄두를 못냈다. 사실 DP란 것을 알았으면.. N번째부터 생각해봤을텐데.. 그게 안된다. https://www.acmicpc.net/problem/9465 #맞은 풀이 #include #include #include using namespace std; int sticker[2][100002]; int dp[2][100002]; // DP int tc; int main(){ ios::sync_with_stdio(0); cin.tie(0); cin >> tc; //테스트케이스 여러개 while(tc--){ //해당 테스트케이스에 대한 입력 int length; cin >> length; //DP 초기화 for(int i = 0; i

앞에서 함수 템플릿을 배웠듯이 클래스 템플릿도 뭔가 찍어내는 것 같은 느낌이다. 맞다. 하지만 조금 느낌은 다른데 클래스 템플릿은 구조나 알고리즘은 같되 멤버의 타입이 다른 클래스를 찍어내는 틀이다. 예를 보면서 알아보자 아래 클래스들은 화면의 특정 위치에 값 하나를 출력하는 클래스다. 우선 int, char 순서대로 class PosValueInt { private: int x,y; int value; public: PosValue(int ax, int ay, int av): x(ax), y(ay), value(av) {} void outvalue(); }; class PosValueChar { private: int x,y; char value; public: PosValue(int ax, int a..

템플릿이란 무엇이냐? 하나의 클래스를 서로 다른 (사용자가 원하는) 타입에 재사용할 수 있도록 하는 것이다. 타입만 넣어주면 자동으로 코드를 찍어내는 틀이라고 보면 된다. 예를 들어서 여러 타입의 객체를 저장할 수 있는 연결리스트와 같은 자료구조를 만들 수 있다. **template 와 template 는 정확히 같은 의미를 같지만 typename키워드를 많이 쓴다. //template class를 만들었다. template class ShiftedList { T* array; // 특정 타입의 배열 int offset, size; public: ShiftedList(int sz) : offset(0), size(sz) { array = new T[size]; // 타입 T의 배열 } ~ShiftedLi..

앞 글에서 보았듯이 부모의 속성, 함수를 물려받는 것이 정말 유용하게 쓸 수 있다는 것을 알았다. 그리고 이왕 상속시킬 부모클래스를 만들것이라면 재사용성이 높은 클래스를 설계하고 만들어야겠다는 생각이 들면 좋다. 그러나 상속과 비슷한 것이 있었으니 바로 포함, Containment이다. 포함이란 객체를 멤버로 선언하여 해당 클래스의 기능을 재활용하는 방법이다. 클래스의 멤버는 타입에 제한이 없어서 기본형뿐만 아니라 객체도 포함이 가능하다. 클래스끼리 중첩되는 형식인데 구조체가 다른 구조체를 멤버로 가질 수 있는 것과 같다. 예를 통해서 알아보자 class Date { protected: int year, month, day; public: Date(int y, int m, int d){year=y, mo..

상속은 OOP하면 가장 먼저 생각나는 특성으로 이미 정의한 클래스를 물려받아 새로운 클래스를 정의하는 기법이다. 이는 재사용성을 높이고 반복을 제거해서 효율성을 높여주며 계층별 다형성을 구현할 수 있게 한다. 참 장점이 많은 아이다. 천천히 알아보자 밑도 끝도 없이 예시부터 보자 class Car { private: char name[12]; public: Car(const *aname){ strcpy(name, aname); } void init(){ cout 이렇게 하지 말라는 말이다. 만약 비워둔다고 해도 상관없다. 비어있으면 부모클래스의 디폴트 생성자가 자동으로 호출되기 때문이다. **다만 디폴트 생성자를 정의해야 한다. 아무튼 상속받은 멤버는 반드시 초기화 리스트에서 부모의 생성자로 전달해서 초..

이것도 정말 구현문제로써 시키는대로 하면 된다. 다만 어떻게 구현할까? 의 선택지에서 DFS를 골랐다면 고생을 덜 할 것이었다 https://www.acmicpc.net/problem/14500 #맞는 풀이 #include #include #include using namespace std; int dx[4] = {1,-1,0,0}; int dy[4] = {0,0,1,-1}; int N,M; int map[500][500]; bool visited[500][500]; // 멍청했따.. 어차피 4칸을 사용하는 건데... DFS로 풀었으면 되었다는 힌트를 듣고.. 현타온다. //즉 DFS로 4칸 탐색하는 과정에 일자 모양도 있고 네모도있고 기역자도 있다. //다만 ㅗ 모양만 DFS로 탐색은 불가능하다. in..

이것도 정말 구현문제로써 시키는대로 하면 된다. 다만 범위에 신경쓰도록 사용자 입력만이 범위가 아니란 것을 명심하자 https://www.acmicpc.net/problem/21608 #맞는 풀이 #include #include #include #define X first #define Y second using namespace std; int seat[21][21];//자리 배치 1~N만 쓸 것임 int dx[4] = { 1,-1,0,0 }; //방향 int dy[4] = { 0,0,1,-1 }; //방향 int good[5] = { 0,1,10,100,1000 }; //점수 int N; vector info[401]; //학생 번호와 선호하는 학생을 저장 int main() { cin >> N; i..

그냥 시키는 대로 하면 된다. 다만 빼먹으면 안된다. 모든 조건을 빼먹으면 안된다. https://www.acmicpc.net/problem/20055 #맞는 풀이 #include #include #define X first #define Y second using namespace std; using ll = long long; int N, K; // 칸과 제한 deque deq; // 로봇이 있는지 1,0 내구도 int int main() { cin >> N >> K; int num = 2 * N; while (num--) { int x; cin >> x; deq.push_back({0,x }); //로봇이 없는 채로 deq 초기화 } int stage = 0; while (1) { stage++;/..

22.02.02 내용 업데이트 1. this C++ 에서 객체의 고유한 상태를 저장하는 멤버 변수는 객체별로 따로 유지하고 객체의 동작을 정의하는 멤버 함수는 공유한다. -> Static의 특징 객체의 개수와 관계없이 유일하게 존재함. 속성은 객체마다 다르지만 동작은 공통적이어서 각 객체가 따로 가질 필요 없다. -> this는 다시 말해서 해당 멤버 함수를 불러낸 객체라고 할 수 있다. 호출의 주체, 함수를 실행시키는 객체 자체 더 설명해보자 // this #include class Simple { private: int value; public: Simple(int avalue) : value(avalue) {} // 생성자 void OutValue(){ printf("value= %d\n", val..