해나의 컴공생존기

미로찾기는 BFS에서 많이 나오는 문제이다. 미로찾기 까지는 성공했지만,,, 이 문제의 핵심인 최단경로구하는거에서 막혔다.. 가다가 이길이 아닐때 어떻게 거리를 구하지...??? 맞는일인지 아닌지 어떻게 알고 거리를 update하지?? 이 것에 대한 해결방안으로 방문했는지 체크하는 배열에 이 자리까지 오는데 걸린 거리를 저장하는걸로 하였다. 다이나믹 프로그래밍..을 이용했다고 볼 수 있을 것 같다. #include #include #include #include using namespace std; int check[100][100]; int n, m; int dx[4] = { 0,1,0,-1 }; int dy[4] = { 1,0,-1,0 }; string a[100]; int main() { ios::..

어떤식으로 해야할지 알 것 같으면서도...코드로 짜려고하니까 잘 생각이 안난다. BFS로 1이 있는한 계속 탐색을 하고 0 으로 둘러쌓이면 탐색을 멈추면된다. 그렇게 그림을 하나 찾아내면 그 다음은 어디에서부터 탐색해야할까? 내가 놓치고 있던게 있었다. 다 0으로 둘러쌓여있으면 Queue는 비기 때문에 BFS는 끝난다. 그럼 그 이후 탐색을 하면서 방문하지 않았고 1인 지점을 찾은 뒤 거기서 부터 다시 BFS를 진행하면된다..! BFS 문제를 처음 풀어봐서 조금의 도움을 받았다는게 너무 아쉽고 찝찝하다... 다음에는 무슨일이 있어도 꼭 내 힘으로만 풀어야지!!!!!!!! #include #include #include using namespace std; int check[500][500]; int ma..

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

앞뒤로 넣기 간단한 deque를 이용하면 해결할 수 있을 것 같다. 1번도 연산자의 일부라고 생각해서 1번을 사용할 수 있으면 1번을 쓰고 1번을 못쓰는경우에만 2번3번을 써야한다고 생각해서 실버4치고 복잡하다고 생각하고있었다.. 아직 문제를 많이 안풀어봐서 문제해석능력이 부족한것같다. 찾을 숫자는 num이라는 배열에 정리하였고 순서판의 숫자들은 deque에 넣어관리하였다. 분명 간단하다고 생각했는데... 자꾸 실패해서 보니까 왼쪽이동 오른쪽이동의 규칙이 명확하지 않았다. 그래서 찾아야하는 숫자의 인덱스와 덱의 사이즈의 절반을 비교하여 오른쪽으로 이동할지 왼쪽으로 이동할지 결정하였다. 그랬더니 바로 원하는 결과가 나왔다! #include #include using namespace std; int num..

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

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

어려운문제는 아니다! 하지만 출력을 예제처럼 깔끔하게 하려고 저장해놨다가 출력했더니 계속 틀렸다. 질의응답을 봤더니 다들 그냥 바로 출력했길래 나도 그렇게 했더니 맞았다..ㅎㅎ #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. 문제정의 모든 노드 쌍들마다의 최단경로 구하기 (path까지는 어렵기 때문에 길이만 구할 것이다) undirect 그래프라고 가정. 가장 쉬운방법은 다익스트라 알고리즘을 n번 돌리는 것이다. 2. Floyd Warshall Alg 각 노드별로 번호를 부여했다고 가정하자. i → j로 가는 최단경로를 구할 건데, {1, 2, ..., k}번 노드 중에서만 거쳐가는 최단 경로를 찾으면 된다. 이 과정을 k가 0부터 N까지 반복한다. (k가 n일 때가 최종 답이된다,) 즉, 구하고자 하는 것은 모든 (i, j) 쌍에 대하여 1번부터 k번 노드 중에서만 거쳐서 갈 수 있는 최단경로이다. k=0이라면 {공집합}이고 i와 j를 연결하는 것은 direct edge밖에 없다. direct edge가 없다면 답은 ..