문제:

n개의 섬 사이에 다리를 건설하는 비용(costs)이 주어질 때, 최소의 비용으로 모든 섬이 서로 통행 가능하도록 만들 때 필요한 최소 비용을 return 하도록 solution을 완성하세요.

다리를 여러 번 건너더라도, 도달할 수만 있으면 통행가능하다고 봅니다. 예를 들어 A 섬과 B 섬 사이에 다리가 있고, B 섬과 C 섬 사이에 다리가 있으면 A 섬과 C 섬은 서로 통행 가능합니다.


문제 풀이:

전형적인 Kruskal 알고리즘을 사용해서 푸는 문제이다. Kruskal 알고리즘이란, 탐욕적인 방법을 이용하여 그래프의 모든 정점을 최소 비용으로 연결하는 방법이다. Kruskal 알고리즘을 사용하는 방법은 간단하다. 처음 시작하는 노드로 부터 하나의 간선을 선택해가면 된다. 

이 문제의 예시로 설명을 들면 처음에 0에서 시작을 한다고 가정을 하자. 

1. 0에 연결되어 있는 간선은 0-1(1), 0-2(2) 두 가지 간선이 있다. 최소 비용으로 연결하는 것이 목적이므로 0-1 간선을 선택하고 1의 노드를 연결된 노드 집합에 넣도록 한다. 

2. 0과 1의 노드에 연결되어 있는 간선을 찾도록 하자. 그러면 0-2 (2), 1-2(5), 1-3(1) 세 가지 간선이 존재하게 되고, 역시 최소를 선택하므로 1-3을 선택하게 된다.

3. 위와 같은 방법으로 진행을 하면 0-2 간선을 선택하게 되어 모든 노드들이 연결되게 된다.

이제 이 방법들을 코드로 옮기면 다음과 같다. connect라는 연결된 노드 집합을 만들고 이 값이 n과 같게 되면 while이 끝나도록 한다. costs를 반복하여 connect에 있는 노드들의 간선을 찾도록 한다. (단 시점과 종점이 모두 connect에 있으면 안된다.) 이 간선들의 최소값을 찾아 answer에 더하고 connect 집합에 노드를 추가시키고 costs에서는 간선을 빼도록 한다. 이 작업을 모든 노드가 connect에 들어갈 때까지 반복한 answer를 반환하면 된다.


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
def solution(n, costs):
    costs.sort()
    connect=[costs[0][0]]
    answer = 0
    while len(connect)!=n:
        temp=1000000000000000
        idx=0
        for i in range(len(costs)):
            if costs[i][0] in connect or costs[i][1] in connect:
                if costs[i][0] in connect and costs[i][1] in connect:
                    continue
                if temp > costs[i][2]:
                    temp=costs[i][2]
                    idx=i
        answer+=temp
        connect.append(costs[idx][0])
        connect.append(costs[idx][1])
        connect=list(set(connect))
        costs.pop(idx)
    return answer
cs


저작자표시 비영리 동일조건

'Algorithm > Python' 카테고리의 다른 글

[BOJ]1904. 01타일  (0) 2019.07.10
[Programmers]Lv 3. 기지국 설치  (0) 2019.07.09
[Programmers]Lv 3. 단속카메라  (2) 2019.07.07
[BOJ]2869. 달팽이는 올라가고 싶다.  (0) 2019.07.06
[BOJ]1011. Fly me to the Alpha Centauri  (0) 2019.07.05

문제:

고속도로를 이동하는 모든 차량이 고속도로를 이동하면서 단속용 카메라를 한 번은 만나도록 카메라를 설치하려고 합니다.

고속도로를 이동하는 차량의 경로 routes가 매개변수로 주어질 때, 모든 차량이 한 번은 단속용 카메라를 만나도록 하려면 최소 몇 대의 카메라를 설치해야 하는지를 return 하도록 solution 함수를 완성하세요.

문제 풀이:

프로그래머스에서 이 문제의 태그를 탐욕법으로 걸어 놓았으니 탐욕적으로 풀려고 한다. 탐욕적인 방법은 말 그래도 욕심을 부려서 최고의 결과를 얻고자 하는 방법이다.( 물론 항상 얻는다는 보장은 없다.!) 따라서 이 문제에서 적게 쓰고 최고의 결과를 얻기 위해서는 차량의 진출입로에 단속카메라를 설치하는 것이 가장 최상의 방법일 것이다. 

따라서 각 차량이 단속카메라에 만났는지 확인하는 check 배열을 만들었고, 임의로 설치한 단속카메라를 만났다면 1로 바뀌도록 하였다. routes를 정렬을 하고 뒤에서부터 진입로에 카메라를 설치해 나가도록 하였다. 
처음에는 -5에 설치를 하고 이 카메라가 확인할 수 있는 다른 차량을 확인해보았을 때. [-14,-5]와 [-20, 15]가 이 카메라로 확인을 할 수 있으니 이 차량들의 check도 1로 바꾼다. 그 다음에는 -18에 설치를 해서 [-18, 13]의 check도 1로 바꾸도록 한다. 따라서 2 개의 단속 카메라가 필요하게 된다.

ps) 뒤에서부터가 아닌 앞에서부터 하려고 했으나 통과를 하지 못해서 하지 못하였습니다.

1
2
3
4
5
6
7
8
9
10
11
12
def solution(routes):
    routes.sort()
    answer = 0
    check =[0]*len(routes)
    for i in range(len(routes)-1,-1,-1):
        if check[i]==0:
            camera = routes[i][0]
            answer+=1
        for j in range(i,-1,-1):
            if check[j]==0 and routes[j][1] >= camera >=routes[j][0]:
                check[j]=1
    return answer
cs


저작자표시 비영리 동일조건

'Algorithm > Python' 카테고리의 다른 글

[Programmers]Lv 3. 기지국 설치  (0) 2019.07.09
[Programmers]Lv 3. 섬 연결하기  (0) 2019.07.08
[BOJ]2869. 달팽이는 올라가고 싶다.  (0) 2019.07.06
[BOJ]1011. Fly me to the Alpha Centauri  (0) 2019.07.05
[Programmers]Lv 3. 여행경로  (0) 2019.07.04

문제:

무인도에 갇힌 사람들을 구명보트를 이용하여 구출하려고 합니다. 구명보트는 작아서 한 번에 최대 2명씩 밖에 탈 수 없고, 무게 제한도 있습니다.

예를 들어, 사람들의 몸무게가 [70kg, 50kg, 80kg, 50kg]이고 구명보트의 무게 제한이 100kg이라면 2번째 사람과 4번째 사람은 같이 탈 수 있지만 1번째 사람과 3번째 사람의 무게의 합은 150kg이므로 구명보트의 무게 제한을 초과하여 같이 탈 수 없습니다.

구명보트를 최대한 적게 사용하여 모든 사람을 구출하려고 합니다.

사람들의 몸무게를 담은 배열 people과 구명보트의 무게 제한 limit가 매개변수로 주어질 때, 모든 사람을 구출하기 위해 필요한 구명보트 개수의 최솟값을 return 하도록 solution 함수를 작성해주세요.

풀이 방법:

구명보트는 작아서 한 번에 최대 2명만 탈 수 있다는 점이 가장 중요하다. 또한 탐욕적 방법으로 해결해야 하므로 사람들의 몸무게를 정렬하고 가장 몸무게가 작은 사람과 무거운 사람과 매칭을 해보는 방법으로 진행을 해보았다. 만약 가장 작은 사람의 무게와 무거운 사람의 무게가 limit보다 작다면 탑승할 수 있는 것 이므로 count를 하나 늘리고 light의 인덱스를 1증가, heavy의 인덱스를 1감소 시킨다. 만약 limit보다 크다면 heavy의 인덱스만 1감소 시킨다.
이를 light의 인덱스가 heavy의 인덱스를 앞지를 때까지 반복한다.
이후 최종 구명보트의 수는 people의 전체 길이에서 count 값을 뺀 값이 된다.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
def solution(people,limit):
    people.sort()
    length=len(people)
    light=0
    heavy=length-1
    count=0
    while(light<heavy):
        if people[light]+people[heavy]<=limit:
            count+=1
            light+=1
            heavy-=1
        else:
            heavy-=1
    return length-count
cs


저작자표시 비영리 동일조건

'Algorithm > Python' 카테고리의 다른 글

[Programmers]Lv 2. 카펫  (0) 2019.02.26
[Programmers]:Lv 3. 예산  (0) 2019.02.25
[Programmers]Lv 3.타일 장식물  (0) 2019.02.23
[Programmers]Lv 2. 숫자 야구  (0) 2019.02.22
[Programmers]Lv 3. 2 X N 타일링  (0) 2019.02.21

문제:

오늘은 체육수업이 있는 날입니다. 그런데 점심시간에 도둑이 들어 몇몇 학생의 체육복이 도난을 당했습니다. 다행히 일부 학생들이 여벌의 체육복을 가져왔습니다. 학생들의 번호는 체격 순으로 매겨져 있기 때문에 바로 앞번호의 학생이나 바로 뒷번호의 학생에게만 체육복을 빌려주려고 합니다.

예를 들어, 4번 학생은 3번 학생이나 5번 학생에게만 체육복을 빌려줄 수 있습니다. 당연히 체육복을 2벌 가져온 학생의 체육복이 도난을 당했다면, 여벌의 체육복을 빌려줄 수 없습니다.

체육복이 없으면 체육수업을 들을 수 없기 때문에 체육복을 적절히 빌려 최대한 많은 학생이 체육수업을 듣고 싶습니다.

전체 학생의 수 n, 체육복을 도난당한 학생들의 번호가 담긴 배열 lost, 여벌의 체육복을 가져온 학생들의 번호가 담긴 배열 reserve가 매개변수로 주어질 때, 체육수업을 들을 수 있는 학생의 최댓값을 return 하도록 solution 함수를 작성해주세요.

풀이 방법:

 여분을 가지고 있는 학생들은 2의 값을 가지고 있고 도난당한 학생은 0의 값, 여분을 가지고 있었지만 도난당한 학생들은 1의 값을 가지도록 한다.
이후 이웃 학생들과의 값을 비교해보았을 때 둘의 차이가 2인 경우에만 여분을 가지고 있는 학생이 도난당한 학생에게 빌려줄수 있는 상황이다. 이를 크게 두 개의 반복문으로 해결하도록 하였다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
def solution(n,lost,reserve):
    cloth=[1]*n
    for i in range(n):
        if i+1 in reserve:
            cloth[i]=2
            if i+1 in lost:
                cloth[i]-=1
                continue
        if i+1 in lost:
            cloth[i]=0
    if cloth[0]-cloth[1]>1:
        cloth[0]-=1
        cloth[1]+=1
    for i in range(1,n-1):
        if cloth[i]-cloth[i+1] > 1:
            cloth[i]-=1
            cloth[i+1]+=1
        elif cloth[i]-cloth[i-1]>1:
            cloth[i]-=1
            cloth[i-1]+=1
        else:
            pass
    if cloth[-1]-cloth[-2] > 1:
        cloth[-1]-=1
        cloth[-2]+=1
    count=0
    for i in cloth:
        if i > 0:
            count+=1
        else:
            pass
    return count
cs

수정:

2월 28일 이후로 테스트 케이스가 추가되었다.


저작자표시 비영리 동일조건

'Algorithm > Python' 카테고리의 다른 글

[Programmers]Lv 1.모의고사  (0) 2019.02.15
[Programmers]Lv 2. 소수 찾기  (0) 2019.02.14
[Programmers]Lv2. 큰 수 만들기  (0) 2019.02.12
[Programmers]Lv 1. K번째수  (0) 2019.02.11
[Programmers]Lv 2.더 맵게  (0) 2019.02.10

문제:

어떤 숫자에서 k개의 수를 제거했을 때 얻을 수 있는 가장 큰 숫자를 구하려 합니다.

예를 들어, 숫자 1924에서 수 두 개를 제거하면 [19,12,14,92,94,24] 를 만들 수 있습니다. 이 중 가장 큰 숫자는 94입니다.

문자열 형식으로 숫자 number와 제거할 수의 개수 k가 solution 함수를 매개변수로 주어집니다. number에서 k 개의 수를 제거 했을 때 만들 수 있는 수 중 가장 큰 숫자를 문자열 형태로 return 하도록 solution 함수를 완성하세요.

풀이 과정:

 단순히 number 중 작은 순으로 빼는 것이 아니라는 것을 마지막 예시 케이스 4177252841을 보면 알 수 있다. 따라서 이 문제는 탐욕법을 사용해서 풀어야 하는 문제이므로 문제 풀이를 생각하였다. 따라서 각 자리별로 한번씩 다 빼보아서(ex 1924의 경우 924, 124, 194, 192) 이 중 가장 큰 경우를 선택하도록 하였다. 대부분의 경우에 대해서 통과를 하지만 역시나 자릿수가 큰 경우에 시간초과가 발생하였다.
 그래서 탐욕법이 아닌 다른 방법도 생각해보았는데 스택을 활용해서 푸는 것이 효율적으로 할 수 있었다.

 숫자를 다음과 같은 규칙에 따라 스택을 쌓아가면 큰 수를 만들어 갈 수 있다.
  1. 하나의 값을 넣는다
  2. 맨 위에 쌓인 값과 그 바로 밑(맨 위에서 두번째 값)을 비교한다.
  3. 맨 위의 값이 더 클 경우 두 개의 값의 자리를 바꾸고 pop 해내서 빼낸다. 맨 위의 값이 작으면 다음 단계로 넘어간다
  4. 1~3을 k번 빼내거나, number를 다 쌓으면 끝낸다.

 다음은 예시 케이스 4177252841을 쌓는 과정을 나타냈다.


 

 

 

 

 

 

 

 

 

 

 1


 4

 비교 대상이 없어 통과한다.

 4

위 값이 작으므로  그냥 패스한다. 

 



 

 

 

 

 

 

 7

 

 

 

 

 

 1

 7을 쌓았을 때 자리를 

 7

 자리를 바꾼 후 1을 빼

 

 이 역시 7이 더 크므로

 4

바꾼다.

 4

 고 다시 4와 비교를 함

 7

 자리를 바꾸고 4를 뺌


이 작업을 반복해서 하면 큰 수를 만들 수 있다.


하지만 54321, k=1 와 같은 경우에는 하나도 빠지는 것 없이 54321 순으로 쌓이게 된다. 이 규칙으로 쌓았을 때 마지막으로 갈 수록 수가 작아지므로 뒤에서 부터 잘라서 사용하도록 한다.


우선 number가 string이므로 이를 list로 쪼개 하나씩 넣을 수 있도록 만들었다. 그리고 첫 수는 항상 넣고 시작하였다. 하나씩 넣으면서 Tos(Top of stack) 즉 지금 맨 위에 쌓인 부분의 인덱스를 하나씩 늘렸다. while 문이 규칙의 2,3번을 반복하는 과정이다. correct라는 변수는 4177252841와 같은 경우에 7을 넣을 때 두 번 연속 빼야하는데 이와 같은 행위를 하기 위해서 넣은 변수이다.

그리고 맨마지막에 54321 과 같은 경우를 해결하기 위해 뒤에서 부터 자르도록 하였다.


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
def solution(number,k):
    number=list(number)
    answer=[number[0]]
    Tos=0
    for i in range(1,len(number)):
        answer.append(number[i])
        Tos+=1
        correct=1
        while (correct and k !=0):
            correct-=1
            for j in range(Tos,len(answer)):
                if answer[j-1]>=answer[j]:
                    pass
                else:
                    answer[j-1],answer[j]=answer[j],answer[j-1]
                    answer.pop()
                    correct+=1
                    Tos-=1
                    k-=1
                    break
    answer="".join(answer)
    return answer[:len(answer)-k]
cs



저작자표시 비영리 동일조건

'Algorithm > Python' 카테고리의 다른 글

[Programmers]Lv 2. 소수 찾기  (0) 2019.02.14
[Programmers]Lv 1. 체육복  (0) 2019.02.13
[Programmers]Lv 1. K번째수  (0) 2019.02.11
[Programmers]Lv 2.더 맵게  (0) 2019.02.10
[Programmers]Lv 1.같은 숫자는 싫어  (0) 2019.02.09

문제:

조이스틱으로 알파벳 이름을 완성하세요. 맨 처음엔 A로만 이루어져 있습니다.
ex) 완성해야 하는 이름이 세 글자면 AAA, 네 글자면 AAAA

조이스틱을 각 방향으로 움직이면 아래와 같습니다.
▲ - 다음 알파벳
▼ - 이전 알파벳(A에서 아래쪽으로 이동하면 Z로)
◀ - 커서를 왼쪽으로 이동 (첫 번째 위치에서 왼쪽으로 이동하면 마지막 문자에 커서)
▶ - 커서를 오른쪽으로 이동

예를 들어 아래의 방법으로 "JAZ"를 만들 수 있습니다.

-첫 번째 위치에서 조이스틱을 위로 9번 조작하여 J를 완성합니다.
-조이스틱을 왼쪽으로 1번 조작하여 커서를 마지막 문자 위치로 이동시킵니다.
-마지막 위치에서 조이스틱을 아래로 1번 조작하여 Z를 완성합니다.
따라서 11번 이동시켜 "JAZ"를 만들 수 있고, 이 때가 최소 이동입니다.

만들고자 하는 이름 name이 매개변수로 주어질 때, 이름에 대해 조이스틱 조작 횟수의 최솟값을 return 하도록 solution 함수를 만드세요.

풀이방법:

이 조이스틱은 크게 두가지를 최적의 방법으로 정해야 한다.

첫번째는 문자의 이동이다. 위 방향키를 사용해서 원하는 문자로 이동을 할지 아래 방향키를 사용할지를 정해야 한다. 이것은 비교적 간단하다. 알파벳은 총 26자이므로 A에서 14번째에 존재하는 알파벳은 위 방향키보다 아래 방향키로 이동하는 것이 더 효율적이기 때문이다. 이는 아스키코드 함수인 ord를 사용해서 이동하고 그 차이만큼 answer에 더하도록 한다.

두번째는 위치의 이동이다. 문자 중 A가 존재한다면 문자를 이동시킬 필요가 없으므로 왼쪽으로 이동할지 오른쪽으로 이동할지 결정을 해야한다.
이는 하나의 반복을 이용해서 결정하도록 하였다. 방금 문자를 이동시킨 인덱스에서 오른쪽 문자와 왼쪽 문자 중 A가 아닌 것을 더 빨리 만나는 쪽으로 이동하도록 하였다. 파이썬의 인덱스는 음수로 가면 오른쪽 맨 끝으로 이동하기 때문에 1씩 빼는 과정에서 음수로 가도 문제가 없다.

이 두가지의 방법을 원하는 알파벳을 만들때까지 반복하도록 한다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
def solution(name):
    answer = 0
    name=list(name)
    base=["A"]*len(name)
    idx=0
    while(True):
        rightidx=1
        leftidx=1
        if name[idx]!="A":
            if ord(name[idx])-ord("A")>13:
                answer+=26-(ord(name[idx])-ord("A"))
            else:
                answer+=ord(name[idx])-ord("A")
            name[idx]="A"
        if name ==base:
            break
        else:
            for i in range(1,len(name)):
                if name[idx+i]=="A":
                    rightidx+=1
                else:
                    break
                if name[idx-i]=="A":
                    leftidx+=1
                else:
                    break
            if rightidx>leftidx:
                answer+=leftidx
                idx-=leftidx
            else:
                answer+=rightidx
                idx+=rightidx
    return answer
cs



저작자표시 비영리 동일조건

'Algorithm > Python' 카테고리의 다른 글

[Programmers]Lv 2.더 맵게  (0) 2019.02.10
[Programmers]Lv 1.같은 숫자는 싫어  (0) 2019.02.09
[Programmers]Lv 1.문자열 내 마음대로 정렬하기  (0) 2019.02.07
[Programmers]Lv 2.주식 가격  (0) 2019.02.06
[Programmers]Lv 1.소수 찾기  (0) 2019.02.05

+ Recent posts

티스토리툴바