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

투포인터 : 리스트에 순차적으로 접근해야 할 때 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/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/14501 분류:: dp, dfs 1. 문제 이해 및 해결과정 - 뒤쪽부터 풀어 해결하는 DP - 뒤쪽부터 상담에 대해서 현재 상담 일자의 이익(p[i]) + 현재 상담을 마친 일자부터의 최대이익 dp[t[i]+i]] 을 계산하면됨 - dp[i] : i번째 날부터 마지막 날까지 낼 수 있는 최대 이익 - dp[i] = max(dp[i] + dp[t[i]+i]],maxv) - maxv: 현재까지의 최대 상담금액 2. 풀이방법 1. DP #퇴사 #https://www.acmicpc.net/problem/14501 import sys sys.stdin = open("input.txt","r") n=int(input()) t=[] #각 상담을 완..