해나의 컴공생존기

https://www.acmicpc.net/problem/2493 문제 KOI 통신연구소는 레이저를 이용한 새로운 비밀 통신 시스템 개발을 위한 실험을 하고 있다. 실험을 위하여 일직선 위에 N개의 높이가 서로 다른 탑을 수평 직선의 왼쪽부터 오른쪽 방향으로 차례로 세우고, 각 탑의 꼭대기에 레이저 송신기를 설치하였다. 모든 탑의 레이저 송신기는 레이저 신호를 지표면과 평행하게 수평 직선의 왼쪽 방향으로 발사하고, 탑의 기둥 모두에는 레이저 신호를 수신하는 장치가 설치되어 있다. 하나의 탑에서 발사된 레이저 신호는 가장 먼저 만나는 단 하나의 탑에서만 수신이 가능하다. 예를 들어 높이가 6, 9, 5, 7, 4인 다섯 개의 탑이 수평 직선에 일렬로 서 있고, 모든 탑에서는 주어진 탑 순서의 반대 방향(왼..

백준을 풀다가 처음으로 Segfault가 발생했다...!! 근데 아무리봐도 일어날만한 곳이 없는것이다... 검색을하다가 점검해야할 부분을 깨닫게 되었고 안까먹기 위해 적어놓는다. 1. 배열, stack을 선언하고 내부를 건드는지 2. 반복문 내부에서 적절한 타이밍에 나가지 않아서 건들면 안되는 것을 건드는가..? 1번은 잘 알고있었는데 2번을 놓치고 있었다.

모든 경우의 수를 하나하나 확인해봐야하는 문제다! 엥 간단하다! 하고 덤볐는데 for문 8개 돌리기밖에 생각이 안났다. 어쩌지어쩌지하다가 재귀를 풀면 될 것 같다..! 라고생각했고 배열을 만들어 맨 앞에서 부터 차례대로 채워 나가면 되겠다는 생각을 했다. 인자 n번째 칸을 결정하는 함수를 만든뒤 차례차례 뒤에를 채울 수 있게 재귀를 돌렸다. n번째칸이 문제에서 제시된 M과 같다면 모아놓은 배열을 출력하고 다시 새로운수를 만들면된다. #include using namespace std; int N, M; int num[10]; int check[10]; void NM(int n) { if (n == M) { for (int i = 0; i < M; i++) { cout M; NM(0); return 0; }

별로 어려운 문제는 아니다! 답변을 "재귀함수는 자기 자신을 호출하는 함수라네" 하는 문구를 기준으로 생각해야한다. 답변 앞에를 출력하고 재귀함수를 부르고 답변뒤에는 출력하면 재귀가 알아서 잘 실행이된다! #include using namespace std; int n; void chat(int x) { if (x == n) { for (int i = 0; i < x; i++) cout

찾으려는 값이 들어간 2*2 박스의 첫 칸만 안다면 찾으려는 값도 쉽게 찾을 수 있다 순서가 필요하기 때문에 고민이 되는 문제이다 먼저 제일먼저 생각나는건! 재귀로 배열을 채우고 주어진 배열의 값을 출력하는것이다! 하지만 이런 방법은 너무 비효율적일 것 같다. 2의 15승까지 될 수 있는데..이는너무 오래걸린다. 그래서 생각해본건 4개로 나누고 찾으려는 숫자가 있는 범위를 4칸 중에 한 칸를 선택하고, 또 그 한 칸을 4개로 나누고 범위를 찾고 하면서 구체화 시키면 될 것 같다. 정리하자면 전체 칸을 4칸으로 나누고 각 칸은 그 칸의 제일 앞에있는 수로 관리하는 것이다. 각 칸의 맨 앞에 있는 수의 좌표와 값을 알아야하는데, 규칙을 찾아보면 다음과 같이 된다는 것을 알 수 있다. Z함수는 a,b점이 대표..

하노이탑은 재귀로 아주 유명한 문제이다! 이 문제는 아주 복잡하기 때문에 절차지향적으로 하나하나 생각하면 답이 전혀 안나온다... n개일떄 어떻게 해야하나? 를 생각해야 답이 나온다. hanoi(int a,int b, int n) 이라는 함수는 a에서 b까지 n개의 칸을 옮긴다고 해보자 n칸의 탑을 a에서 b까지로 옮긴다면 6-a-b칸을 이용해야한다. 6-a-b칸에 n-1개의 칸을 옮겨놓고 → hanoi(a,6-a-b,n-1) 맨 밑에 있던 n칸을 b로 옮기고 6-a-b칸에 있는 n-1개의 탑을 b칸으로 옮기면 된다! → hanoi(6-a-b,b,n-1) 이동한 횟수를 매번 세는 것은 어렵다. 점화식을 이용하여 식을 구해보자! n번째 옮기는 식이 k번이라면 n+1번째는 2*k +1 이 된다. n개를 옮기..

처음에는 그냥 문제 그대로 a를 b번 곱해준 뒤 c로 나눠서 출력해줬다. 이렇게 쉬울리가 없는데 하면서 실행시켜보니 음수값이 나왔다... 코드를 보면 음수값이 나올 이유가 전혀 없었는데...곰곰히 생각해보니 overflow가 일어났다는 것을 알 수 있었다. 그래서 곱해주는 것과 동시에 C로 계속 나눠주었다. 하지만 이렇게 하니 A,B,C가 커질수로 시간이 너무 오래 걸렸다. 이 문제의 핵심은 재귀이다 결국 a의 b승을 c로 나눴을 때 나머지를 구하는 것이다. b가 짝수이면 : a^b = a^(b/2) x a^(b/2) b가 홀수이면 : a^b = a^(b/2) x a^(b/2 + 1) 위 식을 이용하여 분할정복 해야한다. 분명 맞는데...왜 자꾸 틀리지 했더니 곱셈과정에서 int의 범위를 넘어가는 것 같..

이번에는 몇모둠이 있나?에 대한 문제이다. 1을 찾아서 BFS를 진행하고 또 1을 찾아서 BFS를 하고 이런식으로 반복하면 금방 개수를 알 수 있지 않을까? 하는 생각이 들었다. 코딩해보자~! 우왕!! 한번에 맞았다. 디테일이 부족해서 계속 while문을 돌아 여러번에 디버깅이 필요햇지만 그래도 크게 어려움을 겪지 않고 성공했다! #include #include #include using namespace std; int farm[50][50]; int dx[4] = { 1,0,-1,0 }; int dy[4] = { 0,1,0,-1 }; int main() { int a, num = 0,N, M ,K, x, y, flag = 0,sx,sy; cin >> a; for (int i = 0; i < a; i+..

흠..쉬울것같았는데 은근 고민스럽다..! 일단 미로문제니까 BFS로 풀자! 먼저 진호의 위치와 불의 위치를 파악하고, 진호의 위치로부터 가장자리로 가는 최단거리를 구한다. 최단거리를 구하는 방법은 check판에 이 자리까지 오는데 걸린거리를 기록하면서 나중에 최대값을 찾으면 될 것 같다. 불이랑 만나는지는 최단거리 루트를 구하고 생각할지, 아니면 BFS하면서 같이 구할지 고민하다가 fire배열을 만들어서 BFS업데이트할때 같이 업데이트해가면서 비교해봐야겠다고 생각했다. 계속 어떤 케이스는 되고 어떤케이스는 안되고 해서 오류를 하나하나 고쳐나갔다. 근데 이제 웬만하면 모든케이스가 다 되는데... 너무 억울한데..도대체 뭐때문에 안되는지 모르겠다ㅠㅠ 일단 내 코드는 차차 고민해보는걸로하고..! 다른 아이디어..

미로찾기는 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::..