해나의 컴공생존기

문제 자연수 N과 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오. 1부터 N까지 자연수 중에서 중복 없이 M개를 고른 수열 고른 수열은 오름차순이어야 한다. 입력 첫째 줄에 자연수 N과 M이 주어진다. (1 ≤ M ≤ N ≤ 8) 출력 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해야 한다 풀이 백트래킹에 대한 감이 아직 없는건지 N과M(1)과 비슷한 문제인데 꽤 헤맸다. 하지만 그저 간단하게 for문을 이전 n 값부터 돌리면 되는 거였다. num[n-1]을 위해 num은 index 1부터 사용했다. 몇개 더 풀어봐야할..

https://www.acmicpc.net/problem/1780 문제 N×N크기의 행렬로 표현되는 종이가 있다. 종이의 각 칸에는 -1, 0, 1 중 하나가 저장되어 있다. 우리는 이 행렬을 다음과 같은 규칙에 따라 적절한 크기로 자르려고 한다. 만약 종이가 모두 같은 수로 되어 있다면 이 종이를 그대로 사용한다. (1)이 아닌 경우에는 종이를 같은 크기의 종이 9개로 자르고, 각각의 잘린 종이에 대해서 (1)의 과정을 반복한다. 이와 같이 종이를 잘랐을 때, -1로만 채워진 종이의 개수, 0으로만 채워진 종이의 개수, 1로만 채워진 종이의 개수를 구해내는 프로그램을 작성하시오. 입력 첫째 줄에 N(1 ≤ N ≤ 37, N은 3k 꼴)이 주어진다. 다음 N개의 줄에는 N개의 정수로 행렬이 주어진다. 출..

https://www.acmicpc.net/problem/5427 문제 상근이는 빈 공간과 벽으로 이루어진 건물에 갇혀있다. 건물의 일부에는 불이 났고, 상근이는 출구를 향해 뛰고 있다. 매 초마다, 불은 동서남북 방향으로 인접한 빈 공간으로 퍼져나간다. 벽에는 불이 붙지 않는다. 상근이는 동서남북 인접한 칸으로 이동할 수 있으며, 1초가 걸린다. 상근이는 벽을 통과할 수 없고, 불이 옮겨진 칸 또는 이제 불이 붙으려는 칸으로 이동할 수 없다. 상근이가 있는 칸에 불이 옮겨옴과 동시에 다른 칸으로 이동할 수 있다. 빌딩의 지도가 주어졌을 때, 얼마나 빨리 빌딩을 탈출할 수 있는지 구하는 프로그램을 작성하시오. 입력 첫째 줄에 테스트 케이스의 개수가 주어진다. 테스트 케이스는 최대 100개이다. 각 테스트..

https://www.acmicpc.net/problem/7562 문제 체스판 위에 한 나이트가 놓여져 있다. 나이트가 한 번에 초록색 칸으로 이동할 수 있다. 나이트는 몇 번 움직이면 이 칸으로 이동할 수 있을까? 입력 입력의 첫째 줄에는 테스트 케이스의 개수가 주어진다. 각 테스트 케이스는 세 줄로 이루어져 있다. 첫째 줄에는 체스판의 한 변의 길이 l(4 ≤ l ≤ 300)이 주어진다. 체스판의 크기는 l × l 이다. 체스판의 각 칸은 두 수의 쌍 {0, ..., l-1} × {0, ..., l-1}로 나타낼 수 있다. 둘째 줄에는 나이트가 현재 있는 칸, 셋째 줄에는 나이트가 이동하려고 하는 칸이 주어진다. 출력 각 테스트 케이스마다 나이트가 최소 몇 번만에 이동할 수 있는지 출력한다. 풀이 이..

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

별로 어려운 문제는 아니다! 답변을 "재귀함수는 자기 자신을 호출하는 함수라네" 하는 문구를 기준으로 생각해야한다. 답변 앞에를 출력하고 재귀함수를 부르고 답변뒤에는 출력하면 재귀가 알아서 잘 실행이된다! #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점이 대표..

처음에는 그냥 문제 그대로 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조건만 좀 수정하면되니까... 근데 이미 코드를 너무 많이 짜서 킵고잉하자..! (뒤늦게 생각난건데 배열하나로 진행하려면 방문했는지 확인하는 배열이 필요하기때문이 메모리는 똑같을 것 같다 ㅎㅎ) 이야!! 성공했다! 짜잘짜잘한 오류가 있었지만 전에 비해 훨씬 빠르게 해결한..

국어를 잘못하는지 집중력이 낮은지.. 문제 이해하는데에 좀 걸렸다. 결론적으로는 괄호문제와 비슷하다고 생각했다. 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