본문 바로가기

Algorithm

 (10)
[백준] 알고리즘 기초 1/2 200 - 자료구조 1 1) 1406번 에디터 2개의 stack을 활용하여 cursor의 위치 나타내고, append(), pop()만을 사용하여 시간 복잡도 줄이기 import sys input=sys.stdin.readline from collections import deque x=list(input().rstrip()) # stack1 n=int(input()) stack=deque([]) # stack2 cursor=len(x) # stack1 x의 개수 for _ in range(n): say=input().rstrip() if say[0]=='L': if cursor==0: continue stack.appendleft(x.pop()) cursor-=1 elif say[0]=='D': # x..
[이것이 취업을 위한 코딩테스트다] 10. 그래프 이론 * 개선된 서로소 집합 알고리즘 소스 코드* import sys input=sys.stdin.readline # 특정 원소가 속한 집합을 찾기 def find_parent(parent,x): if parent[x]!=x: parent[x] = find_parent(parent,parent[x]) return parent[x] # 두 원소가 속한 집합을 합치기 def union_parent(parent,a,b): a=find_parent(parent,a) b=find_parent(parent,b) if a
[이것이 취업을 위한 코딩테스트다] 09. 최단 경로 * 개선된 다익스트라 알고리즘* 한 지점에서 다른 특정 지점까지의 최단 경로를 구하는 경우 사용. '최단 거리가 가장 짧은 노드'를 선택하는 과정을 다익스트라 최단 경로 함수 안에서 우선순위 큐를 이용하는 방식 사용. import sys input=sys.stdin.readline import heapq # 우선순위 큐 INF=int(1e9) # 무한을 의미하는 값 n,m=map(int,input().split()) # 노드의 개수, 간선의 개수 입력 start=int(input()) # 시작 노드 입력 graph=[[] for i in range(n+1)] # 각 노드에 연결되어 있는 노드에 대한 정보 담는 리스트 distance=[INF]*(n+1) # 최단 거리 테이블을 무한으로 초기화 # 간선 정..
[이것이 취업을 위한 코딩테스트다] 08. 다이나믹 프로그래밍 01. 1로 만들기 import sys input=sys.stdin.readline x=int(input()) arr=[0]*30001 for i in range(2,x+1): arr[i]=arr[i-1]+1 if i%2==0: arr[i]=min(arr[i-1],arr[i//2])+1 if i%3==0: arr[i]=min(arr[i-1],arr[i//3])+1 if i%5==0: arr[i]=min(arr[i-1],arr[i//5])+1 print(arr[x]) 02. 개미 전사 import sys input=sys.stdin.readline n=int(input()) food=list(map(int,input().split())) d=[0]*100 d[0]=food[0] d[1]=max(food[0..
[이것이 취업을 위한 코딩테스트다] 07. 이진 탐색 01. 부품 찾기 import sys input=sys.stdin.readline def binary_search(arr,target,start,end): while starttarget: end=mid-1 else: start=mid+1 return None n=int(input()) arr1=list(map(int,input().split())) arr1.sort() # 이진 탐색을 위한 정렬 수행 m=int(input()) arr2=list(map(int,input().split())) for val in arr2: result=binary_search(arr1,val,0,n-1) if result!=None: print('yes',end=" ") else: print('no',end=" ") 02..
[이것이 취업을 위한 코딩테스트다] 06. 정렬 01. 위에서 아래로 import sys input=sys.stdin.readline n=int(input()) arr=[] for _ in range(n): arr.append(int(input())) arr.sort(reverse=True) print(*arr) 02. 성적이 낮은 순서로 학생 출력하기 * sorted와 key* key = abs -> 절댓값을 기준으로 정렬 key = len -> 문자열을 길이를 기준으로 정렬 key = lambda x : (len, x)) -> 문자열의 길이를 기준으로 정렬하되, 길이가 동일하면 사전 순으로 정렬 import sys input=sys.stdin.readline n=int(input()) arr=[] for _ in range(n): name,grad..
[이것이 취업을 위한 코딩테스트다] 05. DFS|BFS 1. 음료수 얼려 먹기(DFS) import sys input=sys.stdin.readline n,m=map(int,input().split()) ice=[list(map(int,list(input().rstrip()))) for _ in range(n)] def dfs(x,y): if x=m: return if ice[x][y]==0: ice[x][y]=1 dfs(x-1,y) dfs(x+1,y) dfs(x,y-1) dfs(x,y+1) return True return False count=0 for i in range(n): for j in range(m): if dfs(i,j)==True: count+=1 print(count) 2. 미로 탈출(BFS) import sys input=sys.stdi..
[이것이 취업을 위한 코딩테스트다] 04. 구현 01. 상하좌우 import sys input=sys.stdin.readline n=int(input()) plans=list(input().rstrip().split()) x,y=1,1 move_types=['L','R','U','D'] dx=[0,0,-1,1] dy=[-1,1,0,0] for plan in plans: for i in range(len(move_types)): if plan==move_types[i]: nx=x+dx[i] ny=y+dy[i] if nxn or nyn: continue x=nx y=ny print(x,y) 02. 시각 import sys input=sys.stdin.readline n=int(input()) cnt=0 for i in range(0,n+1): for j ..
[이것이 취업을 위한 코딩테스트다] 03. 그리디 04. 1이 될 때까지 import sys input=sys.stdin.readline n,k=map(int,input().split()) cnt=0 while n!=1: if n%k==0: n=n//k cnt+=1 else: n-=1 cnt+=1 print(cnt)
[Python] 파이썬 문법 정리 1) import sys input=sys.stdin.readline 2) 예외처리 : try, except 3) sys.stdin.readline은 EOF error(더 이상 입력 문자열이 없음.) 발생 시 빈 문자열 return -> 일반적인 input() 사용해야함. 4) reversed는 reversed 객체를 return -> str로 바꿔주는 작업 필요(join 활용.) 5) import math 6) from collections import deque 7) 소수점 둘째자리까지 출력 : '{:.2f}'.format(변수)

티스토리툴바