문제 고정점(Fixed Point)이란, 수열의 원소 중에서 그 값이 인덱스와 동일한 원소를 의미합니다. 예를 들어 수열 a = {-15, -4, 2, 8 ,13}이 있을 때 a[2] = 2이므로, 고정점은 2가 됩니다. 하나의 수열이 N개의 서로 다른 원소를 포함하고 있으며, 모든 원소가 오름차순으로 정렬되어 있습니다. 이때 이 수열에서 고정점이 있다면, 고정점을 출력하는 프로그램을 작성하세요. 만약 고정점이 없다면 -1을 출력합니다. 단, 이 문제는 시간 복잡도 O(logN)으로 알고리즘을 설계하지 않으면 '시간 초과' 판정을 받습니다. 풀이 import sys import bisect ip = sys.stdin.readline n = int(ip()) arr = list(map(int,ip().sp..
문제 N개의 원소를 포함하고 있는 수열이 오름차순으로 정렬되어 있습니다. 이때 이 수열에서 x가 등장하는 횟수를 계산하세요. 단, 이 문제의 시간 복잡도 O(logN)으로 알고리즘을 설계하지 않으면 '시간 초과' 판정을 받습니다. 풀이 import sys from copy import deepcopy from collections import deque import bisect ip = sys.stdin.readline n,x = map(int,ip().split()) arr = list(map(int,ip().split())) res = bisect.bisect_right(arr,x)-bisect.bisect_left(arr,x) if res == 0 : print(-1) else : print(res..
최단경로 알고리즘은 BFS, DFS, 그리디 등의 알고리즘을 이용하여 어떤 그래프 내의 한 노드에서 다른 노드까지의 최단 경로를 찾는 알고리즘이다. 최단경로 알고리즘은 보통 3가지의 풀이법으로 풀린다. 다익스트라 알고리즘, 플로이드 워셜 알고리즘, 벨만 포드 알고리즘 이다. 1. 다익스트라 알고리즘 일단 기본적으로 최단경로 알고리즘은 그래프에서 여러개의 노드가 있을 때, 특정한 노드에서 출발하여 다른 노드로 가는 각각의 최단 경로를 구해주는 알고리즘이다. 여기에서 추가로 다익스트라 알고리즘은 '음의 간선'이 없을 경우에 정상 동작한다. 다익스트라 알고리즘은 시작노드 기준으로 시작노드와 가까운 노드부터 최단경로를 구하고 지금까지 구한 최단경로를 가지고 다음 노드들의 최단경로를 구하는 알고리즘이다. 다이나믹..
8-2. 1로 만들기 문제 정수 X가 주어질때 정수 X에 사용할 수 있는 연산은 다음과 같이 4가지이다. 1) X가 5로 나누어떨어지면, 5로 나눈다. 2) X가 3으로 나누어 떨어지면, 3으로 나눈다. 3) X가 2로 나누어 떨어지면, 2로 나눈다. 4) X에서 1을 뺀다. 정수 X가 주어졌을때, 연산 4개를 적절히 사용해서 1을 만들어야한다. 이 연산을 사용하는 횟수의 최솟값을 출력해라. X = 26일 경우 1. 26 - 1 = 25 2. 25 /5 = 5 3. 5 / 5 = 1 입력 첫째 줄에 정수 X이 주어진다. (1
학교에서 코테스터디를 시작하였다. 코테 빈출유형 14가지에 대해 약 7주동안 스터디를 진행할 예정이다. 이번이 첫주차이다. 이번 주차에는 그리디와 구현 유형에 대해 공부하였다. 쉬운 유형이지만 그만큼 방심하면 안된다고 생각해서 열심히 풀었다. 3-2. 큰수의법칙 3-2. 소스코드 import sys ip = sys.stdin.readline #입력부분 n, m, k = map(int,ip().split()) arr = list(map(int,ip().split())) #값 정렬 (가장큰수와 두번째로큰수 찾기위함) arr.sort() res = 0 # m번반복 for i in range(1,m+1) : # 한 수를 k번 반복시 두번째로 큰수로 갈아탐 if (i % k == 0) : res += arr[-2..
