PS하는 깃털

문제 링크 : https://www.acmicpc.net/problem/14500문제 풀이 이 문제는 NxM 칸에 숫자들이 적혀 있을 때, 테트로미노 타일을 이용해 타일이 포함하는 수들의 합의 최댓값을 구하는 문제이다.  여기서 테트로미노는 폴리노미노의 한 종류로 네 개의 정사각형이 변끼리 인접하여 만들어지는 도형을 의미한다.    N,M ≤ 500 이라서 그냥 브루트포스로 모든 점들에 대해서 백트랙킹으로 탐색해줘도 충분하다. 이때 시간복잡도는 O(MN)인데, 정확히는 백트랙킹 할 때 최대 4^4 개의 가짓수가 있어서 16MN만큼의 연산이 필요하다.  먼저 Back Tracking 함수를 먼저 구현해보자. 초기 좌표와 깊이, 그리고 현재까지 숫자의 합을 매개변수로 하였다.void BT(int x, int..

파이썬에서 tkinter 모듈을 이용해서 암호화 복호화 프로그램을 만들어보았다. 그러려면 tkinter 창의 간단한 디자인과 암호화 복호화 방법을 정해야한다.디자인 먼저 디자인은 크게 중요하지 않으므로 간단하게 하였다. 암호화 시킬 텍스트를 집어넣는 엔트리와 암호화된 결과를 보여줄 엔트리, 또 암호화 시킬 버튼이 필요하고, 복호화도 마찬가지로 복호화 시킬 암호를 넣는 엔트리와 복호화된 결과를 보여주는 엔트리, 또 복호화 버튼이 필요하다. 추가적으로 무슨 엔트리인지를 보여주는 텍스트와 모든 내용을 지우는 지우기 버튼도 추가하였다.코드from tkinter import *win = Tk()win.title('Encryption & Decryption')win.geometry('400x400')entry1 =..

예전에 LIS알고리즘을 DP로 O(n^2)만에 구현하는 포스팅을 올린 적이 있다. 하지만 이 알고리즘을 쓰기엔 시간복잡도가 크다보니 시간초과가 나는 문제가 많다.LIS O(n^2) : https://code-feather.tistory.com/19 최장 증가 부분 수열 DP O(N^2)백준 : https://www.acmicpc.net/problem/11053 11053번: 가장 긴 증가하는 부분 수열수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {10, 20, 10, 30, 20code-feather.tistory.com 이번 포스팅에서는 이분탐색을 활용한 O(nlogn) LIS 알고리즘을 올려보려고 한다. 이분탐색을 써서 푸는 백준 문제..

solved.ac 사이트에 들어가봤는데 그랜드 아레나 파티 퍼즐 힌트라는 것을 하고 있길래 궁금해서 들어가봤다. 문제가 첫 번째부터 열 번째까지 있는데 한 문제 한 문제가 다 쉽지 않다. 여기에는 하나씩 문제들을 풀면서 풀이를 적어보겠다. 높은 수준의 지능이 요구되니 오랫동안 고민해보면 지능 상승(?)에 도움이 될 수도 있을 것 같다. 1. 첫 번째 이야기 - 카드더보기 첫 번째 문제는 주어진 게 "cards.pdf"라는 파일만 주고 답을 입력하라고 한다. 파일을 열어보면 이상한 문자들밖에 없다. 처음에는 뭘 해야할지 다 막막하다. 오래 고민하다 보니 문자들이 알파벳의 일부라는 사실을 알게 되었다. 그래서 이 문자들을 조합해서 의미있는 문자를 만들어야겠다고 생각했다. 문자들을 회전도 해보고 계속 조합해서..

문제 링크 : https://www.acmicpc.net/problem/28325 문제 풀이 이 문제는 그래프가 주어질 때 서로 연결되어있는 정점이 없도록 최대한 많은 정점을 선택하는 문제이다. 처음 보자마자 이색 염색이 떠오르긴 했지만 홀수사이클이 존재하는 경우에는 이색 염색이 안되므로 다른 방법으로 해야한다.  Case 1) 쪽방이 아예 존재하지 않는 경우(∀Ci = 0)N = 1 → 1마리N = 2k or N = 2k+1→ k마리 Case 2) 쪽방이 존재하는 경우 먼저 당연하게 쪽방의 개수가 1개 이상인 칸에 경우 쪽방에만 개미를 배치하는 것이 유리하다. 그럼 쪽방에 있는 방을 기준으로 구간을 나누어볼 수가 있다. 문제의 예시에서는 쪽방이 존재하는 방은 1, 4, 6으로 3개이다. 이 3개를 기준..

내신 공부를 위해 과학 공부를 하고 있던 중 친한 친구가  떨어진 거리나 비열에 따라서 복사 평형에 도달하는 시간이 어떻게 되냐라고 물어봐서 탐구해보게 되었다. 복사 평형은 물체가 흡수하는 에너지의 양과 물체의 온도에 의한 복사에너지의 양이 같아질 때 온도가 일정하게 유지되는 상태를 말한다. 이를 그래프로 나타내어 보면 아래와 같이 표현된다.    물체는 (흡수하는 에너지량) - (방출하는 에너지량) 만큼의 에너지로 자신의 온도를 변화시킨다. 이 점을 이용해서 시간을 계산해볼 것이다. 먼저 사용할 공식을 먼저 써보자.여기서 위의 식은 대부분이 알 것이라 생각하고, 밑의 식은 슈테판-볼츠만 법칙으로 M은 단위 시간, 물체의 단위 면적 당 물체가 방출하는 복사에너지를 의미한다. 시그마는 슈테판-볼츠만 상수로..

문제 링크 : https://www.acmicpc.net/problem/28218  문제 풀이 이 문제는 문제에 나온 격자칸에서 두 사람이 게임을 진행할 때 각 칸에 따라 선공이 이길지 후공이 이길지 판단하는 문제이다. 이런 유형의 문제는 게임이론에서 winning state와 losing state를 설정하는 것으로 풀 수 있다. 간단히 말하면 winning state는 받았을 때 이기는 게임의 상태를 의미하고 losing state는 받았을 때 지는 게임의 상태로서 재귀적으로 정의된다. 예를 들어서 상대가 마지막에 (N-1,M)칸으로 돌을 이동시켰다면,  (N,M)으로 칸을 이동시킬 수 있으므로 (N-1,M)은 winning state로 정의 된다.winning state : 갈 수 있는 칸 중 lo..

문제 링크 : https://www.acmicpc.net/problem/1005 1005번: ACM Craft 첫째 줄에는 테스트케이스의 개수 T가 주어진다. 각 테스트 케이스는 다음과 같이 주어진다. 첫째 줄에 건물의 개수 N과 건물간의 건설순서 규칙의 총 개수 K이 주어진다. (건물의 번호는 1번부 www.acmicpc.net 문제 풀이 누가 봐도 위상정렬을 사용하는 문제이지만 처음 보자마자 그냥 dp로 풀 수 있을 것 같아서 dp로 시도해보았다. 일단 유향그래프니까 각 점에서 들어오는 선분에 연결된 점들을 graph에 저장해주었다. 또 time이라는 배열에 각 건물을 짓는데 걸리는 시간을 저장하였다. dp를 아래와 같이 정의하자. dp[i] := 건물 i를 건설완료 하는데 드는 최소 시간 그러면 아..

크기를 무시할 수 있는 질량 m인 물체가 질량과 폭을 무시할 수 있는 길이 l인 막대 끝에 달려있다고 하자. 이 물체를 오른쪽으로 아주 살짝 밀었을 때 막대가 회전하여 물체가 지면에 닿을 때까지 걸리는 시간은?보기보다 꽤 어려우니 충분히 고민해봤으면 좋겠다..   1. 첫 번째 접근어짜피 물체는 막대에 매달려서 원 궤도로만 운동하기 때문에 원궤도의 접선 방향의 가속도만 고려해서 직선 운동처럼 접근하려고 했다. 연직선으로부터 기울어진 각도를 θ라고 할 때 접선 방향 가속도는 g sinθ이다. 이 상황에서 원궤도를 직선으로 바꾸어보자.lθ만큼 진행했을 때 가속도가 g sinθ이고 최종적으로 πl/2를 가는 상황과 같다. 여기서 구간을 무한히 쪼갠다음 각각의 구간에 대해서 등가속도 운동을 한다고 가정하여 시간..

문제 링크 : https://www.acmicpc.net/problem/16891 16891번: 탄성 충돌 탄성 충돌은 운동 에너지가 보존되는 충돌이다. 일차원 상에서 질량이 m1, m2인 두 물체가 각각 속도(여기서 속도는 방향을 포함하는 양이다) u1, u2로 운동하다가 탄성 충돌하면 충돌 후 두 물체 www.acmicpc.net "물리학" 카테고리에 있는 문제들을 풀어보다가 이 문제가 재미있게 생겨서 풀어보았다. 예전에 이런 충돌수에 관련된 문제를 3Blue1Brown 이라는 굉장히 좋은(?) 채널에서 본 적이 있다. 유튜브 영상 이 영상에서는 두번째 물체의 질량이 100의 거듭제곱 꼴일 때 충돌횟수가 π의 앞의 자리수가 되는 이유를 설명해주고 있는데 예전에 흥미롭게 봤던 경험이 있어서 생각이 났다..