4.분할정복 4.5 점화식을 풀기 위한 마스터 방법 T(n) = aT(n/b) + f(n) 마스터 방법은 위와 같은 점화식을 푸는 기본 지침을 제공한다. 여기서 a≥1, b>1 인 상수이고 f(n)은 점근적으로 양인 함수다. 마스터 정리 정리 4.1 (마스터 정리) a≥1, b>1 인 상수이고 f(n)이 양의 함수라 하고, 음이 아닌 정수에 대해 T(n)이 다음 점화식에 의해 정의된다고 하자. T(n) = aT(n/b) + f(n) 여기서 n/b는 ⌈n/b⌉ 또는 ⌊n/b⌋을 뜻하는 것으로 이해한다. 그러면 T(n)의 점근적 한계는 다음과 같다. ...

2023년 8월 28일 알고리즘 문제풀이 문제 1 프로그래머스 숫자 짝꿍 문제 링크 1차 시도 나의 생각 두 문자열에서 각 숫자가 몇번 등장하는 지를 확인한다. 사용할 수 있는 수는 각 숫자의 등장 횟수 중 적은 쪽이다. 예를 들어, 숫자 5가 X에서는 3번, Y에서는 7번 등장한다면 짝꿍을 위해 숫자 5는 3번 쓰일 수 있다. 짝꿍은 가장 큰 수를 나타내야 하므로 사용 가능한 정수 중 큰것부터 소모하면 된다. 사용 가능한 숫자가 0만 있을 경우와 아무것도 없을 경우도 조건문을 통해 따로 체크한다. ...

주간기록 날짜 2023년 8월 21일 ~ 2023년 8월 27일 계획 8월 23일 수요일 : 알고리즘 스터디 매일 클린코드, 알고리즘 3문제, 백엔드 공부 결과 밀린 것 열심히 따라잡는중.. WIL 해야한다고 생각할 시간에 그냥 하자 회고 열심히 산 것 같은데, 돌아보니 한게 없다ㅠ

책너두 5기 24일차 로버트 C. 마틴의 클린코드 p. 216~ p.223 내용 정리 12. 창발성 창발적 설계로 깔끔한 코드를 구현하자 켄트 백이 제시한 단순한 설계 규칙 네 가지가 소프트웨어 설계 품질을 크게 높여준다. 다음은 중요도 순이다. 모든 테스트를 실행한다. 중복을 없앤다. 프로그래머 의도를 표현한다. 클래스와 메서드 수를 최소로 줄인다. 단순한 설계 규칙 1: 모든 테스트를 실행하라 테스트가 불가능한 시스템은 검증도 불가능하고, 출시되어선 안된다. 테스트 케이스가 많을수록 개발자는 테스트가 쉽게 코드를 작성한다. 따라서 철저한 테스트가 가능한 시스템을 만들면 더 나은 설계가 얻어진다. ...

2023년 8월 26일 알고리즘 문제풀이 문제 1 프로그래머스 전력망을 둘로 나누기 문제 링크 1차 시도 나의 생각 한 간선이 없어질 때마다 값을 모두 구한 후 가장 절대값이 작을 때를 찾았다. 결과 정답 코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 from collections import deque def solution(n, wires): answer = n d = len(wires) for i in range(d): arr = deque() arr.append(0) graph = [[] for _ in range(n)] visited = [False for _ in range(n)] visited[0] = True for j in range(d): if j == i: continue else: a,b = wires[j] graph[a-1].append(b-1) graph[b-1].append(a-1) while arr: now = arr.popleft() for x in graph[now]: if not visited[x]: visited[x] = True arr.append(x) cnt = visited.count(True) cnt = abs(n-2*cnt) answer = min(answer,cnt) return answer 문제 2 프로그래머스 쿼드압축 후 개수 세기 문제 링크 ...

책너두 5기 23일차 로버트 C. 마틴의 클린코드 p. 206 ~ p.215 내용 정리 11. 시스템 순수 자바 AOP 프레임워크 순수자바 관점을 구현하는 스프링 AOP, JBoss AOP 등과 같은 여러 자바 프레임워크는 내부적으로 프록시를 사용한다. 스프링은 비즈니스 논리를 POJO(Plain Old Java Object)로 구현한다. POJO는 도메인에 초점을 맞춰서 테스트가 쉽고 간단하며, 상대적으로 단순하기 때문에 사용자 스토리를 올바로 구현하기 쉽고 미래 스토리에 맞춰 코드를 보수하고 개선하기 편하다. AspectJ 관점 관심사를 관점으로 분리하는 가장 강력한 도구는 AspectJ 언어이다. 이것은 언어 차원에서 과넞ㅁ을 모듈화 구성으로 지원하는 자바 언어 확장이다. 관점을 분리하기 좋지만 새 도구를 사용하고 새 언어 문법과 사용법을 익혀야 하는 단점이 있다. 하지만 ‘애너테이션 폼’은 이 부담을 어느정도 완화한다. ...

2023년 8월 25일 알고리즘 문제풀이 문제 1 백준 3055 문제 링크 1차 시도 나의 생각 물을 따로 생각하지 말고 이미 방문해서 방문할 수 없는 곳으로 처리한다면 크게 복잡하지 않을 수도 있겠다는 생각을 했다. 따라서 고슴도치가 이동할 곳을 BFS로 탐색하되, 방문처리를 통해 물이 있는 곳과 바위가 있는 곳을 표시하면 되겠다고 생각했다. 주어진 예시는 답을 출력했는데, 고슴도치가 다음 턴에 물이 찰 곳으로 이동할 수 없는 조건이 적용되지 않았다. 따라서 이동할 수 없는 경우가 누락되어 오답처리되었다. ...

책너두 5기 22일차 로버트 C. 마틴의 클린코드 p.198 ~ p.205 내용 정리 11. 시스템 시스템 제작과 시스템 사용을 분리하라 Main 분리 시스템 생성과 시스템 사용을 분리하는 방법 중 하나는, 생성과 관련한 코드는 모두 main이나 main이 호출하는ㄴ 모듈로 옮기고, 나머지 시스템은 모든 객체가 생성되었고 모든 의존성이 연결되었다고 가정하는 것이다. 팩토리 때로는 객체가 생성되는 시점을 애플리케이션이 결정할 필요도 생긴다. 의존성 주입 의존성 주입(Dependency Injection)은 제어 역전(Inversion of Control, IoC) 기법을 의존성 관리에 적용한 메커니즘이다. 제어 역전에서는 한 객체가 맡은 보조 책임을 새로운 객체에레 전적으로 떠넘긴다. 새로운 객체는 넘겨받은 책임만 맡으므로 단일 책임의 원칙을 지키게 된다. 초기 설정은 시스템전체에서 필요하므로 대개 ‘책임질’ 메커니즘으로 ‘main’ 루틴이나 특수 컨테이너를 사용한다. ...

2023년 8월 24일 알고리즘 문제풀이 문제1 백준 1916 문제 링크 1차 시도 나의 생각 이전에 공부한 다익스트라로 풀면 되겠다고 생각했다. 출발지부터 각 도착지까지 비용을 표시하는 배열을 만들고 최소값으로 업데이트하였다. 그런데 이상하게 오답처리가 된다. 이유를 찾아봐야겠다. 결과 오답 코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 import sys from heapq import heappop, heappush n = int(sys.stdin.readline()) m = int(sys.stdin.readline()) graph = [[0 for _ in range(n+1)] for _ in range(n+1)] for _ in range(m): s, a, c = map(int, sys.stdin.readline().split()) graph[s][a] = c start, arrive = map(int, sys.stdin.readline().split()) def search(x): cost = [10**9 for _ in range(n+1)] cost[x] = 0 arr = [] heappush(arr,[0, x]) while arr: price, now = heappop(arr) if price > cost[now]: continue for i in range(1, n+1): if not graph[now][i]: continue new_money = price + graph[now][i] if new_money < cost[i]: cost[i] = new_money heappush(arr,[new_money, i]) return cost ans = search(start) print(ans[arrive]) 2차 시도 나의 생각 원인을 찾아냈다. 나는 두 도시간의 비용을 인접행렬로 표현했다. 즉 행렬의 값이 두 도시의 이동 비용이다. 하지만 문제에서 각 도시 간의 노선이 하나라는 보장이 없다.. 그래서 두 도시간의 버스 비용이 중복해서 주어진다면 내 코드는 가장 마지막에 입력된 것만 나타내게 된다. 하지만 먼저 입력된 버스비용이 더 작다면? 내 코드에선 정답을 도출할 수 없었다. ...

책너두 5기 21일차 로버트 C. 마틴의 클린코드 p.189 ~ p.197 내용 정리 10. 클래스 변경하기 쉬운 클래스 변경으로부터 격리 객체 지향 프로그래밍에는 구체적인(concrete) 클래스와 추상(abstract) 클래스가 있다. 상세한 구현(코드)을 포함하는 것과 개념만 포함하는 것의 차이이다. 상세한 구현에 의존하는 클라이언트 클래스는 구현이 바뀌면 위험하므로 인터페이스와 추상 클래스를 사용해 구현이 미치는 영향을 격리한다. 시스템의 결합도를 낮추면 유연성과 재사용성도 더욱 높아진다. 이는 각 시스템 요소가 다른 요소로부터, 변경으로부터 잘 격리되어 있다는 의미다. 11. 시스템 도시를 세운다면? 도시에는 큰 그림을 그리는 사람들도 있으며 작은 사항에 집중하는 사람들도 있다. 한 사람의 힘으로는 직접 관리할 수 없다. 도시가 돌아가는 이유는 적절한 추상화와 모듈화 때문이다. 시스템도 마찬가지다. ...