분류 전체보기

[ 백준 2533 해설 ] ( python ) 트리와 쿼리

📚 트리와 쿼리 문제 간선에 가중치와 방향성이 없는 임의의 루트 있는 트리가 주어졌을 때, 아래의 쿼리에 답해보도록 하자. 정점 U를 루트로 하는 서브트리에 속한 정점의 수를 출력한다. 만약 이 문제를 해결하는 데에 어려움이 있다면, 하단의 힌트에 첨부한 문서를 참고하자. 입력 트리의 정점의 수 N과 루트의 번호 R, 쿼리의 수 Q가 주어진다. (2 ≤ N ≤ 105, 1 ≤ R ≤ N, 1 ≤ Q ≤ 105) 이어 N-1줄에 걸쳐, U V의 형태로 트리에 속한 간선의 정보가 주어진다. (1 ≤ U, V ≤ N, U ≠ V) 이는 U와 V를 양 끝점으로 하는 간선이 트리에 속함을 의미한다. 이어 Q줄에 걸쳐, 문제에 설명한 U가 하나씩 주어진다. (1 ≤ U ≤ N) 입력으로 주어지는 트리는 항상 올바른..

[ 백준 9252 해설 ] ( python ) LCS 2

📚 LCS 2 문제 LCS(Longest Common Subsequence, 최장 공통 부분 수열)문제는 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다. 예를 들어, ACAYKP와 CAPCAK의 LCS는 ACAK가 된다. 입력 첫째 줄과 둘째 줄에 두 문자열이 주어진다. 문자열은 알파벳 대문자로만 이루어져 있으며, 최대 1000글자로 이루어져 있다. 출력 첫째 줄에 입력으로 주어진 두 문자열의 LCS의 길이를, 둘째 줄에 LCS를 출력한다. LCS가 여러 가지인 경우에는 아무거나 출력하고, LCS의 길이가 0인 경우에는 둘째 줄을 출력하지 않는다. 예제 입력 1 복사 ACAYKP CAPCAK 예제 출력 1 복사 4 ACAK ✍ 접근 가장 긴 공통 부분 수열 dp를..

[ 백준 9251 해설 ] ( python ) LCS

📚 LCS 문제 LCS(Longest Common Subsequence, 최장 공통 부분 수열)문제는 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다. 예를 들어, ACAYKP와 CAPCAK의 LCS는 ACAK가 된다. 입력 첫째 줄과 둘째 줄에 두 문자열이 주어진다. 문자열은 알파벳 대문자로만 이루어져 있으며, 최대 1000글자로 이루어져 있다. 출력 첫째 줄에 입력으로 주어진 두 문자열의 LCS의 길이를 출력한다. 예제 입력 1 복사 ACAYKP CAPCAK 예제 출력 1 복사 4 ✍ 접근 가장 긴 공통 부분 수열 dp를 활용하여 점화식을 세워 풀 수 있다 정답코드 # ✨ 입력 import sys input = sys.stdin.readline A = ' '+i..

[ 백준 7575 해설 ] ( python ) 바이러스

📚 바이러스 문제 새로운 컴퓨터 바이러스가 발견되어서 이를 치료하는 백신 프로그램을 개발하려고 한다. 백신 프로그램을 개발하기 위해서는 바이러스 코드를 알아야 하는데, 감염된 프로그램들에 공통으로 존재하는 부분이 바이러스로 의심되는 부분이다. (프로그램의 코드는 양의 정수들의 나열로 표현된다.) 단, 바이러스는 자신이 탐지되는 것을 막기 위해서, 자신의 코드를 반대로 기입하기도 한다. 또한, 프로그램들의 코드 일부가 우연히 같을 수 있기 때문에, 공통으로 나타나는 코드의 길이가 K 이상인 경우에만 바이러스 코드로 추정한다. 프로그램 1: 10 8 23 93 21 42 52 22 13 1 2 3 4 프로그램 2: 1 3 8 9 21 42 52 22 13 41 42 프로그램 3: 9 21 42 52 13 2..

[ 백준 11779 해설 ] ( python ) 최소비용 구하기 2

📚 최소비용 구하기 2 문제 n(1≤n≤1,000)개의 도시가 있다. 그리고 한 도시에서 출발하여 다른 도시에 도착하는 m(1≤m≤100,000)개의 버스가 있다. 우리는 A번째 도시에서 B번째 도시까지 가는데 드는 버스 비용을 최소화 시키려고 한다. 그러면 A번째 도시에서 B번째 도시 까지 가는데 드는 최소비용과 경로를 출력하여라. 항상 시작점에서 도착점으로의 경로가 존재한다. 입력 첫째 줄에 도시의 개수 n(1≤n≤1,000)이 주어지고 둘째 줄에는 버스의 개수 m(1≤m≤100,000)이 주어진다. 그리고 셋째 줄부터 m+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 버스의 출발 도시의 번호가 주어진다. 그리고 그 다음에는 도착지의 도시 번호가 주어지고 또 그 버스 비용이 주어진다..

[ 백준 9370 해설 ] ( python ) 미확인 도착지

📚 미확인 도착지 문제 (취익)B100 요원, 요란한 옷차림을 한 서커스 예술가 한 쌍이 한 도시의 거리들을 이동하고 있다. 너의 임무는 그들이 어디로 가고 있는지 알아내는 것이다. 우리가 알아낸 것은 그들이 s지점에서 출발했다는 것, 그리고 목적지 후보들 중 하나가 그들의 목적지라는 것이다. 그들이 급한 상황이기 때문에 목적지까지 우회하지 않고 최단거리로 갈 것이라 확신한다. 이상이다. (취익) 어휴! (요란한 옷차림을 했을지도 모를) 듀오가 어디에도 보이지 않는다. 다행히도 당신은 후각이 개만큼 뛰어나다. 이 후각으로 그들이 g와 h 교차로 사이에 있는 도로를 지나갔다는 것을 알아냈다. 이 듀오는 대체 어디로 가고 있는 것일까? 예제 입력의 두 번째 케이스를 시각화한 것이다. 이 듀오는 회색 원에서 ..

[ 백준 2533 해설 ] ( python ) 사회망 서비스(SNS)

📚 사회망 서비스(SNS) 문제 페이스북, 트위터, 카카오톡과 같은 사회망 서비스(SNS)가 널리 사용됨에 따라, 사회망을 통하여 사람들이 어떻게 새로운 아이디어를 받아들이게 되는가를 이해하는 문제가 중요해졌다. 사회망에서 사람들의 친구 관계는 그래프로 표현할 수 있는데, 이 그래프에서 사람은 정점으로 표현되고, 두 정점을 잇는 에지는 두 정점으로 표현되는 두 사람이 서로 친구 관계임을 표현한다. 예를 들어, 철수와 영희, 철수와 만수, 영희와 순희가 서로 친구 관계라면 이를 표현하는 친구 관계 그래프는 다음과 같다. 친구 관계 그래프를 이용하면 사회망 서비스에서 어떤 새로운 아이디어가 전파되는 과정을 이해하는데 도움을 줄 수 있다. 어떤 새로운 아이디어를 먼저 받아들인 사람을 얼리 아답터(early a..

[SEMO] 프로젝트 회고록 1

0. 팀 프로젝트 진행 이유 개발자에게 가장 중요한 소양 중 하나가 커뮤니케이션 능력이라는 것은 다들 잘 안다. 개발자가 아니더라도 아주 중요하다! 싸피 사람들과 일상적인 이야기를 나누고, 알고리즘이나 수업에 대한 이야기를 나누는 것도 커뮤니케이션이지만, '개발자에게 필요한 커뮤니케이션 능력'은 조금 더 개발과 협업에 맞닿아있는 부분이라는 것을 알게 되고 팀 프로젝트 경험과 협업, 커뮤니케이션 능력을 기르기 위해 팀 프로젝트를 모집하게 되었다. 또한 원티드 프리온보딩 챌린지에 깔짝깔짝 참여하면서 다른 사람의 코드를 읽는 능력, 내 코드를 읽기 쉽게 쓰는 능력이 얼마나 중요한지 깨닫게 되었다. 프론트엔드를 꿈꾸는 멋찐 개발자님의 코드를 참고하며 함께 쑥쑥 성장하고 싶은 마음도 컸다 마지막으로, 어차피 현업..