one Book a Day

Trie 역방향, 정방향검색, 길이별 검색. class Node: def __init__(self): self.child = {} self.count = 0 class Trie: def __init__(self): self.root = Node() def insert(self,word): node = self.root for char in word: if char not in node.child: node.child[char] = Node() node.count += 1 node = node.child[char] def startswitch(self,prefix): node = self.root for char in prefix: if char=='?': return node.count if char n..

보자마자 price(1~count) 가 생각나서 제출. 했으나 제출 누르자마자 음수인 경우 예외처리 안해줬다는 생각이 나서 결과보니 아니나다를까 testcase 하나 오답.. 음수처리 해주었더니 통과 def solution(price, money, count): answer = price * count * (count + 1) // 2 - money if answer < 0: answer = 0 return answer

내풀이. deque하면 pop안에 인덱스가 안들어 간다는걸 몰랐다. 그래서 결국 그냥 큐로 바꿈. def solution(cacheSize, cities): cache = [] total_cost = 0 for city in cities: lo_city = city.lower() if lo_city not in cache: cache.append(lo_city) total_cost += 5 if len(cache) > cacheSize: cache.pop(0) else: cache.append(cache.pop(cache.index(lo_city))) total_cost += 1 return total_cost 남의 코드 볼 것 :maxlen으로 크기제한, remove로 바로 없애기. # 남의 풀이 de..

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

최대길이 회문 확인. 사실 while문보다 for문, slicing이 더 빠르다. import sys inmput = sys.stdin.readline def check(a,left,right): while left < right: if a[left] != a[right]: return 0 left += 1 right -= 1 return 1 s = input().rstrip() n = len(s) # 최대 길이가 회문 아니면 n if not check(s,0,n-1): print(n) # 최대길이에서 하나뺀게 회문 아니면 n-1 elif not check(s,0,n-2): print(n-1) else: print(-1)

결국 반복문으로 x나y를 증가시켜 일정 배수를 만드는게 목표이다. 변수가 나오면 항등식을 잘 세울 것. ==만 생각하는게 아니라 %로 일정 배수 만드는 경우도 유의할 것. def num(m, n, x, y): while x

프로그래밍 문제를 분석해 문제를 해결하는 방법과 과정. (Problem Solving) 조직화하는 것을 '설계'라 함. 구조적 프로그래밍에서의 분할기준은 프로시저(절차, 함수). 절차지향과 차이점은 캡슐화, 다형성, 상속 지원, 데이터 접근 제한을 걸 수 있는지 여부. 효율적으로 하기 위한 방법론 중 하나가 객체지향. 알고리즘은 수학적인 풀이. 하지만 이로 모든 문제를 해결 할 수 없음. 객체지향은 어떤 문제를 잘게 나눠서 각각의 능동적인 주체로 만들기 위함. 잘게 나눈 객체들을 조합해 큰 문제를 해결하는 Bottom-Up 지향 큰 문제를 10개로 나눠 할당하고 각 주체가 자기가 맡은 책임에 대해 해결을 위해 '자율적'으로 노력하고 '협업'하기 위한 패러다임. 즉 객체지향에서 우리가 배워야 할 것은 '협..

튜플을 이용해 union-find로 그룹핑했습니다 import sys input = sys.stdin.readline from collections import defaultdict def find(a): if parents[a] == a: return a parents[a] = find(parents[a]) return parents[a] def union(a, b): a = find(a) b = find(b) if a > b: a, b = b, a parents[b] = a N = int(input()) matrix = [list(map(int, list(input().rstrip()))) for _ in range(N)] delta = ((0, 1), (1, 0), (-1, 0), (0, -1)) ..

dfs로 백트래킹하며 최솟값을 갱신해주는 로직입니다. 높이가 '이상' 임이 명확히 주어져있어서 수월했습니다. def dfs(u, total): global min_val if total >= B: min_val = min(min_val, total) for v in range(u + 1, N): if not visited[v] and total + s[v] < min_val: visited[v] = True dfs(v, total + s[v]) visited[v] = False for test in range(1, int(input()) + 1): N, B = map(int, input().split()) s = list(map(int, input().split())) visited = [False] *..

브라우저는 어떻게 동작하는가? 1편 파싱과 돔트리 구축 브라우저의 주요기능은 사용자가 선택한 자원을 서버에 요청하고 브라우저에 표시하는 것. 자원은 보통 HTML. 자원의 주소는 URI(Uniform Resource Identifier)에 의해 결정됨. 브라우저는 웹 표준화 기구가 정한 HTML과 CSS 명세에 따라 HTML파일을 해석해서 표시한다. 브라우저의 UI요소 URI 주소 표시 줄 이전, 다음 버튼 북마크 새로고침, 현재문서 로드를 중단하는 정지버튼 홈 버튼 브라우저의 기본 구조 UI : 주소 표시줄, 이전/다음버튼.. 등등 요청한 페이지를 보여주는 창을 제외한 나머지 모든 부분 브라우저 엔진 : UI와 렌더링 엔진사이 동작을 control 렌더링 엔진 : 요청한 컨텐츠를 표시. 보통 HTML요..

페이징과 세그먼테이션 기법을 쓰는 이유 다중 프로그래밍 시스템에 여러 프로세스를 수용하기 위해 주기억장치를 동적 분할하는 메모리 관리 작업이 필요해서 메모리 관리 배경 각각 프로세스 는 독립된 메모리 공간을 갖고, 운영체제 혹은 다른 프로세스의 메모리 공간에 접근할 수 없는 제한있음. 운영체제 만이 운영체제 메모리 영역과 사용자 메모리 영역의 접근에 제약을 받지 않음. Swapping : 메모리의 관리를 위해 사용되는 기법. 표준 Swapping 방식으로는 round-robin 과 같은 스케줄링의 다중 프로그래밍 환경에서 CPU 할당 시간이 끝난 프로세스의 메모리를 보조 기억장치(e.g. 하드디스크)로 내보내고 다른 프로세스의 메모리를 불러 들일 수 있다. 이 과정을 swap이라함. 주 기억장치(RAM)..

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

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

첫번째 장고 앱 작성하기, part 7 관리자 폼 커스터마이징 수정 폼의 필드를 재정렬해 작동하는 법을 본다. admin.site.register(Question) 를 아래와 같이 수정한다. from django.contrib import admin from .models import Question class QuestionAdmin(admin.ModelAdmin): fields = ['pub_date', 'question_text'] admin.site.register(Question, QuestionAdmin) 모델의 관리자 옵션을 변경해야 할 때마다 모델 어드민 클래스를 만든 다음, admin.site.register()에 두 번째 인수로 전달한다. 수십 개의 필드가 있는 폼에 관해서는 폼을 fi..

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

문자열 매칭 연습하기위해 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..

LCA 기본 형에 dists배열만 만들어주어 루트노드에서 각 정점까지의 거리를 저장해준 구조이다. dfs를 이용해 각 노드 본인의 depth를 기록함과 동시에 top-down으로 거리도 dp_dists에 기록한다. (여기까지의 거리 = 부모노드까지의 거리 + cost값이다.) 그럼 dists와 depth는 끝. sparse table을 통해 각 노드에서 2의 0승,1승,2승 위의 부모노드 번호에 대해 수집한다. LCA함수를 통해 2의 n승 단위로 부모를 빠르게 타고 올라가며 공통조상의 위치를 찾는다. 공통조상만 알면 거리 배열의 연산을 통해 각 정점 간 거리를 구할 수 있다. # 정점들 사이의 최단거리는 dist[a] - dist[lca] + dist[b] - dist[lca] # LCA를 지나는 거리가..

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

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

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

희봉, 티거, 알리님의 10분 테코톡 유튜브 영상 보고 작성했습니다. Web? -인터넷을 기반으로 한, 정보를 공유, 검색할 수 있게 하는 서비스 -URL(주소), HTTP(통신규칙), HTML(문서) 3가지 요소를 가짐. Client -웹 브라우저. Server -클라이언트에게 네트워크를 통해 정보나 서비스를 제공하는 컴퓨터 시스템 Web Server -인터넷을 기반으로 클라이언트의 요청에 따라 웹 서비스(HTML등 각종 리소스)를 제공하는 컴퓨터 => Client는 웹 서버에게 URL을 가지고 HTTP에 맞게 요청(특정 path로 특정 파일을 요청)하면 HTML을 응답 받음. => Web server는 클라이언트의 요청을 기다리고 웹 요청(HTTP)에 대한 데이터를 만들어서 응답. 이때 데이터는 웹에..

img{ -webkit-filter: opacity(.5) drop-shadow(0 0 0 gray); filter: opacity(.5) drop-shadow(0 0 0 gray); } 그림에 필터씌우는 코드. gray는 색상코드로 변경가능. opacity는 필터 두께 filter는 흐림이나 색상변형 등 이미지, 배경, 테두리 렌더링. drop-shadow(offset-x offset-y blur-radius color) filter 속성 /* SVG 필터를 가리키는 URL */ filter: url("filters.svg#filter-id"); /* 값 */ filter: blur(5px); filter: brightness(0.4); filter: contrast(200%); filter: drop..

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

협업을 진행하다보면 conflct가 당연히 발생합니다. PR을 밀어 넣었을 때 기존 코드와 내 코드가 비교되는 과정에서 다른 코드가 원본에 Merge되면 비교과정이 올바르지 않게 되기 때문에 conflict가 발생하는데 이는 3-way-merge 방법 또는 rebase를 이용해 해결이 가능하다. 3-way-merge : base + 내 branch + upstrem의 최신버전 rebase : 내 branch + rebase 한 내용 rebase는 말 그대로 re + base로 내가 머지하려는 브랜치가 갈라져 나온 branch의 base를 바꾸겠다는 것이다. 이 과정을 통해 내 코드는 새로이 만들어진 base와 코드 대사과정을 하게되므로 Merge하는데 문제가 없게된다. 원리는 내 branch가 지속적으로..

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

Symbol 뒤에 HTML Number를 붙혀주면 특수문자를 입력할 수 있다. Symbol HTML Number HTML Name Description ! ! exclamation point " " "\; double quotes # # number sign $ $ dollar sign % % percent sign & & &\; ampersand ' ' single quote ( ( opening parenthesis ) ) closing parenthesis * * asterisk + + plus sign , , comma - - minus sign - hyphen . . period / / slash : : colon ; ; semicolon > > greater than sig..

Regular Expression 컴퓨터 과학의 정규 언어로 부터 유래 특정한 규칙을 가진 문자열의 집합을 표현, 형식언어 정해진 형식을 사용자가 제대로 입력했는지 검증 즉 입력값이 형식에 맞는지 검증할 때 자주 사용함. java.util.regex 패키지 안의 Pattern Class와 Matcher Class 사용 문법 ^ 문자열 시작 $ 문자열 종료 . 임의의 한 문자(단 \은 넣을 수 없음). (SQL Like에서 _) * 앞 문자가 없을 수도 무한정 많을 수도 있음 (SQL Like에서 %) + 앞 문자가 하나 이상 ? 앞 문자가 없거나 하나 있음 [ ] 문자의 집합이나 범위를 나타내며 두 문자 사이는 - 기호로 범위를 나타냅니다. [] 내에서 ^ 가 선행하여 존재하면 not을 나타냄 { } 횟..

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