정옴팡의 애플앤마블

안녕하세요! 이번에는 JavaScript를 사용하여 이진 탐색(Binary Search) 알고리즘을 구현하는 방법에 대해 알아보겠습니다. 이진 탐색은 정렬된 배열에서 특정 요소를 빠르게 찾는 알고리즘으로, 배열을 반으로 나누어 탐색 범위를 줄여가며 원하는 요소를 찾아내는 효율적인 방법입니다. 자, 그럼 바로 시작해봅시다! 1. 이진 탐색 알고리즘 구현하기 아래의 JavaScript 코드는 이진 탐색 알고리즘을 구현한 예시입니다. 주어진 배열에서 특정 요소(target)를 찾는 함수를 구현하였습니다. function binarySearch(arr, target) { let left = 0; let right = arr.length - 1; while (left

안녕하세요! 오늘은 JavaScript를 사용하여 스택(Stack)을 구현하는 방법에 대해 알아보겠습니다. 스택은 가장 간단한 자료 구조 중 하나로, 후입선출(LIFO, Last-In-First-Out) 원칙을 따릅니다. 이러한 특성 때문에 스택은 많은 프로그래밍 문제에서 유용하게 사용됩니다. 자, 그럼 바로 시작해봅시다! 1. 스택 클래스 생성하기 우선, 스택을 구현하기 위해 Stack 클래스를 생성합니다. 아래의 코드를 참고해주세요. class Stack { constructor() { this.items = []; } // 스택에 요소 추가하기 push(element) { this.items.push(element); } // 스택의 가장 위의 요소 제거하기 pop() { if (this.isEmp..

#include #include using namespace std; bool check[1001]; int a[1001][1001]; int n, m; void dfs(int x){ //x를 방문한다. check[x] = true; //x를 방문처리하고 printf("%d ", x); //x를 출력 for(int i=1; i>n>>m>>v; while(m--){ int p, q; cin>>p>>q; a[p][q]=1; a[q][p]=1; } dfs(v); cout

일곱난쟁이인줄 알았던 백설공주는 알고보니 난쟁이가 9명이었다고 한다. 그래서 백설공주는 일곱난쟁이의 키가 합이 100이 되는걸 알게되어서 누가 진짜 난쟁이인지 알고싶다고 한다. 이 문제는 백준 2309번을 보면 풀 수 있고 저는 순열을 이용해서 풀었습니다. https://www.acmicpc.net/problem/2309 2309번: 일곱 난쟁이 아홉 개의 줄에 걸쳐 난쟁이들의 키가 주어진다. 주어지는 키는 100을 넘지 않는 자연수이며, 아홉 난쟁이의 키는 모두 다르며, 가능한 정답이 여러 가지인 경우에는 아무거나 출력한다. www.acmicpc.net #include #include #include using namespace std; int main(){ int n = 9; vector a(n); ..

두 수가 주어졌을 때 두 수의 최소공배수는 gcd(최대공약수)를 이용할 수 있는데, 두 수의 곱을 gcd로 나눠주면 된다. #include using namespace std; int gcd(int a, int b){ if(b==0) return a; else return gcd(b, a%b); } int main(){ int t; cin>>t; while(t--){ int a, b; cin>>a>>b; int g = gcd(a,b); cout

최대 공약수 : gcd //두 수의 최대공약수를 구하는 가장 쉬운 방법 int a, b; int g = 1; for(int i=2; i

1. 개요 자바스크립트로 Queue를 구현하고 이를 이용하여 Server가 3명인 경우 Customer에 대한 time과 number요소들을 출력한다. 2. Code에 대한 설명 전체 서비스의 시간을 관장하는 Clock을 선언하고 이는 전체 시간을 담당한다. Function Queue(){}에는dataStore[] 배열, 원형 큐의 처음과 끝, enqueue, dequeue 그리고 큐가 비어있음을 확인하는 함수인 is_empty를 선언한다. Server를 3명으로 설정하기 위해 Server가 가지는 service_time을 각각 1, 2, 3으로 선언하고 이를 0으로 초기화 한다. 단, Server가 Customer를 받지 않을 경우 “잉여시간”으로 설정하기 위해 이를 service_idle_time으로..

1. 개요 자바스크립트로 Queue를 구현하고 Queue를 이용하여 Customer에 대한 time과 number요소들 을 출력한다. 2. Code에 대한 설명 전체 서비스의 시간을 관장하는 Clock을 선언하고 이는 전체 시간을 담당한다. Server가 가지는 service_time은 Server가 Customer에게 할당하는 시간이고 이를 0으로 초기화 한다. 각 경우 모두 유의미한 값을 도출해 내기 위해 초기 값들을 조정할 필요가 있다. 따라서duration = 100, arrival_prob = 0.5, max_serv_time = 4로 설정했다. If( is_customer_arrived())에서 0.5보다 작을 경우 Customer가 입장한 것으로 보고insert_customer 함수를 통해 ..

1. 서론 자바스크립트로 스택을 구현하고, 스택을 이용하여 현재 위치에서 출구까지의 경로를 기록하고 미로를 탈출한다. 2. Pseudo Code Int main() { 스택과 위치를 기록할 공간을 생성한다. 스택을 초기화하고 미로를 불러낸다. 지정된 시작점을 찾고 시작점에서부터 미로를 탈출한다. while(탈출구까지) { do현재 위치를 좌표에 입력한다; 현재 위치를 표시한다.(이미 다녀간 위치) do동쪽에 이동 가능한 길이 있는지 확인한다. 서쪽에 이동 가능한 길이 있는지 확인한다. 남쪽에 이동 가능한 길이 있는지 확인한다. 북쪽에 이동 가능한 길이 있는지 확인한다. If(스택이 비었다면) { then탈출 실패 } else(이동 가능하다면) { then이동한 위치를 기록하고 출력한다. } (탈출구를 발..

1. 개요 Queue를 이용하여 Server가 3명인 경우 Customer에 대한 time과 number요소들을 출력한다. 2. Code에 대한 설명 전체 서비스의 시간을 관장하는 Clock을 선언하고 이는 전체 시간을 담당한다. Server를 3명으로 설정하기 위해 Server가 가지는 service_time을 각각 1, 2, 3으로 선언하고 이 를 0으로 초기화 한다. 단, Server가 Customer를 받지 않을 경우 “잉여시간”으로 설정하기 위해 이를 service_idle_time으로 선언하고 초기화 한다. 모든 직원이 쉬고 있을 경우를 표현하기 위해 모든 Server의 service_time이 0이 될 경우 “직원 이 모두 쉬고 있습니다.” 를 출력한다. 단, clock이 1일 때부터 Cus..

1. 서론 스택을 이용하여 현재 위치에서 출구까지의 경로를 기록하고 미로를 탈출한다. 2. Pseudo Code 3. maze.c(Code) #include #include #define MAX_SIZE 100 #define MAZE_SIZE 20 typedef struct Pos{ short x; short y; }Pos; typedef struct Stack { Pos data[MAX_SIZE]; int top; }Stack; char maze[MAZE_SIZE][MAZE_SIZE]={ {'0', '0', '0', '0', '0', '0', '0', '0', '0', '0', '0', '0', '0', '0', '0', '0', '0'}, {'0', '1', '1', '1', '1', '1', '1'..

1. 개요 Fibonacci Algorithm 을 recursive call, recursive call with memoization 을 이용하여 이 두가 지를 각각 프로그램하고 수행시간을 측정하고 그 결과를 그래프를 이용하여 비교하여 관찰 한다. 2. Fibonacci Algorithm 의 두 코드에 대한 Pseudo code 2.1 recursive call Pseudo code fib(n) { if n is 1 or 2, return 1; return fib(n-1) + fib(n-2); } 2.2 recursive call with memoization Pseudo code fib(n) { if memo[n] is zero; memo[n] = fib(n-1) + fib(n-2); return m..

저번 시간은 연결리스트와 단방향 연결리스트에 대해 알아보고 구현해보았습니다. 오늘은 양방향 연결리스트와 C++ STL에 들어있는 함수들을 알아보고자 합니다. #양방향 연결리스트 양방향연결리스트의 특징은 head와 tail 노드를 사용하여 이 리스트를 관리하는 특징을 가지고 있습니다. 또한 한 노드가 전 노드 혹은 후 노드와 연결되어 있다는 점이 특징입니다. #include #include typedef struct Node { int data; struct Node *prev; struct Node *next; } Node; Node *head, *tail; void insert(int data){ Node* node = (Node*) malloc(sizeof(Node)); node->data = dat..

알고리즘의 시간 복잡도를 표기하기 위해 Big-O 표기법을 사용하여 이를 정리하고자 합니다. #O(1) : constant time 입력 데이터의 크기와 관계 없이 일정한 시간 #O(n) : linear time 입력 데이터의 크기와 비례해 시간 ex) for문 1개 #O(n^2) : quadratic time 입력 데이터의 크기의 제곱에 비례해 시간 ex) for문 2개 #O(nm) : quadratic time O(n^2)에서 m이 n보다 작으면 보다 더 적은 시간이 걸리지만 m이 n보다 같어나 큰 순간 같거나 많은 시간 #O(n^3) : polymomial or cubic time 입력 데이터의 크기의 세제곱에 비례해 시간 ex) for문 3개 #O(2^n) : exponential time 함수를..

연결리스트에 대해 알아보려 합니다. 연결리스트로는 크게 배열, 단방향, 양방향리스트로 구현 가능한데요. 각각의 구현과 장단점을 정리해보고자 합니다. #연결 리스트란 메모장에 할 일이나 쇼핑목록을 나열하듯 데이터를 저장하는 자료구조이며, 이들을 연결해 삽입과 삭제, 탐색을 할 수 있습니다. #배열 리스트 배열 리스트의 장점은 어느 위치에 저장되어 있는지 index(위치)를 알고 있다면 바로 접근해서 데이터를 가져올 수 있지만, 배열의 크기를 처음에 지정해야 하므로, 적정한 배열의 크기를 정해야 하는 단점이 있습니다. 또한 삭제나 삽입을 할 때 모든 배열을 앞으로나 뒤로 방문하여 밀거나 당겨야 하는 상황에 불필요한 메모리 낭비나, 탐색을 할 수 있습니다. #include int arr[10]; int cnt..

#include using namespace std; int main(){ int T; cin>>T; for(int t=1; t

https://www.fastcampus.co.kr 패스트캠퍼스 | 커리어 성장을 위한 최고의 실무교육 아카데미 커리어 성장을 위한 최고의 실무교육 아카데미 www.fastcampus.co.kr 위에 가면 더 좋은 강좌들이 많이 개설되어 있습니다. 개인적으로 사서 듣고있는데 도움이 많이 되는거 같아서 그 중 흥미로운 부분을 하나 발췌해서 소개해드리고자 합니다. 코드들이 전부 개인적인 소유를 갖고 있을 수 있어 업로드를 안하지만, 이 실습 코드 같은 경우에 Git에 연동하여 공유하는 실습까지 함께 진 행 했을 뿐만 아니라 '이런것도 배워보고 싶었는데....!'하시는 분들(저같은 경우도 포함) 에게 접근성을 높일 수 있을 거 같아 포스트합니다. 한번 가셔서 저는 '컴퓨터공학 올인원 패키지'를 수강하고 있는데..

이번에 응용회로설계실습이라는 과목에서 프로젝트 과제로 만들걸 구상하고 있는데 핵맨을 만들까해서 C++로 먼저 동작시켜 봤어용,,, 코드는 아래입니당~ #include #include using namespace std; int main(){ string s; cin>>s; char c[s.length()]; bool check[s.length()]; cout

이 문제는 swexpertacademy P.1231 문제임을 알립니다. 또한 패스트 캠퍼스 수강자이며 안경잡이개발자 나동빈님의 강의를 보고 활용하여 푼 것이므로 안경잡이 개발자 님의 블로그를 링크 할테니 많이 가서 좋은 배움 얻으시길 바랍니다. https://blog.naver.com/ndb796 안경잡이개발자 : 네이버 블로그 2017 대한민국 인재상 SW 마에스트로 9기 BoB 6기 보안컨설팅 트랙 에듀캐스트 Unity 강사 ndb796@naver.com 카카오톡 : blow796 blog.naver.com 중위 순회 알고리즘을 가져와 풀었는데 문제를 보면 주어진 node의 갯수에 따라 몇번 째 번호에 이를 시 입력을 각각 다르게 받으며 node의 갯수가 짝수인지 홀수인지 또한 구분..

본 문제는 swexpertacademy D4. 1226 문제이며 히하15님의 코드를 보고 배웠음을 알리며 히하15님이 이 글을 본다면 감사의 의미를 전하고 싶으니 쪽지 부탁드립니다. 미로의 기본적인 문제이며 미로를 입력받고 출발점과 끝점을 저장한다. 그 후 지나온 길을 표시하고 갈 수 있는 길에 대해 상하좌우를 탐색하며 미로를 찾는다. #include using namespace std; char maze[16][16]; int visit[16][16]; int dx[4] = {0,0,-1,1}; int dy[4] = {-1,1,0,0}; int entry_x, entry_y, exit_x, exit_y; int sol; bool check(int y, int x){ if(y>=0&&y=0&&x

이 문제는 swexpertacademy D3 P.6808임을 알립니다. 하단 URL참조 인영이와 규영이의 카드를 입력받고 recursion을 이용해 순열을 비교하면 된다. 이 때 순열의 조건으로 경우를 줄이지 않으면 runtime이 초과될 수 있으니 조심한다. #include using namespace std; int iy[9]; int ky[9]; bool checkArr[9]; int win; void permutation(int idx, int ky_score, int iy_score){ if(idx==9){ if(ky_score>iy_score) { win++; return; } return; } for(int i=0; iiy[i]) permutation(idx+1, ky_score+(ky[id..

본 문제는 swexpertacademy D3 1206번 문제임을 알립니다. 하단 URL 참조 각 층을 입력받고 0층이 입력될 때는 계속 진행하고 층이 입력되면 그 층까지 모두 2차원 배열에 1을 넣는다. 그 후 각 경우에 count를 세는데 if(arr[i-1][j]==0&&arr[i-2][j]==0&&arr[i+1][j]==0&&arr[i+2][j]==0) 이 조건에 맞으면 count를 올린다. #include #include using namespace std; int main(){ for(int t=1; t

이 문제는 swexpertacademy의 7102번 문제임을 알립니다. N 과 M이 각 케이스마다 입력되는데 1~N, 1~M의 숫자를 더했을 때 확률이 가장 높은 숫자를 출력하므로 배열을 N+M+1칸으로 선언한다. 그 이유는 두개의 숫자를 더했을 때 나온 수의 배열 칸에 count++를 할 것인데 N, M, 을 2,3이라고 했을 때 arr[5]으로 선언하면 arr[0]~arr[4]까지 5개가 나오므로 편의를 위해 +1을 해준다. 그 후 가장 많이 등장한 숫자(들)을 출력한다. #include #include using namespace std; int main(void){ int T; cin>>T; for(int i=1; i

본 문제는 swexpertacademy의 문제임을 알립니다. 아래 URL 참조 n진법의 수를 n-1진법으로 나눈 나머지는 각자리 수를 더하여 N-1로 나누는 원리를 사용하면 됩니다. #include #include #include using namespace std; int main(){ int T; cin>>T; for(int t=1; t

https://book.naver.com/bookdb/book_detail.nhn?bid=6068296 C언어로 쉽게 풀어쓴 자료구조 이 책은 도입부에서부터 C언어에서 시행착오를 겪는 자료 구조와 알고리즘에 대한 정의를 그림을 통해 충분히 설명하면서 자바 애플릿으로 작성된 가상 실습 소프트웨어로 개념을 확실히 잡아주고 있다. 더 나아가 유사코드로 작성된 알고리즘을 학습하고 최종적으로 C언어로 구현된 내용을 학습할 수 있도록 구성하고 있어, 자료 구조와 알고리즘의 개념의 이해는 물론이고 C언어로 구현된 내용을 통해 C언어를 쉽게 이해할 수 있다. book.naver.com C언어로 쉽게 풀어쓴 자료구조를 참고한 내용입니다. #include #define MAX_STACK_SIZE 100 typedef in..