live the life you love

www.acmicpc.net/problem/9376 9376번: 탈옥 상근이는 감옥에서 죄수 두 명을 탈옥시켜야 한다. 이 감옥은 1층짜리 건물이고, 상근이는 방금 평면도를 얻었다. 평면도에는 모든 벽과 문이 나타나있고, 탈옥시켜야 하는 죄수의 위치도 나타 www.acmicpc.net 첫 플레문제였다. 단순히 다익스트라나 BFS로 하면 될 것 같았는데 아무리 고민을 해도 시간복잡도를 알맞게 할 수 없을 것 같아서 다른 블로그를 보고 풀었다. 찾아보니 이런 유형의 문제는 0-1 BFS라고 한다. 가중치가 0과 1만 있는 그래프에서 사용할 수 있는데, 기존의 BFS는 방향탐색을 마치고, 다음에 갈 지점을 큐에 삽입할 때 단순히 큐의 맨뒤에 push 했다. 또한, 다익스트라의 경우도 우선순위 큐를 사용하여 항..

www.acmicpc.net/problem/10711 10711번: 모래성 첫째 줄에는 모래성의 가로세로 격자 크기 H, W가 주어진다. (1 ≤ H, W ≤ 1,000) 그 다음 H줄에 걸쳐 W개의 문자로 모래성의 상태를 나타내는 문자가 들어온다. 각 문자는 1~9 사이의 숫자, 또는 '.' 이 www.acmicpc.net 맨 처음에는 단순히 전체 배열을 탐색하는 BFS 코드를 짰더니 시간 초과가 발생했다. 최악의 경우 O(N^3) 까지 들어 올 수 있기 때문에 그렇다. 그래서 조금 다른 방법을 사용했다. 비어있는 부분의 위치를 모두 큐에 삽입하고, 이를 기준으로 BFS 탐색을 한다. 8방 탐색을 하는 동안 모래성을 만나면 해당 모래성에서 1을 빼주고, 큐에서 popleft를 한다. 만약 모래성의 값이..

Pod내의 컨테이너에 접속하기 # Deprecated $ kubectl exec -it [Pod_Name] /bin/bash # Recommended $ kubctl exec -it [Pod_Name] -- bash Namespace 확인, 생성, 교체 $ kubectl create ns {namespace_name} # 생성 $ kubectl get ns # 확인 $ kubectl config set-context --current --namespace={namespace_name} # 현 위치에서 namespace 변경 Node에 태그 붙이기 # kubectl label nodes [node 이름] [key=value] $ kubectl label nodes aks-agentpool-19228959-..

이슈 트래킹 및 협업 툴 사용을 위해 Jira Server를 구축해봤다. 참고 블로그 (여기서는 DB를 mariadb를 쓰는데, mysql로 설치) How to Install Jira Project Management Software on Ubuntu 18.04 | 16.04 This brief tutorial shows students and new users how to install Jira project management platform on Ubuntu 18.04 | 16.04 servers. Jira is a proprietary project management software from Atlassian which… websiteforstudents.com VM 및 설치 소프트웨어 정보 L..

www.acmicpc.net/problem/14620 14620번: 꽃길 2017년 4월 5일 식목일을 맞이한 진아는 나무를 심는 대신 하이테크관 앞 화단에 꽃을 심어 등교할 때 마다 꽃길을 걷고 싶었다. 진아가 가진 꽃의 씨앗은 꽃을 심고나면 정확히 1년후에 꽃이 피므 www.acmicpc.net 백트래킹을 활용하는 문제였다. dfs 함수에서 반복문을 돌면서 백트래킹을 하는 부분을 블로그 참고해서 풀었다. 소스 코드 import sys sys.stdin = open("input.txt", "r") flower_dir = [(0,0),(-1,0),(1,0),(0,-1),(0,1)] # 현위치, 상, 하, 좌, 우 n = int(input()) board = [list(map(int, input().spl..

가끔 알고리즘 문제에 나오는 소수계산을 위해 정리하는 글이다.소수란, 1과 자기 자신 이외에 약수를 가지지 않는 1보다 큰 자연수 이다. 1은 소수가 아니다 소수 판별 알고리즘은 대표적으로 두가지 방법으로 구현 할 수 있다. 일반적인 방법 우선, 반복문을 사용하는 것이다. 이 방법은 1개의 숫자가 소수인지 아닌지 판별하는데 사용하면 좋다. 여러 숫자를 소수 판별해야하는 경우는 아래 있는 에라토스테네스의 체가 더 유용하다. n이라는 숫자가 소수인지 확인하기 위해서는 2부터 n-1까지 나눠보면서 나머지가 0이 나오는 숫자가 한개도 없으면 n은 소수이다. 하지만 n-1까지 나눠보지 않더고 √n 까지만 확인해봐도 된다. 소스코드 import sys, math # 소수 판별 알고리즘 : 제곱근까지 구하기 def ..

www.acmicpc.net/problem/1747 1747번: 소수&팰린드롬 어떤 수와 그 수의 숫자 순서를 뒤집은 수가 일치하는 수를 팰린드롬이라 부른다. 예를 들어 79,197과 324,423 등이 팰린드롬 수이다. 어떤 수 N (1 ≤ N ≤ 1,000,000)이 주어졌을 때, N보다 크거나 같고, www.acmicpc.net 소수 판별과 팰린드롬을 사용하는 문제이다. 파이썬의 경우 팰린드롬은 굉장히 쉽게 판별할 수 있으므로 패스한다. 소수 판별은 에라토스테네스의 체 2부터 제곱근까지 나머지 확인 2가지 방식으로 테스트를 해봤는데, 시간복잡도는 크게 차이나지 않는 것 같다. 다만, 소수의 갯수보다 팰린드롬의 갯수가 더 많으므로 팰린드롬인지 확인해주는 것을 먼저 해주는게 시간복잡도 측면에서 효율적이..

4358번: 생태학 (acmicpc.net) 4358번: 생태학 프로그램은 여러 줄로 이루어져 있으며, 한 줄에 하나의 나무 종 이름이 주어진다. 어떤 종 이름도 30글자를 넘지 않으며, 입력에는 최대 10,000개의 종이 주어지고 최대 1,000,000그루의 나무가 주어 www.acmicpc.net 문제는 골드 4였지만, 딕셔너리를 사용하면 쉽게 풀리는 문제다. 단순한 딕셔너리가 아니라, defaultdict를 썼다면 if, else 분기를 안해도 됐을 것이다. 주의해야할 부분은 다음과 같다. 입력 소숫점 넷째짜리까지 계산 소숫점 넷째짜리까지 출력 우선 입력이 밑도 끝도 없이 들어와서 밑도 끝도 없이 끝난다. 들어오는 나무의 개수라도 알려주면 좋겠지만 그딴게 없다. 더 이상 입력이 들어오지 않을 때 까..

www.acmicpc.net/problem/15565 15565번: 귀여운 라이언 꿀귀 라이언 인형과, 마찬가지로 꿀귀인 어피치 인형이 N개 일렬로 놓여 있다. 라이언 인형은 1, 어피치 인형은 2로 표현하자. 라이언 인형이 K개 이상 있는 가장 작은 연속된 인형들의 집합의 www.acmicpc.net 슬라이딩 윈도우를 활용하는 문제였다. 문제에서 K개 이상의 라이언 인형을 포함하는 가장 작은 연속된 인형들의 집합의 크기를 구하라고 했으므로 일단 어피치는 신경쓰지말고 라이언 인형이 딱 K개가 되는 구간만 확인해주면 된다. 항상 K개가 되는 것을 확인해야 하므로 슬라이딩 윈도우를 활용할 수 있는 것이다. 예제에서 라이언 인형의 위치는 0, 4, 6, 9 이다. 라이언 인형은 총 4개가 있으며 K가 3이기 ..

www.acmicpc.net/problem/11659 11659번: 구간 합 구하기 4 첫째 줄에 수의 개수 N과 합을 구해야 하는 횟수 M이 주어진다. 둘째 줄에는 N개의 수가 주어진다. 수는 1,000보다 작거나 같은 자연수이다. 셋째 줄부터 M개의 줄에는 합을 구해야 하는 구간 i와 j www.acmicpc.net 누적 합을 구해놓으면 쉽게 풀리는 문제였다. 단, python의 경우 input( )이 아닌 sys.stdin.readline()을 써야 시간초과에 걸리지 않는다. 소스코드 import sys n, m = map(int, sys.stdin.readline().split()) _list = list(map(int, sys.stdin.readline().split())) _sum = [0 f..