해나의 컴공생존기

국어를 잘못하는지 집중력이 낮은지.. 문제 이해하는데에 좀 걸렸다. 결론적으로는 괄호문제와 비슷하다고 생각했다. A괄호와 B괄호가 있다고 생각하고 풀면 어렵지 않을 것 같다. 한 줄 읽고 한글자씩 보면서 읽은 글자가 스택의 맨 위와 같으면 pop해주고 그렇지 않다면 스택에 push 해준다. 스택이 비어있다면 무조건 push해준다. #include #include #include using namespace std; int main() { ios::sync_with_stdio(0); cin.tie(0); int N,cnt=0; cin >> N; for(int i=0;i

괄호문제는 스택을 쓰는 대표적인 문제이다! 문자열을 하나씩 읽어서 괄호만 스택에서 관리해야겠다. 나름 생각한대로 알고리즘을 짰는데,,, 시간초과가 났다. 먼저 간단하게 할 수 있는 것들부터 했다. 1. ios::sync_with_stdio(0); 2. cin.tie(0); 3. endl안쓰기 하지만 해결이 안됐고,, 결국 답지를 보면서 원인을 찾아봤다. 시간초과가 안나기 시작한건 char배열으로 getline을 받았는데 string으로 getline으로 받았다는 것과 이 변화에 따라서 for each문으로 바꾼것!이다. 그랬더니 틀렸습니다! 가 떴고 일단 시간초과가 안난것이 기뻤다 ㅎㅎ 그다음에 여러가지 반례를 찾아보고 열리는 괄호만 있을 때 안된다는 것을 발견했다! 그것만 고쳤더니 맞았습니다!를 만났다..

1. 알고리즘 설명 다차원 배열에서 각 칸을 방문할 때 너비를 우선으로 방문하는 알고리즘 시작하는 칸을 큐에 넣고 방문했다는 표시를 남김 큐에서 맨 앞의 원소를 꺼내어 그 칸에 상하좌우로 인접한 칸에 대해 3번을 진행 해당칸을 이전에 방문했다면 아무것도 하지 않고, 처음으로 방문했다면 방문했다는 표시를 남기고 해당 칸을 큐에 삽입 큐가 빌 때까지 2번을 반복 시간복잡도는 모든 칸이 큐에 한번씩 들어가므로 칸이 N개일 때 O(N)이된다. 2. 코드 BFS는 코딩테스트에서 굉장히 중요한 부분이므로 꼭 잘 숙지해야함! #include using namespace std; #define X first #define Y second // pair에서 first, second를 줄여서 쓰기 위해서 사용 int bo..

큐를 이용하면 구현이 어렵지 않을 것 같다! #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. 문제정의 행렬의 곱에서 어떤 행렬을 먼저 곱하냐에 따라 걸리는 시간이 달라진다. 행렬들은 M1, M2, ... Mn으로 표현되며, 행렬의 크기는 di-1 * bi로 표현된다. Cij는 Mi부터 Mj까지 곱했을 때 최소 비용을 의미하며 C1n이 최종 답이 된다. 2. solution 전체 답을 제일 좋은 답으로 만들기 위해서는 어떤 곱을 나중에 해야할까? 우리는 이 문제에 대한 해답을 알지 못한다. 따라서 하나씩 다 해볼 것이다. Cij에서 i-j가 작은 값부터 해볼 것이다. 1) i-j =0 C11,C22,C33, ... Cnn 위와 같은 경우는 비용이 모두 0이라고 할 수 있다. 2) i-j =1 C12,C23,C34, ... Cn-1n 비용은 di-1 * di * di+1 3) i-j =2 C1..

정의해준 재귀함수를 분석해보겠다. 인자로 a,b,c 가 들어오고 이 값에 따라 재귀호출을 하는 것 같다. a,b,c 중 하나라도 0이하가 되면 1을 리턴한다. a,b,c 중 하나라도 20이상이 되면 a,b,c에 20을 넣고 재귀호출한다. a> b >> c; if (a == -1&&b==-1&&c==-1) break; //종료조건 cout