코딩스토리

백준 1600번 - 말이 되고픈 원숭이 https://www.acmicpc.net/problem/1600 1600번: 말이 되고픈 원숭이 첫째 줄에 정수 K가 주어진다. 둘째 줄에 격자판의 가로길이 W, 세로길이 H가 주어진다. 그 다음 H줄에 걸쳐 W개의 숫자가 주어지는데, 0은 아무것도 없는 평지, 1은 장애물을 뜻한다. 장애물이 있�� www.acmicpc.net 이 문제는 BFS 알고리즘을 사용한 문제였다. 결론부터 얘기하면 3차원 배열을 사용하는 문제였다. 처음에 2차원 배열로 BFS 구현 후 horse란 배열을 따로 만들어 놓고 말의 움직임을 체크해 놓았었는데 이렇게 구현해 보니 당연히 틀렸습니다... 이유는 아래와 같은 테스트 케이스였다. 1 5 5 0 0 0 0 0 0 0 0 0 0 0 0..

백준 3190번 - 뱀 https://www.acmicpc.net/problem/3190 3190번: 뱀 문제 'Dummy' 라는 도스게임이 있다. 이 게임에는 뱀이 나와서 기어다니는데, 사과를 먹으면 뱀 길이가 늘어난다. 뱀이 이리저리 기어다니다가 벽 또는 자기자신의 몸과 부딪히면 게임이 끝난다. www.acmicpc.net 이 문제는 시뮬레이션 문제이다. 조건은 다음과 같다. 뱀은 몸길이를 늘려 머리를 다음칸에 위치시킨다. 만약 이동한 칸에 사과가 있다면, 그 칸에 있던 사과가 없어지고 꼬리는 움직이지 않는다. 만약 이동한 칸에 사과가 없다면, 몸길이를 줄여서 꼬리가 위치한 칸을 비워준다. 즉 몸길이는 변하지 않는다. 이 문제의 핵심은 뱀의 꼬리에 있다. 뱀의 머리가 이동하는 것은 입력 받은데로 움직..

백준 14499번 - 주사위 굴리기 https://www.acmicpc.net/problem/14499 14499번: 주사위 굴리기 첫째 줄에 지도의 세로 크기 N, 가로 크기 M (1 ≤ N, M ≤ 20), 주사위를 놓은 곳의 좌표 x y(0 ≤ x ≤ N-1, 0 ≤ y ≤ M-1), 그리고 명령의 개수 K (1 ≤ K ≤ 1,000)가 주어진다. 둘째 줄부터 N개의 줄에 지도 www.acmicpc.net 이 문제는 시뮬레이션 문제이다. 주사위를 지도 안에서 굴리면서 윗면(바닥 면과 반대되는 면)을 출력하는 문제이다. 조건은 다음과 같다. 주사위를 굴렸을 때, 이동한 칸에 쓰여있는 수가 0이면, 주사위의 바닥면에 쓰여 있는 수가 칸에 복사된다. 0 이 아닌 경우에는 칸에 쓰여 있는 수가 주사위의 바..

목차 그래프 추상 데이터 타입 그래프의 기본 연산 최소 비용 신장 트리 최단 경로와 이행적 폐쇄 작업 네트워크 1. 그래프 추상 데이터 타입 그래프는 이산수학에서도 배웠다시피 오일러의 퀸즈 버그 다리 문제에서 처음 사용되었다고 한다. 그래프의 정의 : 그래프는 두 개의 집합 V와 E로 구성된다. V는 정점(vertex), E는 간선(edge)로 이루어진 유한 집합이다. 임의의 그래프 G = (V, E)로 나타낼 수 있으며, 간선을 나타내는 정점의 쌍에 순서가 있거나 없음을 통해 무방향, 방향 그래프로 나눌 수 있다. 예를 들어 트리구조도 그래프라 할 수 있는데 이는 무 방향 그래프라 할 수 있다. ex) (u,v) 는 무방향 그래프에서 표현, (v, u)와 같은 표현임. 는 유방 향 그래프에서 표현, 와..

목차 개요 이진트리 이진트리 순회와 트리 반복자 이진트리의 추가 연산 스레드 이진 트리 히프 이원 탐색 트리 선택 트리 포리스트 1. 개요 5강을 공부하기 위해선 트리에 대해 알아야 한다. 트리 구조란 정보의 항목들이 가지로 연결될 수 있게 데이터가 조직되는 구조이다. 예를 들면 족보 같은 경우 조상과 자손들, 부모와 자식들의 관계를 잘 보여준다. 정의 : 트리는 한 개 이상의 노드로 이루어진 유한 집합 (1) 노드 중에는 루트(root)라고 하는 노드가 있음 (2) 나머지 노드들은 n(>=0) 개의 분리 집합 T1,..., Tn으로 분할될 수 있다. 여기서 T1,..., Tn은 각각 하나의 트리이며 루트의 서브 트리(subtree)라고 한다. 트리의 차수 = max [노드의 차수] -> 쉽게 말해 자식..

목차 1. 단순 연결 리스트와 체인 2. C++에서의 체인 표현 3. 템플릿 클래스 체인 4. 원형 리스트 5. 가용 공간 리스트 6. 연결 스택과 큐 7. 다항식 8. 동치 관계 9. 희소 행렬 10. 이중 연결 리스트 11. 범용 리스트 12. 가상 함수와 동적 바인딩 1. 단순 연결 리스트와 체인 List = [ CAT, HAT, EAT, BAT, RAT, SAT,...] 다음과 AT로 끝나는 순서 리스트가 있다고 생각해보자. 지금까지 공부했던 배열은 삽입과 삭제에 불필요한 동작들이 많아 많은 시간이 소모되었었다. 이런 데이터들의 이동적인 측면에서의 문제점을 해결하기 위해서는 연결 리스트라는 자료구조가 도움이 된다. 연결 리스트의 표현 방법으로는 pointer(포인터)와 link(링크)가 연관되어 ..

목차 1. C++의 템플릿 2. 스택 추상 데이터 타입 3. 큐 추상 데이터 타입 4. C++의 서브타입과 상속 5. 미로 문제 6. 수식의 계산 1. C++의 템플릿 템플릿이란 클래스와 함수들의 재사용성을 증대시키기 위하여 C++에서 제공하는 기법으로 같은 알고리즘으로 문제를 해결할 수 있을 때, 인수(매개변수)의 타입만 교체하고 싶을 때 사용한다. 예를 들어보자. template void add (T& a, T& b){ T sum = a + b; } 위의 코드 add함수를 보면 원래대로라면 사용자가 int형으로 인수를 받을지, float형으로 받을지를 모르기 때문에 int형 인수를 갖는 add와 float형을 인수로 갖는 add를 두 번 정의해 줘야 한다. 하지만 template 클래스로 정의함으로써..

목차 1. 추상 데이터 타입과 C++ 클래스 2. 추상 데이터 타입으로서의 배열 3. 다항식 추상 데이타 타입 4. 희소 행렬 5. 배열의 표현 1. 추상 데이타 타입과 C++ 클래스 C++에서는 C언어의 struct 도 사용 가능하지만, 명세와 구현을 구별하고(데이터 추상화), 정보를 은닉(데이터 캡슐화) 하기 위해 class(클래스)라고 하는 명시적인 기법을 제공한다. class는 아래와 같이 네 부분으로 구성된다. 클래스 이름 : ex) Rectangle 데이터 멤버 : 클래스를 만드는 데이타 ex) xLow, height,... -> priavte 영역에 선언된다(for 데이터 캡슐화) 멤버 함수 : 클래스의 객체에 적용할 수 있는 연산의 집합 ex) GetHeight()... -> 주로 publ..