라비린스6_개발 블로그

강의듣고 실습하면서 만들었습니다.

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <string.h>
#include <stdlib.h>

// 구조체 정의 및 초기화
typedef struct PokemonList
{
	char p_no[5];
	char p_name[10];
	struct PokemonList* p_next;
}PokemonList;

int main(void)
{
	PokemonList pokelist[9] = {
		{"001","파이리", NULL},
		{"002","리자드", NULL},
		{"003","리자몽", NULL},

		{"004","이상해씨", NULL},
		{"005","이상해풀", NULL},
		{"006","이상해꽃", NULL},

		{"007","꼬부기", NULL},
		{"008","어니부기", NULL},
		{"009","거북왕", NULL},
	};
	PokemonList* pcurr = NULL;
	pokelist[0].p_next = &pokelist[1];
	pokelist[1].p_next = &pokelist[2];
	pokelist[2].p_next = &pokelist[3];

	pokelist[3].p_next = &pokelist[4];
	pokelist[4].p_next = &pokelist[5];
	pokelist[5].p_next = &pokelist[6];

	pokelist[6].p_next = &pokelist[7];
	pokelist[7].p_next = &pokelist[8];

	pcurr = &pokelist[0];
	while (pcurr !=NULL)
	{
		printf("도감번호: %s 이름: %s\n", pcurr->p_no, pcurr->p_name);
		pcurr = pcurr->p_next;

	}
}

https://www.acmicpc.net/problem/4659

문제에 있는 조건을 기준으로 비밀번호를 평가 하여야 한다

풀이

입력받은 비밀번호를 조건 1, 2, 3 를 기준으로 차례로 판단해주면 된다.

2번 조건의 경우 모음, 자음을 나누어 등장할 때마다 루프를 돌며 카운트를 올리고, 3이상인 경우 false 를 반환해준다

3번 조건의 경우 해당 인덱스와 인덱스 -1 의 char 값을 비교하고 같은경우, 허용된 케이스가 아니면 false 를 반환하도록 구현

전체 코드

#include <iostream>
#include <vector>
#include <string>
#include <cmath>
#include <algorithm>
#include <climits>
#include <cstring>
#include <queue>
#include <map>

using namespace std;
// 4659: 비밀번호 발음하기

// 1. 모음 하나를 반드시 포함
bool isAccept1(string str)
{
	bool result = false;
	for (int i = 0; i < str.size(); i++)
	{
		if (str[i] == 'a' || str[i] == 'e'|| str[i] == 'i' || str[i] == 'o' || str[i] == 'u')
		{
			result = true;
			break;
		}
	}
	return result;
}
// 2. 모음 자음이 연속 3개이상 오면 안됨
bool isAccept2(string str)
{
	int mcnt = 0;
	int jcnt = 0;

	for (int i = 0; i < str.size(); i++)
	{
		// 모음
		if (str[i] == 'a' || str[i] == 'e' || str[i] == 'i' || str[i] == 'o' || str[i] == 'u')
		{
			mcnt++;
			jcnt = 0;
			if (mcnt >= 3)
			{
				return false;
			}
		}
		else
		{
			jcnt++;
			mcnt = 0;
			if (jcnt >=3)
			{
				return false;
			}
		}
	}
	return true;
}
// 3. 같은 글자 연속 2번
bool isAccept3(string str)
{
	for (int i = 1; i < str.size(); i++)
	{
		if (str[i] == str[i-1])
		{

			if (str[i]  == 'e' || str[i] == 'o')
			{

			}
			else
			{
				return false;
			}
		}
	}
	return true;
}

int main() 
{
	ios::sync_with_stdio(false);
	cin.tie(nullptr);

	while (true)
	{
		string str;
		cin >> str;

		if (str == "end")
		{
			return 0;
		}
		else
		{
			if (isAccept1(str) && isAccept2(str) && isAccept3(str))
			{
				//<a> is acceptable.
				cout << "<" << str << ">" << " is acceptable." << "\n";
			}
			else
			{
				cout << "<" << str << ">" << " is not acceptable." << "\n";
			}
		}
	}
}

객체지향의 4가지 특성

• 캡슐화: 데이터와 데이터를 처리하는 함수를 하나로 묶음
• 다형성: 같은 자료형에 여러 가지 타입의 데이터를 대입하여 다양한 결과를 얻어낼 수 있는 성질
• 상속: 부모 클래스에 정의된 변수 및 메서드를 자식 클래스에서 상속받아 사용하는 것
• 추상화: 객체의 공통적 속성과 기능을 추출하여 정의

캡슐화의 목적

• 멤버 변수에 대한 보호
• 중요한 멤버는 다른 클래스, 객체에서 접근 불가하도록 보호
• 외부 인터페이스를 위해 일부는 접근 허용

생성자와 소멸자

1. 생성자

• 객체가 생성될 때 자동으로 호출되는 함수

2. 소멸자

• 객체가 소멸될 때 자동으로 호출되는 함수
• 동적 메모리를 할당 한 경우 소멸자에서 해제 해야 한다

생성자는 별도로 정의하지 않으면 컴파일러에서 기본 생성자를 사용한다

접근 제어

• private, public, protected 의 종류가 있음
• 디폴트 접근 지정은 private

public

• 모든 클래스에서 접근 가능

private

• 해당 클래스에서 접근 가능
• 멤버 변수는 일반적으로 private 로 선

protected

• 해당 클래스 및 상속된 클래스에서 접근 가능

getter 와 setter(접근자와 설정자)

• 멤버 변수의 접근을 제한
• 접근자는 보통 get, 설정자는 보통 set

자유실습

포켓몬의 정보를 저장할수 있는 클래스를 정의 한 후 입력 값을 설정자 함수를 통해 값을 저장

접근자 함수를 통해 저장된 값을 불러와 출력

#include <stdio.h>
#include <iostream>
#include <string>
using namespace std;

class Pokemon
{
private:
// 멤버 변수 정의
	string name;
	int level;
	string type;
	string item;
public:
// 생성자와 소멸자
	Pokemon() { name = "", level = 1, type = "노말", item = ""; }
	~Pokemon() {};
 // 멤버 함수 정의 (설정자와 접근자)
	int getLevel()
	{
		return level;
	}
	void setLevel(int lev)
	{
		level = lev;
	}
	string getName()
	{
		return name;
	}
	void setName(string nm)
	{
		name = nm;
	}
	string getType()
	{
		return type;
	}
	void setType(string tp)
	{
		type = tp;
	}
	string getItem()
	{
		return item;
	}
	void setItem(string item)
	{
		this->item = item;
	}
};

int main()
{
	int n;
	cout << "등록할 포켓몬의 수: ";
	cin >> n;
	Pokemon* pk = new Pokemon[n];
	for (int i = 0; i < n; i++)
	{
		string new_name;
		int new_level;
		string new_type;
		string new_item;
		cout <<  "이름: ";
		cin >> new_name;
		cout << "레벨: ";
		cin >> new_level;
		cout << "타입: ";
		cin >>  new_type;
		cout << "지닌물건: ";
		cin >> new_item;
		pk[i].setName(new_name);
		pk[i].setLevel(new_level);
		pk[i].setType(new_type);
		pk[i].setItem(new_item);
	}

	cout << "====== 포켓몬 목록 ======" << "\n";
	for (int i = 0; i < n; i++)
	{
		string curr_name = pk[i].getName();
		int curr_level = pk[i].getLevel();
		string curr_type = pk[i].getType();
		string curr_item = pk[i].getItem();
		cout << "이름: ";
		cout << curr_name;
		cout << "/ 레벨: ";
		cout << curr_level;
		cout << "/ 타입: ";
		cout << curr_type;
		cout << "/ 지닌물건: ";
		cout << curr_item << "\n";
	}
	delete[] pk;
}

실행 결과

https://www.acmicpc.net/problem/16928

사다리, 뱀의 수를 입력 받고 사다리의 정보를 의미하는 x, y 

뱀의 정보를 의미하는 u, v 를 입력 받아 마지막 칸에 도착할 때 까지 주사위를 굴리는 최소 횟수를 구한다.

풀이

최단 경로를 찾는 문제이므로 bfs 로 탐색해야 한다.
먼저 탐색은 1번째 칸에서 시작 한다 
다음칸으로 이동할 때 거리는 주사위로 정하므로 1~6 사이이다
따라서 현재칸 +1 ~ 현재칸 + 6 을 탐색한다.

여기서 고려해야 하는 건 뱀칸과 사다리 칸이 있는 경우다
뱀칸, 사다리 칸의 좌표는 map 에 따로 저장 했다가 해당 칸이 사다리 시작점이면 다음 칸을 사다리 끝점으로 지정한다.
제 코드에서는 뱀, 사다리를 분리해서 배열, map에 저장하고 처리 했는데 분리안하고 같이 처리해도 될것으로 보인다.

전체 코드

#include <iostream>
#include <vector>
#include <string>
#include <cmath>
#include <algorithm>
#include <climits>
#include <cstring>
#include <queue>
#include <map>

using namespace std;
// 뱀과 사다리 게임

bool visited[101];
bool isladder[101];
bool issnake[101];

map<int, int> ladder;
map<int, int> snake;
int len[101];

void bfs(int n)
{
    visited[n] = true;
    queue <int> q;
    q.push(n);

    while (!q.empty())
    {
        int curr = q.front();
        q.pop();
        // 6칸탐색
        int nextmove = 0;
        for (int i = 1; i <= 6; i++)
        {
            nextmove = curr + i;
            if (nextmove <= 100)
            {
                // 사다리
                if (isladder[nextmove])
                {
                    nextmove = ladder[nextmove];
                }
                // 뱀
                if (issnake[nextmove])
                {
                    nextmove = snake[nextmove];
                }

                if (!visited[nextmove])
                {
                    visited[nextmove] = true;
                    q.push(nextmove);
                    len[nextmove] = len[curr] + 1;
                }
            }
        }
    }
}

int main() 
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int n, m;
    // 사다리, 뱀의 수
    cin >> n >> m;

    // 사다리
    for (int i = 0; i < n; i++)
    {
        int x, y;
        cin >> x >> y;
        // 사다리 칸 여부
        isladder[x] = true;
        ladder[x] = y;
    }

    // 뱀
    for (int i = 0; i < m; i++)
    {
        int u, v;
        cin >> u >> v;
        // 뱀 칸 여부
        issnake[u] = true;
        snake[u] = v;
    }
    bfs(1);
    cout << len[100] << "\n";
}

https://www.acmicpc.net/problem/7576

토마토가 들어 있는 상자를 입력 받아 모든 토마토가 익게 되는 최소 일수를 구하는 문제 이다.

상자의 가로, 세로 길이는 M, N 이고 익은 토마토는 1, 익지 않은 토마토는 0, 빈 칸은 -1 로 입력된다.

토마토가 모두 익지 못하는 경우는 -1로 출력 한다.

풀이

최단 경로 구하기므로 bfs 로 탐색 해야 한다. 탐색은 기준점에서 상, 하, 좌, 우 로 이루어진다.

먼저 고려해야할 점은 처음 입력될 때 익은 토마토가 2개 이상일 수 있는 것이다.

처음 시작 시 익은 토마토의 위치를 모두 큐에 넣고 탐색해야 한다.

그리고 토마토가 모두 익지 못하는 경우는 탐색을 끝낸 후

(입력받은 토마토가 있는 칸) 이면서 (방문 여부 = false) 인 경우로 판단 해 주었다.

토마토가 모두 익는 최소 일수는 맨 마지막에 일수만 저장한 배열에서 max() 를 활용해 찾는다.

(가장 늦게 걸린  토마토 익는 일수를 배열에서 찾음)

전체 코드

#include <iostream>
#include <vector>
#include <string>
#include <cmath>
#include <algorithm>
#include <climits>
#include <cstring>
#include <queue>

using namespace std;
int tomato[1001][1001];
bool visited[1001][1001];
int days[1001][1001];

int max_x = 0;
int max_y = 0;
void bfs(queue<pair<int, int>> &q)
{
    // 상 하 좌 우로 탐색
    int dirx[4] = { 0,0,-1,1 };
    int diry[4] = { 1,-1, 0,0 };

    while (!q.empty())
    {
        int curr_x = q.front().first;
        int curr_y = q.front().second;
        q.pop();

        for (int i = 0; i < 4; i++)
        {
            int currx = curr_x + dirx[i];
            int curry = curr_y + diry[i];
            if (currx >=0 && currx < max_x && curry >= 0 && curry < max_y)
            {
                if (!visited[currx][curry] && tomato[currx][curry] == 0)
                {
                    visited[currx][curry] = true;
                    q.push(make_pair(currx, curry));
                    days[currx][curry] = days[curr_x][curr_y] + 1;
                }
            }
        }
    }
}

// 토마토
int main() 
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, m;
    cin >> m >> n;
    max_x = n;
    max_y = m;

    queue<pair<int, int>> q;

    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < m; j++)
        {
            cin >> tomato[i][j];
            // 처음부터 토마토면 큐에 넣음
            if (tomato[i][j]== 1)
            {
                visited[i][j] = true;
                q.push(make_pair(i, j));
            }
        }
    }
    bfs(q);
    int max_day = 0;

    for (int i = 0; i < n; i++) 
    {
        for (int j = 0; j < m; j++) 
        {
            // 토마토 있는 칸인데 방문 못함
            if (visited[i][j] == false && tomato[i][j]==0) 
            {
                cout << -1;
                return 0;
            }
            // 가장 늦게 익는 토마토의 일수를 max 로 저장
            max_day = max(max_day, days[i][j]);
        }
    }
    cout << max_day;
}

[백준 24446] - 알고리즘 수업 - 너비 우선 탐색 3 (실버2)

https://www.acmicpc.net/problem/24446

bfs(너비우선탐색) 문제로 우선 bfs 함수 구현하면 된다.

문제 조건에 따라 노드의 깊이는 -1로 초기화한다.

bfs 탐색 시 노드 깊이를 업데이트 한다. 

먼저 최초 방문 시 노드 깊이 = 0 으로 설정하고,

이후 queue 에서 탐색 하면서 다음 노드 깊이 = 현재 노드 깊이 +1 로 만든다.

이후 정점번호는 1부터임을 주의하며 1~ n 번 까지 정점의 깊이를 출력하면 된다.

예제 넣고 테스트 한 뒤 통과 확인

전체 코드

#include <iostream>
#include <vector>
#include <string>
#include <cmath>
#include <algorithm>
#include <climits>
#include <queue>
#include <cstring>

using namespace std;

vector<int> vec[200001];
bool visited[200001];
int depth[200001];

void bfs(int n)
{
    queue<int> q;
    visited[n] = true;
    depth[n] = 0;
    q.push(n);

    for (int i = 0; i < vec[n].size(); i++)
    {
        q.push(vec[n][i]);
    }

    while (!q.empty())
    {
        int curr = q.front();
        q.pop();

        for (int i = 0; i < vec[curr].size(); i++)
        {
            int next = vec[curr][i];
            if (!visited[next])
            {
                q.push(next);
                visited[next] = true;
                depth[next] = depth[curr] + 1;
            }
        }
    }
}

int main() 
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, m, r;
    cin >> n >> m >> r;

    // 노드 깊이 초기화
    for (int i = 1; i <= n; i++)
    {
        depth[i] = -1;
    }

    for (int i = 0; i < m; i++)
    {
        int u, v;
        cin >> u >> v;

        vec[u].push_back(v);
        vec[v].push_back(u);
    }

    bfs(r);

    for (int i = 1; i <= n; i++)
    {
        cout << depth[i] << "\n";
    }

    return 0;
}

https://www.hanbit.co.kr/store/books/look.php?p_code=B8975427001

해당 책의 난이도는 중고급 으로 분류되어 있다. (한빛 공식사이트 기준)

주요 내용

최적화에 대한 간단힌 팁들만 정리해 보았다. 

<문자열 최적화>

Q. 다음 두 코드 중에서 무엇이 빠를까?

(1번) :

   string str = "Optimized C++ book page 101";
    string str_new = "";

    for (int i = 0; i < str.size(); i++)
    {
        str_new = str_new + str[i];
    }

(2번) :

    string str = "Optimized C++ book page 101";
    string str_new = "";

    for (int i = 0; i < str.size(); i++)
    {
        str_new += str[i];
    }

로직은 동일하니까 같은 거 아닌가요 라고 할수 있지만 실제로는 후자가 더 빠르다.

chrono 를 통해 타이머 설정하고 측정 해 보면 

(1번): TIME: 91500 ns 
(2번): TIME: 15400 ns

으로 2번이 더 빠른것을 확인 할 수 있다. (실행할 때마다 실행 시간은 달라지나 2가 더 빠르다)

지금 코드에서는 미미한 차이긴 하나 더 긴 문자열을 처리하고 해당 코드가 자주 반복될수록 이 차이는 커질 것이다.

이렇게 차이가 나는 이유는 이렇다. 

첫 번재 코드는 str_new + str[i] 로 임시 객체를 만든 후 그것을 다시 str_new 객체에 대입한다. 이 과정에서 힙 메모리 할당과 문자열 복사가 반복적으로 일어난다.

반면 두 번째 코드는 기존 버퍼에 덧붙이므로 추가 메모리 할당이 일어나지 않는다.

후기

중고급 난이도 책은 처음 접해 보는데 역시 아직은 어려운것 같다. 

먼저 중고급 난이도 라서 C++ 기본 구현 관련 내용은 나오진 않고, 여러 파트로 나누어 최적화 방법에 대해 사례를 들어 설명한다.

그리고 단순 C++ 뿐 아니라 OS 나 하드웨어 관련된 내용도 나와(비중이 크진 않다) 어느정도 기초 지식이 있어야 이해하기 좋을 것 같다.물론 최적화를 위해선 결국 저런 레벨에 대한 이해가 필요할 것 같다

흔히 어떤 알고리즘을 사용하면 시간 복잡도가 뭐 이니이니 어떤 코드가 어떤 코드보다 빠르다 라고 생각 하는 경우가 많은데, 실제 pc로 실행 시에는 결과가 다르게 나올 수 있다는 것도 보여준다.

해당 부분에 대한 내용을 이 책에선 예제 코드와 그 코드를 개선 했을 때, 얼마의 시간이 걸리는 지에 대해서 비교하면서 확인 시켜 준다.

내용이 나에게는 어려워 한번만 가볍게 읽었는데 이해 하지 못한 부분이 더 많다. 그래도 유용한 부분이 많아서 파트별로 자세히 읽어보며 더 공부해 보고 싶다.

https://hongong.hanbit.co.kr/%EC%BB%B4%ED%93%A8%ED%84%B0-%EA%B5%AC%EC%A1%B0-%EC%9A%B4%EC%98%81%EC%B2%B4%EC%A0%9C/

한빛미디어에서 주최하는 혼공학습단이라는 프로그램에 참여하게 되면서 구매한 책이다

책의 반 정도는 컴퓨터 구조에 관한 내용이고 나머지 반은 운영체제에 대한 내용이다.

해당 책의 난이도는 초급 으로 분류되어 있습니다 (한빛 공식사이트 기준)

책의 상세 내용은 혼공컴운 학습링크 참조

https://labyrinth6.tistory.com/category/%ED%98%BC%EA%B3%B5-%20%EC%BB%B4%ED%93%A8%ED%84%B0%EA%B5%AC%EC%A1%B0%2C%20%EC%9A%B4%EC%98%81%EC%B2%B4%EC%A0%9C

후기

컴퓨터 구조와 운영체제를 한 권에 같이 볼 수 있는데, 전반적으로 운영체제 파트가 더 어려운 편이였다

그림과 함께 설명해서 직관적으로 이해하기 좋은 편이다

파트마다 뒤에 학습문제가 있는데, 난이도는 책의 설명파트가 많이 깊게 들어가지 않는 걸 감안해도 꽤 쉬운 편이다

용어 문제 같은거도 대부분 보기중에 고르는 식이고

프로세스 스케줄링 같이 직접 적어보며 풀어야 하는 문제도 설명파트에 있는 내용이 정답도 동일하게 그대로 나온다.

예제 코드가 같이 제공되는 것도 좋았고 추가 학습 자료같은 거도 있어서 기본 내용 외에도 찾아보면서 학습할 수 있었다. 

참고로 예제 코드는 리눅스용이다. 윈도우 사용자들은 코드를 직접 고쳐서 해보거나 아니면 가상머신 깔아서 하면 된다

책 자체는 쉽게 설명된 편이고 학습 문제도 간단하게 확인만 하기 때문에 전공자들은 가볍게 복습하기 좋은 것 같다

설명이 어렵지 않고 그림이랑 같이 있어 이해하기 쉬워서 비전공자들도 읽어보기 좋을 것 같다