본문 바로가기

전체 글

 (201)
[Cisco Packet Tracer] D, D EX의 차이점을 알아보자, EIGRP command 명령어 정의 D와 D EX의 차이점은, 아래처럼 정리할 수 있다. D - 같은 AS내의 EIGRP Neighbor인 라우터의 network command를 통해서 얻어진 라우팅 D EX - 같은 AS내의 EIGRP Neighbor인 라우터에서 redistribute (RIP | OSPF | connected)을 통해서 얻어진 라우팅 위 설명에 대한 이해를 돕기 위해서, 아래 구성도를 살펴보자. R1, R2, R3는 같은 AS 100으로 잡혀있다. 따라서 R1, R2, R3는 Neighbor 관계이다. R4는 Neighbor 관계가 아니다. 따라서, 3.3.3.0은 R3의 Connected로 라우팅이 잡혀있을 것이다. 만약에 R3에서, redistribute 3.3.3.0 / 24를 하지 않았다면, R1에서는 D EX..
[BOJ 9251] LCS(왜 동적계획법인가?) https://www.acmicpc.net/problem/9251 9251번: LCS LCS(Longest Common Subsequence, 최장 공통 부분 수열)문제는 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다. 예를 들어, ACAYKP와 CAPCAK의 LCS는 ACAK가 된다. www.acmicpc.net 이 문제는 정말 다이나믹 프로그래밍의 정석같은 문제라고 볼 수 있다. 이 문제를 재귀 함수나, 동적 계획법으로 풀지 않았을 경우를 생각해보자. 두 문자열중에, 짧은 문자열을 사용해서 나올 수 있는 조합들을 모두 체크해본다고 가정하자. 짧은 문자열의 길이가 5라고 가정하면, 5C0 + 5C1 + 5C2 + 5C3 + 5C4 + 5C5의 연산이 필요하다. ..
재귀호출(recursive), 동적 계획법(Dynamic Programming) 알고리즘의 기본이라고 할 수 있는 재귀호출과 동적 계획법에 대해서 알아보자! 재귀호출 - 문제를 해결 하기 위해, 기존 문제를 작은 문제로 나눠서 문제를 푸는 것 - Big -> Small 동적 계획법 - 문제를 해결 하기 위해서, 작은 문제의 해결법을 이용해 기존 문제를 해결하는 것 - Small -> Big 그렇다면, 여기서 모든 재귀호출을 동적 계획법으로 표현할 수 있을까? 정답은 아니다. 동적 계획법이라면, 특정 단계의 문제를 해결하기 위해서, 특정 이전 단계의 문제들을 모두 해결해야 한다는 것이다. 하지만, 특정 이전 단계들의 문제들을 차례로 해결하지 않으면, 특정 단계의 문제를 해결할 수 없게 된다. 따라서, 모든 재귀호출이 동적계획법으로 표현될 수 있는 것이 아니다. 동적 계획법으로 특정 단..
두 수의 부호가 같은지 다른지 확인하는 방법[XOR], C++, 코딩스킬 일반적으로 두 수의 부호가 다르기 위해서, if문을 쓸 수도 있다. 물론 이 방법은 너무 쉽기 때문에... 누구든지 생각할 수 있다. 만약에 a, b라는 숫자가 있다고 하면, 여기서 곱하기로 부호를 체크한다면, overflow가 발생하기 때문에 틀린 방식이다. 따라서, a와 b의 부호를 각각 확인해주는 방식을 사용한다. if((a > 0 && b >0) || (a = 0 처음보면 낯설 수도 있다. 하지만..
[CISCO PACKET TRACER] L2 - L3 네트워크 구성하기, Trunk, Vlan CISCO PACKET TRACER 프로그램을 이용한 L2 - L3 네트워크 구성하는 방법에 대해서 자세히 기술. 위의 방식은, 일반적인 회사에서 사내망을 구성하기 위해서 사용하는 방식이다. 2개의 PC에서 해줘야 할것은, Default-gateway설정과 인터페이스 IP 설정만 해주면 된다. 나의 목적은 네트워크 주소가 다른 두 PC 사이에, 핑이 가능하게끔 하도록 하는 것이다. 따라서, DNS 서버는 넣지 않았다. 그 다음은 스위치 설정인데, 스위치에 Vlan 2개를 넣을 것이다. 아래는 위에 위치하는 스위치에 대한 설정이다. switchport trunk allowed add vlan 30, 40을 이용하면, 아래와 같이 설정된 것을 확인할 수 있다. 위 아래, 스위치 설정은 동일하므로 L3 스위치..
Manacher's Algorithm, 펠린드롬 길이가 N인 문자열이 있을 때, 펠린드롬을 가장 빠르게 판단할 수 있는 방법은 마나체스 알고리즘이다. 시간 복잡도는 O(N)이다. Manacher's algorithm은 문자열 내에서 팔린드롬(palindrome,회문)을 찾는것과 관련된 알고리즘이며, 시간 복잡도는 O(n) 이다.(n은 문자열의 길이) 이 알고리즘은 문자열 S를 입력으로 받아 다음을 반환한다: 문자열 S와 길이가 같은 정수 배열 A, 각 A의 원소 A[i]는 i번째 문자열을 중심으로 하는 가장 긴 팔린드롬의 반지름의 길이.(즉, S[(i−A[i])⋯(i+A[i])]는 팔린드롬이며, S[(i−A[i]−1)⋯(i+A[i]+1)]은 팔린드롬이 아니다) 예를 들면, S='banana'라는 입력에 대해 A의 결과는: 알고리즘은 다음과 같다: i는..
9252번 : LCS 2 https://www.acmicpc.net/problem/9252 9252번: LCS 2 LCS(Longest Common Subsequence, 최장 공통 부분 수열)문제는 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다. 예를 들어, ACAYKP와 CAPCAK의 LCS는 ACAK가 된다. www.acmicpc.net 이 문제는 다이나믹 프로그래밍 문제이다. DP 정의를 잘하면 쉽게 풀 수 있는 문제이다. 두 문자열의 가장 긴 공통된 부분 수열을 찾아야 하는 문제이다. str1 : ACAYKP str2 : CAPCAK 이 두 수열에서 가장 긴 공통된 부분 수열을 어떻게 찾을 수 있을까? 만약 가장 긴 공통된 부분 수열이 있다고 가정하면, CAPCAK에서 각 문자는..
2096번 : 내려가기 https://www.acmicpc.net/problem/2096 2096번: 내려가기 첫째 줄에 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 N개의 줄에는 숫자가 세 개씩 주어진다. 숫자는 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 중의 하나가 된다. www.acmicpc.net 이 문제는, 간단하게 상향식 접근으로 문제를 풀 수 있지만, 메모리 초과가 계속 발생한다. 따라서, 계속 사용되는 DP 값들만 저장해둬야 한다는 아이디어가 필요하다. 점화식은 다음과 같이 작성할 수 있다. R = ROW(1 ~ N) C = COL(1 ~ 3) 만약 C가 1이고, DP를 R, C까지 온 최댓값이라고 정의하자 DP[R][C} = max(DP[R - 1][0], DP[R - 1][1]) + arr[R..

티스토리툴바