컴공과고씨

https://www.acmicpc.net/problem/1541 1541번: 잃어버린 괄호 첫째 줄에 식이 주어진다. 식은 ‘0’~‘9’, ‘+’, 그리고 ‘-’만으로 이루어져 있고, 가장 처음과 마지막 문자는 숫자이다. 그리고 연속해서 두 개 이상의 연산자가 나타나지 않고, 5자리보다 www.acmicpc.net 문제를 보고 -가 있는 순간 뒤에 나오는 모든 숫자를 - 처리해주면 최소값이 된다. 위 아이디어를 생각해내면 풀리는 문제였다. 이유는 -가 있으면 뒤에 숫자는 괄호를 활용하여 +가 나오든 -가 나오든 모든 숫자를 -로 처리가 가능하기 때문이다. 단계별 문제 풀이 1. 더해야할 숫자, 빼야할 숫자 저장하는 배열 선언 2. 전에 -가 부호가 나왔는지 저장하는 bool 변수 선언 (초기값 : tr..

https://www.acmicpc.net/problem/9663 9663번: N-Queen N-Queen 문제는 크기가 N × N인 체스판 위에 퀸 N개를 서로 공격할 수 없게 놓는 문제이다. N이 주어졌을 때, 퀸을 놓는 방법의 수를 구하는 프로그램을 작성하시오. www.acmicpc.net 이 문제의 핵심은 각 행에 있을 수 있는 퀸은 단 한개라는 것을 인지하고 풀어주어야한다. 0번째 행의 퀸의 위치를 결정하고 그 다음 위치를 결정할 때 한 열씩 그 위치에 퀸이 들어갈 수 있는지 조사한 후 다음행으로 넘어가서 다시 퀸이 들어갈 수 있는 열을 구해주는 식으로 풀어주면된다. 이런 구조를 구현하려면 백트래킹 기법을 사용해야 구현이 가능하다. 단계별 문제풀이 1. 각 행의 퀸의 위치 열을 저장하는 배열 c..

https://www.acmicpc.net/problem/1065 1065번: 한수 어떤 양의 정수 X의 각 자리가 등차수열을 이룬다면, 그 수를 한수라고 한다. 등차수열은 연속된 두 개의 수의 차이가 일정한 수열을 말한다. N이 주어졌을 때, 1보다 크거나 같고, N보다 작거나 www.acmicpc.net n이 100보다 작으면 모두 등차수열인 수 인것을 인지. 숫자마다 각 자리수를 빼서 비교하여 등차 수열인지 아닌지 판별해주면됨. 문제풀이 1. 자리수 배열, 자리수 차이 배열 선언 2. 100보다 작은 경우 입력값 N을 출력 3. 100보다 클 경우 각 자리수를 배열에 저장 4. 각 자리수 배열에서 그 다음 인덱스 값을 빼서 자리수 차이 배열에 저장 5. 자리수 차이 배열의 값을 비교하여 한개라도 다..

https://www.acmicpc.net/problem/4673 4673번: 셀프 넘버 셀프 넘버는 1949년 인도 수학자 D.R. Kaprekar가 이름 붙였다. 양의 정수 n에 대해서 d(n)을 n과 n의 각 자리수를 더하는 함수라고 정의하자. 예를 들어, d(75) = 75+7+5 = 87이다. 양의 정수 n이 주어졌을 때, www.acmicpc.net 각 자리의 수와 그 숫자를 더해서 만든 수는 생성자가 있는 경우이므로 표시를 해주고 표시가 된 숫자들을 빼고 출력해주면된다. 문제 풀이 1. bool 형 배열 만들고 false로 초기화 2. 1부터 10,000까지 각 자리수를 더해주고 그 수를 더한 배열 index에 true를 넣어줌 3. bool 형 배열 중 false인 것을 출력 전체코드 1 ..

https://www.acmicpc.net/problem/2798 2798번: 블랙잭 첫째 줄에 카드의 개수 N(3 ≤ N ≤ 100)과 M(10 ≤ M ≤ 300,000)이 주어진다. 둘째 줄에는 카드에 쓰여 있는 수가 주어지며, 이 값은 100,000을 넘지 않는 양의 정수이다. 합이 M을 넘지 않는 카드 3장 www.acmicpc.net 카드를 3장을 뽑아서 주어진 숫자를 넘지 않고 최대한 가깝게 만들어주면 되는 문제이다. 문제 풀이 1. 카드 입력을 받아 배열에 저장 2. 3중 포문을 이용하여 3장의 카드의 합을 구함. 3. (주어진 숫자) - (3장의 합) 의 절대값을 이전 값과 비교 그리고 3장의 합이 주어진 숫자보다 작은지 확인 4. 위 조건일 경우 ans에 저장하고 다음 3장의 합으로 넘어..

https://www.acmicpc.net/problem/2309 2309번: 일곱 난쟁이 아홉 개의 줄에 걸쳐 난쟁이들의 키가 주어진다. 주어지는 키는 100을 넘지 않는 자연수이며, 아홉 난쟁이의 키는 모두 다르며, 가능한 정답이 여러 가지인 경우에는 아무거나 출력한다. www.acmicpc.net 입력을 받은 총합에서 2개의 값을 빼주었을 때 값이 100이 되는 것을 찾아서 출력해주었다. 브루트 포스(brute force) 유형의 문제였다. 단계별 문제 풀이 1. 입력 값을 배열에 저장 그리고 전체 합을 저장 2. 정렬 -> 나중에 출력을 오름차순으로 해야하기 때문에 미리 sort해줌 3. 이중 포문을 이용하여 2개의 값을 빼면서 합이 100이 되는 것을 찾음 구조 4. 합이 100이 될 경우 2개..

https://www.acmicpc.net/problem/1620 1620번: 나는야 포켓몬 마스터 이다솜 첫째 줄에는 도감에 수록되어 있는 포켓몬의 개수 N이랑 내가 맞춰야 하는 문제의 개수 M이 주어져. N과 M은 1보다 크거나 같고, 100,000보다 작거나 같은 자연수인데, 자연수가 뭔지는 알지? 모르면 www.acmicpc.net 이 문제의 경우 시간초과를 잘 통과해야하는 문제이다. 그러기 위해서는 해시맵을 사용해야하며 문제를 보면 번호를 주면 포켓몬 이름을 포켓몬 이름을 주면 도감 번호를 답해야한다. 하지만 해시맵은 Key, value가 있고 key값으로 value를 찾는건 빠르지만(포켓몬 이름(key)을 주었을 때 도감 번호(value)를 찾는) value(도감번호)로 key(포켓몬 이름) ..

https://www.acmicpc.net/problem/1463 1463번: 1로 만들기 첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 정수 N이 주어진다. www.acmicpc.net 이 문제를 보고 bfs로 탐색을 하여 풀면 쉽게 풀릴거라고 생각해서 bfs로 풀어주었다. 풀고 난 후 힌트 부분쪽에는 다이나믹 프로그래밍이라고 되어있어서 다이나믹 프로그래밍으로도 풀고 두 개 방식 모두 정리해보았다. 첫번째 방식은 bfs로 푼 방식으로 처음에 딱 떠올라서 푼 방식이다. 입력 받은 n을 bfs에 넣어주면 bfs는 - 3으로 나눠지고 나눈수가 방문되어지지 않은 경우 큐에 넣어준다. - 2로 나눠지고 나눈수가 방문되어지지 않은 경우 큐에 넣어준다. - 1을 뺀 수가 방문되어지지 않은 경우 큐에 넣어준..

https://www.acmicpc.net/problem/1107 1107번: 리모컨 첫째 줄에 수빈이가 이동하려고 하는 채널 N (0 ≤ N ≤ 500,000)이 주어진다. 둘째 줄에는 고장난 버튼의 개수 M (0 ≤ M ≤ 10)이 주어진다. 고장난 버튼이 있는 경우에는 셋째 줄에는 고장난 버튼 www.acmicpc.net 해결하는 방법은 브루트 포스 방식을 이용해서 풀어주었다. 문제를 풀때 3단계로 나눠서 풀어주었는데 그 방식을 정리해보았다. 1. bool형 배열을 생성 -> 이 배열에는 채널이 번호를 눌러서 만들어 질 수 있는지를 저장한다. 그래서 없는 버튼이 들어가있는 채널에는 false 넣어준다. 이 때 버튼이 있는지 없는지를 확인하는 방법은 채널을 string으로 바꾸어주고 처음에 버튼을 입..

https://www.acmicpc.net/problem/3079 3079번: 입국심사 첫째 줄에 N과 M이 주어진다. (1 ≤ N ≤ 100,000, 1 ≤ M ≤ 1,000,000,000) 다음 N개 줄에는 각 심사대에서 심사를 하는데 걸리는 시간인 Tk가 주어진다. (1 ≤ Tk ≤ 109) www.acmicpc.net 이 문제는 처음에 감을 잘 못잡았다. 처음에는 최소 시간을 구하려는 방법을 생각하니 당연히 답이 나올 수 없었다. 그래서 고민 좀 많이 하고 생각을 바꿔서 시간을 기준으로 해서 각 시간마다 얼만큼의 사람을 통과시킬 수 있는지로 구현을 하여서 심사할 수 있는 인원의 조건을 만족하는 시간 중에서 최소값을 찾아주는 식으로 구현하였다. 중요한 것은 범위가 엄청 크기때문에 시간초과에 걸릴 수..