백준 알고리즘 9935번 문제 - 문자열 폭발



사실 이 문제는 틀렸다. 문제 유출을 위해서 문제를 밝힐 순 없지만 제니퍼 소프트 문제와 약간 비슷한 측면이 있어서 풀어보았다. 물론 제니퍼는 DP를 썼어야 했지만 이건 아니다.

결론적으로 코드는 작성했지만 틀렸다.

그 이유는 시간초과였다. 이 모든 과정을 1초 내에 끝내야 하는데 DP를 사용하지 않은 탓인지 1,000,000의 문자열을 주었을 때 수행시간이 오버가 된다.


틀린 코드지만 올려보았다.


접근 방식

- 해당 문자열로 split을 한 후, join을 통해 새로운 문자열을 만든다.

- 해당 문자열이 있는 동안 loop를 돌린다.

- 남아 있는 문자열이 있는지 없는지를 체크한다.



코드 (python v2)

1
2
3
4
5
6
7
8
9
10
iStr = map(list, raw_input('input the first String : '))
fStr = map(list, raw_input('input the first String : '))
 
while fStr in iStr:
    iStr = "".join(iStr.split(fStr))
 
if iStr:
    print iStr
else:
    print "FRULA"
cs


백준 알고리즘 1924번 2007년


알고리즘을 이제는 슬슬 공부해보자고 결심했고 백준 알고리즘 사이트에서 쉬운 문제들만 가지고 풀어보기 시작했다.
왜 공부하게 됐냐면 제니퍼소프트 인턴문제를 풀면서 뭘 써서 풀면 될지는 알았는데 코딩이 안된다는 사실에..
또한, 개발자로써 알고리즘에 대한 자부심을 갖추어야 한다고 생각했기 때문에
또한, 내 학점을 커버하기 위해서!?ㅠㅠ 


무튼 그 시작으로 쉬운 문제들을 연습삼아 풀어보았다.

개발 언어는 python으로 풀었는데 그 이유는 언어도 공부할 겸 굉장히 코드가 짧아진다는 것. (사실 Java를 안한지 좀 되어서 기억이 잘 안나...)

이 문제는 2007년 1월1일 월요일이 주어지고 두 정수를 받아 해당 월 일이 무슨 요일인지를 구하는 문제이다.

이 문제 되게 쉽다.....근데 업로드 하는 이유는 그냥... 어쨌든 심심풀이로 풀었자나..


코드 (python v2)

1
2
3
4
5
6
7
mList = [0,31,28,31,30,31,30,31,31,30,31,30,31]
wDay = {1 : 'MON'2 : 'TUE'3 : 'WED',4 : 'THU',5 : 'FRI',6 : 'SAT',0 : 'SUN'}
sum =0
month, day = map(intraw_input().split(" "))
 
for i in range(month):
    sum += mList[i]sum += dayprint wDay.get(sum%7)
cs


백준 알고리즘 11727번 2xN 타일링 2


백준 알고리즘의 11727번을 풀어보았다.
혼자서 조금 고민하다가 규칙이 좀 쉬웠는데 어떻게 잘 풀어서 쓸까 고민중이었다.
그런데 고으니양의 '피보나치 수열'을 보는 순간 그냥 코드를 외워버렸다.


DP(dynamic programming)으로 풀었는데 다른 DP들을 풀기 전에 어떻게 접근하면 될지 참고하며 되겠다.


**생각한 방식**

n번째의 count를 구할 때
    - 2x1을 더하는 1가지 경우 > [n-1]까지의 값
    - 2X2를 더하는 2가지 경우 (2x2 한 개 or 1x2 두 개[) > [n-2]까지의 값 x2

이 두 경우의 수를 더한(+)값이 찾고자 하는 counting 갯수이다.


코드 (Python v2)

1
2
3
4
5
6
7
8
9
10
11
12
13
def countBricks(n):
    blist = []
    for i in range(0, n + 1):
        if i == 0 or i == 1:
             blist.append(1)
        else:
            blist.append((blist[i - 1+ blist[i - 2* 2) % 10007)
       
    return blist[n] % 10007
 
 
= input()
print countBricks(n)
cs


'Data Engineer > Algorithm' 카테고리의 다른 글

(python) 백준 알고리즘 9935번 - 문자열  (0) 2016.05.04
(python) 백준 알고리즘 1924번  (0) 2016.05.03

+ Recent posts