[백준/9252] 음식물 피하기 | 배운 점이 많은 문제
·
PS/BOJ&Programmers
1743 음식물 피하기   알고리즘cnt 처리방식 구현이 쉽게 떠오르지 않았다.  def dfs(x,y) : cnt = 1 visited[x][y] = True for dx, dy in d : nx, ny = x+dx, y+dy # 여기가 연결되는 부분이니까 cnt += 1 처리를 해주고, if 0  이 문제에서 dfs 함수는 #를 발견하면 주변(d 좌표)을 탐색하면서 같은 영역에 속하는 곳의 크기가 얼마인지 세어주는 함수이다. 따라서 if문 조건은 주변 영역에서 계속 #이 이어지는 경우이므로, 이때 개수를 세어주어야 한다. 처음에 잘 생각이 안나서 cnt += 1 이런식으로 세어주고 return했는데 그러면.. 같은 ..
[백준/9251] LCS | 최장공통수열
·
PS/BOJ&Programmers
9251 LCSLCS 문제 해결 기법두 수열 중 하나를 비교대상으로 잡고 나머지 수열의 문자열을 하나씩 추가하면서 공통 수열 길이 값을 table에 표시해준다.문자열이 같으면 dp table에 저장을 하고, 다시 구하지 말자.dp table은 memoization 방식으로 이어나간다.알고리즘이 문제는 부분 수열 중 가장 긴 것을 찾는 것으로 그냥 숫자만 출력해주면 돼서 dp table에 같은 문자를 확인하면 +1 누적해주면 된다,,table 설명을 위해 i=6, j=4일 때를 예를 들어보자면일단 table은 이중 for문으로 j가 먼저 돌고있는 상황이다. 그러니까 'ACAYKP'라는 문자열에 대해서 'CAPCAK'를 상대적으로 놓고 하나씩 비교를 하고 있는 것이다. 가장 긴 공통 문자열의 길이를 묻는 거..
[백준/2178] 미로 탐색 | BFS와 최단 경로
·
PS/BOJ&Programmers
BFS와 최단 경로BFS는 최단거리와 관련있다. 왤까?BFS 알고리즘과 구현에 대해 이해하면, 이에 대한 해답을 얻을 수 있다. BFS 알고리즘을 이해하기 위해서는 먼저 bfs 알고리즘이 node를 방문하는 순서를 살펴봐야 한다.bfs는 위 그림과 같이 인접한 노드를 먼저 방문한다.그리고 방문한 순서대로 노드들을 Q에 넣고 시작점에서 인접한 Node를 모두 방문하면, Q 맨앞의 노드를 popleft한다. 이후 popleft된 노드들의 인접한 노드를 탐색하여 이 노드들도 똑같이 Q에 저장한다. 결론적으로 queue는 선입선출 방식으로 동작되기 때문에 방문 노드들이 순서대로 queue에 저장된다.흠.. 이렇게만 봐서는 왜 최단경로인지 모르겠다;; 예시를 보자.시작점 A에서 F까지의 최단경로를 알아본다고 했을..
[OS] CPU Scheduling | preemptive & non-preemptive | 스케줄링 알고리즘 | 스케줄러 알고리즘 평가
·
CS/OS
스케줄링 개념앞단원까지 cpu는 hw 자원의 효율적인 사용을 위해 context-switching을 통해 마치 concurrency(동시병렬)한 것처럼 hw 자원들을 사용한다고 배웠다. 이러한 context-switching을 관장하는 것이 CPU scheduling이다. 말 그대로 cpu의 스케쥴을 관리한다. [스케쥴링 전제]일단 스케쥴러의 판단 하에 있으려면, 프로세스들은 모두 메모리에 load가 되어있는 상태이어야 한다.multi programming 환경이어야 한다. batch programming은 schedule을 나눈다는 가정 자체가 성립 안되니 당연하다.[cpu schedular의 역할]스케줄러가 ready queue에서 작업을 선택해서 CPU burst하고 나머지는 I/O하면 효율적으로 ..
[BackEnd] API 명세서 작성 가이드 라인 | 작성 예시
·
Dev/Backend
프로젝트에서 API 명세서와 ERD 설계를 맡았다. API 명세서를 작성해본 적이 없어서 최대한 공식적인 자료를 바탕으로 찾아보다가 사막의 오아시스같은 글을 발견해서 정리하고 두고두고 보려고 한다. 이번 프로젝트에서 활용을 당연히 하겠지만 앞으로도 정말 큰 도움이 될 것같다..😍 API는 '서버와 클라이언트가 데이터를 주고 받을 수 있도록 도움을 주는 매개체'이다.API 명세서는 서버와 클라이언트간 특정 기술을 사용하기 위한 약속이다. API 문서화에 들어가야할 내용1) 개요기술 문서의 서론은 독자들에게 본문의 요약, 작성 배경, 관련 개념을 설명해준다. 즉, 독자들을 위한 '가이드'이다. API 문서에도 서론의 역할을 하는 개요(Overview)가 필요하다. API 소개단순히 API에 대한 기능 설명..
[알고리즘] Segment Tree
·
PS/Algorithm
1. 구간 l,r의 합 구하기(O(N)) 2. i 번째 수를 v로 바꾸기(O(1)) ⇒ 총 시간 복잡도는 O(NM) + O(M) = O(NM) segment tree를 써야 하는 이유 이때 구간합 알고리즘 사용해서 앞에서부터 차례대로 합을 구해놓는 방식으로 풀 수 있음. 여기서 2번 연산을 하려면 수가 바뀔 때 마다 prefix_sum 배열을 변경해줘야 한다. 가장 앞에 있는 0번째 수가 바뀐다면 모든 prefix_sum 배열을 변경해야 하기 때문에 시간 복잡도는 O(N) 따라서, M과 N이 매우 큰 경우에는 결국..! 시간 초과. 세그먼트 트리를 사용하면 O(N) → O(lg N), O(M) → O(lg N) 정의 리프 노드를 제외한 다른 모든 노드는 항상 2개의 자식을 가진다. ⇒ Full Binar..
[알고리즘] 헷갈려서 정리해보는 DP 🙀 | 재귀 - Memoization | for 배열 - Tabulation | Top-down & Bottom-up | 문제 유형
·
PS/Algorithm
피보나치 수와 파도반 수열 동적계획법 알고리즘 마인드를 떠올리기 힘들면 피보나치 수열, 파도반 수열을 떠올려 보자. 재귀함수와 dp의 관계: Memoization Top-down 재귀함수와 dp의 관계는 "비교 대상이자 구현법"이다. 따라서 dp의 특성을 파악하기 위해 먼저 재귀함수에 대한 이해가 필요하다. 재귀함수는 아래와 같은 그림을 기억해두면 이해하기 훨씬 수월하다! 한동안 재귀, 백트레킹 이해를 힘들어 하고 있었는데 재귀 작동 방식과 아래 그림을 연결해서 생각해보니 훨씬 이해가 잘됐다. 재귀 구현 코드는 다음과 같다. n = int(input()) def fibo(n) : if n memoization if m[n] != -1: return m[n] elif n 오 형태로) 바텀업 방식이다. dp..
[DB] RDMBS | ERD설계 시 주의할 점
·
DB
내가 맡기로한 챗봇 구현(Amazon Lex V2)이 기획 상에서 사라져서 급하게 ERD 설계와 API 명세 작성을 도맡았다. 2-3 주 간 Lex에만 매달렸고 이번 주에 Amazon에서 제공하는 챗봇 서비스를 학습&연동 시킬 기대감이 컸어서 너무 아쉬웠지만,, 아쉬운 마음이 큰 만큼 할 수 있는 것에 최선을 다하여 기여도를 높이기로 다짐했다..🥲 암튼 각설하고! 사실 이렇게 본격적으로 ERD를 처음 설계해봐서 공부할 게 매우 많았다. 이 포스팅을 통해 하나씩 정리해보려고 한다. Relational data model Relation in mathematics set은 서로 다른(중복 없는), 순서와 상관없는 요소를 가지는 collection이다. 두 개의 집합에 쌍(pair)를 설정해보자. 가능한 모든..
[OS] 운영체제가 하는 일4가지
·
CS/OS
https://cobinding.tistory.com/entry/OS-%EC%9A%B4%EC%98%81%EC%B2%B4%EC%A0%9C%EB%9E%80-%EB%AA%A9%EC%A0%81-%EC%99%9C%EB%B0%B0%EC%9B%80 [OS] 운영체제란 | 목적 | 왜배움? [운영체제란] 컴퓨터 하드웨어 바로 위에 설치되어, sw와 hw를 연결하는 sw 계층 좁은 의미 : 커널(운영체제의 핵심, 부팅 이후 항상 메모리에 상주) 넓은 의미 : 각종 시스템들 [운영체제의 목적] 1. cobinding.tistory.com OS는 컴퓨터 자원을 효율적으로 관리하고 user와 hw 간의 효용성을 위해 존재한다고 배웠었다. 그럼 os는 어떤 방식으로 일을 하며 이를 제공해주는지 알아보자. 크게 4가지가 있다. ..
[백준/14565] 역원(Inverse) 구하기 | 확장 유클리드 알고리즘 | 덧셈역,곱셈역
·
PS/BOJ&Programmers
확장 유클리드 알고리즘 유클리드 알고리즘에서는 나누는 값, 나머지로 r = 0일 때까지의 b값을 통해 최대공약수를 구했다. 확장 유클리드 알고리즘은 이를 활용하여 ax + by = gcd(a,b)가 존재하는 선형 방정식을 푸는 문제다. 지금까지 이런 식으로 유클리드 알고리즘을 통해 최대공약수를 구했다면 다음과 같이 x, y 값을 통해 gcd 값과 선형방정식의 정수해를 구할 수 있다. 이 문제에서 구하고자하는 곱셈역은 결국 (a*c) % n = 1을 찾는 문제인데, 물론 주어진 a와 n을 활용하여 1부터 n까지의 연산을 통해서 구할 수도 있다. 하지만 n의 범위는 10**12로 더 효율적인 방법인 확장 유클리드 알고리즘으로 해를 구하는 방법이 분명히 존재한다. 이 문제에서는 xgcd(11*x, 26)=1이..
[백준/13706] 제곱근 | 이진탐색
·
PS/BOJ&Programmers
https://www.acmicpc.net/problem/13706 13706번: 제곱근 첫째 줄에 양의 정수 N이 주어진다. 정수 N의 제곱근은 항상 정수이며, N의 길이는 800자리를 넘지 않는다. www.acmicpc.net Heron's method(헤론 방법) 제곱근을 근사하는 방법이다. 이 방법은 대략적인 제곱근 값을 계산하고, 이를 시작점으로 반복적인 계산을 통해 값을 얻어낸다. 주어진 숫자 x의 제곱근을 구하는 방법 x의 대략적인 제곱근 값을 구한다.(x/2) x를 x/2로 나눈다. x/2 + x(x/2): 이전 단계에서 구한 대략적인 제곱근 값과 그 역수의 합을 구한다. (x/2 + x(x/2)) / 2 : 이전 단계에서 구한 대략적인 제곱근 값과 그 역수의 평균값을 구한다. 이후 다시 ..
[DB] SQL vs NoSQL
·
DB
프로젝트 데이터베이스를 설계하는데 sql vs nosql에 대해 정확히 파악하고 결정해야겠다는 생각이 들어서 이번에 제대로 공부해보았다. 회원 정보가 있는 웹사이트는 table대로 관리를 해야하니까 대부분 sql을 사용한다고 생각했는데 꼭 그런 것만은 아니었다. 페이스북이나 인스타그램같은 소셜 미디어에서는 사용자 이용수가 대폭 증가할 확률이 높고, 간단한 데이터들이 저장되기에 nosql을 사용한다. sql을 사용하는 경우는 유저, 트랜젝션 등을 민감하게 관리해야 할 때이다. 자세히 알아보자. SQL vs NoSQL 2010-03: 빅데이터에 대한 관심이 쏟아지면서 rds로 해결할 수 없는 문제들이 나오기 시작함. 수평적 확장성(Horizontal Scalability)vs 수직적 확장성(Vertical ..
sebinChu
Studying IT with cobinding
상단으로

티스토리툴바