컴퓨터에서의 문자표현 영어는 대소문자 합쳐서 52이므로 6(64가지)비트면 모두 표현할 수 있다. 코드체계라고 부른다. 지역마다 해석이 달라 혼동을 피하기 위해 표준안을 만들기로 했다. ASCII(American Standard Code for Information Interchanber) 문자 인코딩 표준이 제정 7bit 인코딩으로 128문자를 표현하며 33개의 출력 불가능한 제어 문자들과 공백을 비롯한 95개의 출력 가능한 문자들로 표현 확장 아스키는 표준 문자 이외에 악센트, 도형, 특수 문자 등 부가적인 128개의 문자를 추가할 수 있게 하는 부호이다. 표준 아스키는 7bit 사용, 확장 아스키는 1B 내의 8bit 사용 확장 아스키는 프로그램이나 컴퓨터 또는 프린터가 그것을 해독할 수 있도록 설..

지날 글에서는 배열, 정렬, 그리디알고리즘에 대해 가볍게 알아보았다. 알고리즘 사이트들을 통해서 쉬운 문제부터 단계적으로 풀어보며 익숙해지고 있다. 오늘은 1차원 List를 묶어놓은 List인 2차원 배열에 대해 알아보자. 선언 2차원 이상의 다차원 List는 차원에 따라 Index를 선언 2차원 List의 선언: 세로길이(행의 개수), 가로 길이(열의 개수)를 필요로 함 Python에서는 데이터 초기화를 통해 변수선언과 초기화가 가능함 arr = [[0,1,2,3],[4,5,6,7]] (2행 4열의 2차원 List) N = int(input) arr = [list(map(int, input().split()) for _ in range(N)] 배열 순회 n X m 배열의 n*m개의 모든 원소를 빠짐없이..

알고리즘 첫 글에서는 배열이라고 하는 자료구조에 대해 알아보자. 파이썬을 배우며 리스트, 딕셔너리 등을 배웠는데 이런 것들도 배열과 비슷한 구조를 띄고 있다. 배열 일정한 자료형의 변수들을 하나의 이름으로 열거하여 사용하는 자료구조 아래의 그림처럼 6개의 숫자를 배열로 바꾸어보았다. 배열이 왜 필요할까? 프로그램 내에서 여러 개의 변수가 필요할 때, 일일이 다른 변수명을 이용하여 자료에 접근하는 것은 매우 비효율적일 수 있다. 배열을 사용하면 하나의 선언을 통해서 둘 이상의 변수를 선언할 수 있다. 단순히 다수의 변수 선언을 의미하는 것이 아니라, 다수의 변수로는 하기 힘든 작업을 배열을 활용해 쉽게 할 수 있다. 즉, 여러 데이터를 하나의 이름으로 그룹핑해서 관리하기 위한 자료구조 그렇다면 배열을 사용..

저번에 배웠던 버블, 선택 정렬은 비교와 교환에 기반한 정렬 방식이었고 카운팅 정렬은 비교환 방식이었다. 이번엔 분할 정복 알고리즘에 기반한 퀵 정렬과 합병 정렬에 대해서 알아보자. # 합병 정렬 컴퓨터에 관해 일을 한다면 꼭 알아야 되는 '존 폰 노이만'이 제안한 방법 일반적으로 구현 시 중복된 값을 입력 순서와 동일하게 정렬하는 '안정 정렬' 하나의 리스트를 두 개의 균등한 크기로 분할하고 분할된 부분 리스트를 정렬한 다음, 두 개의 정렬된 부분 리스트를 합하여 전체가 정렬된 리스트가 되게 하는 방법 과정 리스트의 길이가 0 또는 1이면 이미 정렬된 것으로 보고 그렇지 않다면 리스트를 절반으로 자른다. 각 부분 리스트를 재귀적으로 합병 정렬을 이용해 정렬하고 다시 하나의 정렬된 리스트로 합병 추가적인..

지난 시간의 배열도 그렇고 오늘 배울 정렬은 대체 어떤 것을 위해 배우는 것일까? 그걸 알기 위해 '인덱스'에 대해 조금 알아보고 가자. 인덱스 인덱스라는 용어는 데이터베이스에서 유래했으며, 테이블에 대한 동작 속도를 높여주는 자료 구조이다. Database 분야가 아닌 곳에서는 Look up table 등의 용어를 사용하기도 한다. 인덱스를 저장하는데 필요한 디스크 공간은 보통 테이블을 저장하는데 필요한 디스크 공간보다 작다. 왜냐하면 인덱스는 키-필드만 갖고 있고, 테이블의 다른 세부 항목들은 갖고 있지 않기 때문이다. 배열을 사용한 인덱스 대량의 데이터를 매번 정렬하면, 프로그램의 반응은 느려질 수 밖에 없다. 이러한 대량 데이터의 성능 저하 문제를 해결하기 위해 배열 인덱스를 사용 정렬 2개 이상..

알고리즘을 풀다 보니 스택, 큐, 트리와 같은 형태를 자주 만나게 되는데 과연 자료구조란 무엇이며, 왜 사용하고, 어떤 점이 좋은 가에 대해 궁금해지기 시작해서 자료를 찾아보고 정리하기로 하였다. 1. 의미 Data Structure 즉, Data의 집합 각 원소들이 논리적으로 정의된 규칙에 의해 나열되며 자료에 대한 처리를 효율적으로 수행할 수 있도록 자료를 구분하여 표현한 것 쉽게 표현하자면 처리하고자 하는 데이터들이 모여있는 형태 처리하고자 하는 데이터들 사이의 관계(수직, 상하, 일방, 상호 등)를 정의한 것 데이터들을 사용하기 용이하게 저장해 놓은 형태 2. 목적 및 선택 기준 효율적으로 저장, 관리 잘 선택된 자료구조는 실행시간 단축, 메모리 절약의 효과를 이끌어 낸다. 자료구조를 잘 선택한다..

https://www.acmicpc.net/problem/1920 1920번: 수 찾기 첫째 줄에 자연수 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 줄에는 N개의 정수 A[1], A[2], …, A[N]이 주어진다. 다음 줄에는 M(1 ≤ M ≤ 100,000)이 주어진다. 다음 줄에는 M개의 수들이 주어지는데, 이 수들 www.acmicpc.net # 조건 자연수 N이 주어진다. 다음 줄에는 N개의 정수 A[1] ---- A[N]이 주어지고 다음 줄에는 M 그 다음 줄에는 M개의 수들이 주어지는데, M개의 수들이 A안에 존재한다면 1, 아니면 0 출력 # 접근 방법 처음엔 리스트로 받아서 contain method in을 이용하여 제출 시간초과가 나서 이분탐색으로 접근하였다. 정렬을 해준 후,..

https://www.acmicpc.net/problem/10845 10845번: 큐 첫째 줄에 주어지는 명령의 수 N (1 ≤ N ≤ 10,000)이 주어진다. 둘째 줄부터 N개의 줄에는 명령이 하나씩 주어진다. 주어지는 정수는 1보다 크거나 같고, 100,000보다 작거나 같다. 문제에 나와있지 www.acmicpc.net 10828 스택문제와 마찬가지로 Queue의 기본 기능을 구현하는 문제였다. # 조건 push X: 정수 X를 큐에 넣는 연산이다. pop: 큐에서 가장 앞에 있는 정수를 빼고, 그 수를 출력한다. 만약 큐에 들어있는 정수가 없는 경우에는 -1을 출력한다. size: 큐에 들어있는 정수의 개수를 출력한다. empty: 큐가 비어있으면 1, 아니면 0을 출력한다. front: 큐의 ..

https://www.acmicpc.net/problem/10828 10828번: 스택 첫째 줄에 주어지는 명령의 수 N (1 ≤ N ≤ 10,000)이 주어진다. 둘째 줄부터 N개의 줄에는 명령이 하나씩 주어진다. 주어지는 정수는 1보다 크거나 같고, 100,000보다 작거나 같다. 문제에 나와있지 www.acmicpc.net # 조건 push X: 정수 X를 스택에 넣는 연산이다. pop: 스택에서 가장 위에 있는 정수를 빼고, 그 수를 출력한다. 만약 스택에 들어있는 정수가 없는 경우에는 -1을 출력한다. size: 스택에 들어있는 정수의 개수를 출력한다. empty: 스택이 비어있으면 1, 아니면 0을 출력한다. top: 스택의 가장 위에 있는 정수를 출력한다. 만약 스택에 들어있는 정수가 없는 ..