✅문제 - 괄호의 값(2504번) ✅사용 개념 및 알고리즘◼ 자료구조 : 위의 문제는 괄호를 닫아줄 때 가장 마지막에 넣은 값과 현재 괄호를 비교해야하기 때문에 Stack 자료구조를 사용해야한다. ◼ 알고리즘1) 값을 임시로 저장할 변수 tmp를 1로 설정한다.2) [ or ( 을 만나면 tmp에 2 또는 3을 곱해준다.3) 괄호를 닫을 때 적합성 판단을 한다. 만약 스택이 비어있거나 stack[-1]과 현재 괄호가 매칭되지 않으면 answer = 0 으로 만들고 break 한다.4) 앞의 괄호가 여는 괄호일 경우 answer 에 현재 tmp를 더해준다.5) 괄호를 닫았으므로 tmp 값을 2 or 3으로 나누어준다. ❓ 위의 4) 과정에서 왜 앞에 여는 기호가 있을 때만 값을 더해줄까?!만약 앞에 기호..
✅문제 - 동전1 (2293번) ✅필요 알고리즘 개념 - DP🔵DP의 적용◼ 모든 동전의 가격을 고려하며 dp를 만들면 경우의 수가 복잡하므로 동전의 종류를 1개씩 늘려간다.◼ 처음에는 가장 저렴한 동전 1개만 사용하여 dp를 만든다. (예제 입력의 경우 가치가 1인 동전을 사용한다.)동전의 가치가 1인 경우 DP는 위의 표와 같다. 위의 표는 동전의 가치가 1인 동전만을 사용해 k원을 만든 것이다.◼ 동전의 가치가 2인 경우를 dp에 추가하자현재 dp[n]은 n원을 1원짜리 동전으로 만들 때의 경우의 수이다.2원 짜리 동전을 사용하게 되면 (1) 1원짜리 동전으로만 경우의 수를 만든 경우와 (2) 2원짜리 동전도 사용한 경우의 수가 있다.위의 (1)의 경우의 수가 dp[n] 이고 (2)의 경우는 d..
✅문제 - 내리막 길 (1520번) ✅필요 알고리즘 개념 - DP/DFS🔵 DFS 와 BFS 중 무엇을 쓸 것인가◼ 이 문제는 경로 찾기 문제와 유사하므로 DFS와 BFS 중 하나를 써야 하는데 왜 DFS를 사용할까?이 문제의 경우 경로가 겹칠 때 다른 경로에게 영향을 주기 때문에 먼저 DFS로 한 경로를 끝까지 탐색하는 것이 유리하다. 🔵 DP 사용 법 ◼ 2차원 리스트에 (x,y)에서 (row,col) 까지 가는 경우의 수를 저장한다. DFS를 진행하던 도중 이미 들렀던 지점인 경우에는 바로 dp 값을 사용한다. ✅코드 설명import sysrow,col = map(int,sys.stdin.readline().rstrip().split())board = [] delta = [(1,0),(-1,0)..
✅문제 - 이분 그래프 (1707번) ✅필요 알고리즘 개념 - BFS🔵 BFS 활용 방법◼ 이 문제는 연결된 두 Node를 다른 색으로 색칠하는 것이 가능한지 물어보는 문제이다. 예를 들어 아래 처럼 인접한 두 노드를 서로 다른 색으로 칠할 수 있다면 이분 그래프로 나눌 수 있는 그래프이다. 하지만 아래의 경우 Node 5번을 보면 빨간 Node와 파란 Node와 모두 연결돼 있기 때문에 인접한 Node와 다른 색으로 칠할 수 없다. 그러므로 이분 그래프가 아니다.이 아이디어를 활용하여 BFS를 구현하면 이분 그래프를 확인할 수 있다.✅코드 설명 - BFS 구현 부분def bfs(graphs,visited): queue = deque() # graphs 는 edge를 입력 받은 list이다 ..
✅문제 - 파일 합치기 (11066번) ✅필요 알고리즘 개념 - DP🔵특정 경로를 지나는 DP◼ 예제 입력 40 30 30 50의 경우위의 경우에 3가지 케이스가 존재할 수 있다.1) (1) + (2 + 3 + 4)2) (1+2) + (3+4)3) (1+2+3) + (4) 즉 중간 경로로 k를 선택해 지나가는 것이다. 그러므로 dp를 1차원 배열이 아닌 2차원 배열로 만들어 준다.dp[start][end] = min(dp[start][mid] + dp[mid+1][end]) + cost[start][end]를 만족하는 dp를 만든다. ✅필요 알고리즘 개념 - Knuth optimizationdp[start][end] = min(dp[start][mid] + dp[mid+1][end]) + cost[st..
✅문제 - K번째 수 (1300번) ✅필요 알고리즘 개념 / 풀이 알고리즘🔵이분탐색◼ 소주병 뚜껑의 숫자 맞추기 처럼 Up Down 식으로 원하는 값을 찾아 가는 것이다.◼ 정렬된 리스트에서만 사용이 가능하다. 🔵아이디어 - 이분탐색의 적용◼ 숫자가 N^2개 존재하므로 1~N^2 번째 숫자까지 존재한다.◼ k번째를 찾는 것이 아니라 1~N^2까지의 숫자를 선택해 해당 숫자보다 작은 숫자가 k개인 숫자를 찾는다. 🔵아이디어 - 특정 숫자보다 작은 숫자의 탐색◼ 입력 받은 2차원 배열은 구구단의 성질을 띈다. ◼ 이 성질을 이용하면 구구단 i단 에서 k보다 작은 숫자의 갯수는 k//i가 된다.◼ 이 성질을 이용하여 1~N을 탐색하며 k보다 작은 숫자의 갯수를 센다. ✅코드import sysinput =..
