재밌는 코딩 공부

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

해당 문제는 간단해 보였지만 방문할 수 있는 정점이 여러 개인 경우에는 정점 번호가 작은 것을 먼저 방문 하라는 조건 때문에 응근히 까다롭게 느껴졌다.

n, m, v = map(int, input().split())
graph1 = {}
visited = list()
visited_dfs = list()
need_visited = list()
need_visited.append(v)
need_visited_dfs = list()
need_visited_dfs.append(v)

for _ in range(m):
    key, value = map(int, input().split())
    if key in graph1:
        graph1[key].append(value)
    else:
        graph1[key] = [value]

while need_visited:
    vertex = need_visited.pop(0)
    if vertex not in visited:
        visited.append(vertex)
        if vertex in graph1:
            need_visited.extend(graph1[vertex])

while need_visited_dfs:
    vertex = need_visited_dfs.pop()
    if vertex not in visited_dfs:
        visited_dfs.append(vertex)
        if vertex in graph1:
            need_visited_dfs.extend(graph1[vertex])
print(visited)
print(visited_dfs)

위 코드가 처음에 작성한 코드였다. 정점 번호가 작은걸 우선 방문하라는 조건을 빼면 일반 DFS, BFS 기능은 나온 것 같다. 작은걸 우선 방문하라는 조건을 지키기 위해서는 DFS와 BFS의 정렬 순서가 역정렬이 되어야 조건을 충족시킬 수 있을 것으로 보인다. 

아래 코드가 답코드이다.

from collections import deque

def dfs(v):
    print(v, end= ' ')
    visited[v] = True
    for e in adj[v]:
        if not(visited[e]):
            dfs(e)
def bfs(v):
    q = deque([v])
    while q:
        v = q.popleft()
        if not(visited[v]):
            visited[v] = True
            print(v, end=' ')
            for e in adj[v]:
                if not visited[e]:
                    q.append(e)
    
n, m, v = map(int, input().split())
adj = [[] for _ in range(n+1)]

for _ in range(m):
    x, y = map(int, input().split())
    adj[x].append(y)
    adj[y].append(x)
for e in adj:
    e.sort()
    
visited = [False] * (n + 1)
dfs(v)
print()
visited = [False] * (n + 1)
bfs(v)

deque를 사용하는 이유는 그냥 list를 사용하는거 보다 성능상 유리한 면이 있어서인 것 같다.

import java.util.ArrayList;

생성

ArrayList<Integer> arrayList1 = new ArrayList<Integer>();

추가

arrayList1.add(3);

삭제

arrayList1.remove(0);

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

N, S, M = map(int,input().split())
vols = list(map(int,input().split()))
sounds = list()
sounds.append(-1)

def vol_control(now,volumns, start, M):
    if now !=N-1:
        if start + volumns[now] <= M:
            vol_control(now+1, volumns, start + volumns[now], M)
        if start - volumns[now] >= 0:
            vol_control(now+1, volumns, start - volumns[now],M)
    else:
        if start + volumns[now] <= M:
            sounds.append(start + volumns[now])
        if start - volumns[now] >= 0:
            sounds.append(start - volumns[now])

vol_control(0,vols,S,M)
print(max(sounds))

위 문제를 위와같은 공식으로 풀었지만 메모리 초과 오류가 난다.

n, s, m = map(int, input().split())
array = list(map(int, input().split()))

dp = [[0]*(m+1) for _ in range(n+1)]
dp[0][s] = 1

for i in range(1, n+1):
    for j in range(0, m+1):
        if dp[i-1][j] != 0:
            if j + array[i-1] <= m:
                dp[i][j+array[i-1]] = 1
            if j - array[i-1] >= 0:
                dp[i][j-array[i-1]] = 1
                
result = -1
for i in range(m, -1, -1):
    if dp[n][i] == 1:
        result = i
        break
print(result)

해서 아래 방식으로 해결하였다 약간 계수 정렬을 사용한 느낌의 코드이다.

def mergeSort(array):
    if len(array) <= 1:
        return array
    left, right = list(), list()
    mid   = len(array) // 2
    left  = mergeSort(array[:mid])
    right = mergeSort(array[mid:])
    
    i, j, k = 0, 0, 0
    
    while i < len(left) and j < len(right):
        if left[i] < right[j]:
            array[k] = left[i]
            i +=1
        else :
            array[k] = right[j]
            j+=1
        k +=1
    if i == len(left):
        while j < len(right):
            array[k] = right[j]
            j += 1 
            k += 1
    if j == len(right):
        while i < len(left):
            array[k] = left[i]
            i +=1
            k +=1
    return array
    
n = int(input())
nList = []
for _ in range(n):
    nList.append(int(input()))
nList = mergeSort(nList)
for data in nList:
    print(data)

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

위 문제를 pypy3 을 활용해서 해결하면 되는데 python3은 해결되지않는다.

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

data = int(input())
n_list = [0]*46

def fibo(data):
    n_list[0] = 0
    n_list[1] = 1
    if data == 0:
        return 0
    if data == 1:
        return 1
    for i in range(2,len(n_list)):
        n_list[i] = n_list[i-1]+n_list[i-2]
        if i == data:
            return n_list[data]
print(fibo(data))

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

import sys

n = int(sys.stdin.readline())
array = [0]*10001

for i in range(n):
    data = int(sys.stdin.readline())
    array[data] += 1
    
for i in range(10001):
    if array[i] != 0:
        for j in range(array[i]):
            print(i)

import sys를 사용해서 그런지 런타임 에러가 발생한다.

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

testCase = int(input())
cus_info = list()

for _ in range(testCase):
    age, name = input().split()
    cus_info.append([int(age), name])
cus_info = sorted(cus_info, key = lambda x:x[0])
for cus in cus_info:
    print(cus[0], cus[1])

위 코드는 sorted 함수에 인자 값으로 key = lambda x:x[0] 을 매개변수로 주어 2개의 원소중 나의 값만으로 정렬 되게 한 것이 핵심 포인트이다.

https://programmers.co.kr/learn/courses/30/lessons/42746?language=python3 

from itertools import permutations

def solution(numbers):
    
    numbers = list(map(str,numbers))
    strs = []
    permus = list(permutations(numbers,len(numbers)))

    for permu in permus:
        str1 = ''
        str1 = str1.join(permu)
        strs.append(str1)
            
    return max(strs)

위 코드는 기능은 잘 되는 것 같지만 시간 초과로 아쉽게 코딩 테스트를 통과할 수 없었다. 하지만 permutations 라이브러리를 익힐 수 있는 좋은 예제 코드로 탄생한 것 같아 기록에 남긴다. 

i번 숫자부터 j번째 숫짜까지 자르려고 한다면 아래와 같은 방법으로 사용할 수 있다.

Arrays.copyOfRange(배열, i-1, j)

그리고 자른 배열을 사용하기위해 아래와 같이 사용한다.

int[] arr1 = Arrays.copyOfRange(배열,i-1, j)

정렬에 필요한 라이브러리 임포트

import java.util.Arrays;

정렬

Arrays.sort(arr);

정렬은 String도 가능해보이며 결과로 봤을때 알파벳 순으로 정렬하는 것 같다.

역정렬

Arrays.sort(arr,Collections.reverseOrder());