Bruteforce

최소직사각형 문제 바로가기 나의 풀이 enumerate 함수로 input을 쪼개주고 각 케이스별로 최대/최소를 각각 따져주었다. 다만 어떤건 가로가 길고 어떤 건 세로가 더 길기 때문에 모두 가로가 더 길도록 정렬해주는 작업이 추가로 필요했다. def solution(sizes): max_w, max_h = 0, 0 for _, wh in enumerate(sizes): w,h = max(wh),min(wh) if w > max_w: max_w = w if h > max_h: max_h = h return max_w * max_h 고수의 풀이 def solution(sizes): return max(max(x) for x in sizes) * max(min(x) for x in sizes) 출처 다른 분들의 풀이를 구경했는데, 두줄로 끝내버린 분들도 계셨다. input으로 들어오는 값들 중에 큰 값의 최댓값과, 작은 값의 최댓값의 곱이 곧 정답이기에 위처럼 풀 수도 있다. 하지만 메모리 사용량이 늘어나서 과연 좋은 풀이인지에 대해서는 생각해볼 필요가 있다. ...

백준 14501번 문제 바로가기 Bottom-Up 방식 문제는 이해했는데 ‘이걸 어떻게 구현하지’라는 생각에 문제를 해결하기까지 꼬박 이틀이 걸렸다. 예제들을 직접 손으로 그려보기도 하고, 문제를 다시 분석해보면서 해결책을 찾았다. Bottom-Up 방식이 그나마 직관적이고 이해하기 편해서 다음과 같이 구현했다. 0에서 n까지 index에 대해서 이중 max()로 값을 비교하고 최대 기댓값을 산출하는 알고리즘을 구현했다. # 입력 import sys n = int(sys.stdin.readline()) work = list(tuple(map(int, sys.stdin.readline().split())) for i in range(n)) dp = [0] * (n+1) # 처리 # bottom-up 방식 for i in range(n): if i+work[i][0] <= n: dp[i+work[i][0]] = max(dp[i+work[i][0]], max(dp[:i+1]) + work[i][1]) print(max(dp)) Top-Down 방식 아무리 고민해도 Top-Down 방식 구현이 어려워서 다른 블로그들을 참고했다. 예시 꾸준히 공부해나가면서 다른 접근으로도 풀어낼 수 있도록 실력을 키워야겠다. ...

백준 18111번 바로가기 나의 풀이 # 입력 n, m, b = map(int, input().split()) blocks = [] for _ in range(n): for i in map(int, input().split()): blocks.append(i) from collections import Counter blocks=Counter(blocks) time = 1000000000 current = 0 # 처리 for h in range(257): temp = 0 a = b for i in blocks.keys(): dif = h-i if dif >= 0: temp += dif * blocks[i] a -= dif * blocks[i] else: temp -= dif * blocks[i] * 2 a -= dif * blocks[i] if a >= 0: if time >= temp: time = temp current = h print(time, current) CODE REVIEW 브루트포스로 풀어내는 문제. 조건에 맞게 for문을 작성하는게 은근 까다로워 푸는데 시간이 오래 걸렸다. python3이라 그런지 시간 초과 에러가 발생해서 collections라이브러리의 Counter를 이용해서 풀어냈다. 모든 땅을 각각 저장하는 대신 땅의 높이에 따라 정리하니까 시간 복잡도가 O(n*m)에서 O(256)으로 줄어들었다. 반례 모음으로 충분히 테스트 해본 뒤에 결과를 제출하자. 생각지도 못한 반례가 은근 있어서 놀랬다.

백준 16173번 바로가기 나의 풀이 import sys sys.setrecursionlimit(10**6) n = int(input()) maps = [] for i in range(n): lines = map(int,input().split()) maps.append(list(lines)) visited = [[False] * n for _ in range(n)] def dfs(x,y): if not 0<=x<n or not 0<=y<n: return l = maps[y][x] if l == -1: print("HaruHaru") exit(0) if not visited[y][x]: visited[y][x] = True dfs(x+l,y) dfs(x,y+l) return dfs(0,0) print("Hing") 고수의 풀이 import sys from collections import deque def solution(N, graph): visited = [[False] * N for _ in range(N)] dx = [1, 0] dy = [0, 1] def dfs(x, y, visited): queue = deque() queue.append((x, y)) while queue: x, y = queue.popleft() if graph[x][y] == -1: return 'HaruHaru' jump = graph[x][y] # 점프 값 for i in range(2): nx = x + dx[i] * jump ny = y + dy[i] * jump if nx >= N or ny >= N: continue if visited[nx][ny]: continue else: visited[nx][ny] = True queue.append((nx, ny)) return 'Hing' print(dfs(0, 0, visited)) if __name__ == "__main__": N = int(sys.stdin.readline()) graph = [list(map(int, sys.stdin.readline().split())) for _ in range(N)] solution(N, graph) 출처 ...

백준 2670번 바로가기 첫 번째 풀이 l = [] for _ in range(n:=int(input())): l.append(float(input())) s = [] for i in range(n): temp = l[i] s.append(temp) for j in range(i+1,n): temp *= l[j] s.append(temp) print(round(max(s),3)) 메모리 초과 두 번째 풀이 l = [] for _ in range(n:=int(input())): l.append(float(input())) max = max(l) for i in range(n): temp = l[i] for j in range(i+1,n): temp *= l[j] if temp > max: max = temp print(round(max, 3)) 시간 초과 세 번째 풀이 l = [] for _ in range(n:=int(input())): l.append(float(input())) m = max(l) for i in range(n): temp = l[i] for j in range(i+1,n): temp *= l[j] if temp > m: m = temp print('%.3f' % m) 고수의 풀이 n=int(input()) a=[float(input())for _ in[0]*n] for i in range(1,n):a[i]=max(a[i-1]*a[i],a[i]) print(f'{max(a):.3f}') 출처 CODE REVIEW 메모리 초과 문제를 해결하기 위해 list에서 max를 뽑아내지 않고 m(현재 최댓값)보다 크면 update, 크지 않다면 그대로 pass로 바꾸어주었다. 문제 출력 형식이 소수 셋째 자리까지 맞추어줘야하므로 round()함수 대신 '%.3f % m처럼 소숫점 출력 형식으로 바꾸어주었다. 고수의 풀이 방식이 메모리도 덜 차지하고 시간도 빠른데, 각 자리별로 구할 수 있는 max값을 a[i]에 할당하고, 그것의 max를 구한다는 아이디어였다. python에서 max, min같은 이름은 변수에 붙이지 않는걸 권장한다! 웬만하면 다른 이름을 쓰자