포포's 코딩&일상 기록

오늘한거 알고리즘 특강 - DP 다이나믹 프로그래밍 -1 오늘 배운거 ★ DP 문제 풀이방법 : 외우기 !! 1. 문제정의 (= DP Table 정의) 정의한 배열이 뭔지 정확히 문장으로 설명할수 있어야함 => i 번째 원소로 어떤 값이 올지 적는것 !! 2. 초깃값 정의 (제일 작은 문제를 미리 풀어놓기) 답구하기 어렵지 않은건 미리 대답을 구해놓자 3. 점화식을 활용해서 문제 해결하기 점화식: 작은문제와 큰 문제 사이의 관계 예시 기억 하기 ★ DP 문제 풀이방법 : 외우기 !! 1. 문제정의 (= DP Table 정의) 2. 초깃값 정의 (제일 작은 문제를 미리 풀어놓기) 3. 점화식을 활용해서 문제 해결하기

No. 1 - 강의 듣고 풀이 - 문제 : BFS 탐색 / 네 방향 탈출 가능 여부 판별하기 https://www.codetree.ai/missions/2/problems/determine-escapableness-with-4-ways?utm_source=clipboard&utm_medium=text 코드트리 | 코딩테스트 준비를 위한 알고리즘 정석 국가대표가 만든 코딩 공부의 가이드북 코딩 왕초보부터 꿈의 직장 코테 합격까지, 국가대표가 엄선한 커리큘럼으로 준비해보세요. www.codetree.ai 코드 ㅇ 새롭게 알게된것 BFS 에서는.. 큐에 넣을때 방문처리해줘야함!!! 주의할점

탐색은 그래프와 시작점이 주어진다. 아웃풋 : 그점에서 간선을 타고 갈수있는 모든 위치 ... 이걸 찾고싶다 BFS = 너비우선탐색 B First Search 가까이 있는것들로부터 차근차근 퍼져나간다. 호수에 돌을 던지는 모습 (cf. 깊이우선탐색: 개미집) 큐 Queue 자료구조 활용하여 탐색 ( FIFO : 선입선출 ) (cf. 깊이우선탐색:재귀함수) *큐에 담긴 자료는 ... 여기를 갈수있다는걸 인지한 상태임을 의미함 새로운 점을 찾을때마다 계속 큐에 넣어준다. 큐에서 원소를 꺼내면 시작점에서 해당 정점까지 갈 수 있었다는 것을 알게된것임. 다시 해당 정점에 연결된 애들을 보면서 큐에 넣어주며 확장해서 탐색 BFS 기본코드 def bfs(): while q: #q 가 비어있지 않다면... 이라는 조..

No. 1 - 문제 : DFS / 그래프 탐색 https://www.codetree.ai/missions/2/problems/graph-traversal?utm_source=clipboard&utm_medium=text 코드트리 | 코딩테스트 준비를 위한 알고리즘 정석 국가대표가 만든 코딩 공부의 가이드북 코딩 왕초보부터 꿈의 직장 코테 합격까지, 국가대표가 엄선한 커리큘럼으로 준비해보세요. www.codetree.ai 코드 내가 짠 코드 1 .. count = 0 일때... -1 또 안해주도록 장치 해놔야했음... N,M = map(int,input().split()) # 그래프 생성 -> dfs 라서 인접리스트를 사용한다. graph=[[] for _ in range(N)] for _ in range..

그래프 탐색 그래프 + 시작점 주어진다. => 둘다 모두 주어져야함. 시작점에서 간선을 타고 갈수있는 모든 점을 탐색하는것 DFS = 깊이우선탐색 Depth First Search 특정 정점에서 시작하여 갈수있는 곳까지 계속 깊게깊게 들어간다음에 더이상 갈 곳이 없으면 다시 돌아와서 또다른 길을 찾아가는것 주로 재귀함수를 이용해서 구현 다음 정점으로 가는걸.. 그위치에서 재귀호출하는 형태로 .. ------ def dfs(vertex): -> vertex 는 현재위치를 의미함 현재위치에서 갈수있는 점들 보면서.. 더 갈수있으면.. 재귀함수 호출 연결된 점을 찾으면 그점으로 이동시키면됨 단, 이동의 의미는 탐색을 새롭게 확장한다는 의미 처음 만난거면 가는데 이미 가본거면 또 갈 필요 없음 => visite..

둘다 배우는이유 ? 장단점이 있기때문 왜 여러가지 자료를 배울까.. --학생들 대답 -- 인접리스트 특정 정점과 간선을 추가하는데 불리할까? => 링크드리스트로 구현할필요는 없음.. 1차원배열로 동적으로 생성가능 . 추가시 불리하지 않고, 맨앞에 추가할수있기때문에 시간복잡도도 동일함 간선이 많은경우.. 시간이 오랠걸릴 가능성이 있음 ? => 인접행렬도 비슷함.. --- 자료구조란 어떤 연산을 제공하는 자료를 담고있으면서 질문을 던질때마다 그질문에 대한 대답을 해주는 친구 던지는 질문 == 연산 여러개의 자료구조를 배우는이유 각 자료구조마다 똑같은 연산이어도 누구는 빠르게 하고 누구는 느리게 하기때문 정점의 개수 V (10만) , 간선의 개수 E (50만) 인접행렬 인접리스트 공간복잡도 가로세로 V² (1..

#그래프란 정점과 간선이 같이정의된것 순환이 있는트리 뿐만 아니라 순환이 없는트리 도 그래프다

#재귀로 완전탐색을 사용 하는 문제는 어떤문제인가? ( 백트래킹) 완전탐색해야하는데 입력에따라 내가 선택해야하는 개수나 조건이 달라질때 어떻게해야하는가 10개중 3개 이렇게 개수가 정해져있으면 반복문으로 가능하지만, 그개수가 안정해져있고 가변적일때의경우.. 재귀함수 사용하면 쉬워진다! 재귀함수를 이용해서 완전탐색을 하는방법: 백트래킹 # 백트래킹의 3가지 요소 1.종료조건 - 재귀호출은 한다는건 언젠가 멈춘다는건데... 언제멈출지를 정해주는게 중요하다. 2.현재상태 (파라미터 정하기) - 똑같은 함수가 호출 될건데.. 똑같은 함수가 호출되더라도... 다른 상태임을..표현해야하는데 그걸 파라미터로 표현함. 어떤 상태를 표현해야하는지 잘 정의하고 그거에 맞게 파라미터를 정의해야한다. 3. 재귀호출 조건 깊은..

No. 1 - 문제 :연결된 그래프 2 https://www.codetree.ai/problems/connected-graph-2?utm_source=clipboard&utm_medium=text 코드트리 | 코딩테스트 준비를 위한 알고리즘 정석 국가대표가 만든 코딩 공부의 가이드북 코딩 왕초보부터 꿈의 직장 코테 합격까지, 국가대표가 엄선한 커리큘럼으로 준비해보세요. www.codetree.ai 코드1 문제를 잘못이해함 .. 직접연결이 많은걸 찾는 코드를 짰는데.. 문제에서 요구하는 값은 간접연결된 값도 다포함이었음 n,m= map(int,input().split()) #그래프 graph ={i+1:[] for i in range(n)} #간선 세팅 for i in range(m): A,B= map(i..

No. 1 - 문제 :부분 문자열의 개수 https://www.codetree.ai/problems/number-of-substrings?utm_source=clipboard&utm_medium=text 코드트리 | 코딩테스트 준비를 위한 알고리즘 정석 국가대표가 만든 코딩 공부의 가이드북 코딩 왕초보부터 꿈의 직장 코테 합격까지, 국가대표가 엄선한 커리큘럼으로 준비해보세요. www.codetree.ai 코드 A =input() B= input() #항상 길이가 2 cnt = 0 #현재조건 #종료조건 #재귀호출식 작성 def func(idx): # 0 ~ (idx-1) 까지 값이 A에 순서대로 들어있음을 확인 # idx ~ n-1 까지 값이 A에 순서대로 들어있음을 확인해야한다. global aidx #..