본문 바로가기

728x90

python38

[LeetCode] 155. Min Stack (Python) 1. 문제 문제 링크 : 155. Min Stack 문제 태크 : Stack 2. 문제 설명 Implement the MinStack class → MinStack의 클래스를 구현해야한다. MinStack() initializes the stack object. → 스택으로 사용할 객체 생성하기 → Python에서는 List를 사용하여 스택처럼 작업 수행 void push(int val) pushes the element val onto the stack. → 스택에 값을 넣기 void pop() removes the element on the top of the stack. → 가장 최근에 넣었던 값 제거하기 → 스택에 1개 이상의 값이 존재할 경우에만 가능 int top() gets the top e.. 2024. 3. 13.

[LeetCode] 74. Search a 2D Matrix (Python) 1. 문제 https://leetcode.com/problems/search-a-2d-matrix/description/?envType=study-plan-v2&envId=top-interview-150 LeetCode - The World's Leading Online Programming Learning Platform Level up your coding skills and quickly land a job. This is the best place to expand your knowledge and get prepared for your next interview. leetcode.com 2. 문제 설명 Each row is sorted in non-decreasing order. → 각 행은 오.. 2024. 2. 7.

[BOJ] 2437번 - 저울 (Python) 🛠️ 문제 🛠️ 🗒️ 설명 🗒️ 우선 예시 중에서 추 [1, 1, 2]만 가지고 있다고 생각해보자. 그러면 측정할 수 있는 무게는 위의 그림과 같다. 다른 예시로 [1, 2, 3]으로 생각해보면, 1 = 1 2 = 2 3 = 3 4 = 1+3 5 = 2+3 6 = 1+2+3 위와 같이 측정할 수 있다. 즉, 가지고 있는 추들의 무게를 합한 값 이하의 값들은 측정할 수 있다는 것을 알 수 있다. 단, 추의 무게들이 정렬이 되어있어야 하며 추와 추 사이의 무게 차이가 크게 나면 안된다. 여기서 추 사이의 무게 차이가 얼마만큼 차이가 나면 안되는지를 생각해봐야한다. 문제에서 주어진 예시로 현재 [1, 1, 2, 3]의 추를 가지고 있어 7까지 측정할 수 있다고 하자. 다음 추가 현재 측정할 수 없는 8보다 작.. 2023. 10. 27.

[BOJ] 15657번 - N과M(8) (Python) 🛠️ 문제 🛠️ 🗒️ 설명 🗒️ 백트래킹 연습하기 편한 문제라고 생각한다. 오늘 풀면서 틀렸던 이유에 대해 간단하게 남겨놓으려고 한다. 내가 잘못 생각했던 부분은 타입을 생각하지 않고 정렬한 것이다. 처음에는 결과를 쉽게 저장하기 위해 문자형 그대로 사용하여 주어진 예제는 전부 통과해 제출했지만 틀렸다. 다른 동작의 오류가 있나 고민해보았지만 없었고 다른 사람의 풀이를 참고해봐도 동작은 완벽했다. 단 하나 다른 점이 입력받은 데이터 타입이었는데 생각해보니 [입력으로 주어지는 수는 10,000보다 작거나 같은 자연수]이므로 이는 정수로 정렬해야 올바르게 정렬된다는 것을 깨달았다. 🍀 풀이 🍀 import sys n, m = map(int, sys.stdin.readline().split()) nums = .. 2023. 10. 5.

[BOJ] 1911번 - 흙길 보수하기 (Python) 🛠️ 문제 🛠️ 🗒️ 설명 🗒️ 이 문제는 [물웅덩이들을 모두 덮으려고 한다.] 라는 조건이 있으므로 물웅덩이가 보이면 일단 덮으면 된다. 그러나 널빤지의 길이는 정해져 있으므로 덮다보면 입력받은 물웅덩이의 위치가 이미 덮여져 있을 수 있다. 어차피 모든 웅덩이는 덮어야하니 웅덩이의 [끝 위치 - 시작 위치]를 통해 웅덩이의 길이를 구하여 필요한 널빤지의 개수를 구했다. 단, 위에서 설명했듯이 이미 덮여져 있는 위치가 존재할 수 있으므로 이에 대한 처리로 current라는 변수를 두어 시작 위치를 덮여져 있지 않은 위치로 변경할 수 있도록 했다. 🍀 풀이 🍀 import sys n, l = map(int, sys.stdin.readline().split()) water = [list(map(int, sy.. 2023. 9. 7.

[BOJ] 13549번 - 숨바꼭질3 (Python) 🛠️ 문제 🛠️ 🗒️ 설명 🗒️ 어제 공부한 다익스트라 알고리즘을 연습해보았다. 다익스트라 알고리즘과 BFS 2가지 방식으로 풀어보았다. (코드는 아래에) 1. 다익스트라 알고리즘을 이용한 풀이 1. 수빈이의 위치를 시작 정점으로 둔다. 2. 현재 위치 i에 +1, -1 *2 한 위치에 대해 저장되어 있는 시간 times[k]와 도달한 시간(times[i] + 1 또는 times[i])을 비교하여 도달한 시간이 더 작으면 times[k]를 갱신한다. 3. heap이 빌 때까지 2번 과정을 반복한다. 이때, 주의할 점은 가중치가 없지만 가중치로 생각한 값은 도달한 시간으로 times의 값이다. 만약 이를 times를 도착 정점의 개수만큼만 만들면 올바른 값을 도출하지 못할 것이다. 위의 문제에서 주어진 예.. 2023. 9. 5.

[BOJ] 1753번 - 최단경로(Python) + Dijkstra Algorithm 🗒️ 다익스트라 알고리즘 (Dijkstra Algorithm) 모서리 또는 정점에 가중치가 부여된 그래프에서 두 정점 사이의 최단 경로를 찾는 알고리즘 가중치가 없는 그래프에서의 최단경로는 BFS를 사용! 어떤 시작점 s가 주어졌을 때, 그 정점에서 시작하여 다른 모든 정점으로 가는 최단 경로를 찾는다. 단, 음수인 가중치가 없는 경우에만 쓸 수 있다. 실제 최단 경로는 우리집에서 옆집으로 이동하는 것이지만, 우리집에서 은행을 거쳐 가는 것이 비용상 이득이 되는 경우가 발생한다. 즉, 값이 음수인 모서리가 있으면 경로를 만들어가는 도중에 아주 작은 음수 값을 가지는 모서리가 있어서 이미 트리에 들어있는 최단 경로와 전혀 다른 경로를 만들어야 할 수 있다. 동작 과정(간선 완화 과정) 1. 모든 꼭짓점을 .. 2023. 9. 4.

[TIL] Make란? + stack 문제 풀이 1. Make 소프트웨어 개발을 위해 유닉스 계열 운영 체제에서 주로 사용되는 프로그램 빌드 도구 여러 파일들끼리의 의존성과 각 파일에 필요한 명령을 정의함으로써 프로그램을 컴파일할 수 있으며 최종 프로그램을 만들 수 있는 과정을 서술할 수 있는 표준적인 문법을 가지고 있다. Makefile : make를 실행하기 전에 프로젝트의 목록 및 컴파일 및 링크 규칙 1. Makefile 이 필요한 이유 반복된는 컴파일 작업 시간이 오래 걸린다. 수정된 파일만 컴파일할 수 있다. 대규모 프로젝트나 공동 프로젝트에서 반드시 필요하다. 2. 컴파일 과정 소스 파일(*.c) : 우리가 작성한 코드 목적파일(*.o) : gcc compiler 를 이용하여 생성 → 기계어 생성 실행파일(*.out) : gcc compi.. 2023. 5. 7.

[TIL] C언어 공부하기 1. 코드 refactoring 1. 12891번 - DNA 비밀번호 import sys s, p = map(int, sys.stdin.readline().split()) dna = list(sys.stdin.readline().strip()) # A, C, G, T esssential = list(map(int, sys.stdin.readline().split())) def remove(st) : global a, c, g, t if dna[st] == 'A' : a -= 1 elif dna[st] == 'C' : c -= 1 elif dna[st] == 'G' : g -= 1 elif dna[st] == 'T' : t -= 1 return 0 def add(e) : global a, c, g, t i.. 2023. 5. 4.

[TIL] 문제 풀이 연습 - two point (with python) 1. 문제 풀이 연습 1. 2018번 - 수들의 합 import sys N = int(sys.stdin.readline()) start = 1 # 현재 더한 값 중 첫번째 값 end = 1 # 현재 더한 값 중 마지막 값 count = 1 # 자기 자신 포함 sum = 1 # 총 더한 값 # 최소 2개의 연속된 자연수의 합이어야 하므로 # start는 N의 절반보다 클 수 없다. while start != N // 2 + 1 : if sum < N : # 아직 누적합이 N보다 작을 경우 end += 1 sum += end elif sum == N : # N과 같을 경우 count += 1 sum -= start start += 1 else : # N보다 클 경우 sum -= start start += 1.. 2023. 5. 3.

[TIL] 동적 프로그래밍 문제 풀이3 1. 문제 풀이 연습 1. 11660번 - 구간 합 구하기 5 import sys N, M = map(int, sys.stdin.readline().split()) table = [list(map(int, sys.stdin.readline().split())) for _ in range(N)] # 누적합을 저장할 이차원 배열 dp = [[0] * (N+1) for _ in range(N+1)] for i in range(1, N+1) : for j in range(1, N+1) : dp[i][j] = table[i-1][j-1] + dp[i][j-1] + dp[i-1][j] - dp[i-1][j-1] # 원하는 구간합 구하기 for _ in range(M) : x1,y1,x2,y2 = map(int, s.. 2023. 5. 2.

[TIL] 그리디 문제 풀이 + 기계 수준 표현1 1. 그리디 문제 풀이 1. 1931번 - 회의실 배정 import sys N = int(sys.stdin.readline()) # meeting[0] : 시작 시간 / meeting[1] : 끝나는 시간 meeting = [list(map(int, sys.stdin.readline().split())) for _ in range(N)] meeting.sort(key= lambda x : (x[1], x[0])) count = 1 prev = meeting[0][1] # 앞 회의 끝나는 시간 for i in range(1, N) : # 만약 현재 회의 시작 시간이 앞 회의 시간보다 크거나 같으면 if prev people[i][1] : count += 1 interview = people[i][1] pr.. 2023. 5. 1.

[TIL] Algorithm - Greedy 기본 문제 풀이 1. 그리디 알고리즘 (탐욕 알고리즘) 항상 각 단계에 있어서 가장 좋을 거라 생각되는 선택을 한다. 이 선택이 전체적으로 최적해로 안내하게 될 거라는 바람을 가지고 부분적으로 최적인 선택을 한다. 언제나 최적의 해답을 구하지는 못하지만 많은 문제에 대한 해를 구해줄 수 있다. 1. 11047번 - 동전 0 import sys N, K = map(int, sys.stdin.readline().split()) # 오름차순으로 입력을 받는다. coin = [int(sys.stdin.readline()) for _ in range(N)] count = 0 # 동전의 가치가 가장 큰 동전부터 반복 시작 for i in range(N-1, -1, -1) : if K == 0 : break # 현재 K보다 작은 수.. 2023. 4. 30.

[TIL] 동적 프로그래밍 문제 풀이2 1. 11049번 - 행렬 곱셈 순서 1. 최적 괄호 묶기의 구조 : n개의 행렬을 어떻게 곱할지 애매함을 없애기 위해 괄호로 묶는다. ex) ((A1, A2), A3) or (A1, (A2, A3)) 이 문제는 n개의 행렬들의 체인 이 주어졌을 때 A1, A2, ... , An의 스칼라 곱의 개수를 최소화 하도록 괄호를 묶어라! 라고 하는 것과 같다. AiAi+1...Aj를 괄호호 최적으로 묶기 위해 Ak Ak+1의 사이에서 나눈다고 가정 AiAi+1...Ak Ak+1Ak+2...Aj 위의 두 부분문제는 각각 최적 괄호 묶는 방법이 되어야 한다. 2. 재귀해 i == j 일 경우 0 i < j 일 경우 → k, k+1로 나눈다. Ai = pi-1 * pi 라면 Ai..kAk+1..j = pi-1 *pk.. 2023. 4. 29.

[TIL] 동적 프로그래밍 문제 풀이 1. DP 문제 풀이 1. 9084번 - 동전 import sys T = int(sys.stdin.readline()) for _ in range(T) : N = int(sys.stdin.readline()) coin = list(map(int, sys.stdin.readline().split())) M = int(sys.stdin.readline()) dp = [0] * (M+1) # 각각의 금액에 대한 동전으로 만들 모든 방법의 수 저장 dp[0] = 1 # 기저 값으로 지정 for c in coin : for i in range(1, M+1) : if i >= c : dp[i] += dp[i-c] print(dp[M]) 간단하게 생각하면 간단하다고 할 수 있지만 저 방식을 생각해내는 것 자체가 힘들.. 2023. 4. 28.

[TIL] Algorithm - 동적 프로그래밍 기본 1. 그래프 문제 풀이 1. 1388번 - 바닥 장식 import sys N, M = map(int, sys.stdin.readline().split()) graph = [list(sys.stdin.readline().strip()) for _ in range(N)] visited = [[0] * M for _ in range(N)] # 같은 행에 존재하는지 확인해야하므로 열 번호 증가 def col(x, y) : visited[x][y] = 1 stack = [(x, y)] while stack : curx, cury = stack.pop() for i in range(1, M) : ny = cury + i if ny < M and graph[curx][ny] == '-' and visited[curx.. 2023. 4. 27.

[TIL] 위상 정렬 문제 풀이 + Computer System2 1. 위상 정렬 문제 풀이 1. 2637번 - 장난감 조립 import sys from collections import deque N = int(sys.stdin.readline()) M = int(sys.stdin.readline()) basic = [[] for _ in range(N)] inDegree = [0] * N for _ in range(M) : x, y, k = map(int, sys.stdin.readline().split()) basic[y-1].append((x-1, k)) inDegree[x-1] += 1 def topologicalsort() : # component[x][y] -> x를 만드는데 필요한 y의 개수 component = [[0] * N for _ in range.. 2023. 4. 26.

[TIL] Algorithm - 위상 정렬 + 플로이드-워셜 1. 그래프 문제 풀이 1. 2573번 - 빙산 ▶ BFS를 이용한 풀이 import sys from collections import deque N, M = map(int, sys.stdin.readline().split()) iceberg = [list(map(int, sys.stdin.readline().split())) for _ in range(N)] dx = [-1, 1, 0, 0] dy = [0, 0, -1, 1] # 빙산 녹이는 함수 def melting() : change = [] for i in range(1, N-1) : for j in range(1, M-1) : if iceberg[i][j] != 0 : sea = 0 # 현재 위치에서 0과 맞닿아 있는 개수 for k in ran.. 2023. 4. 25.

이전 1 2 3 다음

728x90

티스토리툴바