전체 글 (125) 썸네일형 리스트형 1918 후위 표기식 문제의 조건이 너무 이해가 안되서 따로 찾아본 문제다.. 단순한 규칙에 따라 문자열을 출력하면 되는데, 입력받은 문자열을 첫 번째부터 마지막까지 순회하며 다음과 같이 룰을 적용한다. 현재 문자를 C라 하면 C가 알파벳이라면 그냥 출력한다. C가 *, / 이라면 스택에 남아있는 문자들 중에 자신과 같은 우선순위의 문자들을 모두 pop & 출력한 뒤, C를 push한다. C가 +, - 이라면 스택에 남아있는 문자들 중에 자신과 같거나, 높은 순위의 문자들을 모두 pop & 출력한 뒤, C를 push한다. C가 ( 이라면 C를 스택에 push한다. C가 ) 이라면 (를 만날 때까지 pop & 출력한다. 처음에 우선순위를 어떻게 구현해야 하나 고민했었는데, 우선순위를 적용하는건, 스택에서 pop했을 때, if .. 1916 최소비용 구하기 문제의 조건들을 양의 가중치를 가진 그래프로 추상화할 수 있으며, 최소비용을 구하는 과정은 한 정점과 다른 정점 쌍들의 최단거리를 구하는 문제와 같기 때문에 다익스트라 알고리즘으로 쉽게 구할 수 있다. 정답코드 더보기 #include #include #include #include using namespace std; #define MAX_V 1001 #define INF 987654321 vectoradj[MAX_V]; int N, M; int Start, End; void djikstra(int start) { vector dist(N + 1, INF); priority_queue pq; pq.push({ start, 0 }); dist[start] = 0.. 그래프 이론 관련 알고리즘 정리 프로그래밍 문제를 풀면서, 묵시적인 그래프 구조를 요구하는 문제들이 많이 보여 이 기회에 정리해야 겠다는 생각이 들었다. 먼저 묵시적인 그래프 구조라는건 무엇을 말하는걸까 굳이 그래프라고 언급하지 않아도 그래프로 추상화하여 풀 수 있는 문제들이 많다. 대표적으로, 최단거리, 최소 시간 등등의 키워드가 나오면 그래프로 추상화 해볼 수 있다. 이 때, 입력받는 형식은 1차원 혹은 2차원 배열의 형식으로 저장하게 될텐데 이를 추상화한다. 추상화하는 방식에도 종류가 있다. 인접 행렬 2차원 배열 형태로 간선 여부를 표현한다. 주로 boolean 타입 혹은 int 타입으로 표현하며, fully connected가 아니라면 메모리 공간의 낭비가 생길 수 있다. e.g. bool adj[100][100] 인접 리스트.. 이전 1 ··· 30 31 32 33 34 35 36 ··· 42 다음