one Book a Day

자바의 main() 메서드 Java 프로그램은 특정 순서로 실행되는 Java 명령의 시퀀스기 때문에 시작과 끝이 있다. Java 프로그램을 실행하려면 JVM에 프로그램 실행을 시작할 위치를 신호해야한다. Java의 모든 명령어(코드)는 Java 클래스 내에 위치해야한다. 클래스는 함께 속한 데이터와 명령어를 그룹화하는 방법이다. 따라서 클래스는 변수와 메서드를 모두 포함 할 수 있다. 변수는 데이터를 포함할 수 있으며, 메서드는 데이터에 대한 작업 집합(명령어)을 함께 그룹화한다. 자바 클래스 선언 Java 코드는 클래스와 동일한 파일 이름을 가진 파일에 있어야하며 파일 접미사로 끝나야한다. 즉 파일이 클래스 이름과 일치하는 파일에 있어야 Java SDK의 Java 컴파일러 또는 Java IDE 내부에서..

VID(Variable ID) : 변수 ID CEID(Collected Event ID) : 시스템 내에서 발생되는 Event ID ECID(Equipment Constant ID) : 장비의 입력 Parameter 값 DVID(Data Variable ID) : 특정 시점에만 유효한 변수 SVID(Status Variable ID) : 어느 시점, 순간에도 항상 유효한 변수. 장비 상태값 등 RPTID(Report ID) : 데이터 보고 형식의 ID - 위 변수들을 보고하는 set의 ID

비트문제라기엔 EOF출력이 더 어려웠다.. import sys input = sys.stdin.readline while True: memory = [0 for _ in range(32)] cal = 0 pc = 0 for i in range(32): try: memory[i] = int(input().rstrip(),2) except EOFError: exit() while True: adress = memory[pc] cmd = adress//32 value = adress%32 pc = (pc + 1)%32 if cmd == 0: memory[value] = cal elif cmd == 1: cal = memory[value] elif cmd == 2: if not cal: pc = value el..

코드는 한방에 짰는데 1갯수 확인하는 코드에서 노래수만큼이 아니라 기타수만큼 반복문돌려서 7번 틀렸다.. import sys input = sys.stdin.readline from itertools import combinations # 기타 플레이 리스트 이진수로 바꿔서 set에 저장. N,M = map(int,input().split()) guitars = set() for _ in range(N): name,pos = input().split() bin_change='' for chr in pos: if chr=="Y": bin_change += '1' else: bin_change += '0' guitars.add(int(bin_change,2)) # 셋에서 0 제거하고 비었으면 -1출력후 종료..

틀렸습니다 : output이 틀렷을 경우. testcase 초기화를 잘해줘야함. 시간초과 : 시간복잡도 제한을 못맞췄을 경우. => 보통 추상화 알고리즘을 잘못썼거나, 변하지 않는 dp값을 여러번 계산했을 경우(계산값 저장을 하지 않는 경우), 내장함수 계산값을 저장해두지 않고 반복문마다 돌리는 경우 => 파이썬에서 어떤 값이 같은지 비교할 때 == 대신 is를 사용하면 안됨. ++list를 큐 또는 덱으로 사용하면 절대 안됨. 반드시 collection.deque를 써야함. 런타임 에러 : 실행 시 나타나는 type, index접근 등 에러, 재귀함수가 있는 경우에는 재귀 깊이 제한인 sys.setrecursionlimit(100000)을 써줘야함. 메모리 초과 : sys.setrecursionlimi..

조합으로 거리구하고 간선 heap으로 정렬 후 n-1개만큼 연결 from heapq import heappop, heappush def find(x): if parents[x] == x: return x parents[x] = find(parents[x]) return parents[x] def union(x, y): x = find(x) y = find(y) if x > y: x, y = y, x parents[y] = x for test in range(1, int(input()) + 1): N = int(input()) X = list(map(int, input().split())) Y = list(map(int, input().split())) parents = {i: i for i in rang..

1등을 찾고 삭제한 그룹에서 1등을 찾으면 2등 그룹이 나온다. import sys input = sys.stdin.readline from collections import defaultdict while 1: N, M = map(int, input().split()) if not N and not M: break rankers = defaultdict(int) answer = [] max_cnt = 0 for _ in range(N): a = list(map(int, input().split())) for num in a: rankers[num] += 1 if rankers[num] > max_cnt: max_cnt = rankers[num] answer = [num] elif rankers[num]..

PIO 통신 Parallel Input Output : 평행 입출력 통신 I/O 상태를 전당하는 입출력 =E84 통신 : SEMI 규약으로 장비 간 제품 이동 시 사용 물류장비들을 조작하는 AMHS(Controller), Equipments 간 통신 I/O 8 bit로 통신 Active는 IB 장비들, Passive는 STK 혹은 EQP Active와 Passive 장비들 간의 이동을 시나리오에 따라 통신하는 과정. LR, UR, READY, BUSY, COMPLETE 등. [예시 영상](https://www.youtube.com/watch?v=6qPP4I5hx3Q&t=5s) Reference [Youtube 깹 tv](https://www.youtube.com/watch?v=6qPP4I5hx3Q&t=5s)

최초풀이 : 브루트포스. 시작지점, 종료지점 정해놓고 안에 0있으면 연산 포기 개선풀이 : stack이용 열, 행순회하며 기록해둔 높이값을 기반으로 해 높이가 높은 직사각형부터 연산. 최초풀이 import sys input = sys.stdin.readline def find_rectangle(x,y): max_size = 100 for i in range(100): if x+i >100: break for j in range(100): if y + j > 100: break max_size = max(max_size,calculate_area(x,y,x+i,y+j)) return max_size def calculate_area(x,y,h,w): cnt = 0 for i in range(x,h+1): ..

dp[층수][둘사이 거리]의 경우의 수로 계산. 거리가 그대로일 경우 둘(아래아래, 대각,대각) 거리가 줄경우 하나(대각아래) 거리가 늘경우 하나(아래대각) 거리가 0인경우는 그냥 배제 import sys input = sys.stdin.readline n = int(input()) dp = [[0]*(n+1) for _ in range(n+1)] dp[2][1] = 2 for i in range(3,n+1): for j in range(1,i): dp[i][j] = (dp[i-1][j]*2 + dp[i-1][j-1] + dp[i-1][j+1])%10007 sum_n = 0 for i in range(1,n): sum_n += dp[n][i] print(sum_n%10007)

라인스위핑 스위핑 알고리즘이란? 특정 선이나 공간을 한쪽에서부터 쓸어버리는 식의 알고리즘. 일정 좌표, 축기준 정렬 한 뒤 일정 시점의 좌우 가장 가까운 두 점사이의 거리보다 멀리떨어진 점은 조사하지 않는 방식. 가지치기를 하겠다는 이야기다.(O(NlogN)) 아래는 2261번 문제에 대한 분할정복 풀이. import sys input=sys.stdin.readline INF=sys.maxsize # 두 점 사이의 거리를 구하는 함수 def dist(a,b): return (a[0]-b[0])**2+(a[1]-b[1])**2 def divide(start,end): # 점 하나면 버림 if start==end: return INF # 점 두개면 거리구해서 리턴 elif end-start==1: retur..

이분탐색으로 무게중심 찾고 그 좌우에 있는 마을만 거리비교해서 최솟값으로 가져감. 둘 거리같으면 왼쪽꺼 가져감. import sys input = sys.stdin.readline from bisect import bisect_left def cal_dist(position): dist = 0 for town, population in arr: dist += abs(position-town)*population return dist N = int(input()) arr = [tuple(map(int, input().split())) for _ in range(N)] left = -1000000000 right = 1000000000 answer = 0 while left

디자인 패턴(객체를 어떻게 구성할 것인가?) 이름의 중요성 디자인 패턴 이전에는 명칭이 없어서 같은 내용의 구조를 서로에게 설명해주기위해 수십시간을 낭비. 이름이 곧 개념을 정의한다 디자인 패턴도 이런 자주 사용되는 개념에 이름을 정의한 것. *비슷한 문제 상황을 해결했던 해결책을 잘 기억하고 다시 적용할 수 있다면 유용할 것이다. * 동료 개발자들과 잘 공유하기 위한 방법이 곧 ‘이름’을 지어주는 것이다. 소프트웨어 공학에서 디자인 패턴(Design pattern)은 프로그램 개발 시에 자주 부닥치는 애로 상황에 대한 일반적이고 재사용 가능한 추상화된 해결책이다. 소프트웨어 공학적으로 디자인 패턴은 패러다임과 알고리즘과는 다르다. OOP 패러다임으로 개발을 하든, 함수형 프로그래밍 패러다임으로 개발을 ..

stack란에 있어서 억지로 stack처럼 LIFO구현. 조금 더 만지면 복사안하고 stack2개로 돌릴 수 있을 것같은데 그냥 구상만.. import sys sys.stdin = open('input.txt') test = int(input()) for test in range(1, test+1): n = int(input()) pascals = [[] for _ in range(n)] #* *삼각형을 그릴 틀* pascals[0].append(1) #* *첫열은 그냥 삽입* for i in range(1, n): #* *2열부터 그릴 것임.* stack = pascals[i-1][:] #* *1열(i-1열을 복사)* pascals[i].append(1) #* *첫인자 삽입* for j in range..

선호도 관리를 어떻게 할 것인가? 일단 힙으로 하긴했는데.. 최선일지는 모르겠다. import sys from heapq import heappop,heappush input = sys.stdin.readline # N일 K종류 맥주 무료 제공 # 하루 맥주 1병 전에 받은 종류 못받음. # 맥주 N개의 선호도 합 M이상. # 조합 K 종류 맥주 중 N개 추출 합이 M이상되는. # 도수 낮은거 순으로 먹음. N, M, K = map(int, input().split()) beers = [list(map(int, input().split())) for _ in range(K)] beers2 = sorted(beers,key=lambda x: (x[1],x[0])) heap = [] flav_p = 0 cn..

dfs 탐색 진행했습니다. import sys sys.stdin = open('input.txt') def dfs(v): if v == 99: return True for u in graph[v]: if not visited[u]: visited[u] = True if dfs(u): return True for _ in range(10): test, edge_n = map(int, input().split()) graph = {i: [] for i in range(100)} edge_set = list(map(int, input().split())) visited = {i: False for i in range(100)} for i in range(0, edge_n*2, 2): graph[edge_set..

펜윅 트리(바이너리 인덱스 트리) 시간복잡도 O(MlogN) 구간합, 값 업데이트O(logN) 그림1. 세그먼트 트리 그림2. 펜윅 트리 Fenwick Tree를 구현하려면 어떤 수 X를 이진수로 나타냈을 때 마지막 1의 위치를 알아야 합니다. 마지막 1이 나타내는 값을 L[i]라고 표기하면 L[3]은 11(2)로 1, L(10)은 1010(2)로 2 가 됩니다. 수 N개를 A[1] ~ A[N] 이라고 했을 때, Tree[i]는 A[i] 부터 앞으로 L[i] 개의 합이 저장되어 있습니다. 아래 그림은 각각의 i에 대해서, L[i]를 나타낸 표입니다. 아래 초록 네모는 i부터 앞으로 L[i]개가 나타내는 구간입니다. L[i] = i & -i가 됩니다. 그 이유는 아래와 같습니다. -num = ~num + ..

1. find 2. 여러개 탐색. a = str1.find(str2) print a while str1[a+1:].find(str2) != -1: a = str1[a+1:].find(str2) + a + 1 print a 3. re 모듈의 finditer(b,a) for a in re.finditer(str2,str1) : print a.start() start()는 시작위치 반환, end()는 끝위치 반환 4. A.startswitth(a,b) a문자가 A문자열의 b위치에서 시작되면 True반환. 5. A.endswith(a,b) =>보통 b위치에 find(a)를 넣어 True강제반환하게끔 가능.

미스터코 님의 10분 테코톡 시청 후 작성하였습니다. 간단한 정의 MPM(multi-Processing-modules) 서버는 시스템의 네트웍 포트에 연결하고, 요청을 받아들이며, 받아들인 요청을 처리하기 위해 자식들에게 분배하는 다중처리 모듈(MPM)을 선택할 수있다. NGINX - 웹서버 Node.js : Chrome V8 Javascript 엔진으로 빌드된 JavaScript 런타임. [언제 어떤 것을 선택해야 하는가???????] 세가지 모두 '웹서버'의 역할을 할 수 있다. (Node.js는 웹서버역할도 WAS(Express.js)도 가능함. 때문에 결이 좀 다름.) 동시성은 예전이나 지금이나 중요하다. (어느정도 기간동안 무시하지 않을 수 있는 연결들(+요청들)) -옛적엔 너무느린 네트워크(1..

1. 내 github에 추가할 상대 repository를 fork해오기(오른쪽 위에 포크모양 클릭) 2.fork해서 만들어진 내 github의 repository url을 복사 후 받아오기 (clone URL) 3. 원격 저장소 내 내부 저장소로 받아오기. git clone [Clone URL] 4. pull request작업 수행할 branch 생성 git checkout -b [branchName] 5. 원본 저장소를 원격 저장소에 추가. git remote add origin(branchname) [Clone URL] 6. 코드 수정 및 파일 추가 7. 수정사항을 add git add [fileName] 8.add 한 파일들을 commit git commit -sm "[commit mesagge]"..

LRU cache O(1) 캐시는 불필요한 통신을 줄이고 기민한 UX를 제공 DB과부하를 막음.(query결과 저장) Proxy, CDN(유저와 가까운 CDN node) 메모이제이션 OrderedDict이용 from collections import OrderedDict MAX_SIZE = 2 cache = OrderedDict() def get_user(user_id): if user_id in cache: cache.move_to_end(user_id) return cache[user_id] if len(cache) == MAX_SIZE: cache.popitem(last=False) cache[user_id] = fetch_user(user_id) return cache[user_id] last=F..

D3.js D3은 데이터 기반 문서(Data-Driven Documents) SVG, HTML, CSS를 이용해 웹 브라우저에 맞춤형 데이터 시각화를 생성하기 위한 오픈소스 Protovis는 정적 시각화, D3은 상호작용, 전환 및 변환에 중점. 전역 JavaScript 개체 d3을 정의 D3의 기능 웹 표준 사용 데이터 기반 DOM 조작 데이터 기반 elements 동적 속성 시각화 유형 맞춤형 시각화 전환(transition) 상호작용 및 애니메이션(duration, delay, easy) D3의 장점 모든 JS 프레임워크와 함께 사용 가능. D3는 데이터에 중점을 두고 있으므로 데이터 시각화에 유리. D3는 오픈 소스기 때문에 소스 코드로 작업하고 고유한 기능 추가가 가능 웹 표준과 함께 작동하므로..

Tool - Preferences - Window Types - SQL Window 선택 - AutoSelect statement 를 진행한 후 원하는 쿼리 드래그 하고 F8 누르면 해당 부분만 실행된다.

좀 무식하게 푼 느낌이 없잖아 있습니다. 달팽이 거꾸로 파고들면서 그렸습니다. 빈칸은 -1로 표기 빈칸 없을때와 빈칸이 있을 떄 1열로 펼치는 순서가 다릅니다. import sys input = sys.stdin.readline from collections import deque # 달팽이를 만든다. 시작좌표는 def make_snail(): row, col = n, n if n**2 - N >= n: col -= 1 matrix = [[0] * col for _ in range(row)] q = deque() q.append((row - 1, col - 1, 0)) blank_cnt = row * col - N start = N - 1 while q: x, y, d = q.popleft() matri..

평범한 분할정복문제입니다. 3분할할때 칸막이 설치 위치만 잘 고려해주면 됩니다. import sys input = sys.stdin.readline def count_odd(n): cnt = 0 for i in n: if int(i) & 1: cnt += 1 return cnt def divided(n, cnt): global max_v, min_v s = str(n) cnt += count_odd(s) if len(s) == 1: min_v = min(min_v, cnt) max_v = max(max_v, cnt) return elif len(s) == 2: divided(n // 10 + n % 10, cnt) else: for i in range(1, len(s) - 1): for j in rang..

set으로 정답이 될수있는 경우를 찾아주면 됩니다. 사실 16칸밖에 되지 않으므로 16자리 bit를 인자로 넘겨주거나 3차원 배열(x, y, bit상태)을 만들어 bit상태와 현재num이 같으면 더 조사하지 않게 가지치기를 할 수 있습니다. 근데 안해도 통과되긴 합니다. def dfs(cnt, x, y, num): global answers if cnt == 7: answers.add(num) return for dx, dy in delta: nx, ny = x + dx, y + dy if 0

투포인터를 각 출발선마다 돌리는 로직입니다. 정렬후 앞에서 하나씩 고정값으로 픽스시켜두고 두가지 포인터로 합의 범위를 0으로 수렴시켜나가는 과정입니다. import sys input = sys.stdin.readline n = int(input()) liquid = sorted(list(map(int, input().split()))) close_zero = float('inf') selected = [0]*3 for start in range(n - 2): left, right = start + 1, n - 1 while left < right: sum_value = abs(liquid[start] + liquid[left] + liquid[right]) if sum_value < close_zero:..

마찬가지로 백트래킹 문제. def dfs(depth, cur_node, total): global min_sum if depth == N-1: min_sum = min(min_sum, total + matrix[cur_node][0]) return if total > min_sum: return for next_node in range(N): if not col_check[next_node]: col_check[next_node] = True dfs(depth + 1, next_node, total + matrix[cur_node][next_node]) col_check[next_node] = False for test in range(1, int(input()) + 1): N = int(input())..

카카오 블라인드 1차 6번 효율성 문제. 구간 합을 이용해 갱신하는 방법으로 그때 아이디어만 얻어두었다가 드디어 해결했다. 양 끝에만 적어두고 dp로 누적값 배열을 만든 후 최종 배열은 원배열 + 변화량 배열의 합으로만 구하는 방법. 프로그래머스에 이번년도 문제 올라오면 다시 풀어보자. 사람들이 웰노운 웰노운 거리더니.. 여튼 좋은 방법론을 얻었다. import sys input = sys.stdin.readline N, M = map(int, input().split()) H = list(map(int, input().split())) save = [0] * (N+1) for _ in range(M): a, b, k = map(int, input().split()) save[a-1] += k save[..

카카오톡 2차 정답이 없는 문제. 요구사항을 기반으로 trade-off를 감안해 로직을 설계. 로직을 개선해가는 역량. REST API 호출. API결과가 JSON 포맷. REST API 호출 처리 모듈, JSON 파서 사전 준비. pprint, bs4 쓸수있나? 일단 깔아놔보기. JSON? Java Script Object Notation. 통신을 통해 데이터를 주고 받는데 사용되는 규칙, 형식 JSON은 dictionary에 key - value 형식으로 이루어진다. REST API로 이용해 받아온 값을 JSON형태 import json, requests response = requests.get(URL).json() response = requests.post(URL,header,data).json..

파라매틱 서치. k번 이상 자를 수 있는지 결정하는 문제. 자주나오는데 아직 좀 사고가 더디다. import sys input = sys.stdin.readline def is_minimum(mini): left = 0 cnt = 0 for right in cut_points: if right - left >= mini: left = right cnt += 1 if cnt > k: return True return False N, M, L = map(int, input().split()) cut_points = [int(input()) for _ in range(M)] + [L] for _ in range(N): k = int(input()) # M개의 지점 중 k개 선택. 사잇값의 최솟값이 가장 큰. ..

말 그대로 귀찮은 문제. 하지만 많이 보던 파일 합치기의 idea가 일부 사용된 문제기도 하다. 가장 작은 부분부터 해결하는게 최소 비용을 보장한다. import sys input = sys.stdin.readline n = int(input()) arr = list(map(int, input().split())) arr.sort() total = sum(arr) answer = 0 for num in arr: answer += num * (total - num) total -= num print(answer)

뒤에 2개는 상태인자. 방향전환 가능여부와 바라보는방향 import sys input = sys.stdin.readline # 남북 w 동서도로 h개 # 남북방향 도로는 왼쪽부터 1,2,...w개 동서도로는 아래부터 1,2,.,..h개 # 서쪽 i번째에서 남북 남쪽j번째도로가 만나는 교차로는 i,j이다. # (1,1) (w,h) 가는방법. 방향전환은 최소2칸이상. # 상태값(x과표, y좌표, x방향전환가능, y방향전환 가능) w,h = map(int,input().split()) dp = [[[[0 for _ in range(2)] for _ in range(2)] for _ in range(101)] for _ in range(101)] # 앞의 0,1은 방향전환이 가능하냐, 불가능하냐? 뒤의 0,1은..

배열에서 경우의 수로 합이나 최소 최대 구하기 나올때마다 BFS, DFS 보다 비트마스킹하면 어떨까 상상만 해봤는데 실제로 접한 첫문제. 경우의 수 브루트포스 문제를 비트마스킹으로 어떻게 순회할 것인가 잘 나타낸 문제 같다. 코드 전체 다 외워도 손색없는 문제. 아이디어는 배열의 가로, 세로 계산 여부를 0,1로 나누어 1이면 가로계산에 이용하고 0이면 세로계산에 이용한다. 각 열, 행을 순회하며 1이 이어지면 왼쪽으로 한칸씩 늘려주며 누적합의 자릿수를 늘려주고 0이 나오면 자릿수를 초기화시키는 형식. def bitmask(): global maxAns # 비트마스크로 2^(N*M)의 경우의 수를 따져본다 for i in range(1

JS 30개 프로젝트 만들기. Wes Bos님 강의 2.Analog Clock 제어해야 될 요소들 (시침, 분침, 초침) transform-origin 은 0퍼센트일경우 왼쪽 끝이 축, 100퍼센트는 오른쪽 끝이 축.(변환원점) 하나 더주면 상하 축까지 조정. 축을 기준으로 rotate 움직임은 0.05초 동안 유지 transition-timing-function transition의 진행속도를 조절한다. east. linear, ease-in, ease-out, initial, inherit ... 각 시계침들을 요소로 1초마다 set Date를 불러 업데이트.(setInterval) now 날짜 객체의 시, 분.. 위 코드는 오타. hour은 getHour로 받아옴. 원본은 수정 setInterval..

자바 스크립트 30개 미니 프로젝트 만들기 - 1 Drum Kit JS 30개 프로젝트 만들기. Wes Bos님 강의 Drum Kit data key값으로 오디오를 불러오는 것이 핵심. key와 audio에 대해 각 event 속성을 불러 control event를 트리거로 classList를 통해 class를 추가, 제거시키므로써 입력에 대한 제어를 가능케 함. const div = document.createElement('div'); div.className = 'foo'; // our starting state: console.log(div.outerHTML); // use the classList API to remove and add classes div.classList.remove("foo..

얘는 늘 dfs.. import sys input = sys.stdin.readline def dfs(expression, depth, use_cnt): global max_result, min_result if depth == N: tmp = eval(expression) max_result = max(max_result, tmp) min_result = min(min_result, tmp) return if use_cnt[0] < p_cnt: use_cnt[0] += 1 dfs(expression + "+" + str(nums[depth]), depth + 1, use_cnt) use_cnt[0] -= 1 if use_cnt[1] < mi_cnt: use_cnt[1] += 1 dfs(expressio..

이분탐색 + bfs import sys input = sys.stdin.readline from collections import deque def is_possible(limit): queue = deque() queue.append(s) visited = {i: False for i in range(1,N+1)} visited[s] = True while queue: cur_node = queue.popleft() if cur_node == e: return True for next_node, next_limit in graph[cur_node]: if not visited[next_node] and limit

핵심은 power함수의 logN화. 1번 50점. import sys input = sys.stdin.readline N = int(input()) menus = sorted(map(int,input().split())) MOD = 1000000007 minus = 0 for i in range(N-1): for j in range(i+1,N): minus += ((menus[j] - menus[i])*(2**(j-i-1)))%MOD print(minus%MOD) 2번 50점 N = int(input()) menus = sorted(map(int,input().split())) MOD = 1000000007 minus = 0 plus = 0 for i in range(N): minus += (menus[..

이분탐색 짤때마다 느끼지만 조금 인덱싱 꼬일때가 있움.. l =(0.9)*f[m]: l = m + 1 else: r = m c += r-i-1 print(c)

소프트웨어 공학 소프트웨어는 상품. 공학은 좋은 상품을 낮은 가격에 계획대로 만들기 위한 방법론. 소프트웨어란? 단순 프로그램이 아닌 개발, 운용, 보수에 필요한 모든 관련 정보(설계문서가 가장 큰 비중) 설계, 개발과정에서 비용이 많이들고 완제품 생산은 비교적 저비용 소프트웨어엔 물리적인 부품이 없기 때문에 신뢰도의 결정은 생산과정이 아닌 설계과정에서 측정 결함을 설계과정의 테스팅으로 찾아내는 형식.(물리적 검출 불가) 소프트웨어의 특징 복잡성 (complexity) - 수 많은 내부요소들이 있어 상호작용이 많고 복잡하다. 문제가 무엇인지, 요구가 무엇인지 잘 정의하기 힘들다. 요구되는 사항이 서로 상충되어 설계가 어렵다. 순응성 (conformity) - 요구나 환경, 데이터에 따라서 적절하게 변형된..

가장 큰 정사각형 만들기와 동일하다. 장애물이 나오면 최소 길이가 0으로 끊기고 다시 1부터 하나씩 늘려가는방식. import sys input = sys.stdin.readline # 가장 큰 정사각형 문제와 같은 문제. 위 좌, 대각 안쪽 중 가장 변의 길이가 짧은 변에 하나를 추가시켜주는 방식이며 # 장애물을 만나면 다시 0부터 시작한다. M, N = map(int, input().split()) matrix = [list(map(int, input().split())) for _ in range(M)] dp_length = [[0 for _ in range(N+1)] for _ in range(M+1)] max_length = 0 for i in range(1,M+1): for j in range..

마나커 알고리즘의 핵심은 #을 삽입해 짝수 펠린드롬에 대비하는것, 중심점과 반지름 a배열의 관리. a배열의 관리는 r과 현재 인덱스now값에 의거해 관리되며 r과c값은 펠린드롬 범위 내 외에서 출발지점 인덱스 0에서 얼마나 멀어졌냐에 따라 관리된다. import sys input = sys.stdin.readline def manacher(string): n = len(string) a = [0] * n # i번째 문자를 중심으로 하는 가장 긴 팰린드롬 반지름 크기. c = 0 # 중심점(center) 초기화 r = 0 # 시작점에서 가장 먼 반경(펠린드롬 끝나는 인덱스중 가장 큰 값.) for now in range(n): # i번째 문자가 now 아래쪽에 있는 문자를 중심으로 하는 팰린드롬 범위 밖의..

문자열 매칭 연습하기위해 kmp사용했고 사실 그냥 패턴을 기준으로 split하거나 replace로 변경시켜주면 더 쉽다. import sys sys.stdin = open('input.txt') def make_failure_function(p): failure_function = [0] * (len(pa)) counter = 0 for idx in range(1, len(p)): while counter > 0 and p[counter] != p[idx]: counter = failure_function[counter-1] if p[counter] == p[idx]: counter += 1 failure_function[idx] = counter return failure_function def kmp..

이분탐색입니다. import sys input = sys.stdin.readline def isPossible(length): cnt = 0 for pa in pas: cnt += pa//length if cnt >= C: return True return False S, C = map(int, input().split()) pas = [int(input()) for _ in range(S)] start = 1 end = max(pas) answer = (start+end)//2 while start

고지식한 매칭 text = 'ABABCA' for i in range(len(text)-len(target)): for j in range(len(target)): if text[i+j] == target[j]: j+=1 else: break print('Identified') break KMP 알고리즘.(시작위치 후보를 잡아놓자) 불일치가 발생한 텍스트 스트링의 앞 부분에 어떤 문자가 있는지를 미리 알고 있으므로, 불일치가 발생한 앞 부분에 대하여 다시 비교하지 않고 매칭을 수행. 패턴을 전처리하여 배열 next[M]을 구해서 잘못된 시작을 최소화함. next[M]: 불일치가 발생했을 경우 이동할 다음 위치 패턴내에서 반복하는 구간이 있을것이라는 전제.. 하지만 없다면 무의미. 하지만 패턴이 길다는 전..

그래프 그리고 DFS~ import sys input = sys.stdin.readline def DFS(cur_node, target): if cur_node==target: return True for next_node in graph[cur_node]: if not visited[next_node]: visited[next_node] = True if DFS(next_node, target): return True n = int(input()) graph = {i:[] for i in range(26)} level = {i:0 for i in range(26)} for _ in range(n): first, arrow, end = input().split() first_num = ord(first)..

1. 투포인터 2. 덱 3. 힙 import sys sys.stdin = open('input.txt') def special_sort(length, arr): arr.sort() max_idx = length-1 min_idx = 0 special_arr = [] # 정렬한 배열의 양끝에서부터 하나씩 특별한 배열로 삽입합니다. # 양끝이 만나면 종료합니다. while min_idx

크누스 최적화(Knuth's optimization) 특수한 DP 점화식에 대해 적용할 수 있는 최적화. 조건 어떤 2차원 배열 C DP를 사용하는 2차원 배열 dp C는 i부터 j까지 합치는데 드는 비용. 여기서 비용은 이전 비용에 현재 비용을 누적해서 계산하는 문제이다. quadrangle inequeality : 사각부등식으로 (a,b,c) + (b,c,d)

딱히 소수판별을 체를 사용해서 할 필요는 없을 것 같아서 더한값들 개별적으로 진행해줬다. 조합은 DFS로 구성. import sys input = sys.stdin.readline def DFS(start,depth,sum_cow): if depth==M: if isPrime(sum_cow): answer.add(sum_cow) for i in range(start,N): if not visited[i]: visited[i]=True DFS(i+1,depth+1,sum_cow+H[i]) visited[i]=False def isPrime(n): if n