알고리즘/자료구조
백준 11660 구간합
import sys input = sys.stdin.readline n,m=map(int,input().split())#n=4,m-3 이면 4x4행렬/테케3개 입력한단 의미 arr=[] for i in range(n):#4x4 행렬 만들기 a=list(map(int,input().split())) arr.append(a)#ex.[[1, 2, 3, 4], [2, 3, 4, 5], [3, 4, 5, 6], [4, 5, 6, 7]] <- 테케1 4x4 배열 dp=[[0]*(n+1) for i in range(n+1)] #n=4이면 dp=[[0, 0, 0, 0, 0], [0, 0, 0, 0, 0], [0, 0, 0, 0, 0], [0, 0, 0, 0, 0], [0, 0, 0, 0, 0]] #[[0]*5 for i in range(5)]/[0]*5 = [0,0,0,0,0,] 이게 총 5개 만들어지는데 list안에 들어감 for i in range(1,n+1):#dp를 5x5로 선언해놓고 1행 1열은 안쓸거니까 애초에 인덱스 시작을 1부터 해주고 마지막값에도 +1 맞춰줌 for j in range(1,n+1): dp[i][j]=dp[i][j-1]+dp[i-1][j]-dp[i-1][j-1]+arr[i-1][j-1]#2차원배열 누적합 / 마지막 arr[i-1][j-1]은 arr을 4x4 배열로 받았고 dp에서는 5x5로 했으니까 좌표 위치 맞추려면 행,열 하나씩 줄여야함 for k in range(m):#테케 입력받기 x1,y1,x2,y2=map(int,input().split()) result=dp[x2][y2]-dp[x2][y1-1]-dp[x1-1][y2]+dp[x1-1][y1-1] # 특정 좌표에서 특정 좌표까지!! print(result)1) n,m = 4,3 이면 4x4짜리 행렬 + 테스트케이스 3개
2) n=4라고 하면 arr에 4x4 행렬 받아옴 (list 형태로)
3) 누적합 구할 dp 배열 5x5짜리 만듬 ([[0,0,0,0,0] ... [0,0,0,0,0]] <- 5개)
4) for문 2번 돌면서 1,1 부터 5,5까지 누적합 구해서 dp 에 넣음
cf) 4)에서 잘 이해가 안된게 dp를 굳이 5x5로 안하고 4x4로 맞춰서 하고싶었는데 index를 이해를 잘 못해서 그런가 테케 index 값에다가 -1 해줘서 index 맞춰보려고 했는데 안됐고 그냥 누적합 구하는 배열 dp는 5x5로 만들고 누적합 구하는 부분 마지막에 원래 data[i][j] 를 더해주는게 맞지만 data랑 dp 배열 index 맞추려면 data[i-1][j-1] 더해줘야했음 !!!
5) 테케 입력받는 좌표대로 결과 출력
4),5) 는 내가 이해한 내용 그림으로 첨부
4) 누적합
5) 좌표에서 좌표까지 누적합
단순 연결 리스트
class Node(): def __init__(self) : self.data=None self.link=None node1=Node() node1.data="다현" print(node1.data,end=' ') node2=Node() node2.data='정연' node1.link=node2 node3=Node() node3.data='쯔위' node2.link=node3 node4=Node() node4.data='사나' node3.link=node4 node5=Node() node5.data='지효' node4.link=node5 print(node1.data, end= ' ') print(node1.link.data, end= ' ') print(node1.link.link.data, end= ' ') print(node1.link.link.link.data, end= ' ') print(node1.link.link.link.link.data, end= ' ') -------------------출력----------------------- -------------------출력----------------------- 다현 정연 쯔위 사나 지효
- 연결리스트 출력 로직
current=node1 print(current.data,end='->') while current.link != None: current=current.link if current.link == None: print(current.data) else: print(current.data,end='->') -------------------출력----------------------- -------------------출력----------------------- 다현->정연->쯔위->사나->지효
- 중간에 노드 삽입
newNode=Node() newNode.data='재남' newNode.link=node2.link #node3의 위치값을 newNode.link로 준겨 node2.link=newNode -------------------출력----------------------- -------------------출력----------------------- 다현->정연->재남->쯔위->사나->지효
- 중간 데이터 삭제
node2.link=node3.link del(node3) -------------------출력----------------------- -------------------출력----------------------- 다현->정연->사나->지효
전역변수를 이용한 연결 리스트
class Node(): def __init__(self): self.data=None self.link=None def printNodes(start): current=start if current==None: return print(current.data,end=' ') while current.link!=None: current=current.link print(current.data,end=' ') print() memory=[] head,current,pre=None,None,None dataArray=['다현','정연','쯔위','사나','지효'] if __name__=="__main__": node=Node() node.data=dataArray[0] head=node memory.append(node) for data in dataArray[1:]: pre=node node=Node() node.data=data pre.link=node memory.append(node) printNodes(head) -------------------출력----------------------- -------------------출력----------------------- 다현 정연 쯔위 사나 지효--> node 라는 class가 가지고 있는 data 와 link 에 접근하여 data들을 연결시켜 단순 연결 리스트 구현
함수를 통한 노드 삽입
class Node(): def __init__(self): self.data=None self.link=None def printNodes(start): current=start if current==None: return print(current.data,end=' ') while current.link!=None: current=current.link print(current.data,end=' ') print() def insertNode(findData,insertData): global memory,head,current,pre if head.data==findData: node=Node() node.data=insertData node.link=head head=node return current = head while current.link!=None: pre=current current=current.link if current.data==findData: node=Node() node.data=insertData node.link=current pre.link=node return node = Node() node.data=insertData current.link=node #전역변수 선언 memory=[] head,current,pre=None,None,None dataArray=['다현','정연','쯔위','사나','지효'] if __name__=='__main__': node=Node() node.data=dataArray[0] #다현 head=node memory.append(node) #memory에다가 node 추가 for data in dataArray[1:]: # 두번째 노드 이후부터 끝까지 가면서 pre=node node=Node() node.data=data pre.link=node memory.append(node) printNodes(head) insertNode('다현','화사') printNodes(head) insertNode('사나','솔라') printNodes(head) insertNode('재남','문별') printNodes(head) -------------------출력----------------------- -------------------출력----------------------- 다현 정연 쯔위 사나 지효 화사 다현 정연 쯔위 사나 지효 화사 다현 정연 쯔위 솔라 사나 지효 화사 다현 정연 쯔위 솔라 사나 지효 문별
함수를 통한 노드 삭제
class Node(): def __init__(self): self.data=None self.link=None def printNodes(start): current=start if current==None: return print(current.data,end=' ') while current.link!=None: current=current.link print(current.data,end=' ') print() def insertNode(findData,insertData): global memory,head,current,pre if head.data==findData: node=Node() node.data=insertData node.link=head head=node return current = head while current.link!=None: pre=current current=current.link if current.data==findData: node=Node() node.data=insertData node.link=current pre.link=node return node = Node() node.data=insertData current.link=node #전역변수 선언 memory=[] head,current,pre=None,None,None dataArray=['다현','정연','쯔위','사나','지효'] def deleteNode(deleteData): global memory,head,current,pre if head.data==deleteData: current=head head=head.link del(current) return current=head while current.link!=None: pre=current current=current.link if current.data==deleteData: pre.link=current.link del(current) return if __name__=='__main__': node=Node() node.data=dataArray[0] #다현 head=node memory.append(node) #memory에다가 node 추가 for data in dataArray[1:]: # 두번째 노드 이후부터 끝까지 가면서 pre=node node=Node() node.data=data pre.link=node memory.append(node) printNodes(head) insertNode('다현','화사') #다현 찾아서 화사 삽입 -> '다현','화사'로 들어감 printNodes(head) insertNode('사나','솔라') printNodes(head) insertNode('재남','문별') printNodes(head) deleteNode('다현') printNodes(head) deleteNode('쯔위') printNodes(head) deleteNode('지효') printNodes(head) deleteNode('재남') printNodes(head) -------------------출력----------------------- -------------------출력----------------------- 다현 정연 쯔위 사나 지효 화사 다현 정연 쯔위 사나 지효 화사 다현 정연 쯔위 솔라 사나 지효 화사 다현 정연 쯔위 솔라 사나 지효 문별 화사 정연 쯔위 솔라 사나 지효 문별 화사 정연 솔라 사나 지효 문별 화사 정연 솔라 사나 문별 화사 정연 솔라 사나 문별--> 디버깅 하면서 천천히 보는거 아니면 수업이랑 동시에 들으면서 이해 어려움
--> 들으면서 이해한다고 해도 그냥 받아쓰기 수준이라 3시간짜리 휘발성 기억
--> 그냥 오른쪽에 띄워놓고 줄줄 받아적는 수준인데 매우 비효율적
--> 중간중간 백준 풀어야겠음
Stack
stack = [None for _ in range(5)] top=-1 #초기값 바닥 top+=1 stack[top]='커피' top+=1 stack[top]='녹차' top+=1 stack[top]='꿀물' for i in range(len(stack)-1,-1,-1):#마지막 index ~ 초기값(-1) 을 거꾸로 print(stack[i]) print('----------pop----------') data=stack[top] #data에 stack에 마지막에 들어간 값 stack[top]=None #stack[top] 비워주고 top-=1 #top 하나 줄여줌 print(f'pop -> {data}') data=stack[top] #data에 stack에 마지막에 들어간 값 stack[top]=None #stack[top] 비워주고 top-=1 #top 하나 줄여줌 print(f'pop -> {data}') data=stack[top] #data에 stack에 마지막에 들어간 값 stack[top]=None #stack[top] 비워주고 top-=1 #top 하나 줄여줌 print(f'pop -> {data}') print('---------stack---------') for i in range(len(stack)-1,-1,-1): print(stack[i]) -------------------출력----------------------- -------------------출력----------------------- None None 꿀물 녹차 커피 ----------pop---------- pop -> 꿀물 pop -> 녹차 pop -> 커피 ---------stack--------- None None None None None
Stack 전체 구현
# 스택 전체 구현 SIZE = 0 stack =[] top = -1 # 스택이 꽉 찼는지 여부 확인 def isStackFull(): global SIZE, stack, top if( top >= SIZE-1): return True else: return False def isStackEmpty(): # 스택 비어있는지 여부확인 global SIZE, stack, top if( top == -1): return True else: return False # 스택에 데이터 추가 def push(data): global SIZE, stack, top if (isStackFull()): print('Stack is Full') return else: top +=1 stack[top] = data # 스택에서 데이터 추출 def pop(): global SIZE, stack, top if (isStackEmpty()): print('Stack is empty!') return None else: data = stack[top] stack[top] = None top -= 1 return data # top이 데이터 확인 def peek(): global SIZE, stack, top if isStackEmpty(): print('Stack is empty!') return None else: return stack[top] # 메인 엔트리 if __name__ == '__main__': SIZE = int(input('스택 사이즈 입력 >> ')) stack = [None for _ in range(SIZE)] top = -1 while True: select = input('삽입(I)/추출(E)/확인(V)/종료(X) >> ') if select.lower() == 'x': # 종료 break elif select.lower() == 'i': # 삽입 data = input('추가할 데이터 >> ') push(data) print(f'스택상태 : {stack}') elif select.lower() == 'e': # 추출 data = pop() print(f'추출 데이터 : {data}') print(f'스택상태 : {stack}') elif select.lower() == 'v': # 확인 data = peek() print(f'확인 데이터 : {data}') print(f'스택상태 : {stack}') else: continue print('스택 프로그램 종료') -------------------출력----------------------- -------------------출력----------------------- 스택 사이즈 입력 >> 3 삽입(I)/추출(E)/확인(V)/종료(X) >> i 추가할 데이터 >> 커피 스택상태 : ['커피', None, None] 삽입(I)/추출(E)/확인(V)/종료(X) >> i 추가할 데이터 >> 녹차 스택상태 : ['커피', '녹차', None] 삽입(I)/추출(E)/확인(V)/종료(X) >> i 추가할 데이터 >> 아이스티 스택상태 : ['커피', '녹차', '아이스티'] 삽입(I)/추출(E)/확인(V)/종료(X) >> v 확인 데이터 : 아이스티 스택상태 : ['커피', '녹차', '아이스티'] 삽입(I)/추출(E)/확인(V)/종료(X) >> e 추출 데이터 : 아이스티 스택상태 : ['커피', '녹차', None] 삽입(I)/추출(E)/확인(V)/종료(X) >> e 추출 데이터 : 녹차 스택상태 : ['커피', None, None] 삽입(I)/추출(E)/확인(V)/종료(X) >> e 추출 데이터 : 커피 스택상태 : [None, None, None] 삽입(I)/추출(E)/확인(V)/종료(X) >> x 스택 프로그램 종료
스택 응용
#위 소스에서 메인 엔트리부분 전부 주석처리 후 다른 파일 생성하여 import 함. import DataStructure03_Stack as st import webbrowser import time st.SIZE=100 st.stack=[None for _ in range(st.SIZE)] st.top=-1 if __name__=='__main__': urls=['www.naver.com','www.daum.net','www.google.co.kr','www.naver.com'] for url in urls: st.push(url) webbrowser.open(f'https://{url}') print(url,end='-->') time.sleep(1) print('방문 종료') time.sleep(5) while True: url=st.pop() if url==None: break webbrowser.open(f'https://{url}') print(url,end='-->') time.sleep(1) print('방문 종료') -------------------출력----------------------- -------------------출력----------------------- www.naver.com-->www.daum.net-->www.google.co.kr-->www.naver.com-->방문 종료 www.naver.com-->www.google.co.kr-->www.daum.net-->www.naver.com-->Stack is empty! 방문 종료
백준 2884번 알람시계
hour,minute=map(int,input().split()) if minute>=45:#45분이 넘으면 그냥 해당 분에서 45빼면 됨 print(hour,minute-45) elif minute<45 and hour>0: print(hour-1,minute+60-45)#ex. 10시 30분에서 45분빼면 hour-1,minute+60-45로 9시 45분 else: print(23,minute+60-45)1) 45분 넘으면 그냥 빼고
2) 10시 30분에서 45분빼면 hour-1,minute+60-45으로 9시 45분
3) 나머지 : 자정 시간대에서 45분 줄이는거니까 hour은 23이고 minute는 2)와 동일
백준 2525번 오븐 시계
h,m=map(int,input().split()) oven=int(input()) h+=oven//60 m+=oven%60 if m>=60: h+=1 m-=60 if h>=24: h-=24 print(h, m)1) oven 즉, 오븐에 돌리는 시간이 ex) 80분 -> 1시간 20분이기에 h+=oven//60 , m+=oven%60
2) oven에 돌리고 분이 60분이 넘으면 ex)70분 -> 1시간 10분이기에 h+=1 m-=60 으로 처리
3) oven에 돌리고 시간이 24시간이 넘게되면 ex)25시 --> -=24로 1시로 바꿔줌
백준 2480번 주사위 세개
x,y,z=map(int,input().split()) price=0 if x==y==z: price=10000+x*1000 elif x==y: price=1000+x*100 elif x==z: price=1000+x*100 elif y==z: price=1000+y*100 else: price=max(x,y,z)*100 print(price)
