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개를 기준..

문제 링크 : 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를 건설완료 하는데 드는 최소 시간 그러면 아..

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

문제 링크 : https://www.acmicpc.net/problem/30928 30928번: Yokohama Phenomena Do you know about Yokohama Phenomena? The phenomenon takes place when three programmers, sitting around a table, hold a single pen together above a board. A grid of squares is drawn on the board, with each square marked with a single letter. Although none www.acmicpc.net 백준에서 대회 문제들을 찾아보다가 이 문제를 발견했는데 실버1이기도 하고, 재미있게 생겨서 시도..

문제 링크 : https://www.acmicpc.net/problem/8983 8983번: 사냥꾼 입력의 첫 줄에는 사대의 수 M (1 ≤ M ≤ 100,000), 동물의 수 N (1 ≤ N ≤ 100,000), 사정거리 L (1 ≤ L ≤ 1,000,000,000)이 빈칸을 사이에 두고 주어진다. 두 번째 줄에는 사대의 위치를 나타내는 M개의 x-좌 www.acmicpc.net 문제 풀이 이 문제를 처음 도전할 때는 모든 사대에 대해서 잡을 수 있는 동물들을 카운트 해주는 Brute Force 방법을 쓸 수 있다(시간복잡도 O(MN). 그렇게 하면 M과 N이 100000이하이기 때문에 시간초과가 날 것이다. 그래서 다른 방법을 생각해보면 이부 분탐색이 떠오른다. 모든 동물에 대해서 조건을 만족하는 사..