본문 바로가기

알고리즘

 (87)
프로그래머스, 광물캐기 프로그래머스, 광물캐기 📜문제 https://school.programmers.co.kr/learn/courses/30/lessons/172927 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 분류 : accepted 📜풀이 처음 문제를 봤을때, 무조건 곡괭이를 순서대로 다 써야하는 줄 알았다. # [dia, iron, stone] picks = [0, 2, 1] 다이아몬드 곡괭이 없으니, 넘어가고 철 곡괭이로 10번 광물 캐기, 돌 곡괭이로 5번 광물 캐기 ❌ 잘못된 풀이 from collections import deque # [dia, iron, s..
백준, 최소 비용 구하기 백준, 최소 비용 구하기 📜문제 https://www.acmicpc.net/problem/1916 1916번: 최소비용 구하기 첫째 줄에 도시의 개수 N(1 ≤ N ≤ 1,000)이 주어지고 둘째 줄에는 버스의 개수 M(1 ≤ M ≤ 100,000)이 주어진다. 그리고 셋째 줄부터 M+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 www.acmicpc.net 분류 : accepted ❌ 초기 접근법 시작점에서 마지막점까지 도달할 모든 경로에 대한 비용을 탐색해 total_costs 리스트에 저장. 결과값으로 total_costs의 최솟값을 반환한다. total_costs = [] def move(start, end): queue = deque([(start, 0)]) # visited ..
3.1 점근적 표기 3. 함수의 증가 입력이 충분히 커지면 정확한 수행시간의 상수계수와 저차항은 입력 크기에 묻혀 버린다. ❓성장률 rate of growth 입렵값의 크기에 따라 함수가 얼마나 빨리 커지는지 즉, 실행시간의 성장률을 알고싶은 것! 우리가 알고 싶은건, 입력값 크기에 따른 알고리즘의 실행시간에 대한 예측이다. 프로그램을 쉽게 예측할수 있도록 불필요한 부분은 과감히 버리고 가장 중요한 부분만 추려서 함수로 간소화해야 한다. 예를 들어 0.6n²+1000n+3000 에서 n이 커질 수록 n²은 기하 급수적으로 커지게 된다. ❓접근적표기법 asymptotic notaion 상수 계수와 중요하지 않은 항목을 제거하는 표기법으로 big-Θ 표기법, big-O 표기법, and big-Ω 표기법이 있다. ❓big-Θ(T..
프로그래머스, 키패드 누르기 프로그래머스, 키패드 누르기 https://school.programmers.co.kr/learn/courses/30/lessons/67256 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 분류 pass 요새 BFS문제를 많이 푸는 중이다. 2023.08.09 - [알고리즘] - 백준, 이모티콘 저번에 풀었던 최단시간 문제 이모티콘도 그렇고! 이번에는 최단거리 문제! 예전에 이문제를 이차원배열로 푼적이 있다. 2023.01.22 - [알고리즘] - 데일리 알고리즘 230120 데일리 알고리즘 230120 데일리 알고리즘 230120 프로그래머스, 키패드 ..
2.3 알고리즘의 설계 2.3 알고리즘의 설계 분할정복 분할 : 현재 문제를 같은 문제를 다루는 다수의 부분 문제로 분할한다. 정복 : 부분 문제를 재귀적으로 풀어서 정복한다. 부분 문제의 크기가 충분히 작으면 직접적인 방법으로 푼다. 결합 : 부분 문제의 해를 결합하여 원래 문제의 해가 되도록 만든다. 병합정렬 분할정복 시간복잡도 연습문제 2.3-1 2.3-2 def merge_without_sentinels(A, p, q, r): nL = q - p + 1 # Length of A[p...q] nR = r - q # Length of A[q+1...r] L = [0] * nL # Initialize arrays L and R R = [0] * nR for i in range(nL): # Copy A[p...q] into L..
프로그래머스, 숫자짝궁 프로그래머스, 숫자짝궁 https://school.programmers.co.kr/learn/courses/30/lessons/131128 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 분류 accepted 문제 테스트 케이스 3,5,8,10 불통 테스트 케이스 11~15 시간초과 오류 풀이 예시 문제가 다 통과되서 다음 풀이가 맞는줄 알았다. X="5525" Y="1255" nums_dict = {x:0 for x in range(10)} for y in Y: if y in set(list(X)): nums_dict[int(y)] += 1 result=..
백준 1303 전쟁- 전투 백준 1303 전쟁- 전투 문제 https://www.acmicpc.net/problem/1303 1303번: 전쟁 - 전투 첫째 줄에는 전쟁터의 가로 크기 N, 세로 크기 M(1 ≤ N, M ≤ 100)이 주어진다. 그 다음 두 번째 줄에서 M+1번째 줄에는 각각 (X, Y)에 있는 병사들의 옷색이 띄어쓰기 없이 주어진다. 모든 자리에는 www.acmicpc.net 분류 그래프 pass(복습필요) 하지만, 시간 지난뒤 다시 풀어봐야 할것같다. dfs, bfs 문제는 자주 안보면 풀이법을 자꾸 까먹는것같다. 풀이 2023.08.11 - [알고리즘] - softeer, 장애물 인식 프로그램 softeer, 장애물 인식 프로그램 softeer, 장애물 인식 프로그램 문제 https://softeer.ai/p..
softeer, 장애물 인식 프로그램 softeer, 장애물 인식 프로그램 문제 https://softeer.ai/practice/info.do?idx=1&eid=409 Softeer 연습문제를 담을 Set을 선택해주세요. 취소 확인 softeer.ai 풀이 pass 풀이 일단 방문했으면 방문여부를 표시해야 재방문하는 일이 없을 것이다. 2차원 region이 주어졌으면 index범위를 벗어나지 않는지도 체크해 봐야 한다. 대각선 방향은 고려하지 않아도 되므로 북동남서를 탐색했을 때, '1'이고 방문한 적 없을 경우에만 탐색한다. 우리가 원하는 값은 방문가능한 범위 카운트한 값이다. 그래서 이를 global 변수로 둔다. # 북동남서 dr = [-1, 0, 1, 0] dc = [0, 1, 0, -1] def dfs(r,c): global cn..
2.2 알고리즘 분석 2.2 알고리즘 분석 알고리즘을 실행 시, 필요한 자원 예측 메모리 통신대역 하드웨어 계산시간 RAM 모델 단일 프로세서 + RAM 캐시나 가상메모리는 고려하지 않는다. 명령어는 동시에 수행되지 않고 차례로 하나씩 실행된다. 명령어 한 행당 상수시간 소요 산술연산(덧셈, 뺄셈, 곱셈, 나눗셈, 나머지, 내림, 올림) 데이터이동 연산(읽기, 저장하기, 복사하기) 제어 연산(조건 분기, 무조건 분기, 함수 호출과 리턴) 입력크기는 수행시간에 비례한다. 최악의 경우 : 크기가 n인 입력 중 가장 오래걸리는 수행 시간 평균적인 경우 : n개의 숫자 무작위 하지만 무엇이 평균적인 입력인지 불확실한 경우, 랜덤화된 알고리즘을 사용한다. 연습문제 2.2-1 θ(n³) 2.2-2 for s = 1 to A.length..
백준, 이모티콘 백준, 이모티콘 문제 https://www.acmicpc.net/problem/14226 14226번: 이모티콘 영선이는 매우 기쁘기 때문에, 효빈이에게 스마일 이모티콘을 S개 보내려고 한다. 영선이는 이미 화면에 이모티콘 1개를 입력했다. 이제, 다음과 같은 3가지 연산만 사용해서 이모티콘을 S개 만 www.acmicpc.net 풀이 set 자료구조를 이용해 방문표시를 해 이미 계산한 적있는 (screen, clipboard)는 또 계산하지 않도록 했다. 계산하는 순간 시간이 늘어나므로! (문제에서 원하는 건 최소 시간이므로) 또한 작업 순서를 순차적으로 하기 위해 queue 자료구조에에 작업 순서 저장해 popleft해가면서 차례로 계산해 나갔다. 분류 30분동안, dp로 접근해 규칙을 찾아내려고 애..

티스토리툴바