목록#include <알고리즘>/Dovelet (16)
HOT프로그래밍
한창 정렬공부를 할 때 풀었던 알고리즘 문제다문제는 내가 입력한 t분짜리 CD에 내가 입력한 곡들을 몇개 담을 수 있는지 출력하는 문제인데딱봐도 정렬해서 시간이 가장 짧은 곡들 순서대로 담아서 출력하면 될 것 같다(지금보면 간단한데 그 때는 정말 힘들게 풀었던 것 같다) http://59.23.150.58/30stair/rocker1/rocker1.php?pname=rocker1 당신은 유명한 그룹 로커스 록 그룹에 대한 아직 발표되지 않은 n(1 input; m.insert(input); } for (multiset::iterator iter = m.begin(); iter != m.end(); iter++) { if ((t-*iter) >= 0) { t -= *iter; dap++; } } cout
함수를 처음배우게 되었을 때 풀었던 문제였다함수에대한 개념도 감이 안잡혔을 때라 상당히 애먹었었다ㅜㅜ결국에는 삼촌이 도와줘서 풀었는데 풀고나서도 코드를 이해하는데 3일이 걸린 것 같다그래도 이 문제 덕분에 지금 내가 함수로 중복코드를 줄일 수 있는게 아닌가 싶다 http://59.23.150.58/30stair/baseball/baseball.php?pname=baseball 정보문화진흥원 정보 영재 동아리에서 동아리 활동을 하던 영수와 민혁이는 쉬는 시간을 틈타 숫자야구 게임을 하기로 했다.영수는 1에서 9까지의 서로 다른 숫자 세 개로 구성된 세 자리 수를 마음속으로 생각한다. (예: 324)민혁이는 1에서 9까지의 서로 다른 숫자 세 개로 구성된 세 자리 수를 영수에게 묻는다. (예: 123)민혁이..
암스트롱 수... 닐암스트롱은 알지만 암스트롱 수는 생전 처음 보는 수이다세자리 수를 한자리씩 나눠서 abc라고 해보자예를 들어 a = 1, b = 5, c = 3 이렇게해서 abc는 153이다 여기서 abc = a*a*a+b*b*b+c*c*c가 성립할 때 암스트롱 수라고 부른다고한다 즉 153 = 1*1*1+5*5*5+3*3*3이 성립하므로 153은 암스트롱 수이다나의 설명이 이해가 안될 수 도 있으니 한번 문제로 넘어가보자 http://59.23.150.58/30stair/amstrong/amstrong.php?pname=amstrong 세자리 자연수 abc 가abc = a*a*a + b*b*b + c*c*c를 만족할 때 암스트롱 수라한다.한 가지 예를 보면 153 = 1*1*1 + 5*5*5 + 3..
나도 그랬지만 아마도 대부분 처음에 문제를 봤을때 아 이거 long형으로 계산하면 되는거 아니야? 하는 생각으로 풀어서 한번씩은 틀릴 것이다 하지만 여기에 나오는 수가 너무 큰수이다보니 문자형을 사용해서 배열에 저장한 뒤에 다시 정수로 바꾼다음에 배열에 저장된 수들을 하나하나 계산해서 푸는 방식으로 코드를 작성했다 작년 ACM-ICPC 연습문제에 비슷한 문제가 나왔던거같아서 기억에 남아서 그런지 올려본다 http://59.23.150.58/30stair/long_sub/long_sub.php?pname=long_sub 매우 큰 길이의 두 개의 수가 입력되었을때 뺄셈을 구하는 프로그램을 작성하시오.예를 들어, 두 수가 218072345632843258023, 521732147023 일 때, 21807234..
나름 문제내용에 흥미를 가지고 풀었던 문제이다 http://59.23.150.58/30stair/HQ9/HQ9.php?pname=HQ9 HQ9+ 라는 프로그래밍 언어는 세상에서 가장 간단한 언어이다.명령어는 아래와 같다.H: 그 유명한 'Hello, world!'라는 문구를 출력시킨다.Q: 프로그램 소스를 출력시킨다.9: "99 Bottles of Beer on the Wall" 라는 노래의 가사를 출력한다. 하지만 이 문제에서는 "99 Bottles of Beer on the Wall" 만 출력한다.+: 누산기를 증가시킨다. 이 문제에서는 나오지 않는다.여러분이 해야 할 일은 소스 코드를 입력받아 결과를 출력하는 일이다. 삼촌이 운영하시는 알고리즘학원을 다니면서 스택,큐,그래프 같은 자료구조 응용문제는..
항상 나의 인내심의 한계를 건드렸던 문제는 DP문제이다몰론 아직도 다이나믹 프로그래밍을 능숙하게 다루진 못한다. 지금은 거의 다 까먹었다고 생각해도 될 것 같다....항상 예전에 배웠던걸 복습하면 '인간은 망각의 동물'이라는 말이 떠오른다그렇기 때문에 이 블로그를 운영하는 걸지도.. 지금 하고있는 일들이 잘 마무리되면 한번 도장깨기로 다이나믹프로그래밍을 처음부터 다시 공부해야할 것 같다 http://59.23.150.58/30stair/scv/scv.php?pname=scv N * N 크기의 맵이 있다. 이 맵에는 미네랄이 군데군데 매장되어 있어서 당신은 SCV 를 이용해 이 미네랄을 채취하려고 한다.SCV 는 (1,1) 의 위치에서 출발하여 (N,N)까지 이동하는데, 이 SCV 는 고물이라 오른쪽 또는..
이 문제는 딱 보면 알 수 있지만 BFS문제이다출력할 때 정렬을 사용하는걸 깜빡해서 한번의 재시도가 있었다는게 아쉬웠다ㅜㅜ그래도 BFS의 개념을 익히는데는 굉장히 도움이 되었던 문제인 것 같다 http://59.23.150.58/30stair/danji/danji.php?pname=danji 아래와 같은 정사각형 모양의 지도가 있다. 1 은 집이 있는 곳을, 0 은 집이 없는 곳을 나타낸다.0 1 1 0 1 0 0 0 1 1 0 1 0 1 1 1 1 0 1 0 1 0 0 0 0 1 1 1 0 1 0 0 0 0 0 0 1 1 1 1 1 0 0 1 1 1 0 0 0 그림 1 철수는 이 지도를 가지고 연결된 집들의 모임인 단지를 정의하고, 단지에 번호를 붙이려 한다. 여기서 연결되었다는 것은 어떤 집이 좌우,..
아무리 생각해도 알고리즘 문제를 풀면서 가장 힘들었던 시기는 재귀함수 파트였던 것 같다이 문제 역시 백트래킹문제인데 재시도 없이 풀었다는게 굉장히 뿌듯했었던 기억이 있다 http://59.23.150.58/30stair/athletic/athletic.php?pname=athletic 프로그램 명: athletic 철수네 학교에서는 육상대회만 있던 가을 운동회에 팔씨름 대회를 추가 시켰다.팔씨름 대회에서는 우승자에게 푸짐한 상품이 돌아가는데 , 우승자를 공정하게 뽑기위해 여러 판의 시합을 해서 먼저 일정 수의 시합을 이기는 사람을 우승자로 가리기로 했다.평소 팔 씨름에는 자신이 있던 철수는 팔씨름 대회에 참여했다. 그리고는 자신이 결승까지 올라갔을 때 우승할 수 있는 경우에는 어떤 것들이 있는지를 따져 ..
처음에 BFS문제인줄알고 BFS식으로 짰는데 시간초과가 나와서 당황했던 문제이다결국엔 Queue로 풀었지만 배열이 메모리를 너무 많이 할당시켜서 깔끔해지 못했던 점이 너무 아쉬웠다 http://59.23.150.58/30stair/dam/dam.php?pname=dam 어느 마을 안에는 큰 호수가 있고, 그것을 막는 댐이 있었다. 그런데 어느날 그 댐이 무너져내려 호수에 있는 물이 마을을 모두 뒤덮으려한다. 호수에 있는 물은 다음 1시간에 한 블럭으로 이동하며, 물의 양은 무한하다 가정하자. 물은 상 하 좌 우로 퍼져나가며 마을을 뒤덮는다.당신은 댐이 터진 순간 이 마을의 지도를 받았다. 당신이 도와줘야 할 일은 완공시간이 K시간인 댐들을 최대한 빨리 지어서 물이 더 이상 진행하지 못하도록 하는 것이다...
나의 첫 백트래킹 문제..풀고나서도 완벽하게 코드를 따라가지 못해서 1주일 동안 하루에 한번씩 반복해서 풀었던 기억이 있다.. [이건 그흔적들...] 백트래킹 알고리즘은 재귀함수를 응용해서 모든 경우의 수를 탐색해버리기 때문에 정확성이 굉장히 높다는 장점이 있는데 반면에 모든 경우의 수를 탐색하기 때문에 속도가 느리다는 단점을 가지고 있다고 한다.자칫했다간 무한루프가 나올 수도 있으니 신중히 생각하면서 코딩하는게 좋다 http://59.23.150.58/30stair/pat/pat.php?pname=pat 두 정수 n , k 를 입력으로 받아 k 개의 1 을 가진 n 자리 이진 패턴을 출력하는 프로그램을 작성 하세요.입력두 정수 n , k 가 입력으로 주어진다. (0 < n =n){ if(y==k){ f..