본문 바로가기

분류 전체보기

 (403)
OOP 기초 (왜 쓰는가?, 캡슐화 등) 1. 소프트웨어공학의 궁극적 목표는 최소한의 비용으로 소프트웨어의 개발, 유지보수를 하는 것이다. 2. 일반적으로 OOP는 프로그래머의 생산성, SW퀄리티, 생명주기, 가독성, 이해력을 증가시킨다. 3. 커플링은 모듈(컴포넌트)간의 의존성을 나타낸다. 일반적으로 커플링은 최소화 해야한다. 4. 응집도는 모듈 내부의 데이터들이 얼마나 하나의 목표를 위해 긴밀한가를 나타낸다. 응집도는 최대화 해야한다. 5. 추상 클래스는 최소 한개의 추상메소드를 포함해야한다. 6. 캡슐화란? 7. 캡슐화를 할때의 장점은 무엇인가? 8. 그냥 인스턴스를 사용할때와 포인터를 사용할 때의 차이는? 일반 인스턴스는 값의 복사값을 콜리에게 주기 때문에 데이터가 안전하다. 포인터를 사용할 경우는 본래의 값이 변경 될 수 있다.
백준 7562 나이트의 이동(C++) #include #include #define MAX 301 using namespace std; int dX[] = { 2,-2, 1,-1, 2 , -1 , -2 , 1}; int dY[] = { 1,-1,2,-2, -1 , 2 , 1 , -2}; int dis[MAX][MAX] = { 0 ,}; bool visited[MAX][MAX] = { false, }; int main() { ios_base::sync_with_stdio(false); cin.tie(NULL);cout.tie(NULL); int N; int Size; int nightX, nightY; int desX, desY; cin >> N; for (int i = 0; i > Size >>..
백준 1261번 알고스팟(C++) 벽을 부수고 이동한다는게 무슨 말인지 모를 수 있지만 결국 비용이 1인길을 선택하느냐 0인길을 선택하느냐의 차이이다. 우리는 목적지까지 최소한으로 이동해야하기 때문에 최대한 0인부분을 잘 이용해야한다. 그렇기 때문에 이 문제는 0-1 BFS 최소비용 or 다익스트라 문제이다. 처음에는 아래 코드로 했다가 예제에서 틀렸다. #include #include #include #define MAX 1001 using namespace std; int dx[] = { 0,0,1,-1 }; int dy[] = { 1,-1,0,0 }; deque Q; int dis[MAX][MAX]; int wall[MAX][MAX]; bool visited[MAX][MAX] = { false, }; void BFS(int N, i..
백준 13549 숨바꼭질3 (C++) 0-1 BFS, 다익스트라, 우선순위 큐 등 많은 방법으로 풀 수 있지만 한 번도 안해본 0-1 BFS를 사용해 풀어보았다. 이 문제의 출제 의도이자 최적화가 잘되어있어 0ms만에 문제를 풀어낼 수 있다. 0-1 BFS의 대한 알고리즘은 https://tigerfrom2.tistory.com/8 0-1 BFS 너비 우선 탐색 0-1 BFS는 기본적으로 BFS와 동일하지만 간선의 이동 비용이 0과 1인 경우를 이야기한다. 때문에 적은 비용으로 이동하기 위해서는 비용이 0인 간선으로 이동하는 것을 최대한 장려해야한다. 0-1 bf tigerfrom2.tistory.com #include #include #include #define MAX 100001 using namespace std; int N, M; ..
0-1 BFS 너비 우선 탐색 0-1 BFS는 기본적으로 BFS와 동일하지만 간선의 이동 비용이 0과 1인 경우를 이야기한다. 때문에 적은 비용으로 이동하기 위해서는 비용이 0인 간선으로 이동하는 것을 최대한 장려해야한다. 0-1 bfs는 덱을 사용하여 구현할 수 있다. 지금까지 스택, 큐는 자주 사용했지만 덱은 다뤄본 적이 거의 없다. 먼저 덱(deque)은 큐와 비슷하지만 왼쪽과 오른쪽 모두 pop이 가능한 자료구조이다. 알고리즘은 다음과 같다. 1. 현재 덱의 현재 노드를 꺼내본다. 2. 인접노드를 살펴본다. 3. 인접노드로 넘어가는데 비용이 0이면 front에 1이면 back에 삽입한다. -> why? 왜 프론트와 백에 따로 저장을 할까? 이것은 본문 두번째 줄의 비용이 0인 간선 이동을 장려해야하기 때문이다. 2*x 는 비용..
Git, 기본사용법 (GitBash, pull, push) Git이란 프로그래머들이 협업할때 서로 복붙해서 코드를 보낼 필요 없이 서로 코드를 공유하고 합쳐주는 소프트웨어이다. 그러나 "알려진 오류의 원인" 이라는 말이 있을 정도로 쓰는법이 어렵다. 기업 우대조건에도 Git 사용에 자유로우신 분 문구가 자주 써있다. 이번에 팀플을 하면서 깃허브를 다른 사람과 사용할 일이 생겨서 벼락치기 중이다. 난 Git은 여러 관리 프로그램이 있는데 난 Git Bash를 사용한다. 나도 거의 메모, 정리용으로 적는 거라 틀린 내용 얼마든지 있을 수 있다. 1. git status 지금 깃과 연결된 폴터의 파일들과 허브의 파일들을 비교해 바뀐 점이 있는지 체크한다. 2. git add . 아직 정확히 모르겠는데 커밋 전 행동으로만 알고 있다. 3. git commit -m "메..
백준 7576번 토마토(C++) 예전에 풀었던 문제이지만 다시한 번 해보았다. 예전의 코드는 구글링의 다른 사람의 코드를 도움 받았기 때문이다. 그리고 BFS의 좋은 예제이다. 먼저 토마토 1이 있으면 하루에 4방향으로 증식한다. 증식한 토마토는 또 4방향으로 증식하게된다. DFS로 계산하면 한 방향으로만 가버리기 때문에 적절하지 않다. 결국 BFS를 통해 첫 1부터 제일 떨어져 있는 거리까지의 최소거리(최소일수)를 구하는 문제로 귀결된다. 그러나 여기서 중요한 것은 1이 한군데만 존재하지 않는다는 것이다. 즉, 두군데 이상의 1에서 동시에 증식을 시작해야한다. 그림으로 표현하면 이런식이다. 때문에 DFS는 절대(적어도 내 기준에선) 사용할 수 없다. 알고리즘은 이러하다. 1. 처음 토마토가 심어져 있는 좌표를 큐에 삽입. 2. 삽입된..
백준 1697 숨바꼭질 (C++) #include #include #include #include #include #include #define MAX 51 using namespace std; queue Q; int x, y; bool visited[100001] = {false,}; void BFS() { Q.push(make_pair(x, 0)); visited[x] = true; while (!Q.empty()) { int X = Q.front().first; int T = Q.front().second; Q.pop(); if (X == y) { cout -1 && X - 1 < 100001 && visited[X - 1] == false) { Q.push(make_pair(X - 1, T + 1)); visited[X - 1] ..

티스토리툴바