인맥의 중요성

얼마 후 상심에 빠져있는 토맹이에게 토달이가 찾아왔다. "넌 내가 잔치에 초대했을 땐 오지 않더니 왜 이제야 온 거니? 잔치는 이미 다 끝나버렸어. 당근과 과일도 모두 떨어져서 너에게 줄 것이 아무것도 없어." 토맹이가 말했다. "토맹아, 난 당근과 과일 때문에 찾아온게 아냐. 난 너를 쭉 지켜 보았어. 넌 친구를 만들기 위해 안간힘을 썼지만 진정한 친구를 만드는 방법은 아직 깨닫지 못한 것 같구나." 토달이의 말에 토맹이는 힘 없는 목소리로 말을 이어갔다. "하지만 난 최선을 다했어. 고향 친구들을 만나기도 했고 왕토끼를 찾아기기도 했어. 그리고 가지고 있는 모든 것을 털어서 날마다 잔치까지 열어봤지. 하지만 매번 실패로 돌아갔어. 아무래도 난 운이 없나봐." "토맹아, 네 모습을 곰곰히 생각해 봐. ..

• format_list_bulleted 생활 유용 정보
• · 2018. 9. 12.
• textsms

알고스팟 - 수강철회 (WITHDRAWAL)

문제 : https://algospot.com/judge/problem/read/WITHDRAWAL 이 문제에서 n개의 수강과목이 주어지고, 이 중에서 k개의 수강과목을 선택하여 누적등수를 높이고자 합니다. 이 문제를 해결하는 가장 단순 무식한 방법은 n개의 과목 중에서 모든 경우의 k개의 과목을 선택하여 가장 낮은 값을 가지는 누적 등수 값을 찾는 것입니다. 즉, n개 중에서 k개를 선택하는 경우의 수만큼 검사를 해야 합니다. 그 공식은 위와 같이 나타낼 수 있는데, 문제에서 n의 값이 1000까지 가능하다고 하기 때문에, 예를 들어, n=1000이고, k=10일 경우, 모든 가능한 경우의 수는 다음과 같이 상당한 값을 가지게 됩니다. 따라서, 단순 무식한 방법으로는 절대 결과를 얻을 수 없다는 것을 ..

• format_list_bulleted 컴퓨터 공학/Algorithm
• · 2018. 9. 12.
• textsms

2-SAT (2-Satisfiability)

2-SAT은 충족가능성 문제로, 위의 식과 같이 OR 연산으로 두 변수가 묶인 절들이 각각 AND 연산으로 연결되어 있는 형태에 대해 f가 참인 경우를 만들기 위해 각각의 변수를 참과 거짓 중 무엇으로 설정해야 하는지 계산해야 합니다. 위와 같이 AND 연산으로만 표현된 식의 형태를 CNF (Closure Normal Form)이라고 합니다. 두 불린 변수 p와 q가 있을 때, p→q는 “p가 참이면 q도 참이다”라는 명제를 의미합니다. 다음의 표는 두 불린 변수의 각 경우에는 p→q의 진리값을 나타냅니다. 만약 p가 참일 때 q가 거짓이라면 이 명제는 거짓인 명제가 됩니다. 그리고, p가 거짓이라면 q와 상관없이 이 명제는 항상 참이되는데요, 그 이유는 이 명제는 항상 p가 참일 경우가 전제가 되어야 ..

• format_list_bulleted 컴퓨터 공학/Algorithm
• · 2018. 9. 12.
• textsms

알고스팟 - 변화하는 중간값 (RUNNINGMEDIAN) 설명

문제 : https://algospot.com/judge/problem/read/RUNNINGMEDIAN문제에서 설명한 바와 같이 수열에 새로운 값을 삽입할 때마다 해당 수열의 중간값을 출력하는 효율적인 방법은 두 개의 우선순위 큐를 이용하는 것입니다. 두 개의 우선순위 큐 중에서 하나는 오름차순 우선순위 큐, 다른 하나는 내림차순 우선순위 큐로 구성합니다. 새로운 데이터를 삽입할 때, Q1의 top보다 작으면 Q1에 삽입하고, Q2의 top보다 크면 Q2에 삽입하면서, 모든 경우에 대해 만약 Q1과 Q2의 데이터 개수를 동일하거나 전체 데이터 개수가 홀수 개이면서 Q1의 데이터 개수가 Q2보다 한 개 더 많을 때, Q1의 top이 중간값이라고 할 수 있습니다.예시를 위해 입력 데이터를 다음과 같이 구성..

• format_list_bulleted 컴퓨터 공학/Algorithm
• · 2018. 9. 12.
• textsms

강한 연결 요소 (Strongly Connected Component)

이번에 제가 설명할 주제는 강한 연결 요소 (Strongly Connected Component)입니다. 유향그래프에서, 어느 한 정점에서 출발하여 다시 자신으로 돌아오는 경로를 사이클이라고 합니다. 위의 그림은 사이클이 존재하는 유향그래프를 나타냅니다. 유향그래프에서 하나의 사이클은 내부적으로 하나 이상의 서브사이클이 존재할 수 있습니다. 그림과 같이 유향그래프에서 A->B->D->C->A의 사이클 내에 A->B->C->A와 B->D->C->B와 같은 서브사이클이 존재하는 것을 알 수 있습니다. 여기서, 한 정점을 지나는 모든 사이클 중에서 가장 많은 정점을 포함하는 사이클의 정점들의 집합을 강한 연결 요소 (Strongly Connected Component)라고 합니다. 그림의 예시에서는 A->B-..

• format_list_bulleted 컴퓨터 공학/Algorithm
• · 2018. 9. 12.
• textsms

알고스팟 - 어린이날 (CHILDRENDAY) 문제 설명

알고스팟의 어린이날 문제에 대해 설명해보겠습니다.문제 : https://algospot.com/judge/problem/read/CHILDRENDAY먼저, 어린이날 문제를 요약해보도록 하겠습니다. 모든 어린이들의 총합은 N 명이고, 우리는 N 명의 어린이들에게 균등한 개수의 선물을 나눠줘야 합니다. 예를 들어, 각 어린이들에게 한 개의 선물을 나눠준다고 하면, N개의 선물이 필요하게 됩니다. 단, M명의 욕심쟁이 어린이들에게는 한 개의 선물을 더 주어야 하기 때문에 최소한으로 주어야 하는 선물의 총 합은 N+M이 됩니다.N명의 어린이들에게 균등한 수의 선물을 나눠줘야 한다.N명 중 M 명의 욕심쟁이 어린이들에게 선물 하나를 더 줘야 한다.선물 개수 총합은 주어진 숫자 목록의 숫자들만 사용해야 한다.주어진..

• format_list_bulleted 컴퓨터 공학/Algorithm
• · 2018. 9. 12.
• textsms