내 맴

문제 ) https://www.acmicpc.net/problem/9663 9663번: N-Queen N-Queen 문제는 크기가 N × N인 체스판 위에 퀸 N개를 서로 공격할 수 없게 놓는 문제이다. N이 주어졌을 때, 퀸을 놓는 방법의 수를 구하는 프로그램을 작성하시오. www.acmicpc.net [ 설명 ] N개의 Queen을 서로 상대를 공격하지 않도록 NxN 체스판에 위치 시키는 문제 → 상대를 공격하지 않으려면 같은 행,열,대각선 상에 위치하면 안된다 예를들어 4 Queen의 경우 , 첫번째 queen을 (1,1)에 둔다면 2번째 queen은 노란색으로 표시한 자리에는 올 수 없다. [ 풀이 ] Backtracking Algorithm으로 풀 수 있는 대표적인 문제다. - Backtrack..

문제 ) https://www.acmicpc.net/problem/1541 1541번: 잃어버린 괄호 첫째 줄에 식이 주어진다. 식은 ‘0’~‘9’, ‘+’, 그리고 ‘-’만으로 이루어져 있고, 가장 처음과 마지막 문자는 숫자이다. 그리고 연속해서 두 개 이상의 연산자가 나타나지 않고, 5자리보다 많이 연속되는 숫자는 없다. 수는 0으로 시작할 수 있다. www.acmicpc.net [ 풀이 ] 우선 식의 값에 괄호를 넣어 최솟값이 되도록 하려면 '-'를 기점으로 나눠서 괄호를 씌워야 한다 문제에서 나온 예제를 보면 55-50+40 의 식의 값을 최소로 만들기 위해 '-'를 기점으로 괄호를 씌운다 즉, 55-(50+40) 으로 만들어줘야 -35로 식의 값을 최소로 만들 수 있다. 우선 '-'를 기점으로 ..

문제 ) https://www.acmicpc.net/problem/11399 11399번: ATM 첫째 줄에 사람의 수 N(1 ≤ N ≤ 1,000)이 주어진다. 둘째 줄에는 각 사람이 돈을 인출하는데 걸리는 시간 Pi가 주어진다. (1 ≤ Pi ≤ 1,000) www.acmicpc.net [ 풀이 ] ✔ Greedy Algorithm을 사용하여 풀어준다. 결정을 해 야 할 때마다 그 순간에 가장 좋다고 생각되는 것을 solution으로 선택함으로써 최종 solution에 도달하는 Algorithm이다. 각 사람이 돈을 인출하는데 필요한 시간의 합의 최솟값을 구하기 위해서는 돈을 인출하는 데 걸리는 시간인 P(i) 가 작은 순서대로 돈을 뽑아야한다. 그러므로, P(i)의 list를 오름차순으로 정렬한 순..

문제 ) https://www.acmicpc.net/problem/1931 1931번: 회의실배정 (1,4), (5,7), (8,11), (12,14) 를 이용할 수 있다. www.acmicpc.net [ 풀이 ] Greedy Algorithm으로 풀어야 할 거 같긴 한데, 무엇을 기준으로 최적의 solution을 선택할 것인지 한참을 고민했다. 고민 끝에 회의가 끝나는 시간을 기준으로 잡았다. 회의가 끝나는 시간을 기준으로 회의시간이 있는 list를 정렬시키고 " 회의가 끝나는 시간

문제 ) https://www.acmicpc.net/problem/11047 11047번: 동전 0 첫째 줄에 N과 K가 주어진다. (1 ≤ N ≤ 10, 1 ≤ K ≤ 100,000,000) 둘째 줄부터 N개의 줄에 동전의 가치 Ai가 오름차순으로 주어진다. (1 ≤ Ai ≤ 1,000,000, A1 = 1, i ≥ 2인 경우에 Ai는 Ai-1의 배수) www.acmicpc.net [ 풀이 ] 동전의 가치가 큰 것부터 사용해야하기 때문에, 그 순간에 가장 좋다고 생각되는 것을 solution으로 선택하는 Greedy Algorithm을 사용하여 문제를 해결하였다. ✔ Greedy Algorithm을 사용하여 풀어준다. 결정을 해 야 할 때마다 그 순간에 가장 좋다고 생각되는 것을 solution으로 선..

문제 ) https://www.acmicpc.net/problem/5430 5430번: AC 문제 선영이는 주말에 할 일이 없어서 새로운 언어 AC를 만들었다. AC는 정수 배열에 연산을 하기 위해 만든 언어이다. 이 언어에는 두 가지 함수 R(뒤집기)과 D(버리기)가 있다. 함수 R은 배열에 있는 숫자의 순서를 뒤집는 함수이고, D는 첫 번째 숫자를 버리는 함수이다. 배열이 비어있는데 D를 사용한 경우에는 에러가 발생한다. 함수는 조합해서 한 번에 사용할 수 있다. 예를 들어, "AB"는 A를 수행한 다음에 바로 이어서 B를 수행하는 함수이다. www.acmicpc.net [ 풀이 ] AC연산에 대한 알고리즘을 설명하기 전에 이 문제는 입력과 출력의 형식이 정해져있기 때문에 입력과 출력 방식에도 신경을..

문제 ) https://www.acmicpc.net/problem/1021 1021번: 회전하는 큐 첫째 줄에 큐의 크기 N과 뽑아내려고 하는 수의 개수 M이 주어진다. N은 50보다 작거나 같은 자연수이고, M은 N보다 작거나 같은 자연수이다. 둘째 줄에는 지민이가 뽑아내려고 하는 수의 위치가 순서대로 주어진다. 위치는 1보다 크거나 같고, N보다 작거나 같은 자연수이다. www.acmicpc.net [ 풀이 ] 문제 이해를 하는 것이 제일 우선! 문제 이해를 위해 Algorithm의 Flow를 작성해보았다. 예제 2번에 대한 flow이다 뽑아내려는 원소의 위치가 queue의 중간위치보다 ✔ 왼쪽에 위치하면 왼쪽으로 원소들을 이동시키는것이 더 편리할 것이고 → Leftmove Function ✔ 오른쪽..

문제 ) https://www.acmicpc.net/problem/10866 10866번: 덱 첫째 줄에 주어지는 명령의 수 N (1 ≤ N ≤ 10,000)이 주어진다. 둘째 줄부터 N개의 줄에는 명령이 하나씩 주어진다. 주어지는 정수는 1보다 크거나 같고, 100,000보다 작거나 같다. 문제에 나와있지 않은 명령이 주어지는 경우는 없다. www.acmicpc.net [ 풀이 ] ✔ Deque에 대한 문제! Array의 양쪽에서 입출력이 모두 가능한 자료구조 저번에 풀었던 큐 문제를 참조해서 코딩하였다. (코드가 겹침) https://luz0911.tistory.com/108?category=765467 [ BAEKJOON ] No. 18258 큐2 문제 ) https://www.acmicpc.net..