티스토리

great_park

검색하기

블로그 홈

great_park

great-park.tistory.com/m

GitHub : https://github.com/great-park

구독자: 7

방명록 방문하기

주요 글 목록

[2023 Google Solution Challenge] Global Top 10 진출 들어가며올해 1월 달, 고려대학교 GDSC (Google Developer Student Club)에 들어가게 되었다. 당시 진행했던 큰 프로젝트가 끝나갔고, 종강도 했던 터라 시간적인 여유가 많았었다. 그래서 작년에 활동했던 CMC 처럼 IT 개발 동아리에 들어가 또 다른 프로젝트를 진행하고자 했다. 그러던 중 전세계 대학교에서 구글이 지원하는 학생 개발 동아리인 GDSC에 대해 알게 되었다. 마침 우리 학교에도 막 1기가 생겨서 바로 서류를 넣고, 최종 면접 후 합격하였다. Google Solution ChallengeGDSC 활동 중에서 가장 메인 이벤트라고 할 수 있는 2023 Google Solution Challenge에 참가하였다. https://developers.google.com/com.. 공감수 5 댓글수 1 2023. 6. 3.
[Algorithm] 크루스칼 (Kruskal) 알고리즘 Idea Kruskal Algorithm 크루스칼 알고리즘은 최소 신장 트리, MST 를 찾는 알고리즘입니다. 그래프의 간선을 하나씩 늘리면서 가중치가 최소인 간선부터 추가하는 Greedy 방식을 사용합니다. 즉, 간선을 추가하는 각 단계에서 사이클을 이루지 않는 최소 비용 간선을 선택하며 MST를 만들어가는 알고리즘입니다. 동작 과정 그래프의 간선들을 가중치의 오름차순으로 정렬한다. 정렬된 간선 리스트에서 순서대로 사이클을 형성하지 않는 간선을 선택한다. - 즉, 가장 낮은 가중치를 먼저 선택한다. - 사이클을 형성하는 간선을 제외한다. 해당 간선을 현재의 MST(최소 비용 신장 트리)의 집합에 추가한다. 각 단계에서 간선 선택을 Greedy하게 실시 하고, 이전 단계에서 만들어진 신장 트리와는 상관없.. 공감수 0 댓글수 0 2023. 5. 22.
[Algorithm] Spanning Tree와 MST (Minimum Spanning Tree) Idea Spanning Tree Spanning tree는 그래프 내의 모든 정점을 포함하는 트리를 의미합니다. 그래프의 일부 간선을 이용해 만든 트리로서 항상 그래프의 부분집합이 됩니다. 이때 간선의 개수가 최소이어야 하며, 따라서 최소 연결 부분 그래프라고도 합니다. N개의 정점에 대해서 모든 정점을 포함하는 트리를 만들기위해서는 최소 N-1개의 간선이 필요합니다. 따라서 Spanning Tree는 그래프에 있는 n개의 정점을 정확히 (n-1)개의 간선으로 연결합니다. 이때 사이클을 포함해서는 안됩니다. MST (Minimum Spanning Tree) MST는 한 그래프에 대한 Spanning Tree 중에서 간선들의 가중치 합이 최소인 트리를 의미합니다. 그림에서 아래 3개의 신장 트리 중에서 .. 공감수 0 댓글수 0 2023. 5. 22.
[Algorithm] 유니온 파인드 (Union-Find) 알고리즘 Union-Find Idea 유니온 파인드 알고리즘은 두 노드가 같은 그래프에 속하는지 판별하는 알고리즘입니다. 노드를 합치는 Union 연산과 root 노드를 찾는 Find 연산으로 이루어집니다. 이러한 연산을 토대로 서로소 집합(공통 원소가 없는 두 집합) 자료 구조라 불리기도 합니다. 기차를 통해 출발지와 도착지를 정해서 이동이 가능한 지 판별하려고 합니다. 그래프를 통해 기차를 타고 서울에서 강릉으로 가는건 가능하지만 서울에서 부산으로 가는건 불가능하다는 것을 알 수 있습니다. 문제는 그래프가 복잡해지면 이러한 판단이 어려워 집니다. Union-Find 알고리즘을 이용하여 복잡한 그래프에서 두 노드가 연결되어 있는지 판별할 수 있습니다. 동작 과정 8개의 단절된 노드들이 있고, 이 노드들은 배열에.. 공감수 0 댓글수 0 2023. 5. 15.
[Algorithm] 플로이드 워셜 (Floyd-Warshall) 알고리즘 Floyd-Warshall Idea 플로이드-워셜 알고리즘은 모든 정점에서 다른 모던 정점까지의 최단 경로를 모두 구하는 알고리즘입니다. 모든 정점에서 다른 모든 정점까지의 최단 거리를 저장해야 하기 때문에 2차원 테이블에 최단 거리 정보를 저장합니다. 경로 계산 방식에는 아래와 같은 종류가 있습니다. 1. (One-To-One) 한 지점에서 다른 특정 지점까지의 최단경로 구하기 2. (One-To-All) 한 지점에서 다른 모든 지점까지의 최단경로 구하기 3. (All-To-All) 모든 지점에서 모든 지점까지의 최단경로 구하기 플로이드 워셜 알고리즘은 이 중 3번째 유형(All-To-All) 입니다. 플로이드 워셜 알고리즘의 점화식은 아래와 같습니다. 3중 반복문을 이용하여 위 점화식을 기준으로 테이.. 공감수 0 댓글수 0 2023. 5. 15.
[Algorithm] 벨만-포드 (Bellman-Ford) 알고리즘 Bellman-Ford Idea 벨만-포드 알고리즘은 한 정점에서 다른 모든 정점까지의 최단 경로를 구하는 알고리즘입니다. 이때, 다익스트라와 달리 간선의 가중치가 음수인 경우에도 최단 거리를 구할 수 있습니다. 단, 음의 사이클이 없는 그래프에서만 벨만-포드 알고리즘을 적용할 수 있습니다. 이를 위해 한 노드에서 다른 노드까지의 최단 경로를 많아봐야 V-1개의 간선을 지난다는 가정을 세웁니다. 경로 계산 방식에는 아래와 같은 종류가 있습니다. 1. (One-To-One) 한 지점에서 다른 특정 지점까지의 최단경로 구하기 2. (One-To-All) 한 지점에서 다른 모든 지점까지의 최단경로 구하기 3. (All-To-All) 모든 지점에서 모든 지점까지의 최단경로 구하기 벨만-포드 알고리즘은 이 중 2.. 공감수 5 댓글수 2 2023. 5. 8.
[Algorithm] 다익스트라(Dijkstra) 알고리즘 Dijkstra Algorithm Idea 다익스트라 알고리즘은 그래프에서 한 정점에서 모든 다른 정점까지의 최단 경로를 구하는 알고리즘입니다. 매번 최단 경로의 정점을 선택하며 탐색을 반복함으로써 출발 정점에서 나머지 각 정점까지의 최단 경로를 모두 찾게 됩니다. 단, 모든 링크의 가중치(길이)는 양의 정수 값이어야 합니다! 이러한 최단 경로(최소 비용)을 구하는 알고리즘은 다익스트라 알고리즘 외에도 벨만-포드, 플로이드-워샬 알고리즘 등이 있습니다. 경로 계산 방식에는 아래와 같은 종류가 있습니다. 1. (One-To-One) 한 지점에서 다른 특정 지점까지의 최단경로 구하기 2. (One-To-All) 한 지점에서 다른 모든 지점까지의 최단경로 구하기 3. (All-To-All) 모든 지점에서 모든.. 공감수 0 댓글수 2 2023. 5. 8.
[BOJ/백준] 17291번 새끼치기 (Python 파이썬) https://www.acmicpc.net/problem/17291 17291번: 새끼치기 실험실에서 새로운 종의 벌레 한 마리가 탄생하였다. 벌레는 스스로 분열하며, 분열하면 자기 자신과 같은 벌레를 한 마리 만들어 내게 된다. 벌레가 분열하는 규칙은 다음과 같다. 벌레는 기준 www.acmicpc.net 문제 실험실에서 새로운 종의 벌레 한 마리가 탄생하였다. 벌레는 스스로 분열하며, 분열하면 자기 자신과 같은 벌레를 한 마리 만들어 내게 된다. 벌레가 분열하는 규칙은 다음과 같다. 벌레는 기준년도 1년 2월에 1마리가 탄생한다. 벌레는 매년 1월이 되면 분열한다. 분열시 본래의 개체는 그대로, 새로운 개체가 하나 탄생하는 것으로 본다. 홀수년도에 탄생한 개체는 3번 분열시, 짝수년도에 탄생한 개체는.. 공감수 0 댓글수 0 2023. 2. 6.
[BOJ/백준] 1309번 동물원 (Python 파이썬) https://www.acmicpc.net/problem/1309 1309번: 동물원 첫째 줄에 우리의 크기 N(1≤N≤100,000)이 주어진다. www.acmicpc.net 문제 어떤 동물원에 가로로 두칸 세로로 N칸인 아래와 같은 우리가 있다. 이 동물원에는 사자들이 살고 있는데 사자들을 우리에 가둘 때, 가로로도 세로로도 붙어 있게 배치할 수는 없다. 이 동물원 조련사는 사자들의 배치 문제 때문에 골머리를 앓고 있다. 동물원 조련사의 머리가 아프지 않도록 우리가 2*N 배열에 사자를 배치하는 경우의 수가 몇 가지인지를 알아내는 프로그램을 작성해 주도록 하자. 사자를 한 마리도 배치하지 않는 경우도 하나의 경우의 수로 친다고 가정한다. 입력 첫째 줄에 우리의 크기 N(1≤N≤100,000)이 주어진.. 공감수 3 댓글수 0 2023. 2. 6.
[BOJ/백준] 12026번 BOJ 거리 (Python 파이썬) https://www.acmicpc.net/problem/12026 12026번: BOJ 거리 스타트가 링크를 만나는데 필요한 에너지 양의 최솟값을 출력한다. 만약, 스타트가 링크를 만날 수 없는 경우에는 -1을 출력한다. www.acmicpc.net 문제 BOJ 거리는 보도블록 N개가 일렬로 놓여진 형태의 도로이다. 도로의 보도블록은 1번부터 N번까지 번호가 매겨져 있다. 스타트의 집은 1번에 있고, 링크의 집은 N번에 있다. 스타트는 링크를 만나기 위해서 점프해가려고 한다. BOJ거리의 각 보도블록에는 B, O, J 중에 하나가 쓰여 있다. 1번은 반드시 B이다. 스타트는 점프를 통해서 다른 보도블록으로 이동할 수 있다. 이때, 항상 번호가 증가하는 방향으로 점프를 해야 한다. 만약, 스타트가 현재 .. 공감수 1 댓글수 0 2023. 2. 6.
[BOJ/백준] 1633번 최고의 팀 만들기 (Python 파이썬) https://www.acmicpc.net/problem/1633 1633번: 최고의 팀 만들기 꿍 협회는 매년 세계체스대회에 나갈 팀을 만들고 있다. 팀은 흑으로 플레이하는 15명과 백으로 플레이하는 15명, 총 30명으로 이루어진다. 꿍 협회는 가능한 최고의 팀을 만들려고 하는데 각 플 www.acmicpc.net 문제 꿍 협회는 매년 세계체스대회에 나갈 팀을 만들고 있다. 팀은 흑으로 플레이하는 15명과 백으로 플레이하는 15명, 총 30명으로 이루어진다. 꿍 협회는 가능한 최고의 팀을 만들려고 하는데 각 플레이어의 흑,백 능력치는 각각 1부터 100까지의 정수로 주어진다. 대회가 진행되는 동안 플레이어는 흑, 백 중 한 가지만으로 참여를 해야하며 팀의 전체 능력치는 흑 플레이어의 능력치를 합한것과.. 공감수 0 댓글수 0 2023. 2. 6.
[BOJ/백준] 2011번 암호코드 (Python 파이썬) https://www.acmicpc.net/problem/2011 2011번: 암호코드 나올 수 있는 해석의 가짓수를 구하시오. 정답이 매우 클 수 있으므로, 1000000으로 나눈 나머지를 출력한다. 암호가 잘못되어 암호를 해석할 수 없는 경우에는 0을 출력한다. www.acmicpc.net 문제 상근이와 선영이가 다른 사람들이 남매간의 대화를 듣는 것을 방지하기 위해서 대화를 서로 암호화 하기로 했다. 그래서 다음과 같은 대화를 했다. 상근: 그냥 간단히 암호화 하자. A를 1이라고 하고, B는 2로, 그리고 Z는 26으로 하는거야. 선영: 그럼 안돼. 만약, "BEAN"을 암호화하면 25114가 나오는데, 이걸 다시 글자로 바꾸는 방법은 여러 가지가 있어. 상근: 그렇네. 25114를 다시 영어로 .. 공감수 1 댓글수 0 2023. 2. 6.
[BOJ/백준] 9095번 1,2,3 더하기 (Python 파이썬) https://www.acmicpc.net/problem/9095 9095번: 1, 2, 3 더하기 각 테스트 케이스마다, n을 1, 2, 3의 합으로 나타내는 방법의 수를 출력한다. www.acmicpc.net 문제 정수 4를 1, 2, 3의 합으로 나타내는 방법은 총 7가지가 있다. 합을 나타낼 때는 수를 1개 이상 사용해야 한다. 1+1+1+1 1+1+2 1+2+1 2+1+1 2+2 1+3 3+1 정수 n이 주어졌을 때, n을 1, 2, 3의 합으로 나타내는 방법의 수를 구하는 프로그램을 작성하시오. 입력 첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스는 한 줄로 이루어져 있고, 정수 n이 주어진다. n은 양수이며 11보다 작다. 출력 각 테스트 케이스마다, n을 1, 2, 3의 .. 공감수 2 댓글수 0 2023. 2. 6.
[BOJ/백준] 1965번 상자넣기 (Python 파이썬) https://www.acmicpc.net/problem/1965 1965번: 상자넣기 정육면체 모양의 상자가 일렬로 늘어서 있다. 상자마다 크기가 주어져 있는데, 앞에 있는 상자의 크기가 뒤에 있는 상자의 크기보다 작으면, 앞에 있는 상자를 뒤에 있는 상자 안에 넣을 수가 www.acmicpc.net 문제 정육면체 모양의 상자가 일렬로 늘어서 있다. 상자마다 크기가 주어져 있는데, 앞에 있는 상자의 크기가 뒤에 있는 상자의 크기보다 작으면, 앞에 있는 상자를 뒤에 있는 상자 안에 넣을 수가 있다. 예를 들어 앞에서부터 순서대로 크기가 (1, 5, 2, 3, 7)인 5개의 상자가 있다면, 크기 1인 상자를 크기 5인 상자에 넣고, 다시 이 상자를 크기 7인 상자 안에 넣을 수 있다. 하지만 이렇게 상자를.. 공감수 0 댓글수 0 2023. 2. 6.
[BOJ/백준] 17212번 달나라 토끼를 위한 구매대금 지불 도우미 (Python 파이썬) https://www.acmicpc.net/problem/17212 17212번: 달나라 토끼를 위한 구매대금 지불 도우미 달나라 토끼들이 사용하는 화폐는 동전뿐이다. 동전의 종류는 1원, 2원, 5원, 7원 이렇게 4종류가 있다. 물건을 사고 동전으로 계산을 하는데 동전의 개수가 최소가 되도록 지불하지 않는 것은 www.acmicpc.net 문제 달나라 토끼들이 사용하는 화폐는 동전뿐이다. 동전의 종류는 1원, 2원, 5원, 7원 이렇게 4종류가 있다. 물건을 사고 동전으로 계산을 하는데 동전의 개수가 최소가 되도록 지불하지 않는 것은 불법이다. 예를 들어, 17원을 지불할 때 7원짜리 동전 1개와 5원짜리 동전 2개로 지불해야 합법이고, 7원짜리 동전 2개와 2원짜리 동전 1개, 1원짜리 동전 1개로.. 공감수 0 댓글수 0 2023. 2. 6.
[BOJ/백준] 2491번 수열 (Python 파이썬) https://www.acmicpc.net/problem/2491 2491번: 수열 0에서부터 9까지의 숫자로 이루어진 N개의 숫자가 나열된 수열이 있다. 그 수열 안에서 연속해서 커지거나(같은 것 포함), 혹은 연속해서 작아지는(같은 것 포함) 수열 중 가장 길이가 긴 것을 찾 www.acmicpc.net 문제 0에서부터 9까지의 숫자로 이루어진 N개의 숫자가 나열된 수열이 있다. 그 수열 안에서 연속해서 커지거나(같은 것 포함), 혹은 연속해서 작아지는(같은 것 포함) 수열 중 가장 길이가 긴 것을 찾아내어 그 길이를 출력하는 프로그램을 작성하라. 예를 들어 수열 1, 2, 2, 4, 4, 5, 7, 7, 2 의 경우에는 1 ≤ 2 ≤ 2 ≤ 4 ≤ 4 ≤ 5 ≤ 7 ≤ 7 이 가장 긴 구간이 되므로.. 공감수 1 댓글수 0 2023. 2. 6.
[BOJ/백준] 2670번 연속부분최대곱 (Python 파이썬) https://www.acmicpc.net/problem/2670 2670번: 연속부분최대곱 첫째 줄은 나열된 양의 실수들의 개수 N이 주어지고, 그 다음 줄부터 N개의 수가 한 줄에 하나씩 들어 있다. N은 10,000 이하의 자연수이다. 실수는 소수점 첫째자리까지 주어지며, 0.0보다 크거나 www.acmicpc.net 문제 N개의 실수가 있을 때, 한 개 이상의 연속된 수들의 곱이 최대가 되는 부분을 찾아, 그 곱을 출력하는 프로그램을 작성하시오. 예를 들어 아래와 같이 8개의 양의 실수가 주어진다면, 색칠된 부분의 곱이 최대가 되며, 그 값은 1.638이다. 입력 첫째 줄은 나열된 양의 실수들의 개수 N이 주어지고, 그 다음 줄부터 N개의 수가 한 줄에 하나씩 들어 있다. N은 10,000 이하의.. 공감수 0 댓글수 0 2023. 2. 6.
[BOJ/백준] 2293번 동전1 (Python 파이썬) https://www.acmicpc.net/problem/2293 2293번: 동전 1 첫째 줄에 n, k가 주어진다. (1 ≤ n ≤ 100, 1 ≤ k ≤ 10,000) 다음 n개의 줄에는 각각의 동전의 가치가 주어진다. 동전의 가치는 100,000보다 작거나 같은 자연수이다. www.acmicpc.net 문제 n가지 종류의 동전이 있다. 각각의 동전이 나타내는 가치는 다르다. 이 동전을 적당히 사용해서, 그 가치의 합이 k원이 되도록 하고 싶다. 그 경우의 수를 구하시오. 각각의 동전은 몇 개라도 사용할 수 있다. 사용한 동전의 구성이 같은데, 순서만 다른 것은 같은 경우이다. 입력 첫째 줄에 n, k가 주어진다. (1 ≤ n ≤ 100, 1 ≤ k ≤ 10,000) 다음 n개의 줄에는 각각의 동전.. 공감수 0 댓글수 0 2023. 2. 6.
[BOJ/백준] 15486번 퇴사2 (Python 파이썬) https://www.acmicpc.net/problem/15486 15486번: 퇴사 2 첫째 줄에 N (1 ≤ N ≤ 1,500,000)이 주어진다. 둘째 줄부터 N개의 줄에 Ti와 Pi가 공백으로 구분되어서 주어지며, 1일부터 N일까지 순서대로 주어진다. (1 ≤ Ti ≤ 50, 1 ≤ Pi ≤ 1,000) www.acmicpc.net 문제 상담원으로 일하고 있는 백준이는 퇴사를 하려고 한다. 오늘부터 N+1일째 되는 날 퇴사를 하기 위해서, 남은 N일 동안 최대한 많은 상담을 하려고 한다. 백준이는 비서에게 최대한 많은 상담을 잡으라고 부탁을 했고, 비서는 하루에 하나씩 서로 다른 사람의 상담을 잡아놓았다. 각각의 상담은 상담을 완료하는데 걸리는 기간 Ti와 상담을 했을 때 받을 수 있는 금액 P.. 공감수 0 댓글수 0 2023. 2. 6.
[BOJ/백준] 11726번 2×n 타일링 (Python 파이썬) https://www.acmicpc.net/problem/11726 11726번: 2×n 타일링 2×n 크기의 직사각형을 1×2, 2×1 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오. 아래 그림은 2×5 크기의 직사각형을 채운 한 가지 방법의 예이다. www.acmicpc.net 문제 2×n 크기의 직사각형을 1×2, 2×1 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오. 아래 그림은 2×5 크기의 직사각형을 채운 한 가지 방법의 예이다. 입력 첫째 줄에 n이 주어진다. (1 ≤ n ≤ 1,000) 출력 첫째 줄에 2×n 크기의 직사각형을 채우는 방법의 수를 10,007로 나눈 나머지를 출력한다. 예제 입력 1 2 예제 출력 1 2 예제 입력 2 9 예제 출력 2 55 풀이 주어진 조.. 공감수 0 댓글수 0 2023. 2. 6.
[BOJ/백준] 10026번 적록색약 (Python 파이썬) https://www.acmicpc.net/problem/10026 10026번: 적록색약 적록색약은 빨간색과 초록색의 차이를 거의 느끼지 못한다. 따라서, 적록색약인 사람이 보는 그림은 아닌 사람이 보는 그림과는 좀 다를 수 있다. 크기가 N×N인 그리드의 각 칸에 R(빨강), G(초록) www.acmicpc.net 문제 적록색약은 빨간색과 초록색의 차이를 거의 느끼지 못한다. 따라서, 적록색약인 사람이 보는 그림은 아닌 사람이 보는 그림과는 좀 다를 수 있다. 크기가 N×N인 그리드의 각 칸에 R(빨강), G(초록), B(파랑) 중 하나를 색칠한 그림이 있다. 그림은 몇 개의 구역으로 나뉘어져 있는데, 구역은 같은 색으로 이루어져 있다. 또, 같은 색상이 상하좌우로 인접해 있는 경우에 두 글자는 같은.. 공감수 0 댓글수 0 2023. 1. 30.
[BOJ/백준] 3184번 양 (Python 파이썬) https://www.acmicpc.net/problem/3184 3184번: 양 첫 줄에는 두 정수 R과 C가 주어지며(3 ≤ R, C ≤ 250), 각 수는 마당의 행과 열의 수를 의미한다. 다음 R개의 줄은 C개의 글자를 가진다. 이들은 마당의 구조(울타리, 양, 늑대의 위치)를 의미한다. www.acmicpc.net 문제 미키의 뒷마당에는 특정 수의 양이 있다. 그가 푹 잠든 사이에 배고픈 늑대는 마당에 들어와 양을 공격했다. 마당은 행과 열로 이루어진 직사각형 모양이다. 글자 '.' (점)은 빈 필드를 의미하며, 글자 '#'는 울타리를, 'o'는 양, 'v'는 늑대를 의미한다. 한 칸에서 수평, 수직만으로 이동하며 울타리를 지나지 않고 다른 칸으로 이동할 수 있다면, 두 칸은 같은 영역 안에 속.. 공감수 0 댓글수 0 2023. 1. 30.
[BOJ/백준] 16948번 데스 나이트 (Python 파이썬) https://www.acmicpc.net/problem/16948 16948번: 데스 나이트 게임을 좋아하는 큐브러버는 체스에서 사용할 새로운 말 "데스 나이트"를 만들었다. 데스 나이트가 있는 곳이 (r, c)라면, (r-2, c-1), (r-2, c+1), (r, c-2), (r, c+2), (r+2, c-1), (r+2, c+1)로 이동할 수 있다. 크 www.acmicpc.net 문제 게임을 좋아하는 큐브러버는 체스에서 사용할 새로운 말 "데스 나이트"를 만들었다. 데스 나이트가 있는 곳이 (r, c)라면, (r-2, c-1), (r-2, c+1), (r, c-2), (r, c+2), (r+2, c-1), (r+2, c+1)로 이동할 수 있다. 크기가 N×N인 체스판과 두 칸 (r1, c1), .. 공감수 0 댓글수 1 2023. 1. 30.
[BOJ/백준] 1926번 그림 (Python 파이썬) https://www.acmicpc.net/problem/1926 1926번: 그림 어떤 큰 도화지에 그림이 그려져 있을 때, 그 그림의 개수와, 그 그림 중 넓이가 가장 넓은 것의 넓이를 출력하여라. 단, 그림이라는 것은 1로 연결된 것을 한 그림이라고 정의하자. 가로나 세로 www.acmicpc.net 문제 어떤 큰 도화지에 그림이 그려져 있을 때, 그 그림의 개수와, 그 그림 중 넓이가 가장 넓은 것의 넓이를 출력하여라. 단, 그림이라는 것은 1로 연결된 것을 한 그림이라고 정의하자. 가로나 세로로 연결된 것은 연결이 된 것이고 대각선으로 연결이 된 것은 떨어진 그림이다. 그림의 넓이란 그림에 포함된 1의 개수이다. 입력 첫째 줄에 도화지의 세로 크기 n(1 ≤ n ≤ 500)과 가로 크기 m(1 .. 공감수 0 댓글수 0 2023. 1. 30.
[BOJ/백준] 1068번 트리 (Python 파이썬) https://www.acmicpc.net/problem/1068 1068번: 트리 첫째 줄에 트리의 노드의 개수 N이 주어진다. N은 50보다 작거나 같은 자연수이다. 둘째 줄에는 0번 노드부터 N-1번 노드까지, 각 노드의 부모가 주어진다. 만약 부모가 없다면 (루트) -1이 주어진다 www.acmicpc.net 문제 트리에서 리프 노드란, 자식의 개수가 0인 노드를 말한다. 트리가 주어졌을 때, 노드 하나를 지울 것이다. 그 때, 남은 트리에서 리프 노드의 개수를 구하는 프로그램을 작성하시오. 노드를 지우면 그 노드와 노드의 모든 자손이 트리에서 제거된다. 예를 들어, 다음과 같은 트리가 있다고 하자. 현재 리프 노드의 개수는 3개이다. (초록색 색칠된 노드) 이때, 1번을 지우면, 다음과 같이 변.. 공감수 0 댓글수 0 2023. 1. 28.
[Algorithm] 이진 탐색(Binary Search) 알고리즘 Binary Search Idea 이진 탐색은 정렬된 배열이 주어질 때, 리스트의 중간값과 비교하면서 반씩 제외하며 원하는 값을 찾아가는 과정입니다. 주의할 점은, 이진 탐색 알고리즘은 정렬된 배열에만 적용 가능하다는 점입니다. 따라서 정렬되어있지 않다면 성능이 우수한 퀵 정렬을 통해 약 O(nlogn)의 시간을 들여 정렬을 한 뒤 이진 탐색 알고리즘을 적용해야 합니다. 이진 탐색의 과정을 살펴보면 아래와 같습니다. 중간 인덱스(middle)를 구한다. (첫번째 인덱스 + 마지막 인덱스) / 2 찾을 값(target)이 middle보다 작은 경우, middle과 그 이후 인덱스들을 검색 범위에서 제외한다. target이 middle보다 큰 경우, middler과 그 이전 인덱스들을 검색 범위에서 제외한다.. 공감수 0 댓글수 0 2023. 1. 28.
[Algorithm] 위상 정렬(Topological sort) 알고리즘 Topological sort 위상 정렬이란, 사이클이 없는 방향 그래프(DAG)를 방향성에 거스르지 않도록 순서대로 나열하는 것입니다. 대표적인 예시로, 선수 과목을 고려해서 학습 순서를 설정하는 것이 있습니다. 일반화학, 유기화학1, 유기화학2 라는 3과목이 있을 때, 아래의 학습 순서들 중 적절한 순서는 (2)가 될 것입니다. (1) 일반화학 -> 유기화학2 -> 유기화학1 (2) 일반화학 -> 유기화학1 -> 유기화학2 우선, 비순환 방향 그래프(DAG)에 대해 정리하겠습니다. 비순환 방향 그래프 (Directed Acyclic Graph) 위와 같이 방향 그래프이면서 사이클이 없는 그래프를 DAG라고 한다. DAG와 Topological sort 위상 정렬은 이러한 비순환 방향 그래프에서 정점들.. 공감수 0 댓글수 0 2023. 1. 28.
[Algorithm] 힙 정렬(Heap sort) 알고리즘 Heap sort Idea 우선 heap의 개념부터 정리하겠습니다. Heap 완전 이진트리 형태이며, 최대 힙과 최소 힙으로 나뉜다. 최대 힙은 부모 노드가 자식 노드보다 크거나 같은 완전 이진트리이고, 최소 힙은 부모 노드가 자식 노드보다 작거나 같은 완전 이진 트리이다. 이러한 힙의 형태를 유지하면서 삽입과 삭제 연산이 가능하도록 해야하며, 이러한 연산을 heapify이라 한다. 힙과 이진 탐색 트리는 명확한 차이점을 가진다. 두 자료구조 모두 이진트리라는 점은 같지만, 노드 값이 다르게 구성된다. 이진 탐색 트리의 경우 가장 왼쪽의 리프노드가 가장 작고, 가장 오른쪽의 리프노드가 가장 큰 값을 가진다. 하지만 힙의 경우 부모와 자식 간의 값의 순서만 지키면 되기 때문에 차이점이 있다. Heap 표현.. 공감수 0 댓글수 0 2023. 1. 28.
[BOJ/백준] 2644번 촌수계산 (Python 파이썬) https://www.acmicpc.net/problem/2644 2644번: 촌수계산 사람들은 1, 2, 3, …, n (1 ≤ n ≤ 100)의 연속된 번호로 각각 표시된다. 입력 파일의 첫째 줄에는 전체 사람의 수 n이 주어지고, 둘째 줄에는 촌수를 계산해야 하는 서로 다른 두 사람의 번호가 주어 www.acmicpc.net 문제 우리 나라는 가족 혹은 친척들 사이의 관계를 촌수라는 단위로 표현하는 독특한 문화를 가지고 있다. 이러한 촌수는 다음과 같은 방식으로 계산된다. 기본적으로 부모와 자식 사이를 1촌으로 정의하고 이로부터 사람들 간의 촌수를 계산한다. 예를 들면 나와 아버지, 아버지와 할아버지는 각각 1촌으로 나와 할아버지는 2촌이 되고, 아버지 형제들과 할아버지는 1촌, 나와 아버지 형제들.. 공감수 1 댓글수 0 2023. 1. 27.
[BOJ/백준] 2206번 벽 부수고 이동하기 (Python 파이썬) https://www.acmicpc.net/problem/2206 2206번: 벽 부수고 이동하기 N×M의 행렬로 표현되는 맵이 있다. 맵에서 0은 이동할 수 있는 곳을 나타내고, 1은 이동할 수 없는 벽이 있는 곳을 나타낸다. 당신은 (1, 1)에서 (N, M)의 위치까지 이동하려 하는데, 이때 최단 경로 www.acmicpc.net 문제 N×M의 행렬로 표현되는 맵이 있다. 맵에서 0은 이동할 수 있는 곳을 나타내고, 1은 이동할 수 없는 벽이 있는 곳을 나타낸다. 당신은 (1, 1)에서 (N, M)의 위치까지 이동하려 하는데, 이때 최단 경로로 이동하려 한다. 최단경로는 맵에서 가장 적은 개수의 칸을 지나는 경로를 말하는데, 이때 시작하는 칸과 끝나는 칸도 포함해서 센다. 만약에 이동하는 도중에 한.. 공감수 0 댓글수 0 2023. 1. 27.

문의안내

티스토리
로그인
고객센터

티스토리는 카카오에서 사랑을 담아 만듭니다.