전체 글
[백준 / Python 파이썬] 3098번 - 소셜네트워크
[Silver II] 소셜네트워크 - 3098 문제 링크 분류 그래프 이론, 구현 문제 설명 소셜 네트워크는 이제 우리 삶의 일부가 되어버렸다. 이러한 소셜 네트워크를 분석하는 김동규 석사과정은 흥미로운 현상을 발견했다. 바로 친구 관계의 수가 급속도로 증가한다는 것이다. 예로부터 우리의 조상님들은 "친구의 친구는 나의 친구"라고 했다. 사람들은 매일 조상님들의 말씀을 따르기 위해서 자신의 친구의 친구 목록을 확인하고, 이를 모두 자신의 친구로 추가한다. 친구 관계는 상대방이 수락을 해야 되고, 총 1일이 걸린다. 예를 들어, A와 B가 친구라면, A는 B가 어제 또는 그 이전에 만든 친구만 볼 수 있다. 모든 친구관계는 대칭이다. 즉, A와 B의 친구라면, B도 A의 친구이다. 김동규가 분석하는 소셜 ..
[백준 / Python 파이썬] 25516번 - 거리가 k이하인 트리 노드에서 사과 수확하기
[Silver II] 거리가 k이하인 트리 노드에서 사과 수확하기 - 25516 문제 링크 분류 너비 우선 탐색, 깊이 우선 탐색, 그래프 이론, 그래프 탐색, 트리 문제 설명 n개의 정점과 n - 1개의 간선으로 구성된 트리 T가 있다. 정점 번호는 0부터 n - 1까지이고 0번 정점이 루트이다. 모든 간선의 길이는 1이다. 트리 T의 각 정점에는 사과가 0개 또는 1개 놓여있다. 루트 노드에서 거리가 k이하인 노드에 있는 사과를 수확하려고 한다. 수확할 수 있는 사과 개수를 출력하자. 입력 첫 번째 줄에 정점의 수 n과 정수 k가 공백을 사이에 두고 순서대로 주어진다. 두 번째 줄부터 n - 1개 줄에 걸쳐 간선의 정보가 주어진다. 한 줄에 하나의 간선 정보가 주어진다. 하나의 간선 정보는 부모 정점..
[백준 / Python 파이썬] 14496번 - 그대, 그머가 되어
[Silver II] 그대, 그머가 되어 - 14496 문제 링크 분류 너비 우선 탐색, 그래프 이론, 그래프 탐색 문제 설명 선린에 합격한 대호에게는 큰 고민이 있다. 대호는 중학교 3년 내내 공부만 했기 때문에, 요즘 학생들이 사용하는 ‘야민정음’에 대해서는 문외한이다. 친구들의 대화에 끼고 싶은 대호는 야민정음을 공부하기로 했다. 야민정음이란, 비슷한 모양의 글자를 원래 문자 대신에 사용하는 것을 일컫는다. 예를 들어, ‘그대’는 ‘그머’로, ‘팔도비빔면’은 ‘괄도네넴댼’으로, ‘식용유’는 ‘식용윾’으로, ‘대호’는 ‘머호’로 바꿀 수 있다. 아무 문자나 치환할 수 있는 건 아니며 치환이 가능한 몇 개의 문자들이 정해져있다. 예를 들어보자. (a, b), (a, c), (b, d), (c, d)가 ..
[백준 / Python 파이썬] 27497번 - 알파벳 블록
[Silver II] 알파벳 블록 - 27497 문제 링크 분류 자료 구조, 덱, 스택, 문자열 문제 설명 스타는 알파벳 블록을 일렬로 조립하여 문자열을 만드는 게임을 만들었다. 각 블록에는 문자 하나가 적혀 있으며 게임에는 각각 다음 기능을 수행하는 세 개의 버튼이 있다. 문자열 맨 뒤에 블록 추가 문자열 맨 앞에 블록 추가 문자열을 구성하는 블록 중 가장 나중에 추가된 블록 제거 게임은 처음에 빈 문자열로 시작하며 빈 문자열일 때 문자열을 구성하는 블록 중 가장 나중에 추가된 블록을 제거하는 버튼을 누를 경우 아무런 동작도 하지 않는다. 버튼을 누른 횟수와 누른 버튼이 순서대로 주어질 때 완성된 문자열을 구하여라. 입력 첫째 줄에 버튼을 누른 횟수 N이 주어진다. (1≤N≤1000000)(1≤1000..
[백준 / Python 파이썬] 23304번 - 아카라카
[Silver II] 아카라카 - 23304 문제 링크 분류 재귀, 문자열 문제 설명 아카라카! 아카라카(아라)칭 아카라카(아라)쵸 아카라카(아라) 칭칭 쵸쵸쵸 랄랄라 시스붐바 연세 선수 라플라 헤이 연세 야! AKARAKA(아카라카)는 컴퓨터 과학적 관점으로 바라봤을 때, 튜링도 기립 박수를 치고 갈 가히 최고의 구호라 할 수 있다. AKARAKA는 그 자체로도 팰린드롬이고, 접두사이자 접미사인 AKA가 또한 팰린드롬이기 때문이다. 신촌에서는 AKARAKA같은 특성을 가진 팰린드롬을, 아카라카 팰린드롬이라 아래와 같이 정의한다. 문자열 S가 팰린드롬이다. 팰린드롬이란 거꾸로 뒤집어 읽어도 같은 문자열을 뜻한다. 문자열 S의 길이를 |S|라 할 때, ⌊|S|2⌋|2⌋ 길이의 접두사와 접미사가 모두 아카라..
[백준 / Python 파이썬] 16923번 - 다음 다양한 단어
[Silver II] 다음 다양한 단어 - 16923 문제 링크 분류 구현, 문자열 문제 설명 다양한 단어란 모두 다른 알파벳 소문자로만 이루어진 단어를 의미한다. 예를 들어, "codeplus", "coding", "algorithm"은 다양한 단어, "baekjoon", "startlink"는 다양한 단어가 아니다. 다양한 단어 S가 주어졌을 때, 사전 순으로 S의 바로 다음에 오는 다양한 단어를 구해보자. 입력 첫째 줄에 길이가 26보다 작거나 같은 다양한 단어 S가 주어진다. 출력 사전 순으로 S의 바로 다음에 오는 다양한 단어를 출력한다. 바로 다음에 오는 단어가 없는 경우에는 -1을 출력한다. S = input() L = list(S) N = len(S) alphabet = [0] * 26 f..
[백준 / Python 파이썬] 1821번 - 수들의 합 6
[Silver I] 수들의 합 6 - 1821 문제 링크 분류 브루트포스 알고리즘, 수학 문제 설명 가장 윗줄에 1부터 N까지의 숫자가 한 개씩 적혀 있다. 그리고 둘째 줄부터 차례대로 파스칼의 삼각형처럼 위의 두개를 더한 값이 저장되게 된다. 예를 들어 N이 4 이고 가장 윗 줄에 3 1 2 4 가 있다고 했을 때, 다음과 같은 삼각형이 그려진다. 3 1 2 4 4 3 6 7 9 16 N과 가장 밑에 있는 숫자가 주어져 있을 때 가장 윗줄에 있는 숫자를 구하는 프로그램을 작성하시오. 단, 답이 여러 가지가 나오는 경우에는 사전순으로 가장 앞에 오는 것을 출력하여야 한다. 입력 첫째 줄에 두개의 정수 N(1 ≤ N ≤ 10)과 F가 주어진다. N은 가장 윗줄에 있는 숫자의 개수를 의미하며 F는 가장 밑에..
[백준 / Python 파이썬] 2502번 - 떡 먹는 호랑이
[Silver I] 떡 먹는 호랑이 - 2502 문제 링크 분류 브루트포스 알고리즘, 다이나믹 프로그래밍, 수학 문제 설명 하루에 한 번 산을 넘어가는 떡 장사 할머니는 호랑이에게 떡을 주어야 산을 넘어갈 수 있는데, 욕심 많은 호랑이는 어제 받은 떡의 개수와 그저께 받은 떡의 개수를 더한 만큼의 떡을 받아야만 할머니를 무사히 보내 준다고 한다. 예를 들어 첫째 날에 떡을 1개 주었고, 둘째 날에는 떡을 2개 주었다면 셋째 날에는 1+2=3개, 넷째 날에는 2+3=5개, 다섯째 날에는 3+5=8개, 여섯째 날에는 5+8=13개를 주어야만 무사히 산을 넘어갈 수 있다. 우리는 산을 무사히 넘어온 할머니에게 오늘 호랑이에게 몇 개의 떡을 주었는지, 그리고 오늘이 호랑이를 만나 떡을 준지 며칠이 되었는지를 알..