Hello World

백준 1010 : 다리 놓기 문제 링크 https://www.acmicpc.net/problem/1010 1010번: 다리 놓기 입력의 첫 줄에는 테스트 케이스의 개수 T가 주어진다. 그 다음 줄부터 각각의 테스트케이스에 대해 강의 서쪽과 동쪽에 있는 사이트의 개수 정수 N, M (0 < N ≤ M < 30)이 주어진다. www.acmicpc.net 문제 내용 재원이는 한 도시의 시장이 되었다. 이 도시에는 도시를 동쪽과 서쪽으로 나누는 큰 일직선 모양의 강이 흐르고 있다. 하지만 재원이는 다리가 없어서 시민들이 강을 건너는데 큰 불편을 겪고 있음을 알고 다리를 짓기로 결심하였다. 강 주변에서 다리를 짓기에 적합한 곳을 사이트라고 한다. 재원이는 강 주변을 면밀히 조사해 본 결과 강의 서쪽에는 N개의 사..

GNU readline 사용법 개요 GNU readline은 명령 줄 인터페이스에서 줄 편집 및 입력 기록 저장 등의 역할을 하는 라이브러리다. 입력 자동완성, 커서 이동, 잘라내기, 복사, 붙여 넣기 등의 기능을 지원하며, Bash 등의 명령 줄 기반 인터랙티브 소프트웨어에서 사용된다. GNU readline wiki readline 설치 1 sudo apt-get install -y libreadline-dev cs readline 개념 man readline 1 char *readline(const char *prompt); cs ※ 문자열을 반환하므로 매번 입력을 받을 때는 메모리 관리에 신경써야 한다. ※ 컴파일 할 때는 -lreadline 플래그를 추가해줘야 한다. ※ ex) gcc sampl..

백준 1987 : 알파벳 문제 링크 www.acmicpc.net/problem/1987 1987번: 알파벳 세로 R칸, 가로 C칸으로 된 표 모양의 보드가 있다. 보드의 각 칸에는 대문자 알파벳이 하나씩 적혀 있고, 좌측 상단 칸 (1행 1열) 에는 말이 놓여 있다. 말은 상하좌우로 인접한 네 칸 중의 한 칸으 www.acmicpc.net 문제 내용 세로 R칸, 가로 C칸으로 된 표 모양의 보드가 있다. 보드의 각 칸에는 대문자 알파벳이 하나씩 적혀 있고, 좌측 상단 칸 (1행 1열) 에는 말이 놓여 있다. 말은 상하좌우로 인접한 네 칸 중의 한 칸으로 이동할 수 있는데, 새로 이동한 칸에 적혀 있는 알파벳은 지금까지 지나온 모든 칸에 적혀 있는 알파벳과는 달라야 한다. 즉, 같은 알파벳이 적힌 칸을 두..

atoi 구현 / 문자열을 숫자로 atoi 기본 개념 및 구조 #include 에 내장된 함수인 atoi는 문자열을 숫자로 바꿔주는 함수이다. atoi의 구조는 아래와 같다. 1. 문자열의 초반에 오는 공백 문자(white-space characters)는 무시한다. - whitespace : \t, \v, \n, \f, \r, ' ' - 아스키코드로는 9부터 13까지, ' '는 32 - man isspace 명령어를 사용해보자(리눅스 한정) 2. 부호(+, -)는 최대 한 개까지만 올 수 있다. - 만일, 두 개 이상이라면 0이 반환된다. - 부호가 없다면 기본 양수이다. 3. 숫자를 한번 읽기 시작한다면 다른 문자가 오기 직전까지만 읽는다. - ex) 1234 → 1234 - ex) 12a34 → 1..

백준 1629 : 곱셈 문제 링크 www.acmicpc.net/problem/1629 1629번: 곱셈 첫째 줄에 A, B, C가 빈 칸을 사이에 두고 순서대로 주어진다. A, B, C는 모두 2,147,483,647 이하의 자연수이다. www.acmicpc.net 문제 내용 자연수 A를 B번 곱한 수를 알고 싶다. 단 구하려는 수가 매우 커질 수 있으므로 이를 C로 나눈 나머지를 구하는 프로그램을 작성하시오. 첫째 줄에 A, B, C가 빈칸을 사이에 두고 순서대로 주어진다. A, B, C는 모두 2,147,483,647 이하의 자연수이다. Idea A, B, C는 2,147,483,647 이하의 자연수로 int 형으로 표현 가능하다. ※ int 범위 : -2^31 ~ 2^31 - 1 A를 B번 제곱을 ..

백준 1080 : 행렬 문제 링크 www.acmicpc.net/problem/1080 1080번: 행렬 첫째 줄에 행렬의 크기 N M이 주어진다. N과 M은 50보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에는 행렬 A가 주어지고, 그 다음줄부터 N개의 줄에는 행렬 B가 주어진다. www.acmicpc.net 문제 내용 0과 1로만 이루어진 행렬 A와 행렬 B가 있다. 이때, 행렬 A를 행렬 B로 바꾸는데 필요한 연산의 횟수의 최솟값을 구하는 프로그램을 작성하시오. 행렬을 변환하는 연산은 어떤 3*3 크기의 부분 행렬에 있는 모든 원소를 뒤집는 것이다. (0 -> 1, 1 -> 0) Idea 행렬 A를 행렬 B로 바꾸는데 필요한 최소 연산 횟수를 구하는 문제이다. 이때, 연산이란 3*3 크기의 부..

백준 11403 : 경로 찾기 문제 링크 www.acmicpc.net/problem/11403 11403번: 경로 찾기 가중치 없는 방향 그래프 G가 주어졌을 때, 모든 정점 (i, j)에 대해서, i에서 j로 가는 경로가 있는지 없는지 구하는 프로그램을 작성하시오. www.acmicpc.net 문제 내용 가중치 없는 방향 그래프 G가 주어졌을 때, 모든 정점 (i, j)에 대해서, i에서 j로 가는 경로가 있는지 없는지 구하는 프로그램을 작성하시오. Idea 플로이드 알고리즘은 정점 간의 최단 경로(가중치)를 구하는 알고리즘이지만 이런 경로의 유무를 따지는 문제에도 적용하면 금세 풀 수 있다. 플로이드 알고리즘에 대해 간단히 설명하자면, 다이나믹 프로그래밍과 비슷하다. 우선 이 알고리즘의 포인트는 간선..

백준 14881 : 물통 문제 문제 링크 www.acmicpc.net/problem/14881 14881번: 물통 문제 용량이 a, b 리터인 두 물통이 있다. 이때, 물을 적절히 부어서 정확하게 c리터를 만들 수 있는지 아닌지 구하는 프로그램을 작성하시오. 물은 무한히 많다. www.acmicpc.net 문제 내용 용량이 a, b 리터인 두 물통이 있다. 이때, 물을 적절히 부어서 정확하게 c리터를 만들 수 있는지 아닌지 구하는 프로그램을 작성하시오. 물은 무한히 많다. Idea 수많은 시행착오 끝에... 물통 문제에는 크게 두 가지 규칙이 있다. (사실 저 1번에서 많이 틀려먹었다... 문제 좀 제대로 읽지...) 물통은 a와 b만 있다. 즉, a나 b에 물을 채워 c를 만드는 것이 문제이다.(=a와..

백준 4949 : 균형잡힌 세상 문제 링크 https://www.acmicpc.net/problem/4949 4949번: 균형잡힌 세상 문제 세계는 균형이 잘 잡혀있어야 한다. 양과 음, 빛과 어둠 그리고 왼쪽 괄호와 오른쪽 괄호처럼 말이다. 정민이의 임무는 어떤 문자열이 주어졌을 때, 괄호들의 균형이 잘 맞춰져 있는지 판단 www.acmicpc.net 문제 내용 (요약) "(" 와 ")", "[" 와 "]"이 서로 짝을 이루면 균형잡힌 문자열이라고 할 때, 주어진 문자열에 대해 균형잡힌 문자열인지 아닌지를 판단하자. Idea (, ), [, ] 를 만날 때마다 스택에 push하거나 pop하면서 균형잡힌 문자열인지 판단한다. "(" 또는 "["를 만나면 스택에 쌓는다. ")" 또는 "]"를 만나면 스택의..

선택 정렬 Selection Sort 선택 정렬이란? 최소 혹은 최댓값부터 찾아 정렬하는 방법 다른 정렬들에 비해 비교적 쉽게 구현이 가능하다. (오름차순일 때) 첫 인덱스부터 정렬하는 방법으로 기준으로부터 오른쪽 값들과 비교하여 가장 작은 수를 찾아 값을 교환한다. -핵심코드 1) A와 B의 값을 교환 tmp = A; A = B; B = tmp; 2) for문의 범위 설정 for( i=0; i < SIZE -1; i++){ for( j=i+1 < SIZE; j++){ ... } } 바깥 for 문 현재 기준 인덱스를 가리키는 역할 범위는 SIZE-1까지(SIZE-1까지 정렬하면 마지막은 정해지기 때문) 내부 for 문 최소(혹은 최대) 값을 찾는 역할 범위는 기준+1부터 SIZE까지 정렬 예시 선택 정..