본문 바로가기

취준생

 (24)
[알고리즘] 구현 경우의 수가 100,000개 이하면 완전 탐색 가능 8개를 무작위로 나열하는 모든 순열의 개수 구하는 법 : 8!
[탐욕법] 백준 1439번 '뒤집기' (Python) https://www.acmicpc.net/problem/1439 1439번: 뒤집기 다솜이는 0과 1로만 이루어진 문자열 S를 가지고 있다. 다솜이는 이 문자열 S에 있는 모든 숫자를 전부 같게 만들려고 한다. 다솜이가 할 수 있는 행동은 S에서 연속된 하나 이상의 숫자를 잡고 모 www.acmicpc.net 0에서 1로, 1에서 0으로 바뀌는 지점을 파악하여 연속된 0과 1의 개수를 파악한다. s의 범위를 파악해야 하므로 바뀌는 지점을 담는 변수 change 첫 번째 값에 0을, 마지막 값에 s의 길이를 넣는다. 0과 1 중 연속된 값이 적은 것을 파악하여 개수를 출력한다. '''입력 예제 0001100 11111 00000001 1100110011001100001 11101101 ''' s = in..
[진법변환] 백준 5692번 '팩토리얼 진법' (Python) https://www.acmicpc.net/problem/5692 5692번: 팩토리얼 진법 상근이는 보통 사람들이 사는 것과는 조금 다른 삶을 사는 사람이다. 상근이는 이런 사람들의 시선이 부담스럽기 때문에, 자신만의 숫자를 개발하기로 했다. 바로 그 이름은 팩토리얼 진법이다. www.acmicpc.net 팩토리얼 공식(n! = 1*2*3*...*(n-1)*n)을 알아야 풀 수 있음 Ex) 719 ==> (7 * 팩토리얼(3)) + (1 * 팩토리얼(2)) + 9 * 팩토리얼(1)) 입력이 몇 줄로 이루어지는지 모르므로 무한루프로 입력을 받고 계산하고 계산이 끝나면 바로 출력한다. '0'을 받으면 루프를 종료한다. '''입력 예제 719 1 15 110 102 0 ''' import sys def fa..
[탐욕법] 백준 10162번 '전자레인지' (Python) https://www.acmicpc.net/problem/10162 10162번: 전자레인지 3개의 시간조절용 버튼 A B C가 달린 전자레인지가 있다. 각 버튼마다 일정한 시간이 지정되어 있어 해당 버튼을 한번 누를 때마다 그 시간이 동작시간에 더해진다. 버튼 A, B, C에 지정된 시간은 www.acmicpc.net t가 a, b, c 보다 크면 t에서 a, b, c를 빼고, 1을 더해준다. t가 0이 되면 종료 t가 0이 되지 않을 수도 있는 경우는 10보다 작은 경우이므로 조건문 걸어줌 t가 0이면 결과값을 출력하고, 아니면 -1 출력 '''입력 예제 100 189 ''' t = int(input()) result = [0]*3 while t > 0: if t= 300: t -= 300 resul..
[이분탐색] 난이도1.5, Amazon 인터뷰 '고정점 찾기' (Python) 고정점이란, 수열의 원소 중에서 그 값이 인덱스와 동일한 원소를 의미합니다. 예를 들어 수열 a={-15,-4,2,8,13}이 있을 때 a [2]=2이므로, 고정점은 2가 됩니다. 하나의 수열이 N개의 서로 다른 원소를 포함하고 있으며, 모든 원소가 오름차순으로 정렬되어 있습니다. 이때 이 수열에서 고정점이 있다면, 고정점을 출력하는 프로그램을 작성하세요. 고정점은 최대 1개만 존재합니다. 만약 고정점이 없다면, - 1을 출력합니다. 단, 이 문제는 시간 복잡도 O(logN)으로 알고리즘을 설계하지 않으면 '시간 초과' 판정을 받는다. 첫째 줄에 N이 입력됩니다. (1
[스택] 프로그래머스 L2 '주식가격' (Python) https://programmers.co.kr/learn/courses/30/lessons/42584 코딩테스트 연습 - 주식가격 초 단위로 기록된 주식가격이 담긴 배열 prices가 매개변수로 주어질 때, 가격이 떨어지지 않은 기간은 몇 초인지를 return 하도록 solution 함수를 완성하세요. 제한사항 prices의 각 가격은 1 이상 10,00 programmers.co.kr prices의 길이만큼 시간이 지남 스택으로 사용할 타이머 생성 #1차시도 : 2,3,4,5,6,7,8,9,10 & 효율성테스트 실패 def solution(prices): stack = [0] answer = [0] * len(prices) for i in range(1,len(prices)): if prices[i] ..
[알고리즘] 최단경로 - (Dijkstra(다익스트라)/Floyd-Warshall(플로이드-워셜)) 최단 경로 문제 - 최단 경로 문제란 두 노드를 잇는 가장 짧은 경로를 찾는 문제임 - 가중치 그래프 (Weighted Graph) 에서 간선 (Edge)의 가중치 합이 최소가 되도록 하는 경로를 찾는 것이 목적 최단 경로 문제 종류 1. 단일 출발 및 단일 도착 (single-source and single-destination shortest path problem) 최단 경로 문제 - 그래프 내의 특정 노드 u 에서 출발, 또다른 특정 노드 v 에 도착하는 가장 짧은 경로를 찾는 문제 2. 단일 출발 (single-source shortest path problem) 최단 경로 문제 - 그래프 내의 특정 노드 u 와 그래프 내 다른 모든 노드 각각의 가장 짧은 경로를 찾는 문제 > 따지고 보면 굉장..
[알고리즘] 정렬 - (선택/삽입/퀵/계수/버블/병합/라이브러리) 정렬 (sorting) 이란? - 정렬 (sorting): 어떤 데이터들이 주어졌을 때 이를 정해진 순서대로 나열하는 것 - 정렬은 프로그램 작성시 빈번하게 필요로 함 - 다양한 알고리즘이 고안되었으며, 알고리즘 학습의 필수 > 다양한 정렬 알고리즘 이해를 통해, 동일한 문제에 대해 다양한 알고리즘이 고안될 수 있음을 이해하고, 각 알고리즘간 성능 비교를 통해, 알고리즘 성능 분석에 대해서도 이해할 수 있음 선택 정렬 다음과 같은 순서를 반복하며 정렬하는 알고리즘 1. 주어진 데이터 중, 최소값을 찾음 2. 해당 최소값을 데이터 맨 앞에 위치한 값과 교체함 3. 맨 앞의 위치를 뺀 나머지 데이터를 동일한 방법으로 반복함 https://visualgo.net/en/sorting 시간 복잡도 : O(N^2)..
LIST

티스토리툴바