RUBY

출처:: https://www.acmicpc.net/problem/15683 분류:: BRUTEFORCE DFS 1. 문제 이해 및 해결과정 *문제이해 - 최대한 0을 적게 만들어야한다. = 사각지대 최소지대 - 1번 : 4가지 / 2번 : 2가지 / 3번: 4가지 / 4번: 4가지 / 5번 : 1가지 * 시간복잡도 : CCTV 의 최대 개수는 8개 4^8 * 64 (최대 블럭) => 약 400만 - 입력된 CCTV 방향의 조합을 DFS로 구현 하면서 사각지대의 최소개수를 찾음 -DFS() 종료조건 => cctv의 개수 반복문을 돌면서 1. map backup 2. map update 3. map 복원 *풀이방법 -CCTV개수 만큼 돌면서 -DFS에서 dir을 [4,2,4,4,1] 가지 수 만큼 돔 -u..

투포인터 : 리스트에 순차적으로 접근해야 할 때 2개의 점의 위치를 기록하면서 처리하는 알고리즘 - 2개의 변수를 이용해 리스트 상의 위치를 기록한다. - O(n) - case) 문제에서 연속된 데이터 구간을 처리할 때, 배열의 특정 연속된 구간을 처리할 때 * 특정한 합을 가지는 부분 연속 수열 찾기 - 시작점을 오른쪽으로 이동시키면 합이 감소하고, 끝점을 오른쪽으로 이동시키면 합 증가한다 - 음수데이터가 있으면 투포인터 불가하다 EX ) 1 2 3 2 5에서 부분합이 5가 된는 부분연속 수열의 개수 찾기 ( 1 2 3 2 5 / 1 2 3 2 5 / 1 2 3 2 5) 1. 시작점과 끝점이 첫번째 원소의 인덱시를 가리키도록 한다 2. 현재 부분합이 M과 같다면 카운트한다 3. 현재 부분합이 M보다 작..

출처:: programmers.co.kr/learn/courses/30/lessons/60060 분류:: 이분탐색 1. 문제 이해 및 해결과정 - bisect이용 1. words의 길이를 세서 길이 별로 배열을 따로 저장한다. 2. 접두사를 해결하기 위해 words를 뒤집은 배열을 저장한다 3. 정렬 4. count_by_range()함수를 이용해서 접미사에 ? 있으면 a부터 z까지의 범위 내의 개수를 찾는다 ex) fro?? 라면 froaa보다 크거나 같고 frozz보다 작거나 같은 단어의 개수를 센다 5. 접두사에 ? 인경우를 처리하기 위해 reversed를 이용한다 6. 개수 저장한다 2. 풀이방법 1. python 이분탐색 from bisect import bisect_left,bisect_rig..

출처:: 페이스북 인터뷰 분류:: 구현 1. 문제 이해 및 해결과정 2. 풀이방법 1. 구현 #문자열 재정렬 # import sys sys.stdin = open("input.txt","r") s=input() leng=len(s) alpha=[] sum=0 for i in range(leng): if ord('A')

출처:: 2020 카카오 신입 공채 1차 https://programmers.co.kr/learn/courses/30/lessons/60058 분류:: 구현 1. 문제 이해 및 해결과정 2. 풀이방법 1. 구현 #올바른 괄호 문자열인지 판단 def paren(w): cnt=0 for x in w: if x=='(': cnt+=1 else: if cnt==0: return False cnt-=1 return True #균형잡힌 괄호 문자열인지 def balanced_paren(p): leng=len(p) left=right=0 for i in range(leng): if p[i]=='(': left+=1 else: right+=1 if left==right: return i def solution(p): ..

출처:: https://www.acmicpc.net/problem/2636 분류:: BFS 1. 문제 이해 및 해결과정 1) 공기면 bfs하면서 큐에 넣기 2) 공기가 아니라면 공기에 닿은 것 더해주기 board[i][j]+=1 3) board[i][j]>=2 , 치즈가 공기에 1개이상 닿았다는 의미 이므로 녹임 2. 풀이방법 1. python #치즈 #https://www.acmicpc.net/problem/2636 import sys from collections import deque sys.stdin = open("input.txt","r") n,m=map(int,input().split()) board=[list(map(int,input().split())) for _ in range(n)] d..

출처:: https://www.acmicpc.net/problem/18353 분류:: LIS ,dp 1. 문제 이해 및 해결과정 2. 풀이방법 1. LIS 가장 긴 증가하는 부분수열 #병사 배치하기 #https://www.acmicpc.net/problem/18353 import sys sys.stdin = open("input.txt","r") n=int(input()) arr=list(map(int,input().split())) arr.reverse() dp=[1]*n #최소 한개의 길이는 가짐 for i in range(n): #arr[i]가 마지막항일때 for j in range(i): #i보다 작은 것들 중 if arr[j]

출처:: https://www.acmicpc.net/problem/17144 1. 문제 이해 및 해결과정 - 미세먼지가 있는 곳을 큐에 넣음, 큐에 있는 미세먼지만 처리하므로 답이 틀림 - 순서대로 확산 - 확산될때 임시배열을 만들어 두고 나중에 반영하기 - 1. 확산 2. 청정 1)미세먼지의 확장 과정 2) 공기 청정 2. 풀이방법 1. c++ #if 01 //미세먼지 안녕 //https://www.acmicpc.net/problem/17144 #include #define MAXN (50) using namespace std; int R, C, T; //세로, 가로, 시간 int map[2][MAXN + 5][MAXN + 5]; int up_h, up_w, down_h, down_w; int dh[]..