노는 게 제일 좋아

음 이제부터 무조건 float 절대 안 쓰고.. double 써야징 ㅎㅎ 물론 메모리는 더 먹지만.. float으로 오차가 생기는 것보단 훨씬 낫다. https://www.acmicpc.net/problem/2108 # 맞는 풀이 #include #include #include #include using namespace std; //산술 평균을 위해 필요한 값 - 원소의 개수, 원소의 합 //최빈값 "" - 해당 원소의 출현 횟수 //중앙값 - 해당 원소를 내림차순 또는 오름차순으로 정렬 -> but 항상 홀수의 개수를 가지므로 (원소 사이즈 + 1)/2 idx에 존재 //최대,최소 - 원소를 입력받으며 최소 최대값 갱신. //원소의 개수, 원소의 합을 위한 벡터 vector V; //최빈값 int n..

이 문제 또한.. DP로 즉, 이전 결과가 다음 결과에 쓰이는 문제라고 볼 수 있다. 추가 시간이 없다는 말은 언어마다 추가시간이 없다는 말 같다. C++은 항상 기준이 되므로 시간제한에 추가시간이 있을까 없을까 고민안해도 된다. 시간 초과나면 잘못푼거다 ㅎ https://www.acmicpc.net/problem/9095 9095번: 1, 2, 3 더하기 각 테스트 케이스마다, n을 1, 2, 3의 합으로 나타내는 방법의 수를 출력한다. www.acmicpc.net 맞는 풀이 #include using namespace std; int num[11]; int main(){ int n; cin >> n; num[1] = 1; num[2] = 2; num[3] = 4; //왜 이렇게 되는가? // 4를 만..

흠... 나는 처음에 BFS로 풀었는데 사람들이 DP라고 한다.. 그래서 둘다 풀어보았다. 시간제한이 아주 짧은 것으로 보아... 그렇다. DP가 확실하였구나 1초에 5억번 연산이라치면.. 1/6 대충 8천만번이면 되겠구나. https://www.acmicpc.net/problem/1463 1463번: 1로 만들기 첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 정수 N이 주어진다. www.acmicpc.net 먼저 BFS로 한 풀이 15분만에 푼 것 같다. #include #include using namespace std; int num[1000001]; int dist[1000001]; queue Q; int target; void init() { ios::sync_with_stdio(0);..

음.. 전형적인 구현 문제로 말하는 대로 구현하면 된다. 구현에 무엇을 쓸 지는 모두 사용자의 맘대로 다만 시간보다 메모리는 많기에 맘껏 써도 될 것 같다. https://www.acmicpc.net/problem/15683 15683번: 감시 스타트링크의 사무실은 1×1크기의 정사각형으로 나누어져 있는 N×M 크기의 직사각형으로 나타낼 수 있다. 사무실에는 총 K개의 CCTV가 설치되어져 있는데, CCTV는 5가지 종류가 있다. 각 CCTV가 감 www.acmicpc.net 이건 내가 한 번에 못풀었다. 감은 왔는데 도저히 구현이 되질 않았다. 하지만 풀이를 보니.. 30%정도까지는 맞았더라.. 백트래킹을 써야지~ 생각은 했지만 백트래킹에서 탐색을 하지 못했다. #맞은 풀이(참고해서) #include ..

전형적인 백트래킹 문제다. 백트래킹에 익숙하지 않은 터라 다른 사람풀이를 봐도 이해가 시간이 걸렸다. https://www.acmicpc.net/problem/9663 9663번: N-Queen N-Queen 문제는 크기가 N × N인 체스판 위에 퀸 N개를 서로 공격할 수 없게 놓는 문제이다. N이 주어졌을 때, 퀸을 놓는 방법의 수를 구하는 프로그램을 작성하시오. www.acmicpc.net 백트래킹은 제일 인간다운 생각이 아닌가 싶다. 그리고 무의식적으로 그것이 효율적이라 생각하면서 쓰고 있다. 우선 나는 그렇다. 우선 이 문제를 보자마자 같은 줄에 못놓겠구나 생각이 들었다. 아무튼 거기까지만 하고 들어가보자 한줄에 하나 넣어보고 다음 줄에 되는 것 넣어보고 그 다음줄에 되는 것 넣어보고 하면 될 ..

나 이거 맞았길래 봤더니 파이썬으로 풀었음 ㅎ 파이썬 permutation으로 3초만에 풀었음..ㅎ C++로 해보자꾸나.. https://www.acmicpc.net/problem/15649 15649번: N과 M (1) 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해 www.acmicpc.net 이 문제는 백트래킹이라는 원리를 적용해서 푼다. 코드에 주석을 보면서 이해해보자 #include #include using namespace std; int n,m; /////////////////////////////////////// int arr[10]; // 선택에 ..

나는 재귀가 아직도 헷갈린다. 이 문제를 분석하며 한 번 더 배워가자 https://www.acmicpc.net/problem/17478 17478번: 재귀함수가 뭔가요? 평소에 질문을 잘 받아주기로 유명한 중앙대학교의 JH 교수님은 학생들로부터 재귀함수가 무엇인지에 대하여 많은 질문을 받아왔다. 매번 질문을 잘 받아주셨던 JH 교수님이지만 그는 중앙대 www.acmicpc.net 이 문제는 또 재귀다. 결과를 보고 과정을 생각해내는 것이다. 해보자. 어느 한 컴퓨터공학과 학생이 유명한 교수님을 찾아가 물었다. "재귀함수가 뭔가요?" "잘 들어보게. 옛날옛날 한 산 꼭대기에 이세상 모든 지식을 통달한 선인이 있었어. 마을 사람들은 모두 그 선인에게 수많은 질문을 했고, 모두 지혜롭게 대답해 주었지. 그의..

하노이 탑의 근본을 알려주는 문제다 https://www.acmicpc.net/problem/11729 11729번: 하노이 탑 이동 순서 세 개의 장대가 있고 첫 번째 장대에는 반경이 서로 다른 n개의 원판이 쌓여 있다. 각 원판은 반경이 큰 순서대로 쌓여있다. 이제 수도승들이 다음 규칙에 따라 첫 번째 장대에서 세 번째 장대로 www.acmicpc.net 하노이 탑하면 재귀문제가 떠오른다. 하지만 감은 전혀 안 온다. 아니 감이 안 온다기보다는 코딩을 못하는 것이다. 머리로는 이해가 가는데.. 코딩을 어떻게 해야하지?? 나도 그렇다. 아직 재귀가 익숙치 못하다. 하나씩 알아보자 여기 링크 들어가서 알아보자 https://www.mathsisfun.com/games/towerofhanoi.html Pl..

재귀나 숫자 범위에 대해 기본적인 문제 좋은 것 같다. https://www.acmicpc.net/problem/1629 1629번: 곱셈 첫째 줄에 A, B, C가 빈 칸을 사이에 두고 순서대로 주어진다. A, B, C는 모두 2,147,483,647 이하의 자연수이다. www.acmicpc.net 음.. 처음 봤을 때 당황 많이했다. int, 4바이트 long long 8바이트 재귀함수까지... 재귀함수는 항상 그게 중요하다. 점화식을 찾는 것... 1번, n번 n+1번까지의 식만 찾으면 굿 맞는 풀이( 틀린 풀이도 집어넣어놨다.) #include using namespace std; using ll = long long; ll remain(ll a, ll b, ll c){ //n = 1일 때 if(..

구현하라는 대로 그냥 구현만 해주는 문제다. 메모리가 아주 적다. https://www.acmicpc.net/problem/1476 1476번: 날짜 계산 준규가 사는 나라는 우리가 사용하는 연도와 다른 방식을 이용한다. 준규가 사는 나라에서는 수 3개를 이용해서 연도를 나타낸다. 각각의 수는 지구, 태양, 그리고 달을 나타낸다. 지구를 나타 www.acmicpc.net 문제 범위가 0부터면 쉽겠는데..? 역시 문제를 어렵게 하려면 입력을 드럽게 주면 된다. 하지만 우리가 중요한 것은 연도다. 연도는 해가 한 바퀴 도는 것이 중요하지 연도가 중요하진 않다. 다같이 -1을 해주자 # 맞는 풀이 #include using namespace std; int main(){ int E,S,M; int e,s,m;..