난이도 : 골드 2 걸린 시간 : 1시간 문제 퍼즐 문제 바로가기 3×3 표에 다음과 같이 수가 채워져 있다. 오른쪽 아래 가장 끝 칸은 비어 있는 칸이다. 1 2 3 4 5 6 7 8 어떤 수와 인접해 있는 네 개의 칸 중에 하나가 비어 있으면, 수를 그 칸으로 이동시킬 수가 있다. 물론 표 바깥으로 나가는 경우는 불가능하다. 우리의 목표는 초기 상태가 주어졌을 때, 최소의 이동으로 위와 같은 정리된 상태를 만드는 것이다. 풀이 최단 경로 문제이므로 bfs 이용 memo 해야 똑같은 경로 다시 탐색 x memo는 전체 map의 상태를 저장해야함 string으로 저장 코드 #include #include #include #include #include using namespace std; int map[..

난이도 : 골드 5 걸린 시간 : 1시간 30분 문제 DSLR 문제 바로가기 풀이 DSLR이라는 4가지 경로가 있다고 생각하고 bfs 코드 #include #include #include using namespace std; struct point { int prev; char state; int visited = -1; }; char dslrArr[4] = { 'D', 'S', 'L', 'R' }; int dslrResult(int type, int num) { int tmp; switch (type) { case 0 : return (num* 2) % 10000; case 1 : if (num == 0) return 9999; else return num - 1; case 2 : tmp = num /..

난이도 : 골드 4 걸린 시간 : ㅎㅎ.. 오래 걸림 문제 아기 상어 문제 바로가기 풀이 bfs를 이용하여 먹을 수 있는 고기 찾기 + 상어로부터의 거리 찾기 거리가 가장 가까운 먹을 수 있는 고기들 찾기 그 중 가장 왼쪽 위에 있는 고기 찾기 상어가 해당 물고기의 위치로 이동해서 먹고, 먹은 물고기 개수가 size와 같아지면 size 키우기 상어보다 작은 물고기가 없을 때까지 반복 코드 #include #include #include using namespace std; struct shark { int r; int c; int size = 2; }; struct fish { int r; int c; int distance = 0; fish(int rp, int cp, int dist) { r = rp..

난이도 : 골드 4 걸린 시간 : 40분 문제 알파벳 문제 바로가기 시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율 2 초 256 MB 49866 15734 9600 29.155% 세로 R칸, 가로 C칸으로 된 표 모양의 보드가 있다. 보드의 각 칸에는 대문자 알파벳이 하나씩 적혀 있고, 좌측 상단 칸 (1행 1열) 에는 말이 놓여 있다. 말은 상하좌우로 인접한 네 칸 중의 한 칸으로 이동할 수 있는데, 새로 이동한 칸에 적혀 있는 알파벳은 지금까지 지나온 모든 칸에 적혀 있는 알파벳과는 달라야 한다. 즉, 같은 알파벳이 적힌 칸을 두 번 지날 수 없다. 좌측 상단에서 시작해서, 말이 최대한 몇 칸을 지날 수 있는지를 구하는 프로그램을 작성하시오. 말이 지나는 칸은 좌측 상단의 칸도 포함된다. 풀..

그래프 탐색 그래프를 탐색하는 기법에는 대표적으로 2가지가 있다. 너비 우선 탐색인 BFS(Breadth-First Search)와 깊이 우선 탐색인 DFS(Depth-First Search)이다. BFS BFS는 큐를 이용하여 구현한다. 설명 트리로 예를 들었지만, 모든 그래프에서 마찬가지로 동작한다. 루트 노드를 queue에 넣는다. queue의 노드를 하나 꺼낸 후, 해당 노드와의 인접 노드를 모두 queue에 넣는다. 위의 방식을 모든 노드가 완료될 때까지 반복한다. stack에 들어간 순서를 보면 다음과 같다. 1=>2=>3=>4=>5=>6=>7=>8 따라서 트리에서 BFS를 실행하여 탐색을 하는 것은 레벨 순회를 하는 것과 같다. DFS DFS는 스택을 이용하여 구현한다. 설명 트리로 예를 들..

탐색 탐색은 주어진 자료들 중 원하는 조건에 해당하는 자료를 찾는 과정이다. 컴퓨터에서 탐색은 자주 이루어지므로 효율적인 방식으로 수행하는 것이 중요하다. 이전에 배웠던 '정렬'은 탐색을 수행할 수 있는 방법 중 하나이다. 정렬은 리스트를 하나의 기준으로 나타내기 위해서도 쓰이지만 원하는 자료를 빠르게 탐색하기 위해 쓰이기도 한다. 물론 굳이 정렬이 아니더라도 탐색을 수행할 수 있는 방법은 있다. 정렬 보기 앞으로 소개할 탐색은 다음의 4가지 종류이다. 선형탐색 이진탐색 해시탐색 BST 탐색을 위해서는 배열, 연결 리스트, 트리, 그래프 등 다양한 자료구조가 사용되며, 상황에 따라 맞춰서 사용하면 된다. 자료구조 보기 선형 탐색 순차 탐색이라고도 불리는 선형 탐색은 가장 간단한 탐색 방법이다. 선형 탐색..

BST BST(Binary Search Tree)는 트리의 한 종류이자 이진탐색을 위한 방법 중 하나이다. 과정 BST를 이용한 탐색에서는 다음과 같은 과정을 거친다. 이진 탐색 트리 만들기 (생성) 루트 노드에서 내려가면서 원하는 요소 찾기 (탐색) 삭제 및 삽입 하기 (삭제 / 삽입) 예시 먼저 이진 탐색 트리를 만들어보자. 이진 탐색 트리는 부모 노드를 기준으로 왼쪽 서브트리에는 더 작은 값의 노드가 오른쪽 서브트리에는 더 큰 값의 노드가 있어야한다. 따라서 요소를 하나씩 삽입하면서 알맞은 위치를 찾아주면 된다. 결과적으로 나온 이진 탐색 트리를 중위 순회하면 정렬된 리스트가 된다. 그 다음에는 루트 노드에서 내려가면서 원하는 요소를 찾고 삭제해보자. 원하는 요소는 6이다. 왼쪽 그림에서 오른쪽 그..