코딩스토리

백준 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(링크)가 연관되어 ..