내 맴

문제 ) https://www.acmicpc.net/problem/15649 15649번: N과 M (1) 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해야 한다. www.acmicpc.net [ 풀이 ] Backtracking Algorithm을 사용하여 문제를 풀어주었다 - Backtracking Algorithm 이란? ✔ 해를 찾는도중에 해가 아니면 되돌아가서 다시 해를 찾는 기법 ✔ DFS (깊이 우선 탐색 ) 으로 모든 Node를 검색한뒤 Node의 유망성을 점검하여 유망하지않으면 부모노드로 돌아간 후 다른 자손 노드를 탐색한다 - Node가 Promisi..

- Backtracking Algorithm ✔ 해를 찾는도중에 해가 아니면 되돌아가서 다시 해를 찾는 기법 ✔ 모든 경우의 수를 전부 고려한다 ( 브루트 포스 Algorithm과 유사) ✔ 최적화(optimization) 문제와 결정(decision) 문제 ( yes or no question) 를 해결할수있다. ✔ DFS (깊이 우선 탐색 ) 으로 모든 Node를 검색한뒤 Node의 유망성을 점검하여 유망하지않으면 부모노드로 돌아간 후 다른 자손 노드를 탐색한다 - 순서 1. State Space Tree에서 DFS를 실시한다 2. 각 Node가 promising한 지 점검 3. If Node가 promising한 경우 → 자손 Node 탐색 Else non promising한 경우 → 부모 Node..

문제 ) 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..

예문 ) A: 시간이 얼마 정도 걸릴거 같아? B: 보통은 30분에서 45분 정도 걸리는데,      몇시에 출발하느냐에 따라서 길게는 1시간에서 1시간 반 걸릴 수도 있어     근데 퇴근시간에만 안걸리면 1시간 이상은 안걸릴거야  영작 )    A: How long do you think it's going to take (it'll take) ? B: Normally, it takes about 30 to 45 minutes     Depending on what time we leave, it can take as long as an hour to an hour and a half     But unless we get caught in(during) rush hour, it shouldn't t..

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

정리 ) : 같은 것이 다른 시점(상황, 조건)에서 어떻게 다른지   ✔ ~가 ~에게 잘해주다 (1) be good to   Ex ) He is not good to her (2) treat 사용하기 (의미가 좀 더 직설적임 )  He treats me nice   ✔ last long  : 오래 가다    Ex) 내가 생각했던 것 만큼 어렵진 않았어요  It wasn't as hard as I thought it would be                                                              it was going to be  (= 내가 생각했던 것보다 쉬웠다. )   It was easier than I thought  ✔ 완성형 문장속에서만 as~as가 ..

예문) (1) 제가 운전면허증을 딴지는 사실 좀 오래 됐는데요 본격적으로 하기 시작한지는 얼마 안됐어요. 일을 시작하고 나서야 운전할 일이 좀 생겼거든요 시간이 좀 걸리긴 했는데 , 주차하는게 한번 익숙해지고 나니까, 크게 어렵지 않더라구요. (2) 독립한지는 오래 됐는데요, 요리를 본격적으로 시작한지는 얼마 안됐어요 제가 먹는거에 돈을 얼마나 쓰고 있는지를 알고 나서야 요리를 해야겠다는 생각이 들었어요. 시간이 좀 걸리긴 했는데 장보는거에 한 번 익숙해지고 나니까 크게 어렵지 않더라구요 영작) (1) It's actually been quite a long time since I got my driver's license But It hasn't been very long since I really s..

문제 ) 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를 오름차순으로 정렬한 순..