초콜릿 파워

용기는 어떻게 생겨나는 가 용기가 있고 없음에 따라 삶은 완전히 바뀐다. 이는 그냥 수사로서 하는 말이 아니라 표현 그대로이다. 문제는 용기라는 것이 단지 "난 오늘부터 용기 있는 사람이 될 거야"라고 다짐한다고 해서 쉽게 갖게 되는 힘이 아니라는 점이다. 자신의 삶을 제대로 살게 하는 용기, 주체적이고 독립적으로 살게 하는 용기, 그리하여 자유롭게 살도록 이끄는 용기란 어떻게 한 사람의 내면에 단단히 자리를 잡게 되는 것일가. 한 사람이 유익한 자리에 서도록 용기를 갖게 하기 위해서는 진실을 바로 보지 못하는 눈을 뜨도록 이끌어 주고, 잘못된 방식을 고집하지 않도록 제지하는 데 성공해야만 한다. 아들러의 심리학이 용기를 얻고 그것을 자기화하는데 큰 도움을 줄 수 있는 까닭은, 용기를 갖고 주체적으로 이..

2주가 넘는 검사 후에 드디어~~~ 애드 고사를 통과해버렸습니다! 그래서 이번에는 애드 고사를 어떻게 통과했는지 적어보려고 합니다. 우선 저는 방문자수가 20~40 언저리, 그리고 더 낮을 때는 10이하일 때도 있는 그런 블로그를 가지고 있었습니다. 사실 방문자 수가 적다고 생각해서, 안될 줄 알았는데, 개인적으로 생각해봤을 때 도움이 되었다고 생각한 일은 다음과 같습니다. 1. 매일 글 쓰기 - 하루도 빠짐없이 글을 썼습니다. 2. 사람들이 읽을 만한 글 쓰기 - 유입경로를 보면 티스토리는 매번 다음에서 검색될 때만 상단 노출이 되더군요(카카오 티스토리이다보니 그런가 봅니다), 그리고 다음은 블로그 노출 방법이 최신블로그가 먼저인 건지, 유독 제가 글을 올리면 그날 밤에 해당 글 내용을 검색해서 들어오..

문제 요즘 많은 자동차에서는 GPS 네비게이션 장비가 설치되어 있다. 네비게이션은 사용자가 입력한 출발점과 도착점 사이의 최단 경로를 검색해 준다. 하지만, 교통 상황을 고려하지 않고 최단 경로를 검색하는 경우에는 극심한 교통 정체를 경험할 수 있다. 상근이는 오직 자기 자신만 사용 가능한 네비게이션을 만들고 있다. 이 네비게이션은 절대로 최단 경로를 찾아주지 않는다. 항상 거의 최단 경로를 찾아준다. 거의 최단 경로란 최단 경로에 포함되지 않는 도로로만 이루어진 경로 중 가장 짧은 것을 말한다. 예를 들어, 도로 지도가 아래와 같을 때를 생각해보자. 원은 장소를 의미하고, 선은 단방향 도로를 나타낸다. 시작점은 S, 도착점은 D로 표시되어 있다. 굵은 선은 최단 경로를 나타낸다. (아래 그림에 최단 경..

최단경로를 다익스트라로 풀고 있을 때, 그 경로도 구해야 하는 경우가 있다. (백준 #5719 거의 최단경로 문제, k번째 최단경로 등) 이럴 때는 어떻게 경로를 저장할 수 있는지 알아보았다. 다익스트라의 진행과정은 다음과 같다. 1. distance[S] 3, 0->4 로 갈 때 모두 갱신이 되고, 모든 경로가 최단경로로써 저장이 될 것이다. - 나중에 최단경로가 아님을 알고 지울 방법이 있는가? -> 알수가 없다. - 나중에 최단경로였음을 알고 되돌아 갈 수 있는 방법은? -> 직전노드를 저장해준다면? -> 갱신될 때마다 방문된 각 노드마다 직전노드를 저장한다면, 마지막에 종료되었을 때의 노드를 기준으로 직전노드로 되돌아가면(일명 벡트래킹) 그것이 최단경로일 것이다! 이러한 사고흐름을 통해, 최단경로..

시간 제한메모리 1 초 128 MB 문제 남극에 사는 김지민 선생님은 학생들이 되도록이면 많은 단어를 읽을 수 있도록 하려고 한다. 그러나 지구온난화로 인해 얼음이 녹아서 곧 학교가 무너지기 때문에, 김지민은 K개의 글자를 가르칠 시간 밖에 없다. 김지민이 가르치고 난 후에는, 학생들은 그 K개의 글자로만 이루어진 단어만을 읽을 수 있다. 김지민은 어떤 K개의 글자를 가르쳐야 학생들이 읽을 수 있는 단어의 개수가 최대가 되는지 고민에 빠졌다. 남극언어의 모든 단어는 "anta"로 시작되고, "tica"로 끝난다. 남극언어에 단어는 N개 밖에 없다고 가정한다. 학생들이 읽을 수 있는 단어의 최댓값을 구하는 프로그램을 작성하시오. 입력 첫째 줄에 단어의 개수 N과 K가 주어진다. N은 50보다 작거나 같은 ..

1. 크루스칼 알고리즘 최소 신장 트리를 구하는 알고리즘 중 하나이다. 1. 유니온 파인드 연산을 필요로 한다. 유니온 파인드 보러가기 >> 2.트리 그래프 : 순환을 갖지 않는 연결 그래프. 임의의 두 정점에 대해서 경로가 정확히 1개 존재함. 하나 이상의 정점을 가지며 임의의 간선 e를 제거한 그래프는 연결 그래프가 아니다. (연결 그래프: 모든 정점들을 간선을 통해방문할 수 있는 그래프 : 임의의 v, u 정점에 대해 path(v,u)가 존재하는 그래프) - 느낌: 그래프를 최소한의 간선으로 모두 연결해서 이동가능 할 수 있게 만든 것이되 사이클이 없는 것. - 특징: 전체 노드의 개수가 N개일때, 트리를 만들고 나면 전체 간선의 수는 N-1개가 된다. (1개의 경로로만 이루어져 있기 때문에) 3...

1. 플로이드 워셜 - 임의의 한 지점에서 다른 임의의 지점까지의 최단 거리를 구하는 알고리즘 (모든 지점에 대해 구할 수 있음: dist[V][V]) - 중간 지점을 통해서 최단거리를 갱신하는 알고리즘 - O(N^3)의 시간 복잡도: 3중 for문 - 사용가능한 시점: 시간 초과 제한에 걸리지 않을 때( 정점의 수가 약 500개 이하정도) - 다이나믹 프로그래밍 사용 : dist[i][j] = i에서 j 로 가는 거리라고 할 때, i -j의 최단경로가 i-k-j라면 i-k와 k-j도 최단경로이다. 점화식: dist[i][j](최단) = dist[i][k] + dist[k][j] - code for k

1. 유니온 파인드(Union Find) - 서로소인 집합들의 정보를 확인(find)하고 조작(union)할 수 있는 자료구조. - Union 연산 : 서로소인 집합을 '유니온' 연산을 통해서 같은 집합으로 만들 수 있다. - Find 연산 - 두 원소가 같은 집합에 속해있는지 확인할 수 있다. - 메쏘드 1. init - parent[N] 배열을 모두 자기 자신으로 초기화. 2. find - 루트를 반환하는 함수 - 재귀적으로 짤 수 있음 : 부모가 자신 일 때 종료. - 경로 압축: 변수에 결과를 반환받은 뒤, parent 를 갱신 후 다시 return 3. union - 두 원소를 받아서 한 집합으로 만드는 함수 - C++의 경우 union이라는 이름은 이미 있어서 다른 함수 이름으로 설정. - a..

시간 제한메모리 3 초 512 MB 문제 방향 없는 그래프가 주어졌을 때, 연결 요소 (Connected Component)의 개수를 구하는 프로그램을 작성하시오. 입력 첫째 줄에 정점의 개수 N과 간선의 개수 M이 주어진다. (1 ≤ N ≤ 1,000, 0 ≤ M ≤ N×(N-1)/2) 둘째 줄부터 M개의 줄에 간선의 양 끝점 u와 v가 주어진다. (1 ≤ u, v ≤ N, u ≠ v) 같은 간선은 한 번만 주어진다. 출력 첫째 줄에 연결 요소의 개수를 출력한다. 1. 문제 해석 * 그래프 연결요소란? 그래프가 이어져 있는 노드끼리 같은 색으로 선을 긋다보면, 여러가지 색깔의 그룹이 생긴다. 그러한 그룹들을 그래프의 연결 요소들이라고 부른다. 쉽게 설명한 블로그 : https://velog.io/@kj..

문제 정수로 이루어진 크기가 같은 배열 A, B, C, D가 있다. A[a], B[b], C[c], D[d]의 합이 0인 (a, b, c, d) 쌍의 개수를 구하는 프로그램을 작성하시오. 입력 첫째 줄에 배열의 크기 n (1 ≤ n ≤ 4000)이 주어진다. 다음 n개 줄에는 A, B, C, D에 포함되는 정수가 공백으로 구분되어져서 주어진다. 배열에 들어있는 정수의 절댓값은 최대 228이다. 출력 합이 0이 되는 쌍의 개수를 출력한다. 1. 문제 해석 늘 그렇듯이 브루트 포스부터 생각해볼 수 있다. 이 경우 합이 0이 되는지 안되는지 각 배열을 하나씩 탐색하면, N^4 꼴의 시간 복잡도가 나올 것이다. 따라서 이것은 매우 비효율적이므로 바로 패스. 그 다음으로 생각해볼 것은 배열의 합은 어차피 구해야 ..