99클럽

하고싶은 거 다하며 살자
Algorithm TIL (240909)
·TIL
> [백준] 괄호의 값https://www.acmicpc.net/problem/2504🔥다시 보기🔥 문제 풀이 과정스택 활용괄호로 이루어진 문자열이 주어질 때, 각 괄호에 따라 괄호값을 구해야 한다. ()의 쌍일 때는 값이 2, []의 쌍일 때는 값이 3이라는 간단한 규칙같으나, (x)로 해당 괄호쌍 안에 또다른 괄호값이 있을 경우 값이 2x이 된다. 이는 괄호가 (()) 괄호값이 곱해지는 형태, ()[] 괄호값이 더해지는 형태 2가지로 연산이 나뉘게 된다. 문제에서 주어진 '(()[[]])([])' 문자열은 크게 두가지로 나눌 수 있다. (()[[]]) 과 ([]) 이다. (()[[]]) 는 2 x (2 + 3 * 3) 이고,  ([]) 는 2 * 3 이다. 쟁점은 저 괄호를 어떻게 구현해야 하는가..
99클럽 TIL (240830)
·TIL
> [Middler] Unique Pathshttps://leetcode.com/problems/unique-paths/ 문제 풀이 과정DP(동적 계획법)목표 : 로봇이 피니쉬 지점에 도달하는 모든 경로의 수 (로봇의 움직임은 아래,오른쪽만 가능)접근 방법dp[i][j] 는 (i,j) 좌표에 도달할 수 있는 경로의 수. 로봇은 아래와 오른쪽으로만 이동할 수 있으므로 i,j 지점은 (i-1,j) 혹은 (i,j-1)지점으로 부터만 도달할 수 있다. 그래서 아래와 같은 식이 나온다.dp[i][j] = dp[i-1][j] + dp[i][j-1]  문제 풀이pythonclass Solution: def uniquePaths(self, m: int, n: int) -> int: # 목표 : 로봇이..
99클럽 TIL (240828)
·TIL
> [Middler] https://school.programmers.co.kr/learn/courses/30/lessons/142085  문제 해결pythonimport heapqdef solution(n, k, enemy): skill = [0] * k # 무적권 for i in range(len(enemy)) : if enemy[i] > skill[0] : mn = heapq.heappop(skill) heapq.heappush(skill, enemy[i]) n -= mn else : n -= enemy[i] if n
99클럽 TIL (240827)
·TIL
> [Middler] 부등호https://www.acmicpc.net/problem/2529 🔥 다시 풀기 🔥  문제 풀이 과정이러한 문제 유형을 어려워 한다. 처음 생각은 0부터 10 숫자를 돌면서 이전 숫자와 비교했을 때, 부등호가 맞다면 큐에 계속 적재하고 아니면 맞을때까지 큐를 팝한다는 생각을 했으나 지속되는 index range error로... 풀지 못함. 검색해보니 백트래킹 + 완탐으로 문제를 해결한 것을 알게되어 코드를 참조했다. 완벽히 이해가 가지 않아 백트래킹을 다시 공부했다. ✨ 백트래킹현재 상태에서 가능한 모든 후보군에 따라 들어가며 탐색하는 알고리즘. 주로 재귀의 형태로 코드를 구현, 기본 틀을 두는 편이 좋다. 문제 풀이pythoncheck(왼쪽 숫자, 오른쪽 숫자, 부등호)..
99클럽 TIL (240826)
·TIL
> [Middler] 전력망을 둘로 나누기https://school.programmers.co.kr/learn/courses/30/lessons/86971 문제 풀이 과정전력망을 두개로 나누기 위해 일단 간선을 하나하나 제외한 모든 송전탑의 차이를 구하고 최솟값을 리턴하는 식으로 생각했다... n이 커지면 이게 가능할까 싶은 생각이 들지만 우선 구현해보았다. ✨ 알아야하는 것!abs('절댓값으로 만들 숫자') : 매개변수에 넣은 숫자에 대한 절댓값을 반환 문제 풀이python dfs 로 완전탐색def solution(n, wires): def dfs(start, graph) : v = [False for _ in range(n+1)] stack = [] stac..
99클럽 TIL (240825)
·TIL
> [Middler] 게임 맵 최단거리https://school.programmers.co.kr/learn/courses/30/lessons/1844?language=python3# 문제 풀이 과정캐릭터는 1,1 좌표에서 시작하고 상대팀 진영은 맨 우측 하단에 위치해있다. 최단거리를 구하면 되기 때문에 BFS를 사용했다. 문제 풀이from collections import dequedef solution(maps): dist = [[0] * len(maps[0]) for _ in range(len(maps))] d = [(0,-1),(0,1),(-1,0),(1,0)] dist[0][0] = 1 q = deque() q.append((0,0)) while q ..
99클럽 TIL (240823)
·TIL
> [Middler] 리코쳇 로봇https://school.programmers.co.kr/learn/courses/30/lessons/169199 문제 풀이 과정한 방향으로 계속 이동한 뒤 장애물을 마주쳤을 때, 이동을 멈춘다. 이런 경우 목표지점에 도착하는 최소 이동거리를 구하라. 알아야하는 점처음에 DFS로 생각한 이유는 좌표를 이동할 때 벽을 만날때까지 이동한다면 스택을 이용하는 게 맞지 않나라는 생각이 들어서 DFS를 생각했다. 찾아보니 코테문제 풀 때 보통 아래처럼 DFS/BFS 사용하는 경우가 많다고 하니 참고하자. DFS : 완전탐색BFS : 최단거리이 문제 풀이는 DFS/BFS 둘다 가능하지만, base condition을 통해 시간초과나지 않게 구현하는 것이 중요했던 것 같다. 그 조건..
99클럽 TIL (240822)
·TIL
> [Middler] 무인도 여행https://school.programmers.co.kr/learn/courses/30/lessons/154540 문제 풀이 과정같은 무인도끼리 머물 수 있는 일자를 구해주면 된다. DFS로 문제를 해결했다.문제를 풀면서 어려웠던 점은 주어지는 maps 요소들이 문자열이라는 점이었다. 문자열의 특정 인덱스 값만 변경하려고 하다보니 에러가 발생해서 우선 maps를 2차원 배열로 만들어 주었다. 1. maps를 돌면서 'X' 가 아니고 방문한적 없다면 무인도이므로 식량의 개수를 센다.2. 현재 위치에서 상,하,좌,우로 DFS를 돌려 하나의 무인도에서 발견할 수 있는 식량의 개수를 모두 합하고 정답 배열에 append한다.3. 만일 지낼 수 있는 무인도가 없다면 -1을 담아 ..
wnwlals13
'99클럽' 태그의 글 목록