해나의 컴공생존기

주어진 괄호 문자열이 올바른지 판단하는 것! 어떻게 판단해야할까? 괄호쌍을 찾아야함! 연결리스트로도 구현가능하지만 스택으로도 가능! 여는 괄호면 스택에 넣고 닫는괄호는 스택의 맨 뒤에있는 괄호와 짝 짓기! 짝이 안맞거나, 여는괄호와 닫는괄호의 개수가 맞지않을때 틀린 수식이라는것을 알아 챌 수 있음

큐를 이용하면 구현이 어렵지 않을 것 같다! #include #include using namespace std; int main() { queue p; int N,s=0; cin >> N; for (int i = 1; i

입력되는 숫자를 차곡차곡 스택에 넣다가 0이 입력되면 스택에서 하나를 빼는 방식으로 코드를 짜면 쉽게 해결이 될 것 같다. 마지막에는 스택에 있는 값을 모두 더하면 출력값도 쉽게 구할 수 있을 것 같다. #include #include using namespace std; int main() { int K,a,sum=0; cin >> K; stack s; for (int i = 0; i > a; if (a == 0) { s.pop(); } else { s.push(a); } } a = s.size(); for (int i = 0; i < a; i++) { sum += s.top(); s.pop(); } cout

어려운문제는 아니다! 하지만 출력을 예제처럼 깔끔하게 하려고 저장해놨다가 출력했더니 계속 틀렸다. 질의응답을 봤더니 다들 그냥 바로 출력했길래 나도 그렇게 했더니 맞았다..ㅎㅎ #include #include #include using namespace std; int main() { int n,b; string a; stack s; int* result = new int[n]; cin >> n; for (int i = 0; i > a; if (a == "push") { cin >> b; s.push(b); }else if(a == "top") { if (s.empty()) cout

스택이란 선입후출의 자료구조이다. 원소의 추가,제거,제일상단의 원소확인이 O(1)에 가능하지만 다른 위치의 원소확인과 변경이 원칙적으로 불가능하다. 하지만 배열과 연결리스트로 스택을 구현한다면 가능하다. 1. 배열로 스택 구현하기 cosnt in MX=1000005; int dat[MX]; int pos=0 //위치 void push(int x){ dat[pos++]=x; } void pop(){ pos--; } void top(){ dat[pos-1]; } 2. STL #include using namespace std; int main(void) { stack S; S.push(10); // 10 S.push(20); // 10 20 S.push(30); // 10 20 30 cout

이 문제는 자료구조를 잘 이용하는 문제인것 같다는 생각이 든다. 정해진 만큼 이동하고 출력하고 삭제하고, 마지막을 만나면 다시 처음으로가고 하면될 것 같다. 알고리즘은 별로 안어려운데 자료구조를 잘 활용해야할 것 같다. list도 이용해봤고 vector도 이용해봤는데 동적으로 계속 사이즈가 변해서 코드를 작성하기 힘들었다. 그래서 배열을 이용해서 해결하였다. 사용완료된 배열에는 숫자대신 -1를 넣어줌으로써 k를 셀때 제외할 수 있도록 하였다. 현재 인덱스 번호가 배열사이즈를 넘는다면 다시 처음으로 돌아가도록 하였다. #include using namespace std; int main() { int a; cin >> a; int* p = new int[a]; //동적할당 for (int i = 0; i ..

1. 문제정의 위 모양의 퍼즐을 1234 순서대로 만드는것이다. 빈칸의 상하좌우 숫자들은 빈칸과 자리를 바꿀 수 있다. 2. State Space 상태공간이란, 문제가 처할 수 있는 모든 상태를 모아놓은 것이다. 모든 상태가 다 solve가능한 상태일까? 아니다. 퍼즐 두개를 뽑아서 자리를 바꾸면 풀수 없는 상태가된다. 하지만 또 두개를 뽑아서 자리를 바꾸면 풀 수 있는 상태가 된다. state가 될 수 있는 모든 경우의수를 생각해보면 16!이다. 매우 큰 숫자이다..! 이 퍼즐에는 Invariant가 있다. Permutation과 빈칸과 코너의 거리를 더한 값이 유지된다는 것이다. 먼저 빈칸을 16으로 생각하고 배열을 만든다. 각 숫자에 자신보다 오른쪽 중 자신보다 작은수의 개수를 적는다(Permuta..

1. 문제 정의 N x N 크기의 체스판이 있을 때 N개의 퀸을 서로가 공격할 수 없도록 올려놓는 경우의 수를 구하는 문제이다. 2. idea N이 4일 때를 기준으로 생각해 보겠다. 2.1 다해본다 16C4 * 16 2.2 겹치는 경우는 뺀다. 한 열에 하나 씩 배치 4^4 2.3 cut off (1,1) 에 퀸을 배치하고 그 퀸이 갈 수 있는데를 다 표시한다. 표시되지 않은 칸들 중 하나에 퀸을 배치하고 또 그 퀸이 갈 수 있는데를 다 표시한다. 이런식으로 (1,1) 부터 (1,n)까지 시도해본다. 사실 오른쪽과 왼쪽은 대칭이기 때문에 왼쪽 반만하고 곱하기 2를 해줘도된다.

1. SCC (Strongly Connected Compnent) 방향 그래프에서 임의의 두 정점에 대해 양 방향으로 가는 경로가 모두 있을 때 두 점은 같은 SCC에 속해 있다고 한다. 즉 SCC는 모든 노드가 양방향으로 Reachable한 노드의 Maximal Subset 이다. 쉽게 말하자면 x→y가 있고 y→x가 있다면 strongly conneced하다고 한다. 사이클이 이의 가장 간단한 형태이다. 여기서 Maximal 과 Maximam의 차이를 조금 짚고 넘어갈 필요가 있응 것 같다. Maximal 은 한국어로 번역하면 극대라고 할 수 있다. 그 상황에서 가장 큰 값으로 이해하자. Maximam은 전체에서 가장 큰 것을 의미한다. DFS Tree에서 여러 트리가 있을 때 하나의 트리에는 여러가..

1. Topological Sort 번역하자면 위상정렬이다. *DAG: Directed Acyclic Graph (방향성이 있고 사이클이 없는 그래프) 위상 정렬은 DAG의 노드들을 왼쪽에서 오른쪽 방향(엣지 방향이 모두 오른쪽) 으로 정렬하는 것을 의미한다. DAG에 사이클이 존재하지 않으면 알고리즘은 항상 성공한다. 사이클이 없기 위해서는 indegree=0 인 노드가 최소 하나 이상 있어야한다. 이를 귀류법으로 증명해보겠다. indgree=0인 노드가 없다고 가정해보자. indgree=0인 노드를 안만들기 위해서는 계속 들어가는 노드를 만들어야하는데, 이 과정이 무한하게 흘러간다. 무한하지 않으려면 다른노드와 연결해야하는데 이렇게 되면 사이클이 생긴다. 1.1 algorithm DAG G에서 ind..