[문제] 17608번: 막대기 아래 그림처럼 높이만 다르고 (같은 높이의 막대기가 있을 수 있음) 모양이 같은 막대기를 일렬로 세운 후, 왼쪽부터 차례로 번호를 붙인다. 각 막대기의 높이는 그림에서 보인 것처럼 순서대로 www.acmicpc.net [문제 풀이] - 우선 막대기를 입력받으며 stack에 저장 - 하나씩 pop하며 가장 높은 막대기와 비교 - 맨 오른쪽 막대기는 무조건 보이는 것임 [코드] #include #include using namespace std; int top=-1; int stack[100000]; int main() { int tc=0,num=0; int count=0, pre=0, com=0; cin>>tc; cin.ignore(); for(int i=0;i>num; ci..

Computer Graphics 1. History and application 숙명여자대학교 컴퓨터 그래픽스 수업 - 유석종 교수님 # Computer Graphics - 전통적으로 그리는 그림 vs 컴퓨터 그래픽스 > 컨버스에 그리는 것 vs 픽셀의 밝기 조절 (digital 방식) - 정의 > 컴퓨터 시스템을 사용하여 그림이나 이미지를 제작/만드는 모든 측면에 관련된 예술 또는 학문 분야 > 알고리즘에 의해 복제가능해지고 프로그램화할 수 있음 → 원본이 어떤 것인지 모르는 문제가 발생 # Related Areas > input: 예를 들어 command(명령문)으로 주어짐 # Traditional Computing - Alpha-numeric computing - text → text # Compu..

[문제] Correctness and the Loop Invariant | HackerRank How do you demonstrate the correctness of an algorithm? You can use the loop invariant. www.hackerrank.com [문제 설명] - 주어진 삽입 정렬 코드를 수정하여 프로그램을 완성 - 주어진 삽입 정렬 코드 void insertionSort(int N, int arr[]) { int i,j; int value; for(i=1;i0 && value0 인덱스에 대한 조건식 수정 [코드] #include #include #include #include #include void insertionSort(int N, int *arr) { in..

[문제] Mini-Max Sum | HackerRank Find the maximum and minimum values obtained by summing four of five integers. www.hackerrank.com [문제 설명] - 입력: 5개의 띄어쓰기로 구분되는 숫자 5개를 한 줄로 입력받음 - arr: 주어진 arr에는 5개의 정수 값을 입력받을 수 있음 - 출력: 32bit 정수보다 커야함, 5개의 숫자 중 4개를 골라 가장 작은 합과 가장 큰 합을 출력 [문제 풀이] - 입력 받은 arr를 정렬(버블 정렬 사용)하여 오름차순으로 정리 - for문을 이용하여 두개의 출력 값을 계산 > 가장 합이 작을 때는 인덱스 0~3까지의 합 > 가장 합이 클 때는 인덱스 1~4까지의 합 - 출..

1. 연결 리스트 # 연결 리스트와 배열의 비교 - 리스트: 동일한 자료형으로 된 원소(item)들의 모임으로 선형 리스트(linear list)와 연결 리스트(linked list)로 나뉨 > 선형 리스트: 배열로 구현되는 순서 리스트(ordered list)로 원소들이 메모리에 연속적으로 저장되며 인덱스로 접근 * 배열 원소의 개수는 선언 시점 이후에는 변경할 수 없음 → 크기를 잘못 예측하지 않도록 주의해야 함 * 배열은 시스템에 의해 메모리 상에서 관리됨 > 연결 리스트: 원소들이 프로그램 실행 중에 동적으로 생성되거나 삭제되므로 리스트의 크기를 미리 예측할 필요 X 원소들은 링크(link)를 통해 서로 연결되어 있음 논리적으로는 선형적이지만 물리적으로는 분산되어 있음 * 동적 메모리 관리(dyn..

자료구조 개념 및 구현 Chapter 5. 선형 자료구조 - 연습문제 Q1. 아래와 같이 선언된 배열 A가 메모리 상에 행 우선과 열 우선 순서로 각각 저장된다고 가정할 때 배열 원소 A[2][3][4]의 주소를 계산하시오 (단, &A[0][0][0] = 1000이고, sizeof(int) = 4 이다) int A[9][7][8] ; (1) 행 우선 순서(row-major order)로 저장 시 - 1560 / 1000 + (2 * 7 * 8 + 3 * 8 + 4) * 4 (2) 열 우선 순서(column-mafor order)로 저장 시 - 1572 / 1000 + (2 * 7 * 8 + 3 + 4 * 7) * 4 Q2. 7x7 희소 행렬에서 0이 아닌 원소만을 3-순서쌍(row, column, val..

# A Maze Problem - 목표: 입구로부터 출구까지의 경로를 찾음 - 조건: 0은 지나갈 수 있고, 1은 지나갈 수 없음. 직진이나 대각선 방향으로 이동이 가능 > 한 개의 프로그램은 한 개의 미로 경로를 탐색 > 현재 위치에서 이동 가능한 모든 방향 (북쪽부터 시작 → 시계방향으로 이동) 대하여 이동 가능 여부 판단 > 처음 발견한 이동 방향으로 마우스의 좌표를 수정 > 이동 가능한 방향이 없을 경우, 이전 위치로 되돌아감 > 스택을 이용하여 이동했던 위치를 기록하고 이전 위치로 찾아감. 만일 백 트랙을 시도했으나 스택이 비어있다면 결과는 실패 # 미로 찾기 스택 구현 - 구현: 경우의 수를 진행할 때는 스택 안에 쌓고, 벽에 막히면 pop하여 이전 단계까지 돌아옴 # 미로 문제의 특성 - a..

# Deque - double-ended queue - 후단(rear)으로만 데이터를 삽입할 수 있었던 기존 선형 큐, 원형 큐와 달리 큐의 전단(front) 와 후단(rear)에서 모두 삽입과 삭제가 가능한 큐 * 데이터 삽입: front 감소, rear 증가 * 데이터 삭제: front 증가, rear 감소 # Abstract Data Type in deque 1) 매크로 및 타입 재정의 - boolean: 참과 거짓을 return하는 함수 및 변수들을 위해 정의 - 원하지 않는 곳에서 함수가 종료될 시 return 값 통일을 위해 ERROR(-1) 정의 - int type 이외에 다른 type에도 사용하기 위해 element로 type을 정의 #define TRUE 1 #define FALSE 0 ..

# 수식의 평가 - 수식(expression): 연산자(operator)와 피연산자(operand)로 구성된 문장 - 연산자의 종류: 산술 연산자(arithmetic), 논리 연산자(logic), 대입 연산자(assignment) 등 - 피연산자의 종류: 변수(variable) 또는 상수(constant) - 수식의 표기법 # 연산자 우선순위 - 우선순위 (precedence): 아래의 표에서 번호가 높을수록 우선순위가 높음 - 결합성(associativity) 규칙: 연산의 방향을 결정 (왼 → 오 / 오 →왼) # 중위 표기법 vs 후위 표기법 # 후위 수식 계산 알고리즘 - 후위 수식의 평가: (5 7 * 9 + 3 4 / -) - 수식 평가 스택 > stack: 정수 배열로 선언된 수식 평가 스택..

# 큐 - 큐: 처리를 기다리고 있는 작업(원소)들의 리스트 - 선입 선출(FIFO, First-In, First-Out) 방식 / FCFS (First-Come, First-Served) - 우선순위를 부여하지 않음 - 새로운 원소는 큐의 맨 뒤(rear)에 삽입되고 큐의 맨 앞(front) 원소가 먼저 삭제됨 - insert된 순서대로 처리됨 - 스택과 달리 큐의 맨 앞 원소와 맨 뒤 원소를 가리키기 위한 두 개의 front와 rear 포인터가 필요 Q = [a0, a1, ..., an-1] # 큐의 구현 - front: delete할 때 사용 - rear: stack에서의 top과 같은 역할을하며 add할 때 사용 - front와 rear 포인터의 초기 값 = -1 ← 일반적으로 이렇게 설정 - 새..