원

약 2년 전에 풀었던 문제를 다시 풀어보았다. 기억보다는 기록에 의존하라는 말이 이래서 있는건가. 풀 때는 몰랐는데 당시에 풀었던 게시글을 보니 2일이나 걸려 해결했던 문제였다. 이번 4학년 1학기 때 정확히 기억은 안나지만 대략 5-6회 코딩테스트를 응시했다. 프로그래머스 ,유니콘 기업, 우테캠 등등 적지 않은 코딩테스트를 응시했다. 난 2023년 2월까지만 코딩테스트를 공부하고 그 뒤로는 한 번도 문제를 풀지 않았고 그 전까지 공부했던 내 기억에만 의존한 채 할 수 있을거라는 근자감으로 코딩테스트를 응시했었다. 결과는 당연히 처참했다. C++ 문법도 헷갈려서 많은 시간을 뺏기고 구현 문제 외에는 다른 알고리즘을 해결할 수 없었다. 약 2년 간 양치기로 해결했던 문제들은 모두 나 자신도 속이는 겉핥기식..

c언어 알고리즘 문제를 풀면서 재귀함수 파트를 풀다보면 피할 수 없는 파트이다. 지금까지는 재귀 학습 자체를 안하다가 요즘 하게 되었는데 이제는 피할 수 없는 숙명이라고 받아들이고 이왕 공부하는 거 다시는 찾아보지 않도록 내 블로그에 내가 정리해보려고 한다. 1. 순열이란, - 순열이란 서로 다른 n개 중에서 r개를 택하여 배열하는 경우를 말한다. 기호로는 nPr로 나타낼 수 있다. - 순열의 예) 1) 1, 2, 3, 4, 5가 적혀 있는 숫자 카드가 있다, 이를 이용하여 세자리 수를 만들 수 있는 방법은 몇가지 인가? -> 이 문제를 풀 때 어떻게 할 것인가. 세자리수면 백의 자리, 십의 자리, 일의 자리가 존재하고 각 자리에 올 수 있는 카드의 개수를 곱해줄 것이다. 즉, 백의 자리에는 카드의 개수..

https://www.acmicpc.net/problem/2239 2239번: 스도쿠 스도쿠는 매우 간단한 숫자 퍼즐이다. 9×9 크기의 보드가 있을 때, 각 행과 각 열, 그리고 9개의 3×3 크기의 보드에 1부터 9까지의 숫자가 중복 없이 나타나도록 보드를 채우면 된다. 예를 들어 다 www.acmicpc.net 문제 스도쿠는 매우 간단한 숫자 퍼즐이다. 9×9 크기의 보드가 있을 때, 각 행과 각 열, 그리고 9개의 3×3 크기의 보드에 1부터 9까지의 숫자가 중복 없이 나타나도록 보드를 채우면 된다. 예를 들어 다음을 보자. 위 그림은 참 잘도 스도쿠 퍼즐을 푼 경우이다. 각 행에 1부터 9까지의 숫자가 중복 없이 나오고, 각 열에 1부터 9까지의 숫자가 중복 없이 나오고, 각 3×3짜리 사각형(..

https://www.acmicpc.net/problem/10597 10597번: 순열장난 kriii는 1부터 N까지의 수로 이루어진 순열을 파일로 저장해 놓았다. 모든 수는 10진수로 이루어져 있고, 모두 공백으로 분리되어 있다. 그런데 sujin이 그 파일의 모든 공백을 지워버렸다! kriii가 순 www.acmicpc.net 문제 kriii는 1부터 N까지의 수로 이루어진 순열을 파일로 저장해 놓았다. 모든 수는 10진수로 이루어져 있고, 모두 공백으로 분리되어 있다. 그런데 sujin이 그 파일의 모든 공백을 지워버렸다! kriii가 순열을 복구하도록 도와주자. 입력 첫 줄에 공백이 사라진 kriii의 수열이 주어진다. kriii의 순열은 최소 1개 최대 50개의 수로 이루어져 있다. 놓쳤던 부분..

https://www.acmicpc.net/problem/16938 16938번: 캠프 준비 난이도가 10, 30인 문제를 고르거나, 20, 30인 문제를 고르면 된다. www.acmicpc.net 이 문제도 백트래킹으로 완전 탐색을 하는 문제이다. 개인적으로 전에 풀었던 문제가 더 까다로웠던 것 같은데 이 문제가 난이도는 더 높게 등록되어있다. 이 문제는 조건이 구간으로 나누어져 있어서 정렬을 먼저 한 후 몇 개를 최대로 뽑을 수 있는지 먼저 구해주었다. 만약 입력되는 난이도의 개수가 15개인데, 사실상 조건에 만족하는 개수는 2개 뿐이라면 나머지는 필요없는 연산이기 때문이다. 그래서 가장 먼저 범위에 만족하는 최대 개수를 구해주었다. 그리고 그 후는 똑같이 백트래킹 -> 완전탐색으로 구한 후 최종적으..

https://www.acmicpc.net/problem/18290 18290번: NM과 K (1) 크기가 N×M인 격자판의 각 칸에 정수가 하나씩 들어있다. 이 격자판에서 칸 K개를 선택할 것이고, 선택한 칸에 들어있는 수를 모두 더한 값의 최댓값을 구하려고 한다. 단, 선택한 두 칸이 인접 www.acmicpc.net N과 M을 응용한 문제로 2차원 배열에서 사용해야한다. 인접한 구간끼리는 합을 구하지 않으므로 방문 처리 표시를 통해 인접한 칸을 더하는 것을 방지한다. 그리고 백트래킹을 통해 완전탐색을 해야하므로 한 번 확인하고 나면 방문처리를 원래대로 돌려주어야 하는데 나는 스택으로 몇 개의 인접한 칸을 방문 처리 표시했는지 기억해두고 다시 되돌려야할 경우 기억했던 개수만큼 다시 스택에서 꺼내 방문..

https://www.acmicpc.net/problem/15658 15658번: 연산자 끼워넣기 (2) 첫째 줄에 수의 개수 N(2 ≤ N ≤ 11)가 주어진다. 둘째 줄에는 A1, A2, ..., AN이 주어진다. (1 ≤ Ai ≤ 100) 셋째 줄에는 합이 N-1보다 크거나 같고, 4N보다 작거나 같은 4개의 정수가 주어지는데, 차례대 www.acmicpc.net 연산자는 +, -, *, / 총 4개가 가능하고 그 개수는 입력으로 주어진다. 수의 개수의 최대 크기가 11로 작고 특별한 조건으로 값을 구하는 게 아니므로 완전탐색을 이용해서 문제를 해결할 수 있다. 나는 순열을 이용해서 N-1개의 기호를 뽑아 값을 계산한 후 최대값과 최소값을 갱신하는 방법으로 문제를 해결하였다. 처음에는 조합처럼 해결..

https://www.acmicpc.net/problem/2309 2309번: 일곱 난쟁이 아홉 개의 줄에 걸쳐 난쟁이들의 키가 주어진다. 주어지는 키는 100을 넘지 않는 자연수이며, 아홉 난쟁이의 키는 모두 다르며, 가능한 정답이 여러 가지인 경우에는 아무거나 출력한다. www.acmicpc.net 이 문제는 9명 중 7명을 뽑았을 때, 그 7명 키의 합이 100인 경우 정렬한 후 출력해주면 끝나는 문제이다. n명 중 m명을 뽑는 알고리즘을 설계해서 해결해주었다. bool visited[10]; int od[10]; int nanj[10]; #include #include #include #include #include #include #include #include #define ll long lo..

https://www.acmicpc.net/problem/10971 10971번: 외판원 순회 2 첫째 줄에 도시의 수 N이 주어진다. (2 ≤ N ≤ 10) 다음 N개의 줄에는 비용 행렬이 주어진다. 각 행렬의 성분은 1,000,000 이하의 양의 정수이며, 갈 수 없는 경우는 0이 주어진다. W[i][j]는 도시 i에서 j www.acmicpc.net 문제 외판원 순회 문제는 영어로 Traveling Salesman problem (TSP) 라고 불리는 문제로 computer science 분야에서 가장 중요하게 취급되는 문제 중 하나이다. 여러 가지 변종 문제가 있으나, 여기서는 가장 일반적인 형태의 문제를 살펴보자. 1번부터 N번까지 번호가 매겨져 있는 도시들이 있고, 도시들 사이에는 길이 있다...

https://www.acmicpc.net/problem/10819 10819번: 차이를 최대로 첫째 줄에 N (3 ≤ N ≤ 8)이 주어진다. 둘째 줄에는 배열 A에 들어있는 정수가 주어진다. 배열에 들어있는 정수는 -100보다 크거나 같고, 100보다 작거나 같다. www.acmicpc.net 문제 N개의 정수로 이루어진 배열 A가 주어진다. 이때, 배열에 들어있는 정수의 순서를 적절히 바꿔서 다음 식의 최댓값을 구하는 프로그램을 작성하시오. |A[0] - A[1]| + |A[1] - A[2]| + ... + |A[N-2] - A[N-1]| 입력 첫째 줄에 N (3 ≤ N ≤ 8)이 주어진다. 둘째 줄에는 배열 A에 들어있는 정수가 주어진다. 배열에 들어있는 정수는 -100보다 크거나 같고, 100보..