해나의 컴공생존기

https://www.acmicpc.net/problem/10989 문제 N개의 수가 주어졌을 때, 이를 오름차순으로 정렬하는 프로그램을 작성하시오. 입력 첫째 줄에 수의 개수 N(1 ≤ N ≤ 10,000,000)이 주어진다. 둘째 줄부터 N개의 줄에는 수가 주어진다. 이 수는 10,000보다 작거나 같은 자연수이다. 출력 첫째 줄부터 N개의 줄에 오름차순으로 정렬한 결과를 한 줄에 하나씩 출력한다. 출력 이는 원래 하던 merge sort로 하면 메모리 초과가 난다. 여기서 힌트로 봐야할 것은 숫자의 중복이 있다는 것과 입력되는 수는 10,000이하라는 것이다. 이 문제의 풀이는 10,000짜리 배열을 만들어서 각 숫자가 몇개 들어왔는지 세고 출력하는 것이다. #include using namespa..

https://www.acmicpc.net/problem/15651 문제 자연수 N과 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오. 1부터 N까지 자연수 중에서 M개를 고른 수열 같은 수를 여러 번 골라도 된다. 입력 첫째 줄에 자연수 N과 M이 주어진다. (1 ≤ M ≤ N ≤ 7) 출력 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해야 한다. 풀이 #include using namespace std; int N, M; int check[10]; int num[10]; void NM(int n){ if(n==M){ ..

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

문제 N개의 정수로 이루어진 수열이 있을 때, 크기가 양수인 부분수열 중에서 그 수열의 원소를 다 더한 값이 S가 되는 경우의 수를 구하는 프로그램을 작성하시오. 입력 첫째 줄에 정수의 개수를 나타내는 N과 정수 S가 주어진다. (1 ≤ N ≤ 20, |S| ≤ 1,000,000) 둘째 줄에 N개의 정수가 빈 칸을 사이에 두고 주어진다. 주어지는 정수의 절댓값은 100,000을 넘지 않는다. 출력 첫째 줄에 합이 S가 되는 부분수열의 개수를 출력한다 풀이 백트래킹 문제 너무 어렵다…. 처음에는 연속되는 수열을의 합만 되는줄 알고 풀었다가 틀렸다. 이는 숫자 하나하나 보며 해당 숫자를 더했을때와 더하지 않았을때를 고려한다. 코드 자체는 N과 M 문제보다 쉬운 것 같은데.. 백트래킹 자체가 나한테 잘 안 와..

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 연산을 수행해야 하는지를 알아낼 수 있다. 이를 계산하는 프로그램을 ..

영역찾기는 전에도 해봤지만, 이번에는 각 색의 영역을 찾아야한다..ㅠ 그리고 두케이스를 봐야한다. 먼저 나는 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

어려운문제는 아니다! 하지만 출력을 예제처럼 깔끔하게 하려고 저장해놨다가 출력했더니 계속 틀렸다. 질의응답을 봤더니 다들 그냥 바로 출력했길래 나도 그렇게 했더니 맞았다..ㅎㅎ #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

알고리즘시간에 배운 동적프로그래밍 문제를 하나 가져와봤다. 의사코드를 한번 보면 재귀호출은 들어온 숫자(n)이 1이나 2가 아니라면 n-1과 n-2를 인자로 재귀호출하여 더해준다. 만약 6이 들어온다면 f(6) → f(5) + f(4) → ( f(4)+f(3) ) + ( f(3)+f(2) ) → ( ( f(3)+f(2) ) + ( f(2)+f(1) ) ) + ( ( f(2)+f(1) )+1 ) → ( ( ( f(2)+f(1) )+1 ) + ( 1+1 ) ) + ( (1+1 )+1 ) → ( ( ( 1+1 )+1 ) + 2 ) + 3 → 8 동적프로그래밍 의사코드를 보면 인자로 들어온 n만큼 배열을 만들어서 인덱스 1,2, 에는 1을 넣어주고 나머지 인덱스에는 앞에 두자리를 더한 값을 넣어준다. 하지만 '..