해나의 컴공생존기

https://www.acmicpc.net/problem/1874 문제 스택 (stack)은 기본적인 자료구조 중 하나로, 컴퓨터 프로그램을 작성할 때 자주 이용되는 개념이다. 스택은 자료를 넣는 (push) 입구와 자료를 뽑는 (pop) 입구가 같아 제일 나중에 들어간 자료가 제일 먼저 나오는 (LIFO, Last in First out) 특성을 가지고 있다. 1부터 n까지의 수를 스택에 넣었다가 뽑아 늘어놓음으로써, 하나의 수열을 만들 수 있다. 이때, 스택에 push하는 순서는 반드시 오름차순을 지키도록 한다고 하자. 임의의 수열이 주어졌을 때 스택을 이용해 그 수열을 만들 수 있는지 없는지, 있다면 어떤 순서로 push와 pop 연산을 수행해야 하는지를 알아낼 수 있다. 이를 계산하는 프로그램을 ..

모든 경우의 수를 하나하나 확인해봐야하는 문제다! 엥 간단하다! 하고 덤볐는데 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의 범위를 넘어가는 것 같..

영역찾기는 전에도 해봤지만, 이번에는 각 색의 영역을 찾아야한다..ㅠ 그리고 두케이스를 봐야한다. 먼저 나는 color배열랑 Ncolor배열응 만들어 색약이 아닌 사람과 색약인 사람의 배열을 분리했다. Ncolor에는 G와 R이 있다면 1을 넣었다. 그리고 color배열에서 RGB로 세번 영역을 찾고 Ncolor배열에서 1로 영역을 찾아야겠다고 생각했다. 한참 코드를 짜다가 생각났는데 배열이 하나만 있어도 충분히 가능할 것 같았다. BFS조건만 좀 수정하면되니까... 근데 이미 코드를 너무 많이 짜서 킵고잉하자..! (뒤늦게 생각난건데 배열하나로 진행하려면 방문했는지 확인하는 배열이 필요하기때문이 메모리는 똑같을 것 같다 ㅎㅎ) 이야!! 성공했다! 짜잘짜잘한 오류가 있었지만 전에 비해 훨씬 빠르게 해결한..

이번에는 몇모둠이 있나?에 대한 문제이다. 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업데이트할때 같이 업데이트해가면서 비교해봐야겠다고 생각했다. 계속 어떤 케이스는 되고 어떤케이스는 안되고 해서 오류를 하나하나 고쳐나갔다. 근데 이제 웬만하면 모든케이스가 다 되는데... 너무 억울한데..도대체 뭐때문에 안되는지 모르겠다ㅠㅠ 일단 내 코드는 차차 고민해보는걸로하고..! 다른 아이디어..

골드단계의 문제를 스스로 풀어보는건 처음이라! 꼭 스스로 풀겠다는 다짐을 하며 문제를 보았다. 음..1부터 시작해서 그냥 0인거 BFS하면 되겠다 싶었는데 요일를 세야하니까 한 타임에 몇개가 큐에 들어왔는지 세서 그 큐가 다 소진될때마다 하루씩 늘려야겠다고 생각했다. 풀 수 있을거같은데 시간초과가 날거같은...느낌? 일단 GO 다른 방법이 생각났다. 며칠째에 내가 익었는지 내 칸에 적어놓는다면 내 다음칸은 내 칸을 보고 +1을 하면 된다!! 다이나믹한 방법이다. 야호~! 맞았따~!~! 혼자힘으로 했다는게 너무 뿌듯하다~!~! #include #include #include using namespace std; int dx[4] = {0,1,0,-1}; int dy[4] = { 1,0,-1,0 }; que..