live the life you love

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..

코딩테스트 연습 - 괄호 변환 카카오에 신입 개발자로 입사한 콘은 선배 개발자로부터 개발역량 강화를 위해 다른 개발자가 작성한 소스 코드를 분석하여 문제점을 발견하고 수정하라는 업무 과제를 받았습니다. 소스를 컴 programmers.co.kr 카카오 기출문제이다. 괄호 관련된 문제가 약해서 풀어보려는데, 역시나 실수가 많이 나왔다. 막상 다 풀고보면 문제에 있는 말 그대로를 구현하는 것인데.. 아직 구현력이 부족한 듯 하다. 문제 조건 입력이 빈 문자열인 경우, 빈 문자열을 반환합니다. 문자열 w를 두 "균형잡힌 괄호 문자열" u, v로 분리합니다. 단, u는 "균형잡힌 괄호 문자열"로 더 이상 분리할 수 없어야 하며, v는 빈 문자열이 될 수 있습니다. 문자열 u가 "올바른 괄호 문자열" 이라면 문자..

문제를 풀다보면 배열을 시계방향으로 90도로 회전하는 문제들이 많다. ex) 백준 18808번 스티커 붙이기 예를 들어 3x4 리스트를 시계방향으로 90도씩 회전하면 아래와 같이 만들어진다. 총 4번의 회전이 끝나면 360도가 되어 원래 모양으로 되돌아 온다. 이를 파이썬에서는 2가지 방법으로 구현할 수 있다. 일반적인 방법 import copy _list = [[1,2,3], [4,5,6], [7,8,9], [10,11,12]] n = len(_list) m = len(_list[0]) result = [[0]* n for _ in range(m)] for i in range(n): for j in range(m): result[j][n-i-1] = _list[i][j] _list = copy.deep..

MST(Minimum Spanning Tree) - Kruskal MST는 최소 신장 트리로, 신장 트리를 의미하는 Spanning Tree는 그래프 내의 모든 정점을 포함하는 트리를 의미한다. 이 중 가중치가 최소가 되는 트리가 최소 신장 트리 MST 이다. MST를 구현하는 방법에는 대표적으로 Prim 알고리즘과 Kruskal 알고리즘이 있다. 여기서는 Kruskal 알고리즘을 사용하였다. 통신망, 도로망, 유통망 등에서 길이, 구축 비용, 전송 시간등을 최소로 구축하려는 경우 사용된다 최소 스패닝 트리란? 스패닝 트리란 방향이 없는 그래프에서 모든 노드를 포함하면서, 순환되는 경로를 제거한 형태이다. 이 스패닝 트리에서 가중치의 합을 최소로 만드는 스패닝 트리를 '최소 스패닝 트리(Minim..

MST(Minimum Spanning Tree) MST는 최소 신장 트리로, 신장 트리를 의미하는 Spanning Tree는 그래프 내의 모든 정점을 포함하는 트리를 의미한다. 이 중 가중치가 최소가 되는 트리가 최소 신장 트리 MST 이다. MST를 구현하는 방법에는 대표적으로 Prim 알고리즘과 Kruskal 알고리즘이 있다. 여기서는 Prim 알고리즘을 사용하였다. 통신망, 도로망, 유통망 등에서 길이, 구축 비용, 전송 시간등을 최소로 구축하려는 경우 사용된다 관련 문제 백준 1197번 최소 스패닝 트리 백준 1922번 네트워크 연결 기본 개념 하나의 정점에서 시작 간선의 가중치의 합이 최소이다 사이클이 포함되어서는 안된다. 시간 복잡도 O(ElogV) --> E : 간선의 개수, V : 정점의 ..

www.acmicpc.net/problem/14500 14500번: 테트로미노 폴리오미노란 크기가 1×1인 정사각형을 여러 개 이어서 붙인 도형이며, 다음과 같은 조건을 만족해야 한다. 정사각형은 서로 겹치면 안 된다. 도형은 모두 연결되어 있어야 한다. 정사각형의 변 www.acmicpc.net 문제를 잘 읽자! 문제를 잘 못 읽어서 1시간을 고민하다가 질문검색을 통해 코드를 보고 문제를 잘못 읽은것을 깨달았다. 테트로미노 "하나"를 적절히 놓아서 테트로미노가 놓인 칸에 쓰여 있는 수들의 합을 최대로 하는 프로그램을 작성하시오. 주어진 종이에 여러 종류의 테트로미노를 놓고 그 중에 최대를 구하는 것이 아니다. 최대 500x500 크기의 종이에 테트로미노 1개를 놓고 놓인 부분의 합이 최대가 되는 것을 ..

최장증가부분수열 Longest Increasing Subsequence 문제 예시) 수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이고, 길이는 4이다. 관련 문제 백준 11055번 가장 큰 증가 부분 수열 백준 1965번 상자 넣기 백준 11053번 가장 긴 증가하는 부분 수열 LIS를 해결하는 방법은 두가지가 있다. N의 크기, 문제의 조건에 따라 아래 두 방법중 적절한 것을 사용하면 된다. 방법 1 : 이중 for-loop 시간복잡도 : O(n^2) dp 배열은 i 번째 원소가 가질 수 있는 최대증가..

Floyd-Warshall Floyd-Warshall은 모든 정점에 대해 모든 다른 정점에 대한 최단 경로를 다 구하는 것이다. 또한, 음수 가중치의 경우도 구할 수 있다. 알고리즘은 비교적 간단하다. 관련 문제 백준 11404번 플로이드 기본 개념 3중 for loop 사용 방향, 무방향 그래프 둘다 사용가능, 사이클이 생기면 안된다 음의 가중치 적용 가능 a->b로 가는 최단거리가 a->c->b보다 크면 그 값을 갱신한다 아래의 조건문이 핵심이다 if (arr[i][k] + arr[k][j] < arr[i][j]) { // k를 거쳐가는게 더 작으면 arr[i][j] = arr[i][k] + arr[k][j]; // arr[i][j] 값 갱신 } 시간 복잡도 O(n^3) floyd 구현 각 반복문의 ..