알고리즘 2023. 10. 6.
백트래킹 Backtracking
백트래킹 개념 1. 여러 가지 선택지 (옵션) 들이 존재하는 상황에서 한 가지를 선택한다 2. 선택이 이루어지면 새로운 선택지들의 집합이 생성된다 3. 이런 선택을 반복하면서 최종 상태에 도달한다 4. 올바른 선택을 계속하면 목표 상태(goal state)에 도달한다 백트래킹과 깊이우선탐색(DFS)의 차이 DFS는 완전탐색의 방법 중 한 가지이다. 백트래킹은 어떤 노드에서 출발하는 경로가 해결책으로 이어질 것 같지 않으면 더 이상 그 경로를 따라가지 않음으로써 시도의 횟수를 줄인다. (Prunning 가지치기) 깊이 우선 탐색이 모든 경로를 추적하는데 비해, 백트래킹은 불필요한 경로를 조기에 차단한다. 깊이 우선 탐색을 하기에는 경우에 수가 너무나 많다. 즉 N! 가지의 경우의 수를 가진 문제에 대해 깊..
알고리즘 문제/백준 2023. 9. 30.
4195 친구 네트워크 (Java)
4195 친구 네트워크 문제 🌐 민혁이는 소셜 네트워크 사이트에서 친구를 만드는 것을 좋아하는 친구이다. 우표를 모으는 취미가 있듯이, 민혁이는 소셜 네트워크 사이트에서 친구를 모으는 것이 취미이다. 어떤 사이트의 친구 관계가 생긴 순서대로 주어졌을 때, 두 사람의 친구 네트워크에 몇 명이 있는지 구하는 프로그램을 작성하시오. 친구 네트워크란 친구 관계만으로 이동할 수 있는 사이를 말한다. 입력 첫째 줄에 테스트 케이스의 개수가 주어진다. 각 테스트 케이스의 첫째 줄에는 친구 관계의 수 F가 주어지며, 이 값은 100,000을 넘지 않는다. 다음 F개의 줄에는 친구 관계가 생긴 순서대로 주어진다. 친구 관계는 두 사용자의 아이디로 이루어져 있으며, 알파벳 대문자 또는 소문자로만 이루어진 길이 20 이하의..
알고리즘 2023. 9. 29.
이중 탐색 Binary Search, 퀵 정렬 Quick Sort
이진 검색 이진 검색 Binary Search 자료의 가운데에 있는 항목의 키 값과 비교하여 다음 검색의 위치를 결정하고 검색을 계속 진행하는 방법 목적 키를 찾을 때까지 이진 검색을 순환적으로 반복 수행함으로써 검색 범위를 반으로 줄여가면서 보다 빠르게 검색을 수행함 이진 검색을 하기 위해서는 자료가 정렬된 상태여야 한다 검색 과정 자료의 중앙에 있는 원소를 고른다 중앙 원소의 값과 찾고자 하는 목표 값을 비교한다 중앙 원소의 값과 찾고자 하는 목표 값이 일치하면 탐색을 종료한다 목표 값이 중앙 원소의 값보다 작으면 자료의 왼쪽 반에 대해서 새로 검색을 수행하고, 크다면 자료의 오른쪽 반에 대해서 새로 검색을 수행한다 찾고자 하는 값을 찾을 때까지 1~4의 과정을 반복한다 알고리즘: 반복구조 binar..
알고리즘 2023. 9. 28.
분할 검색 - 개념과 병합 정렬
분할 정복 병합 정렬 분할 정복 분할 정복 기법 유래 1805년 12월 2일 아우스터리츠 전투에서 나폴레옹이 사용한 전략 전력이 우세한 연합군을 공격하기 위해 나폴레옹은 연합군의 중앙부로 쳐들어가 연합군을 둘로 나눔 둘로 나뉜 연합군을 한 부분씩 격파함 설계 전략 분할 (Divide) : 해결할 문제를 여러 개의 작은 부분으로 나눈다 정복 (Conquer) : 나눈 작은 문제를 각각 해결한다 통합 (Combine) : (필요하다면) 해결된 해답을 모은다 Top-down approach 반복 (Iterative) 알고리즘 O(n) Interative_Power(x, n) result = 1 FOR i in 1 -> n result = result * x RETURN result 분할 정복 기반의 알고리즘 ..
알고리즘 2023. 9. 27.
비트마스킹 - 부분집합, 조합
완전 검색 - 부분집합 부분집합 조합 부분집합 Powerset 비트 연산자 연산자 연산자의 기능 & 비트 단위로 AND 연산을 한다 | 비트 단위로 OR 연산을 한다 ^ 비트 단위로 XOR 연산을 한다 ~ 단항 연산자로서 피연산자의 모든 비트를 반전시킨다 피연산자의 비트 열을 오른쪽으로 이동시킨다 부분집합의 수 집합의 원소가 n개일 때, 공집합을 포함한 부분집합의 수는 $2^n$개이다 이는 각 원소를 부분집합에 포함시키거나 포함시키지 않는 2가지 경우를 모든 원소에 적용한 경우의 수와 같다 반복문을 이용하여 부분집합 구하기 sel = {0, 0, 0, 0} for i in 0 to 1: sel[0] = i for j in 0 to 1: sel[1] = j for k in 0 to 1: sel[2] = k..
자료구조 2023. 9. 26.
자료구조 힙 Heap - 정의, 최대 힙, 최소 힙, 우선순위 큐
힙 Heap 완전 이진 트리에 있는 노드 중에서 키 값이 가장 큰 노드에 키 값이 가장 작은 노드를 찾기 위해서 만든 자료구조 최대 힙 max heap 키 값이 가장 큰 노드를 찾기 위한 완전 이진 트리 부모 노드의 키 값 ≥ 자식 노드의 키 값 루트 노드: 키 값이 가장 큰 노드 최소 힙 min heap 키 값이 가장 작은 노드를 찾기 위한 완전 이진 트리 부모 노드의 키 값 ≤ 자식 노드의 키 값 루트 노드: 키 값이 가장 작은 노드 힙의 예 힙이 아닌 이진 트리 힙 - 삽입 17 삽입 23 삽입 힙 - 삭제 힙에서는 루트 노드의 원소만을 삭제할 수 있다 루트 노드의 원소를 삭제하여 반환한다 힙의 종류에 따라 최대값 또는 최소값을 구할 수 있다 힙의 활용 1 우선순위 큐 우선순위 큐를 구현하는 가장 ..
알고리즘 2023. 9. 25.
자료구조 트리 Tree - 정의, 이진 트리
Tree 트리 이진 트리 트리 트리의 개념 비선형 구조 원소들 간에 1:N 관계를 가지는 자료구조 원소들 간에 계층관계를 가지는 계층형 자료구조 상위 원소에서 하위 원소로 내려가면서 확장되는 트리(나무) 모양의 구조 한 개 이상의 노드로 이루어진 유한 집합이며 다음 조건을 만족한다 노드 중 최상위 노드를 루트(root)라 한다 나머지 노드들은 n(≥0) 개의 분리 집합 T1, …, Tn으로 분리될 수 있다 이들 T1, …, Tn은 각각 하나의 트리가 되며 (재귀적 정의) 루트의 부 트리 (subtree)라 한다 용어 정리 노드 (node) 트리의 원소 트리 T의 노드: A, B, C, D, E, F, H, I, J, K 간선 (edge) 노드를 연결하는 선, 부모 노드와 자식 노드를 연결 루트 노드 (r..
알고리즘 2023. 9. 24.
자료구조 연결 스택, 연결 큐
연결 스택 Linked Stack 리스트를 이용해 스택을 구현할 수 있다 스택의 원소: 리스트의 노드 스택 내의 순서는 리스트의 링크를 통해 연결됨 Push: 리스트의 마지막에 노드 삽입 Pop: 리스트의 마지막 노드 반환/삭제 변수 top 리스트의 마지막 노드를 가리키는 변수 초기 상태: top = null 리스트를 이용해 Push와 Pop 연산 구현 null 값을 가지는 노드를 만들어 스택 초기화 원소 A 삽입 push(A) 원소 B 삽입 push(B) 원소 C 삽입 push(C) 원소 반환 pop Push/Pop push(i) { // 원소 i를 스택에 push temp = createNode(); temp.data = i; temp.link = top; top = temp; } pop() { te..
자료구조 2023. 9. 23.
자료구조 LinkedList - 정의, Singly Linked List, Double Linked List
Linked List 연결리스트 Singly Linked List Double Linked List 부록) 연결스택 & 연결큐 연결 리스트 특성 자료의 논리적인 순서와 메모리 상의 물리적인 순서가 일치하지 않고, 개별적으로 위치하고 있는 원소의 주소를 연결하여 하나의 전체적인 자료구조를 이룬다 링크를 통해 원소에 접근하므로, 순차 리스트에서처럼 물리적인 순서를 맞추기 위한 작업이 필요하지 않다 자료구조의 크기를 동적으로 조정할 수 있어 메모리의 효율적인 사용이 가능하다 노드 연결 리스트에서 하나의 원소에 필요한 데이터를 갖고 있는 자료단위 구성 요소 데이터 필드저장할 원소의 종류나 크기에 따라 구조를 정의하여 사용함 원소의 값을 저장하는 자료구조 링크 필드 다음 노드의 주소를 저장하는 자료구조 헤드 리스..
etc 2023. 9. 22.
노션 프로젝트 포트폴리오 작성 (포트폴리오, 프로젝트 기록 템플릿 공유)
안녕!! 이번 하반기 채용에 지원하며 여태까지 진행한 프로젝트2개..에 대해 포트폴리오를 만들었다. 테크 기업의 경우 이름부터 연락처, 경력 등등 모든 것을 담은 포트폴리오를 요구하는 것 같지만... 내가 지원한 기업의 경우에는 인적사항을 제하고 프로젝트에 관한 내용만 정리해서 제출하라고 했기 때문에 프로젝트에 관한 포트폴리오만 제작했다. 인터넷에서 다른 포트폴리오의 예시를 봤는데, 아무래도 만들어서 쓰는 게 나을 것 같아 내가 만들었다.... 그리하여 만든 나의 포트폴리오 예시!! 기록 중인 블로그 링크를 담았다. 개인적으로 Github 블로그를 기록 포트폴리오 제출용으로, 티스토리를 조금 비공식적으로 사용하고 싶어 티스토리의 게시물들을 차근차근 옮기는 중... 목차를 간단히 적었다. 설명을 간결하게 ..
Computer Science/컴퓨터구조 2023. 9. 21.
Chap7 보조기억장치
Chap7 보조기억장치 07-1 다양한 보조기억장치 하드 디스크 플래시 메모리 하드 디스크 자기적인 방식으로 데이터를 저장하는 보조기억장치 → 이때문에 하드 디스크를 자기 디스크 magnetic disk 라고도 한다. 하드 디스크의 동작 원리는 CD와 비슷하다. 원판에 데이터를 저장하고, 이를 회전시켜 리더기로 데이터를 읽는 방식이다. **플래터 platter** 하드디스크에서 데이터가 실질적으로 저장되는 곳 플래터는 자기 물질로 덮여 있어 수많은 N극과 S극을 저장한다. ⇒ 0과 1을 나타냄 ****스핀들 spindle**** 플래터를 회전시키는 도구, 스핀들이 플래터를 회전시키는 속도를 RPM (Rotation Per Minute) ****헤드 head**** 플래터를 대상으로 읽고 쓰는 구성 요소 ..
Web Back/Java 2023. 9. 19.
JSP - Java Server Page
JSP JSP JSP 기본 태그 JSP 기본 객체 페이지 이동 JSP Java Server Page JSP Servlet 표준을 기반으로 작성된 웹 어플리케이션 개발 언어 HTML 내에 Java를 작성하여 동적으로 웹페이지를 생성하여 브라우저에게 돌려주는 페이지 실행 시 Servlet으로 변환된 후 실행 JSP 구성요소 지시자 Directive JSP 페이지에 대한 설정 정보를 지정하기 위해서 사용 스크립트 요소: 스크립트릿 Scriptlet, 표현식 Expression, 선언부 Declaration JSP에서 문서의 내용을 동적으로 생성하기 위해서 사용 JSP 기본 객체 요청 및 응답 관련 정보를 얻거나 응답 결과를 만들기 위해서 사용 표현 언어 Expression Languague JSP를 좀 더 간..
Web Back/Java 2023. 9. 18.
JAVA Servlet
웹 프로그래밍 Web Architecture request, response를 보내기 위해서는 하나의 규약이 필요함: http 웹과 웹 프로그래밍 URL (Uniform Resource Locator) 웹 상의 자원을 참조하기 위한 웹 주소 웹 페이지 (Web page) 웹 브라우저를 통해서 보여지는 화면 웹 서버 (Web Server) 클라이언트 요청에 맞는 응답 (웹 페이지) 를 제공 웹 어플리케이션 (Web Application) 웹 서버를 기반으로 실행되는 응용 소프트웨어 웹 어플리케이션 서버 (Web Application Servser, WAS) 요청이 오면 알맞은 프로그램을 실행하여 응답 만들고 제공하는 서버 Dynamic Web Project Dynamic Web Project 구조 Web ..
알고리즘 문제/SWEA 2023. 9. 13.
2112 [모의 SW 역량테스트] 보호 필름
문제 🌐 성능이 우수한 보호 필름을 제작하려고 한다. 보호 필름은 [Fig.1]과 같은 엷은 투명한 막을 D장 쌓아서 제작된다. 막은 [Fig.1]과 같이 동일한 크기를 가진 바(bar) 모양의 셀들이 가로 방향으로 W개 붙여서 만들어진다. 이렇게 제작된 필름은 두께 D, 가로 크기 W의 보호 필름이라고 한다. 각 셀들은 특성 A 또는 특성 B를 가지고 있다. 보호 필름의 성능은 셀들의 특성이 어떻게 배치됨에 따라 결정된다. [Fig.1]은 셀 6개를 이어서 만든 막의 단면이다. [Fig.2]는 셀 8개로 이루어진 엷은 막 6장을 쌓아서 만든 두께 6, 가로크기 8인 보호 필름의 단면이다. A, B는 각 셀들이 가진 특성 A, 특성 B를 의미한다. 보호 필름의 성능을 검사하기 위해 합격기준 K라는 값을 ..
자료구조 2023. 9. 11.
자료구조 Queue - 원형 큐, 우선순위 큐
원형큐 우선순위 큐 삽입정렬 원형 큐 Circular Queue 원형 큐의 구조 초기 공백 상태 front = rear = 0 Index의 순환 front와 rear의 위치가 배열의 마지막 인덱스인 n-1를 가리킨 후, 그 다음에는 논리적 순환을 이루어 배열의 처음 인덱스인 0으로 이동해야 함 이를 위해 나머지 연산자 mod 사용함 front 변수 공백 상태와 포화 상태 구분을 쉽게 하기 위해 front가 있는 자리는 사용하지 않고 항상 빈자리로 둠 삽입 위치 및 삭제 위치 삽입 위치 삭제 위치 선형큐 rear = rear+1 front = front+1 원형큐 rear = (rear+1) mod n front = (front+1) mod n 원형 큐의 연산 과정 1) create Queue 2) enQ..
자료구조 2023. 9. 8.
자료구조 Queue - 정의, 특성, 선형 큐
질풍노도였던 21세 시절을 지나고 22살 이후 나에게 큐란 이 남성밖에 없었다. 큐 (Queue) 큐 선형큐 큐의 활용 Queue 큐(Queue)의 특성 스택과 마찬가지로 삽입과 삭제의 위치가 제한적인 자료구조 큐의 뒤에서는 삽입만 하고, 큐의 앞에서는 삭제만 이루어지는 구조 선입선출구조 (FIFO: First In First Out) 큐에 삽입한 순서대로 원소가 저장되어, 가장 먼저 삽입 (First In) 된 원소는 가장 먼저 삭제 (First Out) 된다 큐의 구조 및 기본 연산 큐의 선입선출 구조 큐의 기본 연산 삽입: enQueue 삭제: deQueue 연산 기능 enQueue(item) 큐의 뒤쪽(rear 다음)에 원소를 삽입하는 연산 deQueue() 큐의 앞쪽(front)에서 원소를 삭제..
알고리즘 2023. 9. 7.
재귀 호출, Memoization
재귀 호출 재귀 호출이란? 再歸 자기 자신을 호출하여 순환 수행되는 것 함수 호출은 메모리 구조에서 스택을 사용한다. (이름만 같은 다른 메서드) 간단한 문제에 대해서는 반복문에 비해 메모리 및 속도에서 성능 저하가 발생한다 일반적으로 기본 부분 (Base case), 재귀 부분 (Recursive case)로 구성된다 Base case: 재귀 호출에서 빠져나가기 위한 조건 (탈출 조건) Recursive case: 자신을 호출하는 부분 (Base case로 유도하는 방향으로 작성한다) 재귀적 프로그램을 작성하는 것은 반복 구조에 비해 간결하고 이해하기 쉽다 하고자 하는 연산에서 여러 가지 분기가 있을 때 적용하기 좋다. 재귀 호출 작성 재귀 호출의 예) 팩토리얼 계산 함수에서 실행해야 하는 작업의 특성..
개발 일기/ELICE AI 7th 2023. 9. 6.
Cursor based Pagination - Infinite Scroll 구현 (React, Scroll Event)
Cursor based Pagination - Infinite Scroll 구현 (React, Scroll Event) 커서 기반 페이지네이션 구현 과정 - 스크롤 탐지 이벤트로 무한 스크롤 페이지 만들기 엘리스 AI트랙 7기 2차 프로젝트: 채식 장려 커뮤니티 (1) 엘리스 AI 7기 2차 프로젝트를 진행하면서 인피니트 스크롤을 구현했다. 시간이 꽤 지났지만 도전했던 부분들에 대해 하나씩 써보려 한다. 첫 번째로 가장 기억에 남는 무한 스크롤이다. 프로젝트 내 적용된 파일들 - github 바로가기 전체 게시물 페이지 게시물 검색 페이지 게시물 상세 - 댓글 무한 스크롤 Contents 구현 배경 논리 구조 offset 방식 vs cursor 방식 Scroll Event Cursor Based Pagi..
자료구조 2023. 9. 6.
자료구조 Stack - 정의, 특성, 구현
Stack 스택(stack)의 특성 물건을 쌓아 올리듯 자료를 쌓아 올린 형태의 자료구조 스택에 저장된자료는 선형 구조를 갖는다 선형 구조: 자료 간의 관계가 1대1의 관계를 갖는다 비선형 구조: 자료 간의 관계가 1대N의 관계를 갖는다 (예: 트리) 스택에 자료를 삽입하거나 스택에서 자료를 꺼낼 수 있다 마지막에 삽입한 자료를 가장 먼저 꺼낸다. 후입선출(LIFO, Last-In-First-Out)이라고 부른다. 예를 들어 스택에 1, 2, 3 순으로 자료를 삽입한 후 꺼내면 역순으로 3, 2, 1 순으로 꺼낼 수 있다. 스택의 구현 스택을 프로그램에서 구현하기 위해서 필요한 자료구조와 연산 자료구조: 자료를 선형으로 저장할 저장소 C언어에서는 배열 사용 저장소 자체를 스택이라 부르기도 한다 스택에서 ..
알고리즘 2023. 8. 30.
패턴 매칭 - 브루트 포스, 보이어 무어
패턴 매칭 패턴 매칭에 사용되는 알고리즘들 고지식한 패턴 검색 알고리즘 ex) 브루트 포스 카프-라빈 알고리즘 KMP 알고리즘 보이어-무어 알고리즘 고지식한 알고리즘 (Brute-Force) 본문 문자열을 처음부터 끝까지 차례대로 순회하면서 패턴 내의 문자들을 일일이 비교하는 방식으로 동작 알고리즘 설명 고지식한 패턴 검색 알고리즘 // p[] : 찾을 패턴 -iss // t[] : 전체 텍스트 - This iss a book // M : 찾을 패턴의 길이 // N : 전체 텍스트의 길이 // i : t의 인덱스 // j : p의 인덱스 BruteForce(char[] p, char[] t) { i = 0, j = 0 while(j
Computer Science/컴퓨터구조 2023. 8. 30.
Chap4 CPU의 작동 원리
Chap4 CPU의 작동 원리 04 CPU의 작동 원리 04-1 ALU와 제어장치 CPU의 구성 요소: ALU와 제어 장치 ALU와 제어 장치의 정보 처리 방식 및 역할 ALU ALU가 연산을 하기 위해서는 피연산자와 수행할 연산이 필요하다. ALU는 레지스터로부터 피연산자를 받아들이고, 제어장치로부터 수행할 연산을 알려 주는 제어 신호를 받아들인다. 연산 수행 후, 연산 결과는 메모리에 바로 저장되지 않고 레지스터에 저장된다. 이때, 연산 결과는 특정 숫자나 문자가 될 수도 있고, 메모리 주소가 될 수도 있다. 플래그 ALU는 연산 결과와 더불어 플래그를 내보낸다. 연산 결과값이 음수일 경우 음수라는 정보를 보내거나, 연산 결과가 연산 결과를 담을 레지스터보다 클 때 ‘결과값이 너무 크다’는 정보도 보..
Java/클래스 2023. 8. 30.
Java String
문자열 문자열의 분류 java 클래스에서 String 클래스에 대한 메모리 배치 예 그림에서 보이듯, java.lang.String 클래스에는 기본적인 메타 데이터 외에도 네 가지 필드들이 포함되어 있는데, hash값 (hash), 문자열의 길이 (count), 문자열 데이터의 시작점 (offset), 그리고 실제 문자열 배열에 대한 참조 (value) 이다 C언어에서 문자열 처리 문자열은 문자들의 배열 형태로 구현된 응용 자료형 문자배열에 문자열을 저장할 때는 항상 마지막에 끝을 표시하는 널문자(\0)을 넣어줘야 한다. char ary[] = {'a', 'b', 'c', '\0'}; // 또는 char aryp[="abc"; 문자열 처리에 필요한 연산을 함수 형태로 제공한다 strlen(), strcp..
알고리즘 문제/백준 2023. 8. 29.
15684 사다리 조작 (Java)
(15684) 사다리 조작 🌍TISTORY 문제 🌐 사다리 게임은 N개의 세로선과 M개의 가로선으로 이루어져 있다. 인접한 세로선 사이에는 가로선을 놓을 수 있는데, 각각의 세로선마다 가로선을 놓을 수 있는 위치의 개수는 H이고, 모든 세로선이 같은 위치를 갖는다. 아래 그림은 N=5, H=6인 경우의 그림이고, 가로선은 없다. 초록선은 세로선을 나타내고, 초록선과 점선이 교차하는 점은 가로선을 놓을 수 있는 점이다. 가로선은 인접한 두 세로선을 연결해야 한다. 단, 두 가로선이 연속하거나 서로 접하면 안 된다. 또, 가로선은 점선 위에 있어야 한다. 위의 그림에는 가로선이 총 5개 있다. 가로선은 위의 그림과 같이 인접한 두 세로선을 연결해야 하고, 가로선을 놓을 수 있는 위치를 연결해야 한다. 사다리..
알고리즘 문제/백준 2023. 8. 28.
2116 주사위 쌓기 (Java)
(2116) 주사위 쌓기 🌍TISTORY 문제 🌐 천수는 여러 종류의 주사위를 가지고 쌓기 놀이를 하고 있다. 주사위의 모양은 모두 크기가 같은 정육면체이며 각 면에는 1부터 6까지의 숫자가 하나씩 적혀 있다. 그러나 보통 주사위처럼 마주보는 면에 적혀진 숫자의 합이 반드시 7이 되는 것은 아니다. 주사위 쌓기 놀이는 아래에서부터 1번 주사위, 2번 주사위, 3번 주사위, … 의 순서로 쌓는 것이다. 쌓을 때 다음과 같은 규칙을 지켜야 한다: 서로 붙어 있는 두 개의 주사위에서 아래에 있는 주사위의 윗면에 적혀있는 숫자는 위에 있는 주사위의 아랫면에 적혀있는 숫자와 같아야 한다. 다시 말해서, 1번 주사위 윗면의 숫자는 2번 주사위 아랫면의 숫자와 같고, 2번 주사위 윗면의 숫자는 3번 주사위 아랫면의 ..
자료구조 2023. 8. 26.
자료구조 Array - 이차원 배열
2차원 배열 2차원 배열의 선언 2차원 이상의 다차원 배열은 차원에 따라 Index를 선언 2차원 배열의 선언: 세로길이 (행의 개수), 가로길이 (열의 개수) 를 필요로 함 int[][] twoDimArr = new int[2][4] // (2행 4열의 2차원 배열 선언) 배열 순회 n X m 배열의 n * m 개의 모든 원소를 빠짐없이 조사하는 방법 행 우선 순회 int i; // 행의 좌표 int j; // 열의 좌표 for i from 0 to n-1 for j from 0 to m-1 Array[i][j] // 필요한 연산 수행 열 우선 순회 int i; // 행의 좌표 int j; // 열의 좌표 for j from 0 to m-1 for i from 0 to n-1 Array[i][j] //..
알고리즘 2023. 8. 25.
탐욕 알고리즘 Greedy Algorithm
탐욕 알고리즘 Greedy Algorithm 탐욕 알고리즘은 최적해를 구하는 데 사용되는 근시안적인 방법 여러 경우 중 하나를 결정해야 할 때마다 그 순간에 최적이라고 생각되는 것을 선택해 나가는 방식으로 진행하여 최종적인 해답에 도달한다 각 선택의 시점에서 이루어지는 결정은 지역적으로 최적이지만, 그 선택들을 계속 수집하여 최종적인 해답을 만들었다고 하여 그것이 최적이라는 보장은 없다 일반적으로, 머릿속에 떠오르는 생각을 검증 없이 바로 구현하면 Greedy 접근이 된다 탐욕 알고리즘의 동작 과정 해 선택: 현재 상태에서 부분 문제의 최적 해를 구한 뒤, 이를 부분해 집합 (Solution Set)에 추가한다 실행 가능성 검사: 새로운 부분해 집합이 실행 가능한지 확인한다 곧, 문제의 제약 조건을 위반..
알고리즘 2023. 8. 24.
완전 검색 Exhaustive Search
완전 검색 Exhaustive Search Baby-gin Game 설명 0~9 사이의 숫자 카드에서 임의의 카드 6장을 뽑았을 때, 카드가 연속적인 번호를 갖는 경우는 run이라 하고, 3장의 카드가 동일한 번호를 갖는 경우를 triplet이라 한다. 그리고, 6장의 카드가 run과 triplet으로만 구성된 경우를 baby-gin으로 부른다 6자리의 숫자를 입력받아 baby-gin의 여부를 판단하는 프로그램을 작성하라 입력 예 667767은 두 개의 triplet이므로 baby-gin이다 (666, 777) 054060은 한 개의 run과 한 개의 triplet이므로 역시 baby-gin이다 (456, 000) 101123은 한 개의 triplet이 존재하나, 023이 run이 아니므로 baby-gi..
자료구조 2023. 8. 24.
자료구조 Array - 검색, 선택 정렬, 카운팅 정렬
230808 Array (2) 검색(Search) 선택 정렬(Selection Sort) 카운팅 정렬 검색 Search 저장되어 있는 자료 중에서 원하는 항목을 찾는 작업 목적하는 탐색 키를 가진 항목을 찾는 것 탐색 키(search key): 자료를 구별하여 인식할 수 있는 키 검색의 종류 순차 검색 (sequential search) 이진 검색 (binary search) 인덱싱 (indexing) 순차 검색 Sequential Search 일렬로 되어 있는 자료를 순서대로 검색하는 방법 가장 간단하고 직관적인 검색 방법 배열이나 연결 리스트 등 순차구조로 구현된 자료구조에서 원하는 항목을 찾을 때 유용함 알고리즘이 단순하여 구현이 쉽지만, 검색 대상의 수가 많은 경우에는 수행 시간이 급격히 증가하여..
Computer Science/컴퓨터구조 2023. 8. 20.
Chap3 명령어
layout: default title: 명령어 nav_order: 1003 description: 컴퓨터의 명령어 구성 parent: CS Chap3 명령어 생성 일시: 2023년 8월 15일 오후 5:25 소스 코드와 명령어 명령어의 구조 03 명령어 03-1 소스코드와 명령어 프로그래밍 언어가 어떻게 명령어가 되어 실행되는가? 고급 언어와 저급 언어 컴퓨터는 C, C++, Python, Java 같은 프로그래밍 언어를 이해할 수 있는가? 그렇지 않다. 우리가 사용하는 프로그래밍 언어는 컴퓨터가 이해하는 언어가 아니라, 사람이 이해하고 작성하기 쉽게 만들어진 언어이다. 이런 프로그래밍 언어들을 고급 언어(high-level programming language)라고 한다. 컴퓨터가 직접 이해하고 실행..
