수학과의 개발자 도전기

- 문제 : https://www.acmicpc.net/problem/1654

Silver Lv2 문제이고, 스스로 푼 문제다!

알고리즘 수업 때 들은 내용이 어렴풋이 기억나서 적용했다. 

풀이 과정 

• 각 랜선의 길이의 길이를 합한 다음 목표 갯수로 나누어서 원하는 결과를 만들기 위한 최대 길이를 구한다.
• 그 길이를 가장 끝점 이라고 정한뒤 이분탐색을 진행한다.
  • 각 단계에서 랜선을 얼마나 자를지 길이를 mid로 정한다. 
  • 각 랜선을 mid로 자른뒤 나오는 총 갯수를 result에 저장한다. 
  • result가 k 이상이라면, result로 만들 수 있는 총 갯수를 answer에 누적해간다.(문제에서 k개 이상 만들 수 있는 경우는 모두 정답으로 친다고 했다)
  • result가 k 초과라면 mid의 크기가 너무 커서 만들어지는 랜선의 갯수가 적은 것이므로 right를 줄여준다. 
  • answer에는 k개를 만들 수 있는 랜선의 길이들이 있으므로, 그 중에서 최댓값을 출력한다. 

- 정답 풀이 : 

import sys
input = sys.stdin.readline

n, k = map(int, input().split())
wires = [int(input()) for _ in range(n)]

answer = [] 
left, right = 0, sum(wires) // k 
while left <= right : 
    mid = (left + right + 1) // 2
    result = 0
    for wire in wires:
        result += wire // mid
    
    if result >= k:
        answer.append(mid)
        left = mid + 1
    else:
        right = mid - 1

print(max(answer))

신기하게 Pypy3로 돌릴 때보다 Python으로 돌렸을 때 시간이 더 짧다 

- 문제 : https://www.acmicpc.net/problem/10816

Silver Lv4 문제이고, 스스로 푼 문제다!

먼저 떠오른 건 arr1의 각 원소가 총 몇 개씩 있는지 딕셔너리로 표현한 다음, arr2의 원소들이 arr1에 몇 개 있는지 누적하면 풀릴 것이라고 생각했다. 근데 이건 이분탐색으로 푼 게 아니라 이분탐색으로 어떻게 푸는지 알아봐야할 것 같다. 

- 정답 풀이 : 

from collections import Counter

n = int(input())
arr1 = list(map(int, input().split()))
m = int(input())
arr2 = list(map(int, input().split()))

#arr2 원소 돌면서 arr1에 원소가 몇개 있는지 확인하면 될 듯 
dic = Counter(arr1)
answer = [0] * m 
for i in range(m):
    answer[i] = dic[arr2[i]]
    
for i in range(m):
    print(answer[i], end = ' ')

- 문제 : https://www.acmicpc.net/problem/1920

Silver4 문제이고, 스스로 푼 문제다!

전형적인 이분탐색 문제였기에 그렇게 어렵지는 않았다. 

다만 mid를 설정할 때 left + right + 1을 2로 나눈 몫으로 해야하는 걸 까먹어서 약간 헤맸다. 

- 정답 풀이1 : 

이분 탐색으로 푸는게 확실히 이중 탐색보다 5배 정도 시간이 빠른 것 같다. 

import sys
input = sys.stdin.readline

n = int(input())
arr1 = list(map(int, input().split()))
m = int(input())
arr2 = list(map(int, input().split()))
arr1.sort()

#arr2에 있는 원소들이 arr1에 있는지 여부 확인
answer = [0] * m
for i in range(m):
    if answer[i] == 1:
        continue
        
    left, right = 0, n - 1
    target = arr2[i]
    while left <= right:
        mid = (left + right + 1) // 2
        if arr1[mid] == target:
            answer[i] = 1
            break
        if target < arr1[mid]:
            right = mid - 1
        else:
            left = mid + 1
            
            
for i in range(m):
    print(answer[i])

- 정답 풀이2 : 

문제 보자마자 작성한 코드. 이렇게 하면 Python으로 돌렸을 때 10%에서 시간초과가 나고, Pypy3으로 돌리면 좀 오래 걸리지만 통과한다. 

n = int(input())
arr1 = list(map(int, input().split()))
m = int(input())
arr2 = list(map(int, input().split()))
arr1.sort()

#arr2에 있는 원소들이 arr1에 있는지 여부 확인
answer = [0] * m
for i in range(m):
    if arr2[i] in arr1:
        answer[i] = 1

for i in range(m):
    print(answer[i])

- 문제 : https://www.acmicpc.net/problem/16929

Gold Level4 문제 

같은 색인 점을 탐색하다가 그것이 사이클을 이루는 경우는 Yes, 아닌 경우는 No를 출력하는 문제였다

탐색하는 건 괜찮은데, 여전히 사이클을 이루는지 확인하는 것에서 막혔다 

사이클이 되는 조건은 시작 점에 다시 도착하는 것이고, 지나온 점의 갯수가 4개 이상이 되는 것이다.

시작하는 점과 지나온 점의 갯수를 파라미터에 넣어서 같이 탐색 돌리면 된다 

각 점마다 visit도 초기화하고, 각 점을 시작으로 사이클을 찾는 방법인 것 같다 

- 정답 풀이 :

n,m = map(int,input().split())
data = []
dx = [-1,1,0,0]
dy = [0,0,-1,1]

for _ in range(n):
    data.append(list(input()))

def dfs(x,y,letter,count,sx,sy):
    global flag
    for i in range(4):
        nx,ny = x + dx[i], y + dy[i]
        if 0 <= nx < n and 0 <= ny < m:
            if not visit[nx][ny] and data[nx][ny] == letter:
                visit[nx][ny] = 1
                dfs(nx,ny,letter,count+1,sx,sy)
            elif count >= 4 and sx == nx and sy == ny:
                flag = True
                return          
                
flag = False                                               
for i in range(n):
    for j in range(m):
        sx,sy=i,j
        visit = [[0]*m for _ in range(n)]
        visit[sx][sy] = 1
        dfs(i,j,data[i][j],1,sx,sy)
        if flag:
            print('Yes')
            exit()
        
if not flag:
    print('No')