드롱드롱

https://www.acmicpc.net/problem/9461  나선으로 돌아가면서 커지는 도형의 가장 긴 변의 길이는 구하는 문제인데, 이건 딱 봐도 Dp구나 싶어서 n번째의 길이와 그 앞의 길이와의 관계들을 살펴보았다. 내가 직관적으로 그림을 통해 확인했던 건 dp[i] = dp[i-1]+dp[i-5]였기 때문에 기본 값들을 세팅해주고 식을 넣어 문제 풀이를 하였다.      * 나의 코드t = int(input())dp =[0]*101dp[1]=1dp[2]=1dp[3]=1dp[4]=2dp[5]=2dp[6]=3dp[7]=4dp[8]=5for _ in range(t): n = int(input()) if n>8: for i in range(8,n+1): d..

시작은 미약하지만 결말을 기대하게 되는 요즘이랄까요 계속 정진하도록 하겠습니다 군대 안에서 백준으로 시간 녹이기는 즐거워~

이번 주말은 여태까지 틀린 문제들을 모아놓고 모두 해결해보기로 했다. 그중에서 이 문제는 딕셔너리를 활용한 문제이다.본인이 딕셔너리가 약하다고 판단되기에 블로그에 내 풀이와 다른 사람의 풀이, 그리고 문제를 풀 때 자주 활용되는 딕셔너리의 성질과 활용에 대해 알아보고자 이 문제를 블로그에 글을 쓰게 되었다. https://www.acmicpc.net/problem/1157 1. 내 풀이a = input()word=a.lower()dict1 = {}list1 = []for i in word: if i not in list1: list1.append(i) dict1[i] = 1 else: dict1[i] += 1sorted_dict = sorted(dict1...

2주 간의 긴 여행과 휴식기를 지나고 거진 한 달만에 하는 코딩이라 그런지 감을 많이 잃은 것 같다.그런 김에 이번주는 solved.ac의 브론즈 2~실버3까지의 문제를 매일매일 풀어주면서 감을 찾아보려고 한다.   1. 처음에 틀린 풀이num = int(input())list1 = []for _ in range(num): word = input() list1.append(word)ans = list1[0]print(list1)for i in range(len(list1)-1): for j in range(len(ans)): if ans[j] != list1[i+1][j]: fin = ans.replace(ans[j], '?')print(fin)"""ans..

2주 간의 터키 여행 이후 오랜만에 파이썬으로 백준 문제 풀이를 해봤다.오랜만에 하는거니까 몸풀기로 좀 쉬운 문제를 골랐다. 문제풀이num = int(input())ans = 1for _ in range(num): a, b = map(int, input().split()) if a == ans: ans = b elif b == ans: ans = aprint(ans) 공은 처음에 1번에 있고 그것이 바꿔치기하면서 계속 바뀐다는 성질을 이용하였다. 가장 직관적이고 간단한 풀이인 것 같다.

대학교 1학년 2학기 c/c++입문 강의 말미에 abstract data type이라는 말을 처음 들었습니다. 단순히 시험을 보기 위해 내용을 암기했고 제대로된 이해가 되지 않은 채 3년이 지난 지금(병장 3호봉)에 와 있습니다. 이것이 왜 중요하고 파이썬을 공부하면서 객체 지향 프로그래밍과 함께 왜 이렇게 언급이 많이 되는지에 대해 이번 시간에 배워 보는 시간을 가지도록 하겠습니다.  1. Abstract Data Types가 무슨 말일까이름부터 감이 잡히지 않는 ADT는 무엇인지 한글말로 해석하며 설명해보겠습니다. 영어사전에 abstract를 검색하면 '추상적인'이라는 말이 나오고, 추상적인이라는 말이 애매해서 국어사전에 검색해보니구체성(具體性)이 없어서 그 뜻이 분명하지 않은 (것). 이렇게 나옵니..

지난시간에는 재귀와 분할정복에 대해서 알아보았습니다. 이번에는 Brute-force algorithm과 Backtracking 알고리즘에 대해서 살펴보도록 하겠습니다. 1. Brute-force algorithm(완전 탐색 알고리즘)백트래킹을 알기 위해선 먼저 브루트포스 또는 완전 탐색에 대해 알아야 합니다. 브루트포스나 완전 탐색은 solution에 대해 가능성 있는 모든 후보들을 시스템적으로 나열하고 각 후보들이 problem의 상태를 만족하는지 판별하는 알고리즘입니다. 말그대로 주먹구구식의, 무식하게 푸는 방식이지만 때로는 무식한 방법이 더 쉽게 문제를 해결할 수 있는 경우도 있습니다. 또한 광범위하게 사용이 가능합니다. 스도쿠를 예로 들자면, 아래와 같은 스도쿠를 brute-force 기법으로 풀..

https://www.acmicpc.net/problem/11582 문제 풀이 코드n = int(input())list1 = list(map(int, input().split()))k = int(input())num = n // klist2 = []for i in range(0,n,num): listn = sorted(list1[i:i+num]) for j in listn: print(j, end=' ') 분할 정복 알고리즘을 공부한 후, solved.ac를 이용해서 분할 정복 알고리즘 카테고리에 있는 문제들 중 만만해보이는 실버 문제로 선택했다. 재귀를 활용해서 문제를 풀려고 했지만 그러지 못했다. 그냥 재귀를 사용하지 않고 간단하게 문제를 풀이했다.      * Referenc..

저번 글에서 Recursion을 공부한 것을 토대로 이번 시간에는 Recursion을 사용한다는 점에서 Dynamic Programming과 유사하지만 약간 다른 Divide and Conquer을 배워보도록 하겠습니다. 그리고 분할 정복 알고리즘을 이용하여 해결할 수 있는 가장 대표적인 문제인 하노이의 탑도 풀이해보겠습니다.    1. Divide and Conquer(분할 정복) 알고리즘Divide and Conquer를 2문장으로 나눠서 설명하자면,1. algorithm design paradigm(방법) - 즉, 하나의 알고리즘 디자인 패러다임입니다.2. based on multi-branched recursion - 여러 갈래의 재귀에 기반합니다. 저번 글에서 factorial을 recursio..

대학교 2학년 때 자료구조/알고리즘 시간에 배웠던 재귀가 생각났다. 그때는 왜 이런 걸 배우지하면서 이냥저냥 수업듣고 그랬는데 이제보니 기본기를 다질 수 있는 매우 귀중한 시간이었던 것 같다. 그때 공부 제대로 안한 벌을 군대와서 받는.... 무튼무튼 잡담은 여기까지하고,이번 글에서는 재귀에 대해 알아본 뒤, 간략하게 재귀를 배울 때 항상 등장하는 문제인 하노이의 탑을 풀어보도록 하자.  1. Recursion재귀(Recursion)는 본인을 호출하는 메서드이다.  재귀는 어떤 목적을 달성하기 위해 본인, 자기 자신을 스스로 호출하는 방법이다. 재귀에 대한 개념을 알면, 외관상 코드로만 보면 간결해보이는 이중 for loop보다 더 효율적인 알고리즘을 설계할 수 있으며, 다음 글에서 살펴볼 내용인 브루트..