Two pointers algorithm은 연산량을 줄여주는 효과적인 알고리즘입니다. 주로 원하는 해를 구하는 문제의 연산량 줄이기에 사용되는데, 구현 자체는 그렇게 어렵지 않아서 알아두면 두고두고 쓸 일이 많을 겁니다. Two pointers algorithm은 두개의 지점을 최종 지점으로 움직이면서 몇가지 처리를 하면 원하는 해가 구해지는 형태입니다. https://www.acmicpc.net/problem/2003 2003번: 수들의 합 2 첫째 줄에 N(1 ≤ N ≤ 10,000), M(1 ≤ M ≤ 300,000,000)이 주어진다. 다음 줄에는 A[1], A[2], …, A[N]이 공백으로 분리되어 주어진다. 각각의 A[x]는 30,000을 넘지 않는 자연수이다. www.acmicpc.net ..
문자열 문제를 풀다보면 이런건 있으면 편할 텐데... 라는 생각이 들 때가 많다. 예를 들면, 문자열을 비교하거나 문자열의 길이가 주어지지 않은 경우 등의 다양한 경우가 있다. 이번 글에서는 알아두면 유용한 문자열 함수에 대해 알아보자. https://www.cplusplus.com/reference/cstring/ ^-- cstring reference 1. string.h( = cstring ) string.h는 문자열을 처리하는 함수를 모아둔 헤더 파일이다. 이 헤더 파일을 코드에 포함시키면 문자열의 길이, 문자열 비교 등을 쉽게 처리할 수 있다. 예시를 한번 봐보자. - 문자열의 길이를 알아내는 방법 ( strlen ) strlen의 어원은 str( ing )len( gth )으로 문자열의 길이를..
목차 1. Back Tracking의 개념/이해 2. Back Tracking 활용 방향 3. 다양한 Back Track 구현 Back Tracking의 개념/이해 Back Tracking은 최적 값을 찾는데 사용할 수 있는, 글쓴이의 개인적인 의견으로는 제일 쉬운 방법입니다. Back Tracking은 말 그대로 값을 뒤로 추적하는 방법입니다. 기본적인 원리는 DFS를 기반으로 탐색을 진행하고 아니다! 싶으면 다시 돌아가는 방법이자 하나의 기법이라고 생각하면 됩니다. 일반적으로 재귀로 구현하는 것이 정석이고, 그 외의 방법으로 구현하는 것은 아직까지는 보지 못했습니다. Back Tracking을 쉽게 생각하자면 우리가 수학문제 푸는 것과 비슷하다고 생각하시면 됩니다. 우리가 수학문제를 처음 풀 때, 일..
http://koistudy.net/?mid=prob_page&NO=767 - 순위 구하기 (large) - 문제 요약 n명의 순위를 구하려고 하는데, 만약 점수가 같다면 같은 등수로 처리한다. - 해설 여러가지 방법(pair, struct, etc...)이 있을 수 있지만, 구조체를 vector에 넣어서 해결해 보았다. 구조체를 vector에 넣으면 어떻게 접근해야 하나 고민을 많이 했었다. 왜냐하면, 그냥 구조체의 인덱스에 배열처럼 접근하려 하면 전역으로 선언된 벡터에서 에러가 나기 때문이었다. 그래서 찾아본 결과 2가지 가능한 경우가 존재하는 것을 알게 되었다. 1. 구조체의 이름 설정 말 그대로 vector에 넣기 전에 구조체를 이름으로 선언해 저장해 놓은 뒤 넣는 방법이다. 구조체의 이름은 다음..
http://koistudy.net/?mid=prob_page&NO=706 -- R&E 가는길 (Tiny) 지금까지 우리는 정점과 간선으로만 이루어진 그래프를 탐색하였다. 여기서 가중치가 포함되면 물론 일반적인 DFS/BFS의 형식을 벗어나지는 못하지만, 또 다른 방법으로 그래프를 해석할 수 있게 된다. 오늘은 Back_track을 이용해 가중치 그래프에서 최소 경로로 도착지점에 도착하는 비용을 구해보자. 목차 1. 지금가지의 그래프 탐색 2. back_track을 이용한 그래프 탐색과 가중치 처리 지금까지의 그래프 탐색 지금까지 그래프 탐색하면 깊이 우선 탐색으로 파고 들어가는 방법을 떠올렸을 것이다. 대표적으로 KOI 문제 중에는 단지 번호 붙이기가 있다. 이러한 것은 그래프 탐색의 한 종류이지만 그..
목차 1. vector의 기본 사용법 2. vector를 배열처럼 사용하는 방법 3. vector에 구조체 넣고/접근하는 방법 4. vector 정렬 vector는 가변길이 배열이다. 가변길이 배열이란? 배열의 크기를 정해두는 것이 아니라, 코드를 진행하면서 배열의 크기를 결정하는 배열을 말한다( 즉, 배열의 크기를 정하지 않아도 된다. ). 오늘은 이 vector라는 놈에 대해 알아보자. vector의 기본 사용법 우리가 배열을 사용할 때, 변수를 배열에 저장하기 위해서는 해당 인덱스에 직접 접근해야 했다. 하지만 vector는 조금 다른? 저장 방법을 가지고 있다. vector는 가변길이 배열로 코드를 진행하면서 배열의 크기를 진행할 수 있다고 했는데, 이것이 왜 가능할까? 이것을 이해하기 위해서 우..
목차 1. 논리연산 2. 조건문 3. 반복문 4. 배열 5. 함수 논리 연산 수학에서의 논리 연산과 컴퓨터에서의 논리 연산이 다르고, 참 거짓을 판별할 때 중요한 연산 방법이니 여려워 보여도 잘 읽어보세요. 수학에서의 Boolean Algebra 연산자는 크게 3가지로 나뉜다. 1. x ∧ y : 둘 다 참일 경우를 의미한다. 2. x V y : 둘 중 하나라도 참인 경우를 의미한다. 3. ㄱx : 참을 거짓으로 거짓을 참으로 바꾸는 연산자이다. 자 수학에서는 이것 외에도 여러가지 연산자가 있지만, 컴퓨터와 연관지어 설명할 때 꼭 필요한 3가지만 알려주도록 하겠다. 예시를 들어보자면, ( 0은 거짓, 1은 참 을 나타낸다. ) 2.의 경우에 0 1이면 둘 중 하나가 참이므로 1을 출력한다. 또 1 1이어..
목차 1. 기본 출력 2. 기본 입출력 / 변수 3. 변수 타입 4. 연산 기본 출력 C/C++에서 출력은 다음과 같이 할 수 있습니다. #include //standard input output header 기본 입출력 헤더파일이다. int main() // main함수를 실행한다. { printf("Hello"); //printf( = printf format string)은 출력을 담당한다. return 0; // main함수를 종료한다. } #include 는 기본 입출력 헤더파일( standard input output header )을 사용한다는 뜻이다. 이러한 헤더 파일은 엄청나게 많은 종류가 존재한다. C/C++언어에서는 위와 같이 헤더 파일을 추가해서 헤더 파일에 있는 기능을 사용할 수 ..