열심히해보겠씁니다

기민이의 고민을 만들어준 짜증나는 문제 원탑이다. 시작하자마자 틀린 것은 type 선언 문제가 컸고, 17% 혹은 18%에서 틀린 것은 사이클이 여러개 있다는 것을 간과해서 그럴 수 있다. 만약 벨만포드 알고리즘을 사용할 것이라면 1. 사이클 유무 확인 2. 사이클마다 목표지점에 닿는지 확인 두 가지를 필수로 사용해야 한다. 나는 도로를 지나가는데 사용한 비용을 음수로 넣고 city 에서 얻을 수 있는 돈을 city 배열에 저장해서 단순히 + 연산으로만 구현할 수 있게 만들었고, 초반에 distance 구하는 건 줄 알고 dist 배열로 선언한 것을 그냥 총 벌어들인 돈 배열로 생각하기로 했다. 예제에서는 다음과 같은 사실을 발견해야 한다. 1. 자기 자신으로 가는 간선이 존재한다. (dist[S] = ..

값이 빈번하게 수정될 때, 구간의 합을 효율적으로 구하라는 문제이다. 인덱스 트리나 세그먼트 트리 혹은 펜윅 트리를 강요하는 문제가 아닐까 싶다. Bottom-up 방식으로 구성하는 인덱스 트리가 가장 쉬워서 인덱스 트리로 구현했다. 세그먼트 트리도 가능한데 물론, 구현하기가 쉽지 않아서.. (재귀) ㅠㅠ 인덱스 트리는 1차원 배열에다가 배정하며, (부모 인덱스 * 2 , 부모 인덱스 * 2 + 1) 이 자식의 인덱스이다. 물론 완전 이진 트리로 만든다. 고민할 점은, tree 배열을 선언할 때 할당할 메모리를 잘 생각해야 한다는 점이다. 데이터 수가 N 이면 2^n 으로 배정하여 부모-자식 사이의 관계가 유지되도록 만들어줘야 한다. 여기서 루트 노드의 인덱스는 1이고, 배열의 크기는 2^n 으로 보면 ..

임의의 트리를 주고 LCA 를 이용하여 비용과 지나가는 노드를 추출하는 문제이다. 접근 방식 1. 주어진 N-1 개의 입력을 트리로 구성한다.(이진트리조차 아닐 수 있음) 2. LCA 를 위한 parent 배열을 구성한다. 3. Cost 를 빠르게 계산하기 위해 cost 배열을 미리 계산해 놓는다. 이용할 때, a에서 parent[a] 까지 간선을 이동하는데 쓴 비용 = cost[a] - cost[ parent[a] ] 이다.(makeTree에서확인) 4. start node 가 첫 번째이고, k 번째 node 를 구하기 위해 LCA 를 또 이용한다.(query_node 확인) LCA 를 presum 으로 이용하는 방식에 대해 공부한 것 같다. 4번 정도 틀린 것 같은데 오류의 원인은 다음과 같았다. 1..

파이썬 변수와 Namespace 메모리 Namespace 에 사용하는 name(변수명, 함수명, class명, method명, module 명 등) 들이 저장되며, reference 에 name의 주소가 저장된다. name binding name의 reference 영역에 객체의 id를 저장하여 객체를 연결시키는 과정 assignment( =), augmented assignment(*=, +=, -=,...), class method function 정의, import 할 때 발생 del name을 통해 지울 수 있다. id(name) 을 통해 실제 메모리 값 접근 Identifier 변수명 등 식별자 interpreter 는 identifier를 발견하면 namespace에서 탐색한다 읽기 - loc..

기초적인 파이썬과 자바의 문법을 익히기 위해 알고리즘 문제를 풀어보기로 했다. 어려운건 힘들기 때문에(c로 해도 힘든데...) 쉬운 실버부터 차근차근 풀어보도록 하자. 위 문제는 알파벳이 연속적으로 오느냐(1개만 있어도 ok) 혹은 알파벳 사이에 다른 종류의 알파벳이 껴있느냐를 묻는 문제이다. 즉, aaabbbcdd 같은 형태는 가능하고, aaabbbaaa 같은 형태는 불가능하다. 주어진 입력에서 그룹 단어의 개수를 체크하여 출력하면 된다. 자바와 파이썬 코드의 풀이 방식은 동일하다. 1. 입력받은 단어에서 a~z까지 하나씩 확인한다. 2. a를 확인한다면 index를 찾아서 연속되는지 (next-prev==1)인지를 확인하고 연속하지 않고 떨어져있다면 세지 않는다. 파이썬 코드 def group(s:s..

백준에 엄청 자주 등장하는 증가하는 부분 수열 문제이다. N이 1백만 scale 을 가지므로 최대 NlogN 안에 풀어야한다. 그러므로 수열 순회는 N번 안에 종료해야하고 나머지 연산이 log N 안에 끝내야하므로 Binary Search 를 적용하여 풀 수 있을 것으로 기대한다. 1. 문제 접근 - 가장 긴 부분 수열을 만들기 위해 수열을 탐색하며 부분 수열을 지속적으로 갱신한다. 2. 문제 해결 - 가장 긴 수열의 정보를 지속적으로 갱신하며 진행하여 수열을 1번만 순회할 수 있도록 한다. - 가장 긴 수열의 정보를 수정할 때, 수정할 위치를 찾는 것은 Binary Search를 이용하여 logN안에 수행한다. 가장 긴 증가하는 부분 수열 2 문제는 부분 수열의 값이 어떤 것인지 중요하지 않고, 총 갯..

예외처리(Exception Handling) 런타임에서 발생하는 에러를 다루기 위해서, C에서는 조건문을 이용하여 제한을 주었다. C++에서는 드디어 일반적인 조건문과 예외처리문을 구별하여 쓸 수 있게 되었다. try, catch, throw 예외가 발생할 수도 있는 문장과 그 덩어리를 try{} 블럭 안에 작성하고, 예상되는 에러를 처리하기 위해 catch(에러){}의 블럭 안에 예외 처리 코드를 작성한다. 따라서 try와 catch 는 항상 붙여서 작성해야 하므로 가운데 다른 문장이 들어오는 등 따로 작성할 수는 없다. try 문 안에는 예외객체를 전달해주는 throw 키워드가 존재한다. try 안에서 오류가 발생한다면 throw에 의해서 예외가 던져지고 try는 종료되고 catch 블록에서 예외를 ..

함수와 연산자에 대한 오버로딩을 진행하면서 타입별로 하나하나 해줘야 했었던 불편함을 떠올려보자. 가령 제곱에 대해 오버로딩을 진행하려면 int 가 들어왔을 때, double이 들어왔을때 따로따로 해줬어야 했다. 혹은 #define 을 통해 처리했어야 했다. 하지만 이미 알고 있듯이 #define 의 정의가 힘들기 때문에 함수형으로 사용하고 싶다면 템플릿에 대해 공부해보도록 하자. 함수 템플릿(function template) 템플릿은 어떤 물체를 만들어내는 틀이라고 생각할 수 있다. 템플릿은 template 키워드를 사용한다. #include using namespace std; template T SQR(T a) { return a * a; } int main() { int a = 10; cout

목차 연산자 오버로딩의 이해 이제 C++에 대해서 어느 정도 감이 잡혔다. 이번에는 C++의 핵심적인 기능 중 하나인 연산자 오버로딩을 살펴보자. 지난 글까지 객체 다형성과 함수의 다형성에 대해서 들여다 봤다. 하지만 C++ 다형성의 끝판왕은 개인적으로 연산자 오버로딩이라 생각한다. 기본적인 원리와 방식은 기존과 동일하므로 어렵지 않게 공부할 수 있으니 한 번 들여다 보자. 연산자의 오버로딩은 함수의 오버로딩과 거의 차이가 없다. return 타입을 제외한 키값들, 함수명과 인자의 타입, 개수만이 오버로딩의 조건이 된다. 즉 return 타입은 오버로딩과 관련이 없었다는 것을 기억하고 천천히 접근해보자. 가장 기본적인 이해를 위해 잠깐 생성자의 호출을 다시 돌아보자. 앞서 살펴본 생성자 중 복사 생성자라..

목차 상속 객체지향이 절차지향과 아주아주아주 다른 포인트 중 하나인 상속이다. 상속은 말 그대로 누군가에게 물려받는 것을 의미한다. 상속의 개념은 결국 공통점을 묶어서 한 번에 유지,보수하기 편하게 만들기 위함이기 때문에 경제적인 요인과 편의성을 고려한 개념이라고 생각하면 될 것 같다. 클래스에서의 상속은 자신의 멤버 변수와 멤버 함수를 물려주는 것을 의미한다. 이 때, 상속 해주는 클래스는 상위, 기초(base), 슈퍼(super), 부모(parent) 클래스라고 부르고, 상속 받는 클래스는 하위, 유도(derived), 서브(sub), 자식(child) 클래스라고 부른다. 상속의 특징은, 부모의 모든 멤버들을 자식이 물려받는다는 것이다. 또다른 특징은, 부모의 모든 멤버를 자식이 물려받되 온전히 자식..