문제 1181 - 단어 정렬 접근 파이썬의 람다는 사랑입니다. 새로운 것을 배웠다. sys.stdin.readline 은 개행문자를 포함해서 입력을 받게 된다. 나는 주피터 노트북을 쓰기 때문에 test에서는 그냥 input()으로 사용하고 제출할 때만 sys를 사용하다보니 전혀 몰랐다.. 계속 출력 형식이 틀렸다고 나와서 찾아보니 ...

문제 11650 - 좌표 정렬하기 접근 파이썬의 람다는 사랑입니다. 코드 파이썬 코드 import sys input = sys.stdin.readline n = int(input()) arr = [list(map(int, input().split(' '))) for _ in range(n)] arr = sorted(...

문제 1202 - 보석 도둑 접근 분명 DP 처럼 생겼는데, 아니다. 문제 조건 중에 한 가방에는 최대 한 개의 보석만 담을 수 있다고 명시되어 있다. 그럼 가방의 개수만큼 for문을 돌면 될 것 같다. for문이 한번 돌때마다 가방을 하나씩 채우면 된다. 어떻게 채워야할까? 우선 작은 가방부터 차례대로 채워야하는건 확실하다. ...

문제 12015 - 가장 긴 증가하는 부분 수열 2 접근 LIS 알고리즘이다. DP를 이용해서 풀 수 있지만, 이 방법은 O(n^2)이 걸린다. DP[i] = i를 포함했을 때 최장 길이로, i 보다 작은 이전 수들 중에서 LIS가 가장 긴 곳에 +1을 하는 식이다. 이 문제는 입력값이 매우 크기 때문에 위의 방법을 이용하면 시간초과...

문제 10942 - 팰린드롬 접근 DP 문제이다. start에서 end까지의 팰린드롬 여부는 DP(start, end) = 0 or 1 이다. start에서 end까지의 수가 팰린드롬을 이루기 위한 재귀적 조건은 다음과 같다. arr[start] == arr[end] and DP(start+1, end-1) bottom-up 방식으로...

문제 17298 - 오큰수 접근 처음에 그냥 이중 포문으로 리스트 전체를 보는 식으로 구현했다. 당연하게도 시간초과가 나고… 어떻게 시간을 줄일 수 있을지 고민한 문제.. 처음엔 아리송했는데, 리스트를 순서대로 보면서 자신보다 큰수가 나오면 그 수는 오큰수를 찾고 더이상 볼 필요가 없다. 반대로 큰 수가 아직 나오지 않았으면 큰 수가...

문제 20040 - 사이클게임 접근 사이클 여부를 체크하는 문제이다. 사이클을 확인하는 알고리즘은 유니온-파인드 알고리즘이 있다. 유니온-파인드 알고리즘은 그래프 알고리즘의 하나로써, 상호 배타적 집합이라고도 부른다. 유니온-파인드 알고리즘은 최초에 자기 자신을 루트 로드로 가지는 트리 형태로 시작한다. 모든 노드들이 하나의 트리를...

문제 1806 - 부분합 접근 투 포인터 문제이다. start, end를 두고 원하는 값 S 보다 작으면 end에 위치한 원소를 더하고 end를 한칸 움직인다. S보다 커진다면 start에 있는 값을 빼고 start를 한칸 움직인다. 이를 배열의 끝까지 반복하며 S를 만족시키는 end-start 중 최소를 찾는다. 종료 조건을 만들...

문제 2638 - 치즈 접근 BFS이자, 시뮬레이션 문제이다. 상온에 접촉하는 공기와 접촉하지 않는 공기를 나눠서 구분해줘야 하기 때문에, 치즈로 접근하면 문제가 복잡해진다. 공기를 구분해주기 위해 BFS를 수행하고, 치즈에 대해서 다시 BFS를 수행해야 하므로 일을 두 번하는 느낌이다. 문제 조건 중 테두리는 항상 공기가 입력된다고...

문제 2096 - 내려가기 접근 DP 문제이다. 한 줄씩 내려오며 만난 숫자를 더하여 최대값, 최소값을 만드는 문제이다. 이 때 원하는 곳으로 내려갈 수 있는게 아니라, 이전 상태의 영향을 받게된다. 이전 위치에서 좌,우로 최대 한칸밖에 움직이지 못한다. 즉, 이전에 (i, 0)번 위치에 있었다면 (i+1, 0), (i+1, 1)까...