imported>idea0073 |
|
| (5 intermediate revisions by one other user not shown) |
| Line 1: |
Line 1: |
| Google의 그 것!
| | Google 코드잼 및 알고리즘 연습 겸 코드작성 연습 겸!겸!겸! |
| | |
| https://code.google.com/codejam/ | | https://code.google.com/codejam/ |
|
| |
|
| |
|
| = 개요 = | | = 개요 = |
| 군대 안에서 점점 머리가 굳어가는 걸 깨닫고...
| |
|
| |
|
| 머리라도 굴리자는 의미에서 | | 군대 안에서 점점 머리가 굳어가는 걸 깨닫고 머리라도 굴리자는 의미에서 혼자서 달리자! |
| 혼자서 코드 재밍재밍, 달리자! | |
|
| |
|
| | '''그리고 지금''', 퇴화한 머리 이끌고 '''다시 갑니다.''' |
|
| |
|
| __TOC__
| | 코드잼에서 지금껏 나온 문제를 다 풀고 해석하는 것을 목표로 하고 있습니다. |
| | 예전 코드는.. 지웠어요. ~~(볼 게 없어요) (진짜)~~ |
|
| |
|
| | 언어는 제가 할 수 있는 모든 언어로 해볼꺼에요. 코드 작성 및 구현 연습도 포함되어 있어서! |
|
| |
|
| 이 글을 쓰는 곳은 영내 자대이므로, 추후 시간을 들여서~~~휴가를 나와서~~~ 정리하겠습니다.
| | __TOC__ |
| 자세한 풀이 방법 및 발상 등을 적을 생각입니다.
| |
| | |
|
| |
|
| = 문제 풀이 자취 = | | = 문제 풀이 자취 = |
| == 2009년 Round1C ==
| | 준비! |
| | |
| 문제 : https://code.google.com/codejam/contest/189252/dashboard
| |
| | |
| === 정황 및 느낀 점 ===
| |
| 2시간 30분에 A B 다 풀고 C-Small 풀었다. '''65/100''' C-Large 빼고 Incorrect! 본 적 없다.
| |
| 물론, Practice Mode라서 실제하고 틀릴 것 같다.
| |
| | |
| # BackTracking 참으로 오랜만에 써 봤다. 근데 O(N^N)...
| |
| # C번 코드를 2개 짰다...(DC, DP) 2번째 꺼 짜고 돌렸는데 Incorrect! 보고 절망..
| |
| # O(N^N) 코드는 다음부터 짜면 안되겠다. (100^100)
| |
| C-Large 를 넣었는데, '''해방자 100명!''' 터짐..
| |
| # 파이썬으로 알고리즘 처음 짜는데, 확실히 C보다 편하다.
| |
| 그럼에도 불구하고 C++을 많이 쓰는 건.. 상대적으로 2% 부족한 속도 때문인가??
| |
| === 소스코드 ===
| |
| ==== Problem A. All Your Base ====
| |
| for loop in xrange(int(raw_input())):
| |
| mes = raw_input()
| |
| dic = {}
| |
|
| |
| maxi = 0
| |
| count=1
| |
| for S in mes:
| |
| if count==1:
| |
| if dic.get(S)==None:
| |
| dic[S]=count
| |
| count += 1
| |
| elif count==2:
| |
| if dic.get(S)==None:
| |
| dic[S]=0
| |
| break
| |
| for S in mes:
| |
| if dic.get(S)==None:
| |
| dic[S]=count
| |
| count += 1
| |
|
| |
| result=0
| |
| for S in mes:
| |
| result=dic.get(S)+result*count
| |
|
| |
| print('Case #{0}: {1}'.format(loop+1,result))
| |
| | |
| Switch가 없어서 if가 많이 들어갔는데,
| |
| 지금 생각해 보니, dictionary로 엄청 줄일 수 있을 것 같다.
| |
| | |
| ==== Problem B. Center of Mass ====
| |
| import math
| |
|
| |
| for loop in xrange(int(raw_input())):
| |
| flycount = int(raw_input())
| |
| flyinfo =[]
| |
|
| |
| for loop2 in xrange(flycount):
| |
| flyinfo.append(raw_input().split())
| |
|
| |
| c=[0.0, 0.0, 0.0, 0.0, 0.0, 0.0]
| |
|
| |
| for fly in flyinfo:
| |
| for N in xrange(6):
| |
| c[N] += float(fly[N])
| |
|
| |
| x=c[0]/float(flycount)
| |
| y=c[1]/float(flycount)
| |
| z=c[2]/float(flycount)
| |
| vx=c[3]/float(flycount)
| |
| vy=c[4]/float(flycount)
| |
| vz=c[5]/float(flycount)
| |
|
| |
| try:
| |
| tmin = -((x*vx+y*vy+z*vz)/(vx*vx+vy*vy+vz*vz))
| |
| except Exception:
| |
| tmin = 0
| |
|
| |
| if tmin < 0 or tmin == -0 :
| |
| tmin = 0
| |
|
| |
| dmin = math.sqrt(math.pow(x+vx*tmin,2)+math.pow(y+vy*tmin,2)+math.pow(z+vz*tmin,2))
| |
|
| |
| print('Case #'+str(loop+1)+': %(dm).8f %(tm).8f'%{"dm":dmin, "tm":tmin})
| |
| map(float,raw_input().split())를 잊어먹고 안 썼다. 그래서 Input 후 자료처리 부분이 지저분하다.
| |
| | |
| 3D 좌표가 나오고, '''Ouput을 float로 요구'''하는 하는 바람에,
| |
| 반복문 돌려서 풀었다간 틀릴 것이다!라고 생각해서 결국 수학을 했다. 구의 방정식, 어쩌구저쩌구...
| |
| math에 pow하고 sqrt는 있겠지 하면서 임포트. 있어서 겨우 풀었다. ~~~help(math)~~~
| |
| | |
| ==== Problem C. Bribe the Prisoners ====
| |
| ===== Divide&Conquer! =====
| |
| # -*- coding: cp949 -*-
| |
|
| |
| def iinput(): return int(raw_input())
| |
| def inputline(typ): return map(typ, raw_input().split())
| |
|
| |
| def track(start, end, po):
| |
| if len(po)==0:
| |
| return 0
| |
|
| |
| P1,P2 = 0,0
| |
|
| |
| cost = []
| |
| for N in xrange(len(po)):
| |
| P1 = track(start,po[N]-1,po[:N])
| |
| P2 = track(po[N]+1,end,po[N+1:])
| |
| cost.append(P1+P2)
| |
|
| |
| return linesize[start,end]-1+min(cost)
| |
|
| |
|
| |
| for loopC in xrange(iinput()):
| |
|
| |
| P,Q = inputline(int)
| |
| points = inputline(int)
| |
|
| |
| global linesize
| |
| linesize = {}
| |
|
| |
| points+=[0,P+1]
| |
| points.sort()
| |
|
| |
| for x in points:
| |
| for y in points:
| |
| if x < y:
| |
| linesize[(x+1, y-1)] = y-x-1
| |
|
| |
| points.pop(0)
| |
| points.pop()
| |
|
| |
| result = track(1,P,points)
| |
| print('Case #{0}: {1}'.format(loopC+1,result))
| |
| C-Small을 풀어낸 코드이다.
| |
| 전형적인 D&C 방식으로 흐름을 풀어냈다.
| |
| 확실히 코드 작성은 평이하지만, 시간 복잡도가 '''O(N^N)'''
| |
| 이 말도 안되는 코드가 통과할 수 있었던 것은, N<=5 였기 때문이다. ~~~max(O(N^N))<=3125~~~
| |
| 하지만 C-Large에 넣었더니 터졌다! 망...
| |
| ===== Small만 통과한 코드(..?) =====
| |
| # -*- coding: cp949 -*-
| |
|
| |
| def iinput(): return map(int,raw_input().split())
| |
|
| |
| for loopC in xrange(int(raw_input())):
| |
| P, Q = iinput()
| |
| Fr = iinput()
| |
|
| |
| global Size
| |
| Size = {}
| |
|
| |
| Fr.append(0)
| |
| Fr.append(P+1)
| |
| Fr.sort()
| |
|
| |
| for x in xrange(Q+2):
| |
| for y in xrange(x+1,Q+2):
| |
| if (Fr[x],Fr[y]) not in Size:
| |
| Size[(Fr[x]+1,Fr[y]-1)]=100000000000000000
| |
|
| |
| for x in xrange(Q+1):
| |
| Size[(Fr[x]+1,Fr[x+1]-1)]=0
| |
|
| |
| for Diff in xrange(2,Q+2): #간격크기!
| |
| # print("Diff : {0}".format(Diff))
| |
| for Seq in xrange(Q): #Seq번째 구간!
| |
| try:
| |
| # print(" <<{0}~{1}>>".format(Fr[Seq]+1,Fr[Seq+Diff]-1))
| |
| for n in xrange(1,Diff):
| |
| tempsize=0
| |
| tempsize += Size[(Fr[Seq]+1,Fr[Seq+n]-1)]
| |
| tempsize += Size[(Fr[Seq+n]+1,Fr[Seq+Diff]-1)]
| |
| tempsize += Fr[Seq+Diff]-Fr[Seq]-2
| |
| # print(" N:{4} <{0}~{1}> + <{2}~{3}>".format(Fr[Seq]+1,Fr[Seq+n]-1,Fr[Seq+n]+1,Fr[Seq+Diff]-1,n))
| |
| # print(" Tempsize : {0}, {1}+{2}+{3}".format(tempsize, Size[(Fr[Seq]+1,Fr[Seq+n]-1)], Size[(Fr[Seq+n]+1,Fr[Seq+Diff]-1)],Fr[Seq+Diff]-Fr[Seq]-2))
| |
| if tempsize < Size[(Fr[Seq]+1,Fr[Seq+Diff]-1)]:
| |
| Size[(Fr[Seq]+1,Fr[Seq+Diff]-1)] = tempsize
| |
| except Exception:
| |
| pass
| |
| # iinput()
| |
|
| |
| print('Case #{0}: {1}'.format(loopC+1,Size[(1,P)]))
| |
| '''희대의 삽질'''
| |
| '''Size[(Fr[x]+1,Fr[y]-1)]=100000000000000000'''~~~Infinity Integer~~~ '''이런거 넣으시면 안됩니다.'''
| |
| ~~~버그 잡으려고 print 막 넣은 거 봐.. 결국 잡음. 100000000000000000+4~~~
| |
| 기준점을 일정한 숫자로 잡아버리는 바람에 망한 코드. 성공한 코드는 뒤쪽 참조.
| |
| ===== Large도 되는 코드 =====
| |
| # -*- coding: cp949 -*-
| |
|
| |
| def iinput(): return map(int,raw_input().split())
| |
|
| |
| for loopC in xrange(int(raw_input())):
| |
| P, Q = iinput()
| |
| Fr = iinput()
| |
|
| |
| global Size
| |
| Size = {}
| |
|
| |
| Fr.append(0)
| |
| Fr.append(P+1)
| |
| Fr.sort()
| |
|
| |
| for x in xrange(Q+1):
| |
| Size[(Fr[x]+1,Fr[x+1]-1)]=0
| |
|
| |
| for Diff in xrange(2,Q+2): #간격크기!
| |
| for Seq in xrange(Q): #Seq번째 구간!
| |
| try:
| |
| for n in xrange(1,Diff):
| |
| tempsize=0
| |
| tempsize += Size[(Fr[Seq]+1,Fr[Seq+n]-1)]
| |
| tempsize += Size[(Fr[Seq+n]+1,Fr[Seq+Diff]-1)]
| |
| tempsize += Fr[Seq+Diff]-Fr[Seq]-2
| |
|
| |
| if (Fr[Seq]+1,Fr[Seq+Diff]-1) not in Size:
| |
| Size[(Fr[Seq]+1,Fr[Seq+Diff]-1)] = tempsize
| |
| elif tempsize < Size[(Fr[Seq]+1,Fr[Seq+Diff]-1)]:
| |
| Size[(Fr[Seq]+1,Fr[Seq+Diff]-1)] = tempsize
| |
| except Exception:
| |
| pass
| |
|
| |
| print('Case #{0}: {1}'.format(loopC+1,Size[(1,P)]))
| |
| 시간이 정말 많이 걸리기는 한다. 그래도 O(N^3)까지 줄였다. '''O(N^3)<=1000000'''
| |
| Dynamic Programming으로 작성. 확실히 머리가 아프다.
| |
| | |
