공부 기록

✏️ 문제 문제 파악앞에서 부터 차례대로 for 반복문 돌면서 칠해야 하는 구역을 발견했을 때 경우를 두 가지로 나눠야 한다.룰러가 벽에서 벗어나면 안되므로칠해야 하는 구역 + (m-1) 칠해야 하는 구역 + (m-1) > n - 11번 같은 경우는 룰러의 길이만큼 칠한다.2번 같은 경우는 칠해야 하는 구역보다 앞에 있는 구역은 다 칠해져 있으므로 해당 구역부터 배열의 끝까지 칠하면 된다. 이때 인덱스 0부터 4까지 1을 대입하는 코드는 다음과 같다.ary[0:5] = [1] * 5   코드def solution(n, m, section): wall = [1] * n answer = 0 for s in section: wall[s-1] = 0 for i..

✏️ 문제 문제 파악처음에는 차례대로 있는 지가 중요한 거니까 cards1과 cards2의 카드들이 goal에 나타나는 순서와 일치하는지 확인하는 코드를 짰다.goal에 나타나는 cards1과 cards2 카드들이 각각 올바른 순서대로 존재한다면 "Yes"를 반환하고 순서가 틀리면 "No"를 반환하도록 했는데 20, 21, 24, 25번 테스트에서 런타임 에러가 떴었다 .. 딕셔너리를 써서 제출해도 똑같았다..  그래서 goal의 배열 값이 cards1 또는 cards2에 있다면 맨 앞 값을 없애는.. 방향으로 코드를 짰다.이때 배열의 맨 앞 값을 없애는 코드는 다음과 같다.ary.pop(0)   코드런타임 에러 코드def solution(cards1, cards2, goal): for i in r..

✏️ 문제 문제 파악woo는 발음할 수 있으나 wo는 발음할 수 없으므로 할 수 있는 발음과 "정확히" 같아야 한다.그래서 babbling의 배열 값에 할 수 있는 발음을 차례대로 제거하는 방향으로 replace를 활용하면 된다. for b in babbling: for l in languge: b = b.replace(l, '') 연속해서 같은 발음을 할 수 없다는 유의사항이 있기 때문에 연속해서 같은 발음이 있다면 바로 발음할 수 없는 것으로 처리해주어야 한다! 중요한 것은 만약 replace로 발음 대신 빈값을 넣으면 ["yayae"]이 입력으로 들어올 시 aya를 제거하면 남은 문자가 ye가 되어 할 수 있는 발음으로 처리된다!!!때문에 할 수 있는 발음 대신에 빈 값이 아닌 다..

✏️ 문제 문제 파악n이 1, 2, 3, 4, 5일 때 각각 dp[n]의 값을 구하면 쉽게 점화식을 구할 수 있다. 그림을 그려보면 다음과 같다.num 배열은 dp 배열 앞뒤 값의 차이를 담은 배열이다.그림을 보면 다음과 같은 점화식이 나오는 것을 알 수 있다.num[n] = dp[n-1]dp[n] = dp[n-1] + num[n-1] 나중에 보니 dp 배열 자체가 피보나치 수열와 같았음... = 이 말은 즉 num 배열 필요 X..  알고리즘다이나믹 프로그래밍  코드n = int(input())num = [0, 1, 1]dp = [1, 1, 2]for i in range(3, n): num.append(dp[i-1]) dp.append(dp[i-1] + num[i-1])print(dp[n-1])

✏️ 문제 문제 파악n이 1, 2, 3, 4일 때 각각 dp[n]의 값을 구하면 쉽게 점화식을 구할 수 있다. 그림을 그려보면 다음과 같다.하지만 이 문제는 메모리가 적고 시간이 매우 짧다는 점..!고민해보니 3개짜리 배열만 사용하면 되는 거 같아서 인덱스로 들어올 값을 %3 해 인덱스로 써서 풀었다. 그리고 이 문제는 답에 15746으로 나눈 값을 구하고 있다.처음엔 마지막 print에서 % 15746 했었는데 시간 초과가 떠서 애초에 배열에 값을 넣을 때 % 15746을 하니 풀렸다!  알고리즘다이나믹 프로그래밍  코드n = int(input())dp = [1, 2, 3]for i in range(3, n+1): dp[(i-1) % 3] = (dp[i % 3] + dp[(i+1) % 3]) % 1..

✏️ 문제문제 파악dp 배열을 주어진 배열의 누적 합을 담는 배열로 정의한 후 각 배열에 대해 그림으로 작성하면 다음과 같이 나온다.코드에 대해서 너무 헷갈려서 IndexError가 계속 났다..ary 배열은 0부터, dp 배열은 1부터 시작하는 것을 잊지 말자... 두 개가 각각 index 0, 1부터 시작하지 않으면 코드가 매~우 길어져요...  알고리즘다이나믹 프로그래밍 누적 합 코드시간 초과 코드처음엔 그냥 단순하게 풀어봤지만 틀렸다. 당연함. 실버 1문제임.n, m = map(int, input().split())ary = [list(map(int, input().split())) for _ in range(n)]for _ in range(m): x1, y1, x2, y2 = map(int, ..

✏️ 문제 문제 파악처음에는 시작점을 기준으로 잡아서 풀려고 했는데 경우의 수가 너무 많았다...!  뭔가 2156번 포도주 문제랑 2579번 계단 오르기 문제랑 비슷할 것 같아서 시간을 좀 썼는데 결국 못풀었다 ㅠ.. 아쉽 이 문제의 포인트는 시작점이 아닌 "끝점"을 기준으로 푸는 것이 포인트이다!끝점부터 시작점까지 내려오는데 해당 위치에 있을 때 n일 때 상담한다.n일 때 상담하지 않는다.이 두 가지 경우로 나누어서 둘 중에 더 큰 값을 dp[n]에 대입해야 한다.n일 때 상담하지 않는 경우를 왜 고려하냐면 n일 때 상담하지 않고 n-1일 때 상담했을 때 (n-1일 때 t[n-1]이 2 이상일 경우) 더 이득일 경우도 있기 때문이다.무조건 n일 때 꼭 상담하라는 말이 없기 때문이다.그림으로 작성하면 ..

✏️ 문제 문제 파악2579번 계단 오르기 와 유사한 문제이다!저 문제와의 차이점은 계단 오르기는 꼭 마지막 계단을 밟아야 하는데 이 문제는 꼭 마셔야 하는 포도주가 없다는 것이다. 그러면 경우의 수를 나누면 다음과 같이 나온다.n번째 포도주를 마신다.n-2번째 포도주를 마셨다.n-3번째 포도주와 n-1번째 포도주를 마셨다.n번째 포도주를 마시지 않는다.n-2번째 포도주와 n-1번째 포도주를 마셨다.나는 다른 풀이들이 다 해당 포도주를 마시지 않는다는 조건을 두길래 왜 최대를 구하는데 마시지 않는 조건을 고려하는 거지? 라고 생각했는데 이유를 생각해보니 다음과 같았다. 해당 포도주를 마시지 않는다는 조건을 두는 이유는n번째 포도주를 마시지 않고 n-2번째 포도주와 n-1번째 포도주를 마셨을 때 최대일..

✏️ 문제 문제 파악처음에 이중 반복문 써서 풀고 있다가.. 시간 초과나서 찾아보니 최대 부분합을 푸는 방법 중 카데인 알고리즘을 써야 풀리는 문제였다.간단하게 설명하자면 시작 원소를 기준으로 부분 배열을 구하는 게 아니라 끝 원소를 기준으로 모든 부분 배열을 구하는 알고리즘이다.   알고리즘다이나믹 프로그래밍   코드시간 초과 코드import sysinput = sys.stdin.readlinen = int(input())ary = list(map(int, input().split())) value = -1000for i in range(n): temp = ary[i] for j in range(i+1, n): value = max(value, temp) temp += ary[j]pri..

✏️ 문제 문제 파악입력으로 주는 배열을 기준으로 합을 담은 dp 배열의 값을 구하면 다음과 같이 나온다.중요한 것은 그림의 빨간 부분과 같이 중간에 겹치는 부분이 생기는데 이때문에 경우를 나눠서 구해야 한다.dp[n][0]dp[n][1] ~ dp[n][n-1] : 어짜피 최대값을 구하므로 max 값만 두면 된다.dp[n][n]  알고리즘다이나믹 프로그래밍   코드n = int(input())ary = [list(map(int, input().split())) for _ in range(n)] dp = [[0] * (n+1) for _ in range(n)]dp[0][0] = ary[0][0]for i in range(1, n): for j in range(i + 1): if j == 0: ..