아이작의 작(作)

이 문제는 내가 한 번도 안 풀어본 DP문제였다. DP문제를 어떻게 접근하고 해결하는지를 알지 못해 DP알고리즘부터 찾아보며 대략적으로 문제에 어떻게 접근해야 하는지를 알아본 후 바로 문제 해결하러 고고! 문제 후기 처음에는 하향식(Top Down)방식으로 문제를 해결하려 했다. 문제는 재귀 제한이 걸려버린 것. 그래서 3번 런타임 에러로 실패. system 라이브러리를 이용해서 재귀 제한을 늘려도 해결이 되지 않아 상향식으로 풀기로 했다. 상향식으로 해결하니 값을 미리미리 저장해서 해결하기 때문에 재귀를 사용할 일이 없고, 최솟값 비교만 잘해주면 해결! 이번 문제를 통해서 Python의 main함수를 작성하는 방법도 알게되었다. 정답 코드를 작성하면서 설명하겠다. 문제 풀이 import sys def ..

14717번: 앉았다 영학이의 패를 뜻하는 두 개의 정수 A, B가 주어진다. (1 ≤ A, B ≤ 10) www.acmicpc.net from itertools import permutations card = list(range(1, 11)) * 2 # 카드풀 생성 my_card = list(map(int, input().split())) # 내가 뽑은 카드 card.remove(my_card[0]) card.remove(my_card[1]) rank = list(permutations(card, 2)) # 순열을 이용해서 족보 생성 rank.sort(key=lambda x: (x[0] == x[1], (x[0] + x[1]) % 10, x[0])) # 내 카드가 땡일때 if my_card[0] == ..

오늘은 갑자기 삘 받아서 N과 M 문제들을 클리어해보았다. 주어진 규칙에 따라 순열과 조합을 구하면 되는 문제들이다. Python에는 itertools라는 라이브러리가 있다. 이를 이용하면 쉽게 순열과 조합을 구할 수 있는데 이를 정리해보고자 한다, 어떤 리스트나 집합이 있을 때 이들의 순열과 조합을 구하는 경우의 수는 다음과 같은 것이다. 순열 - 중복 O 순열 - 중복 X 조합 - 중복 O 조합 - 중복 X itertools에는 이 4가지 경우에 각각 사용할 수 있는 함수가 존재한다. permutations product combination combinations_with_replacement 일단 기본적으로 각각의 합수로 생성된 결과는 각각의 함수 이름의 객체이다. 따라서 리스트로 바꾸어주어 출력..

1~4번 문제들은 파이썬의 기본 내장 함수들을 이용해서 손쉽게 풀 수 있었다. N-Queen문제부터 끝까지 사실 내가 100% 해결했다고는 못하겠다. 내가 알고 있는 알고리즘과 자료구조 지식이 부족하다는 것을 여기서 다시금 느낀다. 그러한 것들이 부족하니 구현이 마음대로 되지 않는다. - 결론: 백트래킹은 단순히 전체의 경우를 효율적으로 탐색하는것이다. 일단 부족한 내가 내린 결론이다. 혹시 더 나은 결론이 있다면 환영이다. - 알고리즘과 자료구조의 기초적인 지식이 어느 정도 있어야 문제 해결이 가능한 것 같다. 다음에는 책을 보고 공부를 해온 뒤에 다시 도전해야겠다는 생각이 든다. C++도 공부해서 자료구조도 직접 구현해보고 싶다. BOJ Solutions: https://github.com/Isaac..

처음 3문제(수 정렬하기 1,2,3)를 해결하는데 조금 시간이 걸렸다. 특히 마지막 3번에서 리스트에 숫자를 저장하지 않고 인덱싱을 이용해서 정렬을 수행해 메모리를 효과적으로 줄이는 방법은 혼자서 생각해 내기 어려웠다. 그리고 왜 인지 파이썬 내장 정렬 함수는 느렸다. pypy로 제출을 하면 정답이 되긴 했는데, Python언어가 느리다는 것을 다시금 느낄 수 있었다. 후반부 문제들은 sort()함수에 key= lambda a: (함수)를 이용해서 해결하는 방식으로 거의 다 해결했다. 이런 면에서는 Python이 알고리즘 문제를 해결할 때 강력한 언어인 것 같다. 다양한 내장 라이브러리를 제공해 검색만 잘한다면 편하게 풀 수 있다. 하지만 너무 편법으로 푸는 느낌이 자꾸드는건 어쩔 수 없는 것 같다. 나..

본격적으로 코딩 테스트 준비를 하면서 몸풀기로 브루트 포스 알고리즘 문제들을 해결해 보았다. 전체를 모두 무식하게 탐색하고 확인하는 알고리즘 문제들이기 때문에 사실 복잡하게 생각할 필요가 없다. 나는 처음에 다른 문제들처럼 뭔가 규칙을 발견하고 우아하게 풀어야 한다고 생각해서 좀 헤매었다. - 결론: 브루트 포스 알고리즘은 그냥 무식하게 풀어라. 무식하게 풀 때 쉽게 풀리고 해답이 바로바로 나왔다. 뭔가 복잡하게 생각하는 순간 구현은 저 멀리.... - 나름 재미있는 시간이었다. 풀고 나서 다른 분들이 작성한 코드를 보면서 더 무식하게도 할 수 있구나 라는 생각을 했다. 더 무식한 코드일수록 내가 더 쉬워졌다. 근데 자꾸 나는 복잡하게 풀려고만....ㅎ - 다음 단계를 향해서 더 나아갈 예정이다. 모든 ..