728x90
반응형

문제:

풀이방법:

 입력으로 들어오는 값들을 다중집합으로 만들어야 한다. 소문자와 대문자의 구분이 필요 없으므로 소문자로 전부 바꾸고 두개씩 끊어가면서 특수문자가 있는지 파악하고 각 배열에 담는다. 

 summation이라는 두 배열의 길이의 합을 구하고 이를 교집합과 뺌으로써 합집합의 크기를 구할 것이다. summation은 공통된 원소를 두 개씩 가지고 있는 것이기 때문이다. 

 반복문을 사용해서 공통된 원소가 있을 때마다 intersect를 하나씩 증가시킨다.

이 두 변수로 자카드 유사도는 다음과 같이 구한다. int(intersect/(summation-intersect)*65536) 이 값을 구하면 답을 얻을 수 있다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
def solution(str1,str2):
    str1=str1.lower()
    str2=str2.lower()
    str1_set=[]
    str2_set=[]
    for i in range(len(str1)-1):
        if (str1[i]+str1[i+1]).isalpha():
            str1_set.append(str1[i]+str1[i+1])
    for i in range(len(str2)-1):
        if (str2[i]+str2[i+1]).isalpha():
            str2_set.append(str2[i]+str2[i+1])
    summation=len(str1_set)+len(str2_set)
    intersect=0
    for i in str2_set:
        if i in str1_set:
            str1_set.remove(i)
            intersect+=1
    if summation==0:
        return 65536
    else:
        return int(intersect/(summation-intersect)*65536)
cs

 

문제링크:

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

 

728x90
반응형

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

[Programmers]2017 Kakao.비밀지도  (0) 2019.09.28
[Programmers]2017 Kakao.캐시  (0) 2019.09.27
[BOJ]1987. 알파벳  (0) 2019.09.25
[BOJ]1759. 암호 만들기  (0) 2019.09.24
[BOJ]14889. 스타트와 링크  (0) 2019.09.23
728x90
반응형

문제:

풀이방법:

ORDER BY에는 옵션이 존재한다. 아무 옵션도 주지 않으면 자동으로 ASC로 되어 있다. 하지만 이 문제와 같이 역순으로 정렬을 해야 한다는 조건이 있으면 DESC를 사용하면 된다.

1
SELECT NAME, DATETIME FROM ANIMAL_INS ORDER BY ANIMAL_ID DESC;
cs

문제링크:

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

728x90
반응형
728x90
반응형

문제:

세로 R칸,가로 C칸으로 된 표 모양의 보드가 있다. 보드의 각 칸에는 대문자 알파벳이 하나씩 적혀 있고, 좌측 상단 칸(1행 1열)에는 말이 놓여 있다.

말은 상하좌우로 인접한 네 칸 중의 한 칸으로 이동할 수 있는데, 새로 이동한 칸에 적혀 있는 알파벳은 지금까지 지나온 모든 칸에 적혀 있는 알파벳과는 달라야 한다. 즉, 같은 알파벳이 적힌 칸을 두 번 지날 수 없다.

좌측 상단에서 시작해서, 말이 최대한 몇 칸을 지날 수 있는지를 구하는 프로그램을 작성하시오. 말이 지나는 칸은 좌측 상단의 칸도 포함된다.

입력:

첫째 줄에 R과 C가 빈칸을 사이에 두고 주어진다. (1<=R,C<=20)둘째 줄부터 R개의 줄에 걸쳐서 보드에 적혀 있는 C개의 대문자 알파벳들이 빈칸 없이 주어진다.

출력:

첫째 줄에 말이 지날 수 있는 최대의 칸 수를 출력한다.

풀이방법:

제일 많이 파고 들어가야 하는 문제이므로 DFS와 백트래킹을 사용하는 것이 적합하다. DFS를 사용해서 한 번 깊게 파고 난 뒤에 움직이지 못하는 경우가 된다면 다시 되돌아와서 다른 곳으로 깊게 파고 들어가도록 한다. 이때부터는 최대로 깊게 들어간 기록이 있으므로 이 기록을 넘길 때에만 값을 갱신하도록 하였다. 이렇게 모두 탐색을 마치고 더 이상 이동할 곳이 없다면 출력하도록 했다.

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
def go(board,check,x,y):
    ans=0
    for i in range(4):
        nx=x+dx[i]
        ny=y+dy[i]
        if 0<=nx<len(board) and 0<=ny<len(board[0]):
            if check[ord(board[nx][ny])-65]==False:
                check[ord(board[nx][ny])-65]=True
                count=go(board,check,nx,ny)
                if ans < count:
                    ans = count
                check[ord(board[nx][ny])-65]=False
    return ans+1
 
 
r,c=map(int,input().split())
board=[]
for i in range(r):
    board.append(list(input()))
dx=[0,0,1,-1]
dy=[1,-1,0,0]
answer=[]
check=[False]*26
x,y=0,0
check[ord(board[x][y])-65]=True
print(go(board,check,x,y))
cs

문제링크:

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

728x90
반응형

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

[Programmers]2017 Kakao.캐시  (0) 2019.09.27
[Programmers]2017 Kakao. 뉴스 클러스터링  (0) 2019.09.26
[BOJ]1759. 암호 만들기  (0) 2019.09.24
[BOJ]14889. 스타트와 링크  (0) 2019.09.23
[BOJ]1697. 숨바꼭질  (0) 2019.09.22
728x90
반응형

문제:

풀이 방법:

최댓값을 구하는 함수인 MAX를 사용하면 된다. 또한 이 값을 시간이라고 컬럼명을 정했기 때문에 AS로 시간으로 지정했다.

1
SELECT MAX(DATETIME) AS "시간" FROM ANIMAL_INS;
cs

문제 링크:

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

728x90
반응형
728x90
반응형

문제:

 바로 어제 최백준 조교가 방 열쇠를 주머니에 넣은 채 깜빡하고 서울로 가 버리는 황당한 상황에 직면한 조교들은, 702호에 새로운 보안 시스템을 설치하기로 하였다. 이 보안 시스템은 열쇠가 아닌 암호로 동작하게 되어 있는 시스템이다.

 

 암호는 서로 다른 L개의 알파벳 소문자들로 구성되며 최소 한 개의 모음과 최소 두 개의 자음으로 구성되어 있다고 알려져 있다. 또한 정렬된 문자열을 선호하는 조교들의 성향으로 미루어 보아 암호를 이루는 알파벳이 암호에서 증가하는 순서로 배열되었을 것이라고 추측된다. 즉, abc는 가능성이 있는 암호이지만 bac는 그렇지 않다.

 

 새 보안 시스템에서 조교들이 암호로 사용했을 법한 문자의 종류는 C가지가 있다고 한다. 이 알파벳을 입수한 민식, 영식 형제는 조교들의 방에 침투하기 위해 암호를 추측해 보려고 한다. C개의 문자들이 모두 주어졌을 때, 가능성 있는 암호들을 모두 구하는 프로그램을 작성하시오.

 

입력:

첫째 줄에 두 정수 L, C가 주어진다. (3<=L<=C<=15) 다음 줄에는 C개의 문자들이 공백으로 구분되어 주어진다. 주어지는 문자들은 알파벳 소문자이며, 중복되는 것은 없다.

 

출력:

각 줄에 하나씩, 사전식으로 가능성 있는 암호를 모두 출력한다.

 

풀이 방법:

 재귀적인 방법으로 암호를 만들고, 이 암호가 옳은 암호인지 판단하는 check라는 함수를 만들었다. 암호를 만들다가 길이가 L이 된다면 check로 옳은 암호인지 판단을 하고 맞다면 출력, 아니면 끝내도록 했다.

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
l,c = map(int,input().split())
chrs=input().split()
chrs.sort()
 
def check(alphabet):
    ahdma=0
    wkdma=0
    for a in alphabet:
        if a in ['a','e','i','o','u']:
            ahdma+=1
        else:
            wkdma+=1
    return ahdma>=1 and wkdma>=2
            
 
def make(l,chrs,alphabet,idx):
    if len(alphabet)==l:
        if check(alphabet):
            print(alphabet)
        return
    if idx >=len(chrs):
        return
    ne=alphabet+chrs[idx]
    idx+=1
    make(l,chrs,ne,idx)
    make(l,chrs,alphabet,idx)
 
alphabet=''
idx=0
make(l,chrs,alphabet,idx)
cs

 

문제링크:

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

728x90
반응형

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

[Programmers]2017 Kakao. 뉴스 클러스터링  (0) 2019.09.26
[BOJ]1987. 알파벳  (0) 2019.09.25
[BOJ]14889. 스타트와 링크  (0) 2019.09.23
[BOJ]1697. 숨바꼭질  (0) 2019.09.22
[BOJ]2022. 사다리  (0) 2019.09.21
728x90
반응형

문제:

풀이방법:

 모든 정보를 조회하는 문제이므로 전체를 뜻하는 *를 SELECT 부분에 사용하면 된다. 다만 ANIMAL_ID순으로 조회하라는 조건이 있었으므로 ORDER BY ANIMAL_ID를 추가해주었다.

1
SELECT * FROM ANIMAL_INS ORDER BY ANIMAL_ID;
cs

문제링크:

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

728x90
반응형
728x90
반응형

문제:

오늘은 스타트링크에 다니는 사람들이 모여서 축구를 해보려고 한다. 축구는 평일 오후에 하고 의무 참석도 아니다. 축구를 하기 위해 모인 사람은 총 N명이고 신기하게도 N은 짝수이다. 이제 N/2명으로 이루어진 스타트팀과 링크 팀으로 사람들을 나눠야 한다.

 

BOJ를 운영하는 회사 답게 사람에게 번호를 1부터 N까지로 배정했고, 아래와 같은 능력치를 조사했다. 능력치 Sij는 i번 사람과 j번 사람이 같은 팀에 속했을 때, 팀에 더해지는 능력치이다. 팀의 능력치는 팀에 속한 모든 쌍의 능력치 Sij의 합이다. Sij는 Sji와 다를 수도 있으며, i번 사람과 j번 사람이 같은 팀에 속했을 때, 팀에 더해지는 능력치는 Sij와 Ski이다.

 

N=4이고, S가 아래와 같은 경우를 살펴보자.

예를 들어, 1,2번이 스타트 팀, 3, 4번이 링크 팀에 속한 경우에 두 팀의 능력치는 아래와 같다.

  •  스타트 팀: S12+S21 = 1+ 4 = 5
  •  링크 팀: S34 + S43 = 2 + 5 = 7

1,3 번이 스타팀, 2,4번이 링크 팀에 속하면, 두 팀의 능력치는 아래와 같다.

  •  스타트 팀: S13+S31 = 2+ 7 = 9
  •  링크 팀: S24 + S42 = 6 + 4 = 10

 축구를 재미있게 하기 위해서 스타트 팀의 능력치와 링크 팀의 능력치의 차이를 최소로 하려고 한다. 위의 예제와 같은 경우에는 1,4번이 스타트 팀, 2,3 번 팀이 링크 팀에 속하면 스타트 팀의 능력치는 6, 링크 팀의 능력치는 6의 되어서 차이가 0이 되고 이 값이 최소이다.

입력:

첫째 줄에 N(4<=N<=20, N은 짝수)이 주어진다. 둘째 줄부터 N개의 줄에 S가 주어진다. 각 줄은 N개의 수로 이루어져 있고, i번 줄의 j번째 수는 Sij 이다. Sii는 항상 0이고, 나머지 Sij는 1보다 크거나 같고, 100보다 작거나 같은 정수이다.

 

출력:

첫째 줄에 스타트 팀과 링크 팀의 능력치의 차이의 최솟값을 출력한다.

 

풀이 방법:

 N은 최대 20이므로 나올 수 있는 조합의 경우의 수는 20C10이다. 이 정도의 수를 반복하는 것은 충분히 가능하기 때문에 브루트포스로 풀어도 상관없을 것 같았다. 

 우선 python의 itertools를 사용해서 나올 수 있는 조합을 만들었다. 그리고 set을 사용해서 스타트팀과 링크 팀으로 구분을 했고, 스타트팀과 링크 팀을 이중 반복문을 통해서 시너지의 합을 구했다. 그리고 시너지간의 차를 배열에 담았다.위 작업을 모두 마치고 나서 배열의 min을 출력하도록 하였다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
import itertools
import sys
n=int(sys.stdin.readline().strip())
temp=list(range(n))
synergy=[]
for i in range(n):
    synergy.append(list(map(int,sys.stdin.readline().strip().split())))
= list(itertools.combinations(temp,n//2))
answer=[]
for team in p:
    start = list(team)
    link = list(set(temp)-set(team))
    Synergy_start=0
    Synergy_link=0
    for i in start:
        for j in start:
            Synergy_start+=synergy[i][j]
    for i in link:
        for j in link:
            Synergy_link+=synergy[i][j]
    ans=abs(Synergy_link-Synergy_start)
    answer.append(ans)
print(min(answer))
cs

문제 링크:

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

728x90
반응형

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

[BOJ]1987. 알파벳  (0) 2019.09.25
[BOJ]1759. 암호 만들기  (0) 2019.09.24
[BOJ]1697. 숨바꼭질  (0) 2019.09.22
[BOJ]2022. 사다리  (0) 2019.09.21
[BOJ]1561. 놀이공원  (0) 2019.09.20
728x90
반응형

문제:

수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N()<=N<=100,000)에 있고, 동생은 점 K(0<=K<=100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약 수빈이의 위치가 X일 때 걷는다면 1초 후에 X-1 또는 X+1로 이동하게 된다. 순간이동을 하는 경우에는 1초 후에 2*X의 위치로 이동하게 된다.

 

수빈이와 동생의 위치가 주어졌을 때, 수빈이가 동생을 찾을 수 있는 가장 빠른 시간이 몇 초 후인지 구하는 프로그램을 작성하시오.

 

입력:

첫 번째 줄에 수빈이가 있는 위치 N과 동생이 있는 위치 K가 주어진다. N과 K는 정수이다.

 

출력:

수빈이가 동생을 찾는 가장 빠른 시간을 출력한다.

 

풀이 방법:

 여러 행위를 할 수 있는데 가장 빠른 방법을 찾는 문제는 대부분 BFS로 풀리는 경우가 많다. 따라서 이 문제도 X-1, X+1, 2X로 이동할 수 있는데 가장 빠른 시간을 찾기 때문에 BFS로 풀어야 한다.

 한 layer마다 Queue의 값에 따라 이동할 수 있는 위치를 새로 queue에 넣는다. 이 과정을 반복하다가 원하는 위치로 이동했다면(dist[k]의 값이 갱신 되었다면) queue를 종료하도록 해서 답을 출력하도록 했다.

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
import queue
n,k=map(int,input().split())
check=[0]*200000
dist=[0]*200000
check[n]=1
q=queue.Queue()
q.put(n)
while q.qsize():
    number=q.get()
    if number-1 >=0:
        if check[number-1]==0:
            q.put(number-1)
            check[number-1]=1
            dist[number-1]=dist[number]+1
    if number+1 < 200000:
        if check[number+1]==0:
            q.put(number+1)
            check[number+1]=1
            dist[number+1]=dist[number]+1
    if 2*number < 200000:
        if check[2*number]==0:
            q.put(2*number)
            check[2*number]=1
            dist[2*number]=dist[number]+1
    if dist[k]:
        break
print(dist[k])
cs

 

문제 링크:

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

728x90
반응형

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

[BOJ]1759. 암호 만들기  (0) 2019.09.24
[BOJ]14889. 스타트와 링크  (0) 2019.09.23
[BOJ]2022. 사다리  (0) 2019.09.21
[BOJ]1561. 놀이공원  (0) 2019.09.20
[BOJ]1080. 행렬  (0) 2019.09.19
728x90
반응형

문제:

아래의 그림과 같이 높은 빌딩 사이를 따라 좁은 길이 나있다. 두 개의 사다리가 있는데 길이가 x인 사다리는 오른쪽 빌딩의 아래를 받침대로 하여 왼쪽 빌딩에 기대져 있고 길이가 y인 사다리는 왼쪽 빌딩의 아래를 받침대로 하여 오른쪽 빌딩에 기대져 있다. 그리고 두 사다리는 땅에서부터 정확하게 c인 지점에서 서로 교차한다. 그렇다면 두 빌딩은 얼마나 떨어져 있는 걸까?

입력:

첫째 줄에 차례대로 x,y,c에 해당하는 양의 실수 세 개가 입력된다. 수는 소수점 여섯째 자리까지 주어질 수 있다.

 

출력:

두 빌딩사이에 너비가 되는 수치를 출력한다. 절대/상대 오차는 10^-3까지 허용한다.

 

풀이방법:

 이분 탐색을 기반으로 하지만 수학적인 내용이 더 많이 들어가는 문제인 것 같다. 문제의 기본 틀은 두 빌딩 사이의 거리를 d라고 했을 때, 이를 이분 탐색으로 값을 바꾸어 간다. 임의의 d에 따라서 사다리가 교차하는 높이 h가 달라질 것이다. 따라서 이분탐색을 통해서 그 중 c와 같아지는 d를 찾도록 한다.

 임의의 d에 따라서 h를 구하는 방법은 수학의 닮음을 사용하도록 해야 한다. 사다리가 교차하는 높이를 h라 하고 선을 다음과 같이 그리면 닮음 꼴인 직각 삼각형을 얻을 수 있다.

h라는 직선이 생김에 따라 d도 d1과 d2로 나뉘게 될 것이고, h1과 h2도 다음과 같이 정의를 할 수 있을 것이다.

그러면 빗변이 x인 삼각형과 y인 삼각형에 각각 다음과 같은 닮음비를 얻을 수 있다.

 

[위]빗변이 x, [아래]빗변의 y

 우리가 최종적으로 원하는 변수는 h이기 때문에 h=( ~ ) 와 같은 형태로 변형시켜야 할 것이다. 그러기 위해서는 d1+d2 = d임을 알고 있기 때문에 이를 활용해서 변수를 줄이도록 하자.

 

닮음비의 성질
d1과 d2에 관한 식으로 정리

그러기 위해서는 일단 닮음비를 정리해서 d1과 d2에 관한 식으로 만들었다. 그리고 난 뒤에 위 두 식을 더한다면 d1과 d2를 d로 바꿀 수 있게 될 것이다.

 

d1+d2=d이다.

 이제 양변을 각각 d로 나눌 수 있을 것이다. d는 두 빌딩 사이의 거리이므로 0을 초과한 거리일 것이다. 따라서 양변을 나누는 것에 문제가 없다.

 그러면 위 그림의 제일 위의 식과 같이 얻을 수 있을 것이고 좌변을 h에 대해서 묶을 수 있게 될 것이다. 좌변을 h로 묶고 난 뒤에 남은 것들을 우변으로 넘겨준다면 이를 h에 대한 식으로 만들 수 있을 것 이다. 따라서 위 그림의 두번째와 세번째 식은 그 과정을 담고 있다.

 h1과 h2는 x, y, d로 이루어진 변수이기 때문에 정확한 값을 계산할 수 있다. (d는 이분 탐색으로 정해진 값이다.) 따라서 h의 값을 구할 수 있을 것이고 이를 c와 비교하면서 c에 근접하게 d를 이분탐색으로 찾을 수 있을 것이다.

그렇게 찾은 mid값을 소숫점 셋째 자리까지 반올림해서 출력하도록 한다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
import math
x,y,c=map(float,input().split())
left,right=0,min(x,y)
while(abs(right-left)>1e-6):
    mid=(left+right)/2.0
    d=mid
    h1=math.sqrt(x*x-d*d)
    h2=math.sqrt(y*y-d*d)
    h=(h1*h2)/(h1+h2)
    if h > c:
        left=mid
    else:
        right=mid
print("%.3f"%round(mid,3))
cs

문제링크:

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

 

728x90
반응형

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

[BOJ]14889. 스타트와 링크  (0) 2019.09.23
[BOJ]1697. 숨바꼭질  (0) 2019.09.22
[BOJ]1561. 놀이공원  (0) 2019.09.20
[BOJ]1080. 행렬  (0) 2019.09.19
[BOJ]10610. 30  (0) 2019.09.18
728x90
반응형

문제:

N명의 아이들이 한 줄로 줄을 서서 놀이공원에서 1인승 놀이기구를 기다리고 있다. 이 놀이공원에는 총 M종류의 1인승 놀이기구가 있으며, 1번부터 M번까지 번호가 매겨져 있다.

모든 놀이기구는 각각 운행 시간이 정해져 있어서, 운행 시간이 지나면 탑승하고 있던 아이는 내리게 된다. 놀이 기구가 비어 있으면 현재 줄에서 가장 앞에 서 있는 아이가 빈 놀이기구에 탑승한다. 만일 여러 개의 놀이기구가 동시에 비어 있으면, 더 작은 번호가 적혀 있는 놀이기구를 먼저 탑승한다고 한다.

놀이기구가 모두 비어 있는 상태에서 첫 번째 아이가 놀이기구에 탑승한다고 할 때, 줄의 마지막 아이가 타게 되는 놀이기구의 번호를 구하는 프로그램을 작성하시오.

 

입력:

첫째 줄에 N(1<=N<=2,000,000,000)과 M(1<=M<=10,000)이 빈칸을 사이에 두고 주어진다. 둘째 줄에는 각 놀이기구의 운행 시간을 나타내는 M개의 자연수가 순서대로 주어진다. 운행 시간은 1 이상 30 이하의 자연수이며, 단위는 분이다.

 

출력:

첫째 줄에 마지막 아이가 타게 되는 놀이기구의 번호를 출력한다.

 

풀이 방법:

이분 탐색을 사용해서 풀어야 하는 문제이다. 항상 이러한 이분 탐색을 사용해서 푸는 문제들은 찍어서 최적의 값을 맞춰나간다 라는 느낌이 강하다. 따라서 이 문제도 역시 일정 값을 찍어서 근처로 구하고 그 값으로 부터 놀이기구의 번호를 찾도록 하였다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
n,m=map(int,input().split())
times=list(map(int,input().split()))
left,right=0,10**20
answer=0
B_p=0
while(left<=right):
    mid=(left+right)//2
    temp=0
    for time in times:
        temp += ((mid-1)//time)+1
    if temp < n:
        if answer < mid:
            answer = mid
            B_p = temp
        left = mid + 1
    else:
        right = mid - 1
for i in range(m):
    if answer%times[i]==0:
        B_p+=1
        if B_p == n:
            print(i+1)
            break
cs

문제링크:

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

 

728x90
반응형

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

[BOJ]1697. 숨바꼭질  (0) 2019.09.22
[BOJ]2022. 사다리  (0) 2019.09.21
[BOJ]1080. 행렬  (0) 2019.09.19
[BOJ]10610. 30  (0) 2019.09.18
[BOJ]2875. 대회 or 인턴  (0) 2019.09.17

+ Recent posts