목록전체보기 (161)
빠똥빠똥

#문제링크 : www.acmicpc.net/problem/1916 1. 노드 N개, 간선 M개인 그래프에서 최단거리를 구하는 문제. 그래프에서 최단거리를 구하는 알고리즘 중 가장 성능이 좋다고 알려진 다익스트라를 사용하면 됩니다. 2. 다익스트라는 먼저, 인접행렬 또는 인접리스트로 그래프를 표현한 뒤, dist배열과 check배열을 선언합니다. 3. dist[x] = 시작노드로부터 x번째 노드까지의 최소 거리를 의미하고, check[x]=1은 x노드를 방문했다.를 의미합니다. a[i][j]는 i번째 도시에서 j번째 도시로 가는 비용을 의미합니다. 4. 문제에서 살펴야할 조심해야하는 부분은 도시는 최대 1000개, 버스는 최대 10만개 입니다. 이말은, 중복되는 버스노선이 존재한다는 걸 의미하고, 문제에서..

#문제링크 : www.acmicpc.net/problem/11444 1. 피보나치 수3과 동일한 방법으로 풀었습니다.

#문제링크 : www.acmicpc.net/problem/17298 1. O(N^2)의 알고리즘 밖에 떠오르지 않아서 다른 블로그를 참조했습니다. 2. 개인적으로 생각하기 굉장히 어려운 알고리즘이었습니다. 요약하면 이렇습니다. 우선 스택을 만들고, 스택에, 문제에서 주어진 수의 범위보다 큰 수를 미리 하나 넣어놓습니다. 그리고 주어진 수열의 뒤에서부터 차례로 스택top의 숫자와 비교합니다. 3. 만약, 수열의 숫자가 스택top보다 작다면, 스택top에 들어있는 숫자가 오큰수가 됩니다. 따라서, 이때에는 스택top의 숫자를 해당 수열의 인덱스와 같은 정답 배열에 우선 복사하고, 수열 숫자를 스택에 push합니다. (이 과정에서 pop은 없습니다.) 4. 만약, 수열의 숫자가 스택top보다 크다면, 스택to..

#문제링크 : www.acmicpc.net/problem/13305 1. 처음엔, 도시 중 가장 싼 도시를 찾아 그 도시부터 뒤로 쭉 그 가격으로 구매, 도시 범위를 처음~가장 싼 도시로 수정하고 다시 그중에 가장 싼 도시를 찾아 그 도시부터 수정된 범위의 마지막 도시까지 그 가격으로 구매 ... 이런식으로 했었는데, 답은 맞았지만 시간초과가 나왔다. 2. 1의 과정은 뒤에서부터 계산을 더하는 식이지만, 앞에서부터 생각해도 결과는 같다는 걸 알 수 있다. 무슨 말이냐면, 앞의 도시부터 기름을 사나가는데, 지금 내가 있는 도시보다 싼도시가 나올때까지 현재 도시의 가격으로 기름을 사나가는 것이다.

#문제링크 : www.acmicpc.net/problem/9184 1. 단순 재귀로 위의 함수를 수행하면 이미 구했던 함숫값을 다시 구해야하는 경우가 여럿 생긴다. 2. 이미 구했던 함숫값을 배열에 저장하여 동적코딩이 가능하게 한다. 3. 조건문으로 이미 구했던 함숫값이라면 check배열에서 꺼내오고 아니라면 check배열에 저장한다.

#문제링크 : programmers.co.kr/learn/courses/30/lessons/12924 1. 먼저, n이 홀수인 경우, 무조건 n/2 + (n/2 + 1)인 경우가 존재한다. 즉, n -> ㅁ+ㅁ (ㅁ는 빈자리)형태로 표현가능하다. 2. 차근차근 생각해보자. 각 숫자의 자리를 ㅁ으로 표현하겠습니다. ⓐ 연속된 3개의 숫자의 합이 n일때, ㅁ(ㅁ)ㅁ -> 가운데 숫자는 n/3임이 자명하다. 괄호 안의 숫자 양 옆에 위치한 숫자 짝의 합 = 가운데 숫자 * 2 ⓑ 연속된 4개의 숫자의 합이 n일때, ㅁ(ㅁㅁ)ㅁ -> 괄호 안의 숫자와 양 옆에 위치한 숫자 짝의 합이 모두 같다. 그리고 그 합은 홀수임이 자명하다. ⓒ 연속된 5개의 숫자의 합이 n일때, ㅁ(ㅁ(ㅁ)ㅁ)ㅁ -> 가운데 숫자는 n/..

#문제링크 : programmers.co.kr/learn/courses/30/lessons/17680 1. 블로그를 참고했습니다. 2. 리스트와 맵을 이용하여 구현한다. 리스트는 들어온 문자열을 담는 실제 캐시의 역할, 리스트에서 임의의 값을 삭제하는 것은 가능하지만, 임의의 값을 찾는 것은 O(N)만큼의 시간이 걸린다. 왜냐하면, 순차적으로 내가 찾으려는 값과 같은 값인지 반복자를 하나씩 증가시켜가며 찾아야하기 때문. 따라서, 맵의 find 함수를 사용해서 더 수월하고 빠르게 찾기 위해 맵을 사용한다. 임의의 값을 찾는 행위가 필요한 이유는, 캐시에 새로들어오는 문자열이 캐시 안에 이미 존재하는지, 아닌지 확인하기 위함이다. 3. 맵을 통해, 새로 들어온 값이 이미 캐시안에 존재하는지 확인하고, ⓐ 존..

※생활코딩의 수업을 그대로 가져와서 정리했습니다. - git-scm.com 에서 운영체제에 맞는 EXE파일 다운로드 1. 버전관리를 하고자하는 디렉토리 생성, 해당 디렉토리로 위치 이동. 2. git init . -> "현재 디렉토리를 git에게 버전관리 시킨다." 는 의미의 명령어, "."은 하위 모든 디렉토리 포함. git init -> 현재 디렉토리를 저장소로 관리한다. 3. 위의 명령어를 실행하면 ".git" 이라는 디렉토리가 생성된다. ".git"에는 ".git"의 부모디렉토리에 생성되는 문서들을 버전관리하는 정보들이 적당히 저장되고 관리된다. -> ".git"이라는 디렉토리를 지우면 모든 버전이 사라진다. 1. Working tree(날 것) -> add -> Staging Area(버전만들 ..