입력마다 반복문을 사용해서 범위안에 알파벳이 존재하는지 확인하면서 완전탐색으로 풀이할 수 있는 문제긴 하지만 문자열이 변하지 않으므로 DAT(Data Address Table)에 각 알파벳들의 위치를 저장해놓으면 더욱 간단하게 풀이 할 수 있는 문제이다. 1. 알파벳 26개의 위치를 담을 DAT를 생성한다. 2. 입력받은 문자열을 아스키코드를 활용하여 0번에서 25번까지의 위치에 알파벳의 위치를 저장한다. 3. 입력을 받은 후 입력받은 알파벳의 아스키코드를 추출하여 그 알파벳의 위치정보를 담고 있는 DAT에 접근한다 4. 그 위치에서 start와 end사이에 숫자가 존재하는지 확인한다. 만약 존재한다면 answer카운트를 1개 증가시킨다. import sys #sys.stdin = open("/Users..

다이나믹 프로그래밍 문제를 풀면서 Long Increase Subsequence(가장 증가하는 긴 수열) 문제를 풀고 연관된 문제로 골드4문제가 보이길래 바로 풀어보았다. 처음에는 한개의 최댓값 기준을 정해 LIS와 LDS를 나누어서 써보았지만, 시간초과가 발생하였다. 그러던 중 LDS문제를 LIS를 Reverse해서 해결하는 풀이법을 보게 되었다. 그래서 이 문제에도 Reverse를 적용시켜 보았다. import sys #sys.stdin = open("/Users/positive/Desktop/무제 폴더/Algorithm/230106/11054in.txt","r") input = sys.stdin.readline N = int(input()) arr = list(map(int, input().spli..

시간이 남아서 DP문제를 한문제 더 풀어보았다. 아주 간단한 DP문제이다 각 합들이 최대가 되는 DP테이블을 만들어서 풀면 된다. 1. 각 입력을 2차원 배열로 바꿔서 저장한다. 2. 누적합을 계산할 테이블(GOLD)를 생성한 후 첫째줄은 입력받은 값과 동일하게 설정 해준다 3. 맨 윗줄일 경우 우,우상 으로 이동해서 계산하는 방법뿐이고 맨 아랫줄의 경우 우, 우하 로 이동해서 계산하는것뿐이므로 분기를 나누어준다. 그 외에는 우 우상 우하 로 이동하면서 계산 할 수 있다. 4. 최종적으로 계산된 GOLD테이블의 마지막줄에서 최댓값을 출력해주면 된다. import sys sys.stdin = open("/Users/positive/Desktop/무제 폴더/Algorithm/230105/goldin.txt"..

Mootube라는 문제를 읽고 이해하는데 오랜 시간이 걸렸다. 결론부터 말하자면 테스트케이스의 정답은 나오나 문제를 해결하는데 너무 많은 반복문과 while문 사용으로 인한 시간초과가 일어났다. 후에 정답을 확인한 결과 N X N 테이블을 만드는게 아닌 BFS로 해결하는 문제였다. 예전에도 DFS문제를 풀때 N X N테이블을 만들어서 풀이를 하니까 시간초과가 났었는데 이번에도 마찬가지 였다. 먼저 시간초과가 발생한 코드를 설명하자면 1. N X N테이블에 유사도가 적용된 그래프를 입력한다 2. 0인 부분을 탐색해서 상하좌우로 이동해서 위아래에서 가장 가까운 값 중 최솟값(ud), 좌우에서 가장 가까운 값 중 최솟값(lr)을 찾아낸다. 그 두개의 값 중 가장 작은 값을 0대신 입력하면 되는데 바로 입력을 ..

오늘아침에 운동을 안해서 근손실이 날까 걱정하는 찰나에 문제 이름이 근손실이어서 풀어보게되었다. 아주 간단한 조합을 활용한 완전탐색 문제이다. 요즘 itertools를 연습하는데 맛들려서 오늘도 itertools의 permutation을 활용하여 조합을 도출하였다. 먼저 조합의 순서를 활용하기위해 index라는 리스트를 만들어서 순서를 리스트의 index를 조합으로 출력하였다. flag는 0아래로 한번이라도 떨어지면 1이 되고, flag가 0일때만 경우의수를 추가하는 루프를 만들었다. 0 에서 매일 K만큼을 빼준다음에 index에 맞는 운동키트의 근육증가량을 더해주었을때 0보다 작게 된다면 flag를 1로 만들고 루프를 종료시킨다. import sys from itertools import permuta..

다이나믹 프로그래밍의 이해를 돕기위해 간단한 다이나믹 프로그래밍 문제를 풀어보았다. import sys #sys.stdin = open("/Users/positive/Desktop/무제 폴더/Algorithm/230104/14494in.txt","r") input = sys.stdin.readline n,m = map(int,input().split()) MAP = [[0 for _ in range(n)]for _ in range(m)] for i in range(n): MAP[0][i]=1 for j in range(m): MAP[j][0] = 1 for i in range(1,m): for j in range(1,n): MAP[i][j] = MAP[i-1][j] + MAP[i][j-1] + MAP[i..