RUBY

출처:: https://www.acmicpc.net/problem/18406 분류:: 구현 1. 문제 이해 및 해결과정 2. 풀이방법 1. for문이용 #럭키 스트레이트 # import sys sys.stdin = open("input.txt","r") li=list(map(int,input())) leng=len(li) li.insert(0,0) point = leng//2 a=0 b=0 for i in range(1,leng+1): if i

*구현의 유형 - 완전탐색: 모든 경우의 수를 빠짐없이 다 계산하는 해결 방법 - 반복문, 재귀함수 적절히 사용하며 예외케이스 모두 확인 - DFS/BFS 알고리즘 이용 - 시뮬레이션 : 문제에서 제시하는 논리나 동작 과정을 그대로 코드로 옮기는 것 *순열과 조합 - 순열 : 서로 다른 n개 에서 r개를 선택하여 일렬로 나열하는 것 nPr = n!/(n-r)! import itertools data=[1,2] for x in itertools.permutations(data,2): print(list(x)) #[1,2] #[2,1] - 조합 : 서로 다른 n개에서 순서에 상관없이 서로 다른 r개를 선택하는 것 nCr import itertools data = [1,2,3] for x in itertool..

출처:: 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..