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

후위표기법으로 계산기 만들기 계산기 관련 외주가 들어와서 해보던 중, 예전에 배웠던 후위표기법을 사용해야했다. 그런데 기억이 안나서 검색 없이 혼자 구현하려다 보니 너무 어려웠다... 검색해보니까 stack을 이용해서 후위표기법을 만드는 간단한 방법이 나와있어서 까먹지 않기 위해 기록한다. 후위 표기법 수식 트리 후위 표기법이란 계산식에서 계산을 위해 사용하는 표기법이다. 예제와 함께 살펴보자. 수식 : 9x3+1-3%3 수식이 주어졌을 때 비연산자와 연산자로 나눈 후, 각 항목을 하나의 노드라고 생각하면 트리 형태로 만들 수 있다. 이러한 트리는 수식을 트리라는 자료구조로 만든 것이니 수식트리, 즉 Expression Tree라고 불린다. 트리 순회와 표기법 트리를 순회하는 방식에는 prefix(전위)..

정렬 어떤 데이터들이 주어졌을 때 이를 정해진 순서대로 나열하는 문제가 '정렬'이다. 보통 컴퓨터에서는 탐색을 위해서 정렬을 수행한다. 탐색은 정렬을 통해 하는 것보다 더 강력한 알고리즘이 있지만, 한 번 데이터를 정렬해두면 다음부터는 이진 탐색이라는 빠른 알고리즘을 몇 번이고 사용할 수 있기 때문에 유용하다. 그래서 주어진 무작위의 데이터를 정렬하는 것에 많은 연구자들이 방법을 내놓았는데, 앞으로 설명할 6개의 정렬 알고리즘이다. 그 외에도 많은 정렬 알고리즘이 존재한다. 모든 정렬의 설명에 앞서서 예제로 설명할 데이터는 다음 그림과 같이 무작위로 배치되어있는 1~7의 데이터이다. 정렬 알고리즘의 시간 복잡도는 비교 + 이동으로 측정한다. 특성 정렬 알고리즘은 여러 기준에 따라 나뉠 수 있다. 시간 복..

라면공장 https://programmers.co.kr/learn/courses/30/lessons/42629# 코드 #include #include #include using namespace std; vector node; int solution(int stock, vector dates, vector supplies, int k) { int answer = 0; int day = stock; int size = dates.size(); for (int i = 0; i < size; i++) { node.push_back(make_pair(dates[i], supplies[i])); } while (day < k) { int idx = 0; int max_idx = 0; while (idx < nod..

구조체 구조체는 배열과는 다르게 다른 자료형의 변수들을 모아서 하나의 단위로 표현하는 자료형이다. 용도 연결리스트나 그래프에서 노드를 나타낼 때, 데이터와 포인터 부분이 존재한다. 구조체를 사용하면 데이터와 포인터 부분을 각각 구성하여 하나의 자료형으로 만들어줄 수 있다. 이 때, 포인터는 해당 구조체의 포인터형이므로 이 구조체는 자체 참조 구조체가 된다. C++ struct Node { int value; Node* pointer; // 자체 참조 구조체 }; int main() { Node A; // 구조체 선언 A.value = 4; Node* Ap = A.pointer; // . 연산자로 접근 int Avalue = A.value; Ap = A; Avalue = Ap->value; // 포인터로 ..

힙 용도 구현 종류 연산 정렬 힙 힙은 추상적 자료형인 우선순위 큐를 구현하기 위해서 만들어진 자료구조이다. partial-ordering (부분 정렬)을 만족하는 left-complete binary tree (좌측 완전 이진 트리) 이다. 부분 정렬을 만족한다는 말은 '부모 노드와 자식노드' 간에는 특정 대소관계 성립하지만, '형제노드'간에는 해당 대소관계가 성립하지 않는다는 뜻이다. 이진 탐색 트리에서는 중복된 값을 허용하지 않지만 힙 트리에서는 허용한다. 용도 힙은 추상적 자료형인 우선순위 큐를 구현하기 위해서 만들어진 자료구조이다. 배열과 연결리스트를 이용하면 삽입과 삭제 연산 중 하나가 O(n)일 수 밖에 없다. 하지만 힙을 이용하면 가장 큰 값이나 가장 작은 값을 둘 다 O(logn)만에 빠..

트리 용도 용어 정리 종류 이진 트리 일반 트리 스레드 이진 트리 구현 배열 표현법 연결리스트 표현법 트리 활용 탐색 집합 표현 허프만 코드 트리 트리란 그래프의 한 종류로 무방향 연결 비순환 그래프(Connected Undirected Acyclic Graph)이다. 루트 노드가 존재하고, 루트 노드를 제외한 모든 노드의 in-degree가 1인 방향그래프라고 말할 수도 있다. 계층적인 구조를 가지며 그래프의 한 종류이므로 비선형 자료구조에 속한다. 용도 계층적인 조직을 표현하기 위해 사용되거나, 컴퓨터의 디렉토리 구조 / 인공지능의 decision tree 등에 이용된다. 또한 자료의 탐색 / 정렬 / DB 구성이나 분자구조식 설계 등에서도 다양하게 이용된다. (결정트리)(이진탐색) 용어 정리 노드 ..

그래프 용도 용어 정리 기본 심화 구현 인접 행렬 인접 리스트 비교 연산 분류 방향성에 따른 분류 연결에 따른 분류 사이클에 따른 분류 특수한 그래프 탐색 도출된 문제들 관련 알고리즘 참고 그래프 그래프란 '노드'와 노드를 연결하는 '간선'으로 이루어진 자료구조이다. 지금까지의 살펴본 자료구조들(리스트, 스택, 큐 등)과는 달리 그래프는 비선형 자료구조 이다. 용도 그래프는 일상생활에서 연결되어있는 객체 간의 관계를 표현할 때 사용된다. 예로 지도나 지하철 노선도, 전기회로, 도로 등을 들 수 있다. 또한 컴퓨터 세부전공에서는 통신 네트워크 분야에서도 쓰이며, 논리회로를 설계하고 분석하는 데에도 사용된다. 최근에는 웹사이트의 링크 연결(Page Rank)이나 SNS 상의 친구관계를 표현하는 데에도 사용되..