오늘의 문제 | 17825. 주사위 윷놀이약간 브루트포스, 백트래킹이라는 알고리즘을 보고 당황했다. 이게 정말 그냥 돌린다고 해결할 수 있는 문제인가 싶었다. 마지막이라 약간 문제를 칼을 갈고 찾아왔다는 생각이 드는 난이도이다. 골드2 문제는 푼 기억이 없는데…우선 백트래킹을 알아보자.정확히 백트래킹이 어떤 걸 뜻하는지 모르고 문제들을 풀어왔었다. 한번 개념만이라도 간단히 짚어보려 한다.백트래킹도 결국 브루트포스처럼 모든 경우를 탐색하는 것이긴 하다. 다만 조건이 위배된다고 생각이 들면 전 단계로 다시 돌아가서 탐색하는 느낌이다. 즉 완전히 전부다 탐색하는건 아니지만 완전 탐색 과정 중에 약간의 뒷걸음질을 추가한 느낌으로 보인다. pruning이라는 가지치기 과정으로, 탐색 중 이상한 애들이 생기면 잘라..

오늘의 문제 | 프로그래머스: 개인정보 수집 유효기간확실히 마지막이 다가와서 그런지는 몰라도 실제 코딩테스트에 출제됐던 문제들이 조금씩 나온다. 사실 문제를 대충 읽어봤을 때 그리 어렵지 않아보이긴 한다. 기본적인 문자열 파싱/날짜 계산 정도의 난이도이다. 그래서 그냥 무작정 구현하기로 했다. 조건에 날짜가 다 28일까지만 되므로 윤년을 고려할 필요도 없어보인다. 어차피 코드도 금방짜고 항해99도 얼마 남지 않았으니 금방 풀어버리기 보다는 코드를 최대한 신경 써가며 짜보려한다.def isExpired(today,extract_date,month): ty,tm,td=map(int,today.split(".")) ey,em,ed=map(int,extract_date.split(".")) ..

오늘의 문제 | 프로그래머스: 신규 아이디 추천1단계 new_id의 모든 대문자를 대응되는 소문자로 치환합니다.2단계 new_id에서 알파벳 소문자, 숫자, 빼기(-), 밑줄(_), 마침표(.)를 제외한 모든 문자를 제거합니다.3단계 new_id에서 마침표(.)가 2번 이상 연속된 부분을 하나의 마침표(.)로 치환합니다.4단계 new_id에서 마침표(.)가 처음이나 끝에 위치한다면 제거합니다.5단계 new_id가 빈 문자열이라면, new_id에 "a"를 대입합니다.6단계 new_id의 길이가 16자 이상이면, new_id의 첫 15개의 문자를 제외한 나머지 문자들을 모두 제거합니다. 만약 제거 후 마침표(.)가 new_id의 끝에 위치한다면 끝에 위치한 마침표(.) 문자를 제거합니다.7단계 new..

오늘의 문제 | 11054. 가장 긴 바이토닉 부분 수열부분수열 시리즈 중에 가장 어려워보여서 도전하지 않았던 문제이다. 다만 조금 생각해보니, 기존에 가장 긴 증가하는/가장 긴 감소하는 부분 수열을 합친 문제라 생각하니 문제가 편해졌다.아이디어: 각 지점이 중심이라 생각하자.n=int(input())l=[*map(int,input().split())]# 각 지점이 꼭대기일 때를 기준으로 최댓값이 몇인지를 파악하는 걸 목표로 함.# 해당 지점까지 가장 긴 증가/감소 부분 수열을 둘 다 구하면 가능할 수도.dp_increase=[1]*(n)dp_decrease=[1]*(n)dp_bitonic=[]for i in range(n): for j in range(i): if l[j]오늘의 회고부..

오늘의 문제 | 2631. 줄세우기오늘 문제는 오랜만에 골드가 나왔다. 순서대로 배치하기 위해서 드는 최소 비용을 구하라고 했다. 약간은 그리디적이긴 한데, 아이디어가 이전에 풀었던 알고리즘과 비슷하다는 생각이 든다.아이디어: 가장 긴 증가하는 부분 수열우선 우리가 옮기지 않아도 되는 친구들의 수를 최대화시키는 방법을 떠올릴 수 있다. 오름차순으로 정렬하기 위해서, 증가하는 수열을 제외한 나머지만 옮기는건 무조건 이득이라는 것을 알 수 있다. 다만 이게 무조건적으로 최소값인지는 약간은 의문이 들기는 한다.n=int(input())l=[int(input()) for i in range(n)]dp=[1]*(n+1)for i in range(n-1): for j in range(1,i): i..

오늘의 문제 | 1965. 상자넣기문제를 읽어봤더니 지난 번에 풀었던 가장 긴 부분 수열과 같은 문제이다.n=int(input())dp=[1]*(n+1)l=[*map(int,input().split())]for i in range(1,n): for j in range(i): if l[j]코드가 토씨 하나 틀리지 않고 같다는 생각이 든다. 물론 이번에는 내가 직접 떠올려서 풀었다는 점이 다행이긴 하다.오늘의 회고사실 코드가 똑같다보니 배울 점이 없었다. 물론 나는 DP를 배운적이 있기 때문에 더 쉽게 푸는 것일수도 있지만 처음 푸는 사람들도 이정도 풀었다면 적응했을거라는 생각이 든다.별도로 DP문제를 풀어보며 적응해야겠다는 생각이 든다.

오늘의 문제 | 9461. 파도반 수열DP라고 생각하고, 약간은 피보나치와 비슷하다는 생각이 들었다. 초기 5개까지는 그대로 반영되지만, 그 이후부터는 이전 5개 전의 사이즈와 바로 전 사이즈의 합만큼이 추가된다는 것이다. 물론 N이 작아서 크게 문제될 건 없겠지만 전처리로 100까지의 모든 값을 구하고 접근하려 한다.dp=[0,1,1,1,2]for i in range(4,101): dp.append(dp[i-4]+dp[i])for i in range(int(input())): print(dp[int(input())])솔직히 너무 쉬워서 아쉽긴했다. 단순한 피보나치를 구현하는 정도의 난이도였다.오늘의 회고DP 문제가 어제에 비해 너무 쉬워졌다. 물론 이거보다 어려운 DP 문제였다면 조금 골치아..

오늘의 문제 | 11055. 가장 큰 증가하는 부분 수열대충 읽고 지난번 코드와 비슷하겠다는 생각이 들었다. 단순히 가장 긴 증가하는 부분 수열인 줄 알았으나 가장 큰 증가하는 부분 수열임을 보고 약간은 다른 부분이 있겠구나 했다.기존에 DP에 저장하던 것은 현재까지 가장 큰 값.(1) 기본적으로 선형 순회 (2) 자기 아래에 존재하는 부분 수열들 중 본인을 포함하여 만들어지는 최댓값 수열을 찾아다님.n=int(input())l=[*map(int,input().split())]dp=l[:] # 기존에는 길이였기에 1로 시작했으나 이번에는 0으로 시작함.# 앞에서 픽한 친구보다 내가 크면, 그 친구에서 본인을 추가한 값만큼으로 최댓값을 갱신함.for i in range(1,n): for j in ra..