one Book a Day

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

로직이 완전 깔끔하지는 못하지만 시간 내에 통과하도록 최소한의 연산을 하도록 노력함. 기본적으로 재귀를 통해 폭탄을 한발씩 떨어뜨리는 함수, 폭탄이 블록과 만나면 연쇄 폭발을 일으키는 재귀함수 폭발 후 빈칸에 블록을 중력을 적용해 채우는 함수. 3가지 함수와 남은 블록을 카운팅해주는 함수 1개의 함수 총 4개의 함수로 구성했으며 중간에 블록이 모두 터졌을 경우 바로 종료하지는 못했으나 더이상 N을 파고들지 않아도 W를 0~ W-1까지 순회해서 continue로 넘어가게 만듦. 모두 터지지 않을 경우의 로직은 효율적으로 짰다고 생각함. def delete_block(board, x, y, cnt): board[x][y] = 0 if cnt > 1: for i in range(1, cnt): for dx, ..

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]"..

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

배열 회전 알고리즘. 노가다 회전 def rotate(key, N): def getNewValue(i, j, x, y): key[j , N-i-1] = key[i ,j] if (i == x and j == y): return getNewValue(N-j-1, i, x, y) for i in range(0, int(N/2)): for j in range(i, N-i-1): print(i,j ) tmp = key[i,j] getNewValue(N-1-j, i, i, j) key[j, N-1-i] = tmp ZIP을 사용한 깔끔한 회전 def zip_rotate(original): rotated = np.array(list(zip(*original[::-1]))) return rotated numpy를 이용해..

3. events const searchInput = document.querySelector(".search"); const suggestions = document.querySelector(".suggestions"); searchInput.addEventListener("change", displayMatches); searchInput.addEventListener("keyup", displayMatches); search클래스를 가진 input box가 변하거나 key가 눌릴때마다 displayMatches를 불러옵니다. keyup은 키보드를 이용한 입력만 감지함. (마우스 클릭으로 붙혀넣기하거나 자동완성 단어를 클릭해서 입력되는 이벤트 인식x) change는 외부를 눌렀을때만 인지함. 키보드 ..

뒤에 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은..

Trie insert, search만 조금 변형하면 된다. import sys input = sys.stdin.readline from collections import defaultdict class Node: def __init__(self): self.word = False self.children = {} class Trie: def __init__(self): self.root = Node() def insert(self, word): node = self.root for char in word: if char not in node.children: node.children[char] = Node() node = node.children[char] same_nick[word] += 1 node...

최단 경로 알고리즘. 주요 알고리즘 BFS (완전탐색 알고리즘) 가중치가 없거나 모든 가중치가 동일한 그래프에서 최단경로를 구하는 경우 가장 빠르다 다익스트라 알고리즘 (Dijkstra Algorithm) 음이 아닌 가중 그래프에서의 단일 쌍, 단일 출발, 단일 도착 최단 경로 문제 벨만-포드 알고리즘 (Bellman-Ford-Moore Algorithm) 가중 그래프에서의 단일 쌍, 단일 출발, 단일 도착 최단 경로 문제 플로이드-워셜 알고리즘 (Floyd-Warshall Algorithm) 전체 쌍 최단 경로 문제, 다수출발, 단일도착 하나의 정점에서부터 다른 하나의 정점까지의 최단 경로를 구하는 경우 A*알고리즘이 적합하다. 다익스트라 특정 노드에서 다른 모든 노드로 가는 최단경로를 갱신. 음의 간..

물고기 움직이고 상어 움직이면 된다. import sys input = sys.stdin.readline def move_fish(arr): ret = [[[] for _ in range(4)] for _ in range(4)] for x in range(4): for y in range(4): while arr[x][y]: d = arr[x][y].pop() for i in range(d, d - 8, -1): i %= 8 nx, ny = x + delta[i][0], y + delta[i][1] if (nx, ny) != shark and 0

강한 연결 요소(SCC) 무향 그래프에서 절단점이 존재하지 않는 그래프를 우리는 Biconnected component라고 부릅니다. 절단점이 없다면 그래프 상의 어떤 점을 삭제하더라도 임의의 두 정점은 서로로 가는 경로가 존재하게 됩니다. Biconnected Component Undirected Graph에서 절단점이 존재하지 않는 그래프 Strongly Connected Component 만약 그래프의 임의의 한 정점에 대해 다른 모든 정점으로 가는 경로가 존재한다면 그 그래프를 SCC(Strongly Connected Component)라고 한다. SCC(Strongly Connected Component)특징 같은 SCC내에서 뽑은 임의의 U, V 점에서 U->V 혹은 V->U의 경로(직/간접적..

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강제반환하게끔 가능.

조합으로 거리구하고 간선 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..

a==b인경우 생각못해서 좀 걸렸다. import sys input = sys.stdin.readline N = int(input()) arr = [list(map(int, input().split())) for _ in range(N)] max_grade = {i:0 for i in range(1,6)} seq_grade = {i:0 for i in range(1,6)} for i in range(2): seq_grade[arr[0][i]] = 1 max_grade[arr[0][i]] = 1 for i in range(1,N): if arr[i][0] == arr[i][1]: arr[i].pop() for num in arr[i]: seq_grade[num] += 1 if num not in arr[i..

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)

분기있는 bfs. 벽을 뿌순 횟수에 따라 분기를 나눠준다. import sys input = sys.stdin.readline from collections import deque def bfs(x,y): queue = deque() queue.append([x,y,0]) visited = [[[0]*(K+1) for _ in range(M)] for _ in range(N)] visited[x][y][0] = 1 while queue: x,y,b_cnt = queue.popleft() if x==N-1 and y==M-1: return visited[x][y][b_cnt] for i in range(4): nx = x + dx[i] ny = y + dy[i] if 0

유니온 파인드. 정순, 역순으로 오르막길 포함된 갯수 파악해서 연산. import sys input = sys.stdin.readline def find(x): if parent[x] == x: return x parent[x] = find(parent[x]) return parent[x] def union(a,b): a = find(a) b = find(b) if level[a] >= level[b]: parent[b] = a if level[a]==level[b]: level[a] +=1 else: parent[a] = b N, M = map(int, input().split()) parent = {i:i for i in range(N+1)} level = {i:0 for i in range(N+1)..

핵심은 이미 푼 문제를 각 힙에서 제거하는 매커니즘. import sys input = sys.stdin.readline from heapq import heappop,heappush from collections import defaultdict N = int(input()) min_heap = [] max_heap = [] in_list = defaultdict(bool) for _ in range(N): P, L = map(int, input().split()) heappush(min_heap,[L,P]) heappush(max_heap,[-L,-P]) in_list[P] = True M = int(input()) for _ in range(M): command = input().split() if..

하나씩 때리면 시간초과고 마왕이 끔살나는 기준에 따라 죽는 회차가 다르니 그거만 계산해서 용사 죽는 회차랑 비교해주면 된다. import sys input = sys.stdin.readline from math import ceil h_hp, h_atk, d_hp, d_atk = map(int, input().split()) P, S = map(int, input().split()) # h_hp d_atk로 나눈 몫 올림값이 용사 사망 cnt h_death_cnt = ceil(h_hp/d_atk) # d_hp - P 를 h_atk로 때린 나머지에 P를 더한 값이 h_atk보다 작을경우 d_hp - P를 h_atk로 나눈 몫+1에 끔살 if (d_hp-P)%h_atk and (d_hp-P)%h_atk + ..

부동소수점에 대한 이해 : https://thrillfighter.tistory.com/349 Python의 부동소수점 보정 decimal 모듈 : https://docs.python.org/ko/3/library/decimal.html import decimal # 천자리까지 정확도 주기 decimal.getcontext().prec = 1000 N = int(input()) for _ in range(N): # Decimal 객체를 만듬.(float, int같은) # 자릿수 10자리까지 정확하게 입력해줌. d = decimal.Decimal(input().rstrip() + '.0000000000') pow = decimal.Decimal('1') / decimal.Decimal('3') d = de..

슬라이딩 윈도우 import sys input = sys.stdin.readline N, B, W = map(int, input().split()) stone = input().rstrip() # 까만색 B개 이하, 흰색은W개 이상 left = 0 w_cnt = 0 b_cnt = 0 max_len = 0 for right in range(N): if stone[right]=='W': w_cnt += 1 else: b_cnt += 1 while b_cnt > B: if stone[left]=='W': w_cnt -= 1 else: b_cnt -= 1 left += 1 if w_cnt>=W: max_len = max(max_len,right-left+1) print(max_len)

선호도 관리를 어떻게 할 것인가? 일단 힙으로 하긴했는데.. 최선일지는 모르겠다. 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..

JS의 비동기 처리방식 동기 / 비동기 처리 동기(Syncronous)는 먼저 시작한 작업이 끝날 때 까지 다른 작업을 할 수 없다. 비동기(Asyncronous)는 동시에 여러가지 작업을 처리하며 기다리는 과정에서 다른 함수 호출이 가능하다. 비동기 처리의 예 다음과 같은 작업들은 주로 비동기적으로 처리하게 된다. Ajax Web API요청 : 화면을 렌더링해야하는데 서버쪽에서 응답을 해주기까지 마냥 대기할 수 없다. 비동기적으로 처리한다. Ajax function getData() { let data; $.ajax({ type: 'post', url: 'https://devlibrary00108.tistory.com/', data: { seungjoo:zzang, }, s..

코드는 한방에 짰는데 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출력후 종료..

적힌 숫자가 중복 없이 1씩 늘어나기 때문에 배열에 index로 쓸 수 있습니다. 그 후 index에 따라 이동 가능여부를 조사해주면 됩니다. 올해 하반기 라인 코테 3번 문제와 아이디어가 비슷합니다. for test in range(1, int(input()) + 1): N = int(input()) dp = [0] * (N ** 2 + 1) for i in range(N): row = list(map(int, input().split())) for j in range(N): dp[row[j]] = (i, j) delta = ((0, 1), (1, 0), (0, -1), (-1, 0)) max_length, cnt, start, answer = 1, 1, 1, 1 for num in range(1, l..

순서대로 방문하는 문제같은 경우 플로이드 워셜을 많이 쓴다. 최초 1을 써놓고 플로이드 워셜을 통해 갈 수 있는 지점들을 하나하나 1로 바꾸어 주는 전략. import sys input = sys.stdin.readline n, k = map(int, input().split()) matrix = [[0] * n for __ in range(n)] for __ in range(k): a, b = map(lambda x : int(x) - 1, input().split()) matrix[a][b] = 1 for k in range(n): for i in range(n): for j in range(n): if matrix[i][k] and matrix[k][j]: matrix[i][j] = 1 for __..

기본적으로 문자열을 쌓거나 줄이는 방법은 dfs가 기본이다. 1번풀이 : 하나씩 쌓는 방법 left, right로 하나씩 쌓아가며 이어붙힌다. 다 붙히면 중복 없어지고 종료 import sys input = sys.stdin.readline def dfs(left, right, string): if len(string) == target: answers.add(string) return if left > 0: dfs(left - 1, right, string + N[left - 1:right + 1]) if right < n: dfs(left, right + 1, string + N[left: right + 2]) N = input().rstrip() n = len(N) target = n * (n + ..

아직 EOF 다루는게 익숙하지 않다. 예외처리에 대해 공부해야 할 듯. from collections import defaultdict while True: try: a=input() b=input() alpha1=defaultdict(int) alpha2=defaultdict(int) ans='' for s in a: alpha1[s]+=1 for s in b: alpha2[s]+=1 s = [] for char in alpha1: if char in alpha2: s.append(char) s.sort() for char in s: ans += char*min(alpha1[char],alpha2[char]) print(ans) except: break

배열돌리기 1에서 달라진것은 각 cycle마다 회전 횟수의 압축이 필요하다는 점. cycle크기는 하나 안으로 들어갈때마다 8칸씩 줄어들기때문에 각 사이즈로 나눈 나머지값만큼만 회전시켜준다. import sys input = sys.stdin.readline def rotate(start): #init_tmp top = matrix[start][start] left = matrix[N-start-1][start] bottom = matrix[N-start-1][M-start-1] right = matrix[start][M-start-1] # top for i in range(start+1,M-start): matrix[start][i-1] = matrix[start][i] # left for i in r..

말 그대로 귀찮은 문제. 하지만 많이 보던 파일 합치기의 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)

import sys input = sys.stdin.readline dp = [1,1,2,2,3,3] for i in range(6,100001): dp.append((dp[i-2]+dp[i-4]+dp[i-6])%1000000009) for _ in range(int(input())): n = int(input()) print(dp[n])

파이썬 입출력 속도 비교. 입력속도 1 PyPy int(sys.stdin.readline()) 0.9229 2 PyPy map(int,os.read(0, 100000000).split('\n')) 1.1169 3 PyPy3 map(int,os.read(0, 100000000).decode('utf-8').split('\n')) 1.5408 4 PyPy int(raw_input()) 1.925 5 Python 3 map(int,os.read(0, 100000000).decode('utf-8').split('\n')) 4.4033 6 Python 3 int(sys.stdin.readline()) 4.4394 7 PyPy3 int(sys.stdin.readline()) 6.6291 8 Python 3 int(..

트리dp.. 아직 잘 익지는 않는다. 좀 더 연습해야할듯. import sys input =sys.stdin.readline sys.setrecursionlimit(10**6) # dp[u]는 노드 u가 루트인 subtree에서 u부터 다른 모든 노드 까지 가는 모든 경로들의 곱의 합. # 즉 (dp[v] * c) 들의 합. 그 값을 리스트 p에 저장해뒀다가 모든 값들에 대해 (dp[u] - dp[v]*c)*(c*dp[v])들의 합을 구해준다. # 그 후 중복을 제거하기 위해 나누기 2를 해줘야 하나 MOD의 반인 500000004를 곱하고 MOD로 나눔으로써 2로 나누는 것과 같은 효과를 얻을 수 있다. def dfs(u): global ans visited[u] = True p = [] for i i..

Tree DP subtree에서 구한 해를 이용해 전체 트리의 해를 구하는 방식으로 진행이 됨. dp[i] = i를 루트로 하는 서브 트리의 ~같은 식으로 DP Table을 정의. dp는 보통 선형구조에서 이루어지지만 tree는 비선형 구조기 때문에 탐색 순서를 미리 정해주는게 일반적이다. / 그래프에서 우리가 dp를 사용하듯 트리도 dp를 사용하기 충분. 탐색 순서는 보통 dfs를 돌면서 나오는 트리인 dfs트리를 기준으로 한다. 트리 dp도 대부분 상태 dp가 들어간다. ex.) dp/[i]/[j] = i는 i를 루트로하는 subtree에서 i의 상태가 j일때. 보통 i번째 노드를 루트로 하는 서브트리에서 i번째 루트 노드를 포함했을 때와 포함 하지 않았을 떄 조건 중 최적값을 가져온다. 기본 구조 ..

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

장고 생활코딩 장고 템플릿 문법. {% extends "base_generic.html" %} {% block title %}{{ section.title }}{% endblock %} {% block content %} {{ section.title }} {% for story in story_list %} {{ story.headline|upper }} {{ story.tease|truncatewords:"100" }} {% endfor %} {% endblock %} {{}}두개는 변수. 뷰에서 탬플릿으로 context전달이 가능하다. 함수에서 html문서로 객체의 전달이 가능하다. sectin.title은 뷰에서section이라는 객체를 html문서로 보냈다는 뜻이고 그 안에 title속성을 전달..

자바 스크립트 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..

재귀 비교 import sys input = sys.stdin.readline def polling(n,start_x,start_y): half = n//2 if n==2: arr = [matrix[start_x][start_y], matrix[start_x+1][start_y], matrix[start_x][start_y+1], matrix[start_x+1][start_y+1]] arr.sort() return arr[-2] left_top = polling(half,start_x,start_y) right_top = polling(half,start_x+half,start_y) left_bottom = polling(half,start_x,start_y+half) right_bottom = poll..

첫 번째 장고 앱 작성하기, part 5 자동화된 테스트 작성. 자동화된 테스트 소개 자동화된 테스트란 무엇입니까? 테스트는 다양한 수준에서 작동합니다.(4수준) 유닛테스트 : 특정 모델 메서드는 예상대로 값을 반환합니까? E2E테스트 : 사이트에서 사용자 입력 시퀀스가 원하는 결과를 생성합니까? 테스트 자동화는 한 번 작성한 이후에 앱을 변경할 때 수동 테스트를 수행하지 않아도 원래 의도대로 코드가 동작하는지 확인 가능 테스트 자동화는 처음엔 어렵고 복잡할지 모르나 결국 수정과 에러를 적게하는건 테스트코드 과거엔 아키텍처 설계를 통해 시간과 비용을 절약했다면 이제는 테스트코드와 예외처리를 통해 그것이 이루어짐. 테스트를 통해 시간을 절약 특정 시점까지는 제대로 작동하는지 확인하는 테스트로 충분. 하지만..

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

문자열 덧셈. 매개변수로 주고 dfs import sys input = sys.stdin.readline def DFS(sum_num, answer): global cnt if sum_num > n: return if n == sum_num: cnt += 1 if cnt == k: print(answer[:-1]) exit() for i in (1, 2, 3): DFS(sum_num + i, answer+str(i)+'+') cnt = 0 n, k = map(int, input().split()) DFS(0, '') print(-1)

그래프 그리고 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)..

백트래킹을 걸 수 없는 탐색 ( target이 움직여서 중복방문을 막을 수 없을 시)시 사이클도는 구간을 찾아 사이클마다 각 지점에 대한 체크만 해주고 탐색은 더 진행하지 않는 방법을 사용. 중복 구간 탐색을 막고 사이클은 돌며 target이 오나 안오나 감시할 수 있다. import sys input = sys.stdin.readline from collections import deque def BFS(N,K): odd_even_visited = [[False]*500001 for _ in range(2)] queue = deque() queue.append([N,K,0,0]) cur_sister = K odd_even_visited[0][N] = True while queue: cur_node,cu..

LCA(lowest common ancestor)최소 공통 조상 모든 노드에 대한 깊이(depth)를 계산합니다. LCA를 찾을 두 노드를 확인합니다. depth가 동일하도록 거슬러 올라갑니다. 이후 부모가 같아질때까지 반복적으로 두 노드의 depth를 낮춥니다. 모든 LCA(a,b)연산에 대해 2번의 과정을 반복합니다. 느린 탐색 import sys sys.setrecursion(int(1e5)) # 각 노드의 depth를 찾아 기록하기 위한 dfs def find_depth(cur_node, depth): check[cur_node] = True depth[cur_node] = depth for next_node in graph[x]: if not check[next_node]: parent[next..

Tree 탐색등등 종종 나오는 경우의수를 따지는 DFS문제이다. idx 값을 1개 늘리냐 2개 늘리냐의 분기로 재귀를 실시. 실질적인 4방탐색이나 숨바꼭질 같은 문제와 다를게 없다. 재귀로 값을 누적시키며 달릴것이냐 큐나 스택을 이용할 것이냐의 차이. 선택의 문제. 경우의 수. 종료조건은 max값이 수열 길이와 같은 것. 왜 못풀었을까 생각해보자. import sys from collections import deque def DFS(idx): # idx 1부터 시작 kriii의 검사가 모두 끝나면 수열의 가장 큰 값을 찾는다. if idx == len(kriii): high = 0 for i in range(len(sequence)): high = max(high,int(sequence[i])) # 가..

최소 신장 트리(MST, 크루스칼, 프림 알고리즘) 최소 신장 트리(Minnimum Spanning Tree) spanning Tree 중에서 사용된 간선들의 가중치 합이 최소인 트리. 신장 트리(Spanning Tree)란 그래프 내의 모든 정점을 포함하는 트리 최소 연결 : 간선의 수가 가장 적다. n개의 정점을 가지는 그래프의 최소 간선의 수는 (n-1)개 이고, (n-1)개의 간선으로 연결 되어이으면 필연적으로 트리형태가 되고 이게 신장 트리이다. 즉 그래프에서 일부 간선을 선택해서 만든 트리. DFS, BFS을 이용하여 그래프에서 신장 트리를 찾을 수 있다. 탐색 도중에 사용된 간선만 모으면 만들 수 있다. 하나의 그래프에는 많은 신장 트리가 존재할 수 있다. Spanning Tree는 트리의 ..

처음엔 ord chr 쓰는줄 알았는데 도저히 그쪽으론 설계가 안돼서 노가다로 풂. 문제 함정은 testcase는 하나 띡 놓고 실상은 입력이 겁나 많이 들어간다는 것. 때문에 while로 무한 반복에 try except까지 써서 멈출 수 있게 해줘야 정답처리가 된다. moem = ['a','i','y','e','o','u'] zaem = ['b','k','x','z','n','h','d','c','w','g','p','v','j','q','t','s','r','l','m','f'] # 무한입력. try except while 1: try: S = input() ans = "" for i in range(len(S)): if S[i].lower() in moem: if S[i].isupper(): k = ..

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

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