one Book a Day

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

dp 누적으로 최소값 구해줬습니다. import sys input = sys.stdin.readline N, M = map(int, input().split()) matrix = [list(map(int, input().split())) for _ in range(N)] dp = [[[0,0,0] for _ in range(M)]] + [[[float('inf'),float('inf'),float('inf')] for _ in range(M)] for _ in range(N)] for i in range(1,N+1): for j in range(M): if j < M-1: dp[i][j][0] = min(dp[i-1][j+1][1],dp[i-1][j+1][2]) + matrix[i-1][j] if 0 <..

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

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

문자열 덧셈. 매개변수로 주고 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)

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

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

냅색문제고 dp로 풀었습니다. import sys input = sys.stdin.readline for _ in range(3): N = int(input()) coins = {} target = 0 for _ in range(N): a, b = map(int, input().split()) coins[a] = b target += a*b if target&1: print(0) continue target //= 2 dp = [1] + [0] * (target) for coin in coins: for money in range(target,coin-1,-1): if dp[money-coin]: for j in range(coins[coin]): if money + coin*j

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])

이 블로그는 개인 공부정리용 블로그지만 선배 기수분들에게 받은 유용한 정보들을 다음 기수들에게 물려주고자 합격후기를 작성합니다. 최초 전공인 산업공학에서 생산관리직무를 준비하다가 웹개발에 관심을 갖게 되었고 독학은 4개월정도 진행했습니다. Essay 1번문항에서 SW개발경험을 토대로 한 지원동기 2번문항에서 어떤 구직활동을 왜 어떻게 해왔고 어떤것을 얻었는지를 정리하시면 됩니다. 저는 1번문항 2번문항 둘다 2개의 소문단으로 작성했는데 3개월짜리 스마트제조 국비교육을 들은 내용으로 반을 채웠고 나머지는 혼자 독학을 한 내용과 과정, 어떻게 독학을 통해 성장해왔는지를 어필했습니다. (스마트제조의 어플리케이션단 개발, 사용자중심의 웹서비스개발에 대한 관심도를 드러냈습니다.) 개인적으로 SW개발에 대한 관심도..

사이의 중간값 or 양끝까지의 값 중 가장 큰 값. import sys input = sys.stdin.readline N = int(input()) M = int(input()) arr = list(map(int, input().split())) max_size = 0 for i in range(1,M): max_size = max(max_size, arr[i] - arr[i-1]) print(max((max_size+1)//2,arr[0] - 0, N - arr[-1]))

박스 순회하며 누적합. 자주나오는 유형이다. 중요한건 누적합은 뒤에서부터 쌓아줘야 중복이 안생긴다는것. 때문에 H부터 1까지 순회해주며 더해줬다. import sys input = sys.stdin.readline N, M, H = map(int, input().split()) boxes = [list(map(int, input().split())) for _ in range(N) ] dp = [0]*(H+1) for box in boxes: for idx in range(H,0,-1): if not dp[idx]: continue for num in box: if idx + num > H: continue dp[idx+num] += dp[idx] for num in box: dp[num] += 1 pr..

union find의 변형. 특이한 점은 합칠때 부모가 아닌 해당 노드끼리 합치고 대신 해당 노드를 타고 올라가며 length를 갱신해줘야 된다는 점이다. 내 길이 = 부모의 길이들의 합. import sys input = sys.stdin.readline def find(x): if parent[x]==x: return x # 부모쪽 length모두 갱신 tmp = find(parent[x]) # 내 length 갱신 length[x] += length[parent[x]] # 부모값 저장 parent[x] = tmp # 반환. return tmp def union(a,b): length[a] = abs(a-b) % 1000 parent[a] = b for test in range(1,int(input(..

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

단순히 영역을 나누는 문제였습니다. 대각선에 대해 4번 범위 설정이 필요한 문제였습니다. 핵심은 1개씩 늘어나거나 줄어드는 dx, dy설정을 어떻게 할 것인가? 결국 i에서 i의 초깃값을 빼주면 0부터 시작한 다는 것을 알 수 있었습니다. import sys input = sys.stdin.readline N = int(input()) matrix = [list(map(int, input().split())) for _ in range(N)] answer = float('inf') total = 0 for i in range(N): for j in range(N): total += matrix[i][j] for x in range(N - 1): for y in range(1, N - 1): for d1 ..

로직이 완전 깔끔하지는 못하지만 시간 내에 통과하도록 최소한의 연산을 하도록 노력함. 기본적으로 재귀를 통해 폭탄을 한발씩 떨어뜨리는 함수, 폭탄이 블록과 만나면 연쇄 폭발을 일으키는 재귀함수 폭발 후 빈칸에 블록을 중력을 적용해 채우는 함수. 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, ..

조합을 dfs로 짜고, 조합에 속한 요소와 속하지 못한 요소간 차이를 비교. 삼성기출 스타트와 링크. 웰노운 def choose_parts(cur_node, cnt): global min_gap if cnt == N // 2: S1, S2 = 0, 0 for i in range(N - 1): for j in range(i + 1, N): if check[i] and check[j]: S1 += S[i][j] + S[j][i] elif not check[i] and not check[j]: S2 += S[i][j] + S[j][i] min_gap = min(min_gap, abs(S1 - S2)) for next_node in range(cur_node, N): if not check[next_node]:..

카카오톡 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..

https://www.acmicpc.net/problem/2058 2058번: 원자의 에너지 잘 알려져 있듯, 각각의 원자들은 어떤 특정한 에너지 상태(혹은 에너지 준위)에 놓일 수 있다. 각각의 상태는 그 상태에서 그 원자가 갖는 에너지로 나타낼 수 있다. 어떤 원자가 높은 에너지 상 www.acmicpc.net tree_DP기본문제다.. 근데 안풀린다.. 다른문제로 연습하고 다시 도전할 것. 문제를 이해 못한건지 그냥 안풀린다.// 풀었음 정렬해서 한쪽 끝에서만 더하면 될 줄 알았는데 반례가 많은 것같다. 모든 시작지점에서 부터 돌렸다. 다시풀었는데 그냥 양성자를 빼는 경우만 고려해주면 시작점에서만 시작하면 되더라. 시간 500 -> 140 -> 120 까지 줄이고 종료. +gap만 조사 import..

CPU Scheduling 스케줄링 실행준비가 된 프로세스 중에서 하나를 선택해 CPU를 할당 하는 것. 결국 CPU를 잘 사용하기 위해 프로세스를 잘 배정하기 위함. 조건 : 오버헤드는 낮고, 사용률은 높고, 기아 현상은 낮을때. 목표 Batch System : 가능하면 많은 일을 수행한다. 시간(time)보다 처리량(throughout)이 중요하다. Interactive System : 빠른 응답 시간, 적은 대기 시간 Real-time System : 기한(deadline) 맞추기 선점 / 비선점 스케줄링 선점(preemptive) : OS가 CPU의 사용권을 선점 할 수 있는 경우, 강제 회수하는 경우 비선점(nonpreemptive) : 프로세스 종료 or I/O 등의 이벤트가 있을 때까지 실행..

라인스위핑 스위핑 알고리즘이란? 특정 선이나 공간을 한쪽에서부터 쓸어버리는 식의 알고리즘. 일정 좌표, 축기준 정렬 한 뒤 일정 시점의 좌우 가장 가까운 두 점사이의 거리보다 멀리떨어진 점은 조사하지 않는 방식. 가지치기를 하겠다는 이야기다.(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 heapq import heappush, heappop N = int(input()) buses = [] for _ in range(N): arrive, leave = input().split() a = int(''.join((''.join(arrive.split(':'))).split('.'))) b = int(''.join((''.join(leave.split(':'))).split('.'))) buses.append([a,b]) buses.sort() heap = [] heappush(heap,buses[0][..

얘는 늘 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..

기존 마나커 탐색에 1. 중심이 #이 아닐때(크기1짜리 펠린드롬) 2. 반지름 갱신시 #을 뺀 반지름의 크기만큼 펠린드롬수 추가 3. 범위 확장 시 확장된 범위가 #범위가 아니면 펠린드롬 추가 import sys input = sys.stdin.readline def manacher(string): n = len(string) a = [0] * n # i번째 문자를 중심으로 하는 가장 긴 팰린드롬 반지름 크기. c = 0 # 중심점(center) 초기화 r = 0 # 시작점에서 가장 먼 반경(펠린드롬 끝나는 인덱스중 가장 큰 값.) answer = 0 for now in range(n): if string[now] != '#': answer +=1 # i번째 문자가 now 아래쪽에 있는 문자를 중심으로 ..

배열 회전 알고리즘. 노가다 회전 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를 이용해..

마지막 비교때 parent[v]==parent[u]로 썼다가 한참 틀렸다. 부모는 한칸위고 find가 루트를 찾는거라 find비교를 했어야했는데 두개의 차이에 대해 고민을 안해봤던 것 같아서 이런 문제가 생겼던 것같다. 오늘 확실히 알고간다. import sys input = sys.stdin.readline def union(a,b): #집합이 다를경우 합침 a=find(a) b=find(b) if a

1.잔디 옵션이 프라이빗으로 바뀌어있는지 확인한다. => public으로 바꾼다. 2. 깃헙에 등록되어있는 메일이 바뀌어서 local git의 메일주소와 불일치 하게 되었는지 확인한다. => 깃 메일을 일치시키던가 깃헙에서 삭제한 메일을 다시 등록한다. 3. 특정레포의 강제푸시 혹은 merge로 commit기록이 전부 초기화 됐다!! 이러면 정말 눈물나지만 해결 방법이 있다. github api를 이용해 과거로 회귀하는것. 1. Access Token을 발급받는다. https://github.com/settings/tokens 에 가서 토큰 생성을 누르고 repo전체 선택 후 발급 받는다. 2. 강제 푸시 전 혹은 레포가 정상일 적 마지막 커밋 SHA값을 확인한다. curl -H "Authorizatio..

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

git add . git add 시 warning: LF will be replaced by CRLF in 파일명 에러가 뜰 수 있다. 이는 OS마다 줄바꿈을 바라보는 문자열이 다르기 때문에 Git 이 볼때 어떤 방식을 선택할지 몰라 경고를 내린 것 LF : Mac, Linux(Unix) 줄바꿈 문자열 = \n : 다음 줄 같은위치 CR : Mac 초기 줄바꿈 문자열 = \r : 같은 줄 맨앞 CRLF : Window, DOX 줄바꿈 문자열 = \r\n : 다음줄 맨앞 해결방법은 autoarlf를 사용해 바꿔주면 된다. 윈도우 즉 LF -> CRLF는 git config --global core.autocrlf true Linux, Mac 즉 CRLF -> LF는 git config --global co..

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

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)

기본적인 투포인터 문제. 합에 따라 크기를 증감시키며 슬라이딩 시켰습니다. import sys input = sys.stdin.readline N, M = map(int, input().split()) arr = list(map(int, input().split())) left, tmp, cnt = 0, 0, 0 for right in range(N): tmp += arr[right] while tmp > M: tmp -= arr[left] left += 1 if tmp == M: cnt += 1 print(cnt)

플로이드 워셜 기본문제 각 기점에 대해 모든 경로를 전수조사한다. 한번당 기점 하나를 거치는 경로이다. import sys input = sys.stdin.readline n, m = int(input()), int(input()) bus_datas = [[float('inf')] * n for _ in range(n)] for _ in range(m): a, b, c = map(int, input().split()) bus_datas[a - 1][b - 1] = min(bus_datas[a - 1][b - 1], c) for k in range(n): bus_datas[k][k] = 0 for i in range(n): for j in range(n): if bus_datas[i][j] > bus_da..

그리디하게 맨 뒷 자리가 짝수면 2로 나누고 1이면 1빼면 된다. import sys input = sys.stdin.readline A, B = map(int, input().split()) cnt = 1 while A != B: if A > B or (B % 10 != 1 and B % 2 != 0): cnt = -1 break if B & 1: B //= 10 cnt += 1 else: B //= 2 cnt += 1 print(cnt)

Hash 데이터를 효율적으로 관리하기 위해, 임의의 길이 데이터를 고정된 길이의 데이터로 매핑하는 것. 해시함수를 구현하여 데이터값을 해시값으로 매핑시킨다. 내부적으로 array를 사용해 데이터를 저장. 데이터 고유의 인덱스로 key의 고유 숫자 값이 저장됨. 특정 데이터만의 고유한 위치이기 때문에 삽입 연산 시 다른 데이터 사이에 끼어들어나 삭제시 다른 데이터로 채울 필요가 없음. 즉 추가적인 비용이 없도록 만들어진 구조. Hash Table 해시 테이블은 로 데이터를 저장하는 자료 구조 중 하나이다. Key값에 해시 함수를 적용해 index를 생성하고, index를 활용하여 값을 저장, 검색 할 수 있다. Key값을 해싱하여 검색, 저장하므로 평균 시간 복잡도는 O(1)이다. (항상 O(1)이 아닌 ..

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는 외부를 눌렀을때만 인지함. 키보드 ..

파이썬의 int, bin 메서드를 사용해 풀이 import sys input = sys.stdin.readline for test in range(int(input())): a, b = map(lambda x: int(x, 2), input().split()) print(bin(a + b)[2:])

기본적인 union-find로 무리짓고 대푯값의 갯수를 세는 문제입니다. 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, M = map(int, input().split()) parents = {i: i for i in range(1, N + 1)} for i in range(M): a, b = map(int, input().split()) if find(a) != find(b):..

HTTP 통신을 위한 코드를 미리 준비하라고 하여 기출문제를 풀며 작성한 통신 코드를 그대로 들고갔습니다. 저는 주언어가 python이라 그대로 들고갔는데 c++ 나 java를 쓰시는 분들은 python으로 전향하시느라 고생 많이 하시더군요.. 덕분에 자료구조를 남들보다 원활히 다룰 수 있는 위치에서 유리하게 시작할 수 있었던 것 같습니다. 1. CS 20분간 문제를 풉니다. 간단한 지식임이 분명하나.. 예년의 난이도에 비해 많이 어려웠고 비전공자 입장에서 특히 저처럼 취업준비 github 수준의 깊이, 정보처리기사 수준의 지식을 가지고 풀기에는 보기 1, 2개가 모르는게 나와서 좀 까다로웠습니다. 확실히 전공자들은 중간고사, 기말고사에 나올만한 유형의 문제들이라 무난히 풀었다는 의견도 많았습니다. 덕분..

이번 하반기 SW 직군으로 구직하기 시작하고 세 번째로 본 코딩 테스트 였습니다. (토스, 당일 오전 라인 등 서류가 필요없는 코딩 테스트만 응시) 5시간 동안 7문제가 주어지는데요. 시중의 코딩 테스트 중에는 가장 어렵다는 소문에 많이 긴장했었으나 올해의 난이도는 예년에 비해 많이 낮았습니다. 기출문제들에 비해 구현력을 많이 요구하지 않고 단순한 방법론으로 풀리는 문제들로 구성이 되었습니다. 1번. 신고 횟수가 일정이상 되는 유저를 배제시키고 신고한 유저에게메일을 보내주는 문제로 dictionary에 id에 따른 신고 횟수와 신고한 user를 저장시켜뒀다가 후에 반환시켜주면 됩니다. 백준에 set-map 자료구조로 분류되는 문제로 실버 3~4 정도의 난이도로 느껴졌습니다. 2번. 진법변환을 하고 문자열..

일단 n을 무조건 수가 적은쪽으로 통일 시킨 후 dp로 각각 짝을 지어줬을 시 차이가 min인 값을 누적시킵니다. 앞인자는 수가 적은쪽의 인자고 뒤 인자는 수가 많은쪽의 인자입니다. m - (n - 1)은 수가 큰거에서 작은 것을 빼고 1을 더해준 값으로 선택할 수 있는 m쪽 인자의 index 범위를 뜻합니다. import sys input = sys.stdin.readline n, m = map(int, input().split()) boys = list(map(int, input().split())) girls = list(map(int, input().split())) if n > m: boys, girls = girls, boys n, m = m, n dp = [[0] * m for __ in r..

최대 정사각형 만들기 or 직사각형 만들기와 동일한 로직. W가 나오면 초기화, 나오지 않으면 최소거리 갱신하며 dp 양방향으로 한번씩 하고 그 중 최솟값으로 갱신. import sys sys.stdin = open('input.txt') for test in range(1, int(input()) + 1): N, M = map(int, input().split()) pool = [list(input()) for _ in range(N)] dp = [[float('inf')] * M for _ in range(N)] answer = 0 for i in range(N): for j in range(M): if pool[i][j] == 'W': dp[i][j] = 0 continue if j: dp[i][j..

파서의 종류 상향식 : 구문의 낮은수준에서 높은 수준으로 일치하는 부분을 찾음. 항, 항연산자, 표현식, 표현식 연산자 순으로 일치하는 표현식을 하나씩 스택에 쌓음 =이동-감소 파서 : 입력값의 오른쪽으로 포인터가 이동하기때문에 구문 규칙에 남는 것이 점차 감소. ex.) 2+3-1 -> +3-1 -> 3-1 -> -1, 1, 하향식 : 상위 구조로부터 일치하는 부분을 찾음. 표현식부터 쌓음 파서 자동 생성 : 수동파서 최적화는 어렵기때문에 웹킷은 어휘생성을 위한 플렉스와 파서 생성을 위한 바이슨을 사용한다. 플렉스는 토큰의 정규표현식 정의를 포함하는 파일을 입력 받고 바이슨은 BNF 형식의 언어 구문 규칙을 입력 받는다. HTML 파서 마크업을 파싱 트리로 변환 문법은 W3C에 명세로 정의 전통적 파서..

https://www.acmicpc.net/problem/2026 2026번: 소풍 만약 K명의 친구 관계인 학생들이 존재하지 않는다면 -1을 출력한다. 그 외의 경우에는, K개의 줄에 학생들의 번호를 증가하는 순서로 한 줄에 한 개씩 출력한다. 여러 경우가 존재한다면 첫 번째 www.acmicpc.net K명 모두가 친구여야 통과하는 dfs를 짜주면 된다. import sys input = sys.stdin.readline def dfs(v,arr): if len(arr)==K: for num in arr: print(num) exit() for i in range(v+1,N+1): if not visited[i]: for num in arr: if num not in graph[i]: break el..

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번째 루트 노드를 포함했을 때와 포함 하지 않았을 떄 조건 중 최적값을 가져온다. 기본 구조 ..

오일러 경로. 한붓그리기는 홀수인 경로가 2개(출발지, 도착지)거나 없어야함. dfs로도 풀수있다함. 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 V, E = map(int, input().split()) graph = {i: [] for i in range(1,V+1)} parent = {i:..

처음과 끝을 찾고 그 사이를 같은 간격으로 조사하는 방법. import sys input = sys.stdin.readline def check(string): l = len(string) for start_idx in range(l): if string[start_idx] == name[0]: for end_idx in range(start_idx,l): if string[end_idx]==name[-1]: avg_gap = (end_idx-start_idx)//(n-1) cnt = 0 while cnt < n: if string[start_idx+avg_gap*cnt]==name[cnt]: cnt += 1 continue break else: return 1 return 0 N = int(input(..

처음에 lca인가 봤더니 그냥 BFS. 이진트리라면 lca써야했을지도. import sys input = sys.stdin.readline from collections import deque def bfs(start,target): visited = {i: 0 for i in range(n+1)} visited[start] = 1 q = deque() q.append(start) while q: cur_node = q.popleft() if cur_node==target: return visited[cur_node] -1 for next_node in graph[cur_node]: if not visited[next_node]: visited[next_node] = visited[cur_node] + ..

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

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