Google의 그 것!
개요 ¶
2.1.1. 정황 및 느낀 점 ¶
2시간 30분에 A B 다 풀고 C-Small 풀었다. 65/100 C-Large 빼고 Incorrect! 본 적 없다.
물론, Practice Mode라서 실제하고 틀릴 것 같다.
물론, Practice Mode라서 실제하고 틀릴 것 같다.
1. BackTracking 참으로 오랜만에 써 봤다. 근데 O(N^N)...
2. C번 코드를 2개 짰다...(DC, DP) 2번째 꺼 짜고 돌렸는데 Incorrect! 보고 절망..
3. O(N^N) 코드는 다음부터 짜면 안되겠다. (100^100)
2. C번 코드를 2개 짰다...(DC, DP) 2번째 꺼 짜고 돌렸는데 Incorrect! 보고 절망..
3. O(N^N) 코드는 다음부터 짜면 안되겠다. (100^100)
C-Large 를 넣었는데, 해방자 100명! 터짐..
4. 파이썬으로 알고리즘 처음 짜는데, 확실히 C보다 편하다.그럼에도 불구하고 C++을 많이 쓰는 건.. 상대적으로 2% 부족한 속도 때문인가??
2.1.2.1. 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로 엄청 줄일 수 있을 것 같다.
지금 생각해 보니, dictionary로 엄청 줄일 수 있을 것 같다.
2.1.2.2. 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)~
반복문 돌려서 풀었다간 틀릴 것이다!라고 생각해서 결국 수학을 했다. 구의 방정식, 어쩌구저쩌구...
math에 pow하고 sqrt는 있겠지 하면서 임포트. 있어서 겨우 풀었다. ~
2.1.2.3.1. 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에 넣었더니 터졌다! 망...
전형적인 D&C 방식으로 흐름을 풀어냈다.
확실히 코드 작성은 평이하지만, 시간 복잡도가 O(N^N)
이 말도 안되는 코드가 통과할 수 있었던 것은, N<=5 였기 때문이다. ~
하지만 C-Large에 넣었더니 터졌다! 망...
2.1.2.3.2. 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)]))
2.1.2.3.3. 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으로 작성. 확실히 머리가 아프다.
Dynamic Programming으로 작성. 확실히 머리가 아프다.
