문제:

풀이방법:

여러가지 푸는 방법이 있겠지만, 가장 단순하면서 쉬운 방법을 사용하고자 한다. 브루트 포스 방식으로 가능한 모든 경우의 수를 만들고 그 중에서 해당하는 조건을 찾는 방법으로 했다.

 우선 python의 itertools의 permutation을 사용해서 모든 경우의 수를 만든다. 그리고 각 조건에 맞는지 확인을 하는데, 조건의 길이와 다르면 바로 False로 가도록 하고, 길이가 같다면 그 때 조건을 비교하도록 한다.

 이렇게 조건에 맞는 경우를 찾았다면 중복을 방지하기 위해서 set으로 값을 넣도록 한다.

1s
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
import itertools
 
def check(case,banned_id):
    for i in range(len(banned_id)):
        if len(banned_id[i]) !=len(case[i]):
            return False
        else:
            for j in range(len(banned_id[i])):
                if banned_id[i][j]=="*":
                    continue
                elif banned_id[i][j] != case[i][j]:
                    return False
    return True
 
def solution(user_id,banned_id):
    answer=[]
    cases=list(itertools.permutations(user_id,len(banned_id)))
    for case in cases:
        if check(case,banned_id):
            case=set(case)
            if case not in answer:
                answer.append(case)
    return len(answer)
 cs

문제링크:

https://programmers.co.kr/learn/courses/30/lessons/64064

 

코딩테스트 연습 - 불량 사용자

개발팀 내에서 이벤트 개발을 담당하고 있는 무지는 최근 진행된 카카오이모티콘 이벤트에 비정상적인 방법으로 당첨을 시도한 응모자들을 발견하였습니다. 이런 응모자들을 따로 모아 불량 ��

programmers.co.kr

 

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

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

[BOJ]9506. 약수들의 합  (0) 2020.06.09
[Programmers]2018 Kakao[1차]추석 트래픽  (0) 2020.05.26
[BOJ]2468. 안전 영역  (0) 2020.05.19
[BOJ]2167. 2차원 배열의 합  (0) 2020.05.14
[BOJ]1350. 진짜 공간  (0) 2020.05.12

문제:

독일 로또는 {1, 2, ... , 49}에서 수 6개를 고른다.

 

로또 번호를 선택하는데 사용되는 가장 유명한 전략은 49가지 수 중 k개의 수를 골라 집합 S를 만든 다음 그 수만을 가지고 번호를 선택하는 것이다.

 

예를 들어 , k=8, S={1,2,3,5,8,13,21,34}인 경우 이 집합 S에서 수를 고를 수 있는 경우의 수는 총 28가지이다.

{[1,2,3,5,8,13].[1,2,3,5,8,21].[1,2,3,5,8,34],[1,2,3,5,13,21], ... ,[3,5,8,13,21,34]}

 

집합 S와 k가 주어졌을 때, 수를 고르는 모든 방법을 구하는 프로그램을 작성하시오.

입력:

입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스는 한 줄로 이루어져 있다. 첫 번째 수는 k(6<k<13)이고, 다음 k개 수는 집합 S에 포함되는 수이다. S의 원소는 오름차순으로 주어진다.

 

입력의 마지막 줄에는 0이 하나 주어진다.

출력:

각 테스트 케이스마다 수를 고르는 모든 방법을 출력한다. 이때, 사전 순으로 출력한다.

각 테스트 케이스 사이에는 빈 줄을 하나 출력한다.

풀이방법:

 경우의 수를 구하는 문제는 python의 itertools를 사용하면 쉽게 구할 수 있다. itertools.combinations( iterable, k )와 같은 방식으로 사용하면 iterable한 자료형에서 k를 골라 만들 수 있는 모든 경우의 수를 만들어 준다.

 이 경우의 수를 출력하기 위해 *c와 같이 사용을 하고 각 테스트 케이스 사이에는 빈 줄을 하나 출력해야 하므로 print()를 마지막에 넣어주었다.

1
2
3
4
5
6
7
8
9
10
11
12
import itertools
 
while True:
    temp=input().split()
    k=int(temp[0])
    s=map(int,temp[1:])
    if k==0:
        break
    case = itertools.combinations(s,6)
    for c in case:
        print(*c)
    print()
 cs

문제링크:

https://www.acmicpc.net/problem/6603

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

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

[BOJ]1182. 부분수열의 합  (0) 2020.02.18
[BOJ]1431. 시리얼 번호  (1) 2020.02.13
[BOJ]1297. TV 크기  (0) 2020.02.06
[BOJ]10026. 적록색약  (0) 2020.02.04
[Programmers]Lv 4. 카드 게임  (0) 2020.01.23

문제:

풀이방법:

 컬럼의 길이가 최대 8이므로 가능한 모든 경우의 조합을 다 따져보아도 문제가 없을 것이라고 생각했다.(최대 2^8=256개이기 때문이다.) 따라서 우선 check 함수를 통해서 유일성을 만족하는지 파악을 했다.

 유일성을 만족하는 조합을 기준으로 서로 비교하면서 최소성을 만족하는지 확인하였다. 이들을 집합이라고 생각한다면 (1)은 (1,2)의 부분집합이 되게 된다. 따라서 set에서 부분집합인지 확인해주는 내장함수는 issubset을 사용해서 부분집합인지 확인하였다. 그리고 해당하는 조합이 있다면 remove를 통해서 제거해줬다.

 그리고 남은 answer의 길이를 구함으로써 후보키의 갯수를 얻을 수 있다.

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
def check(columns,tuples,relation):
    sets=set()
    for rel in relation:
        tup=''
        for col in columns:
            tup+=rel[col]
        sets.add(tup)
    if len(sets)==tuples:
        return True
    else:
        return False
 
 
def solution(relation):
    answer=[]
    import itertools
    columns=list(range(len(relation[0])))
    tuples=len(relation)
    for i in range(1,len(columns)+1):
        candidate=list(itertools.combinations(columns,i))
        for candi in candidate:
            if check(list(candi),tuples,relation):
                answer.append(list(candi))
    for i in answer[:]:
        for j in answer[:]:
            if i==j:
                continue
            if set(i).issubset(set(j)):
                answer.remove(j)
    return len(answer)
 cs

문제링크:

https://programmers.co.kr/learn/courses/30/lessons/42890

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

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

[BOJ]1890. 점프  (0) 2019.10.04
[Programmers]2017 Kakao.다트 게임  (0) 2019.10.02
[Programmers]2018 Kakao.실패율  (0) 2019.09.30
[Programmers]2018 Kakao. 오픈채팅방  (0) 2019.09.29
[Programmers]2017 Kakao.비밀지도  (0) 2019.09.28

문제:

왕비를 피해 일곱 난쟁이들과 함께 평화롭게 생활하고 있던 백설공주에게 위기가 찾아왔다. 일과를 마치고 돌아온 난쟁이가 일곱 명이 아닌 아홉 명이었던 것이다. 

아홉 명의 난쟁이는 모두 자신이 "백설 공주와 일곱 난쟁이"의 주인공이라고 주장했다. 뛰어난 수학적 직관력을 가지고 있던 백설공주는, 다행스럽게도 일곱 난쟁이의 키의 합이 100이 됨을 기억해 냈다.

아홉 난쟁이의 키가 주어졌을 때, 백설공주를 도와 일곱 난쟁이를 찾는 프로그램을 작성하시오.

입력:

아홉 개의 줄에 걸쳐 난쟁이들의 키가 주어진다. 주어지는 키는 100을 넘지 않는 자연수이며, 아홉난쟁이의 키는 모두 다르며, 가능한 정답이 여러 가지 인 경우에는 아무거나 출력한다.

출력:

일곱 난쟁이의 키를 오름차순으로 출력한다. 일곱 난쟁이를 찾을 수 없는 경우는 없다.

풀이 방법:

브루트 포스 문제이므로 모든 나올 수 있는 경우의 수에 대해서 계산해주면 된다. 사실 경우의 수도 많은 편이 아니다.(9C7=9C2=36개)
파이썬에서 순열과 조합을 계산해줄 수 있도록 하는 모듈은 itertools를 사용했고, 그 중 combinations를 사용해서 9개 중 7개를 선택했다.
이 경우의 수 중 100이 되는 경우를 출력해주도록 한다.(답이 여러개라도 하나만 출력해도 괜찮으므로)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
import itertools
 
Dwarfs=[]
for i in range(9):
    Dwarfs.append(int(input()))
Dwarfs.sort()
answers=list(itertools.combinations(Dwarfs,7))
for answer in answers:
    summation=0
    for i in answer:
        summation+=i
    if summation==100:
        temp=answer
        break
for i in temp:
    print(i)
cs


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

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

[BOJ]7568. 덩치  (0) 2019.05.19
[BOJ]2231. 분해합  (0) 2019.05.18
[BOJ]1015. 수열 정렬  (0) 2019.05.16
[BOJ]1547. 공  (0) 2019.05.15
[BOJ]10253. 헨리  (0) 2019.05.14

문제:

한자리 숫자가 적힌 종이 조각이 흩어져있습니다. 흩어진 종이 조작을 붙여 소수를 몇 개 만들 수 있는지 알아내려 합니다.

각 종이 조각에 적힌 숫자가 적힌 문자열 numbers가 주어졌을 때, 종이 조각으로 만들 수 있는 소수가 몇 개인지 return 하도록 solution 함수를 완성해주세요.

풀이 방법:

 문제의 태그가 완전탐색인만큼 시간이 충분히 주어졌을 것이라고 생각했다. 따라서 numbers로 생성될 수 있는 모든 숫자의 경우들을 다 담아두고 하나씩 소수인지 판별하면 될 것 같다고 생각했다.
따라서 모든 경우의 수를 만들기 위해서 python의 itertools의 permutations 기능을 사용하고자 하였다. 
itertools.permutations(iterable,i) 와 같이 사용을 하며 iterable한 객체 중 i 개를 사용해서 나올 수 있는 경우의 수를 모두 만들어준다.
따라서 이를 활용해 모든 경우의 수를 만들어내었고 중복을 set을 사용해서 제거한 후 소수인지 판별 하였다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
def solution(numbers):
    import itertools
    number=list(numbers)
    a=[]   
    for i in range(1,len(number)+1):
        a+=list(map(''.join,itertools.permutations(number,i)))
    a=list(set(map(int,a))) 
    a.sort()
    count=0
    print(a)
    for i in a:
        if i < 2:
            pass
        elif i ==2:
            count+=1
        else:
            for j in range(2,i):
                if i % j ==0:
                    break;
                elif j==i-1:
                    count+=1
    return count
cs


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

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

[Programmers]Lv 2.전화번호 목록  (0) 2019.02.16
[Programmers]Lv 1.모의고사  (0) 2019.02.15
[Programmers]Lv 1. 체육복  (0) 2019.02.13
[Programmers]Lv2. 큰 수 만들기  (0) 2019.02.12
[Programmers]Lv 1. K번째수  (0) 2019.02.11

+ Recent posts

티스토리툴바