오션코딩학원

개요 백준 1753번 최단경로 문제 에 대한 다익스트라 알고리즘 풀이 입니다. 다익스트라(Dijkstra) 알고리즘은 최단 경로를 구할 때 자주 사용되는 알고리즘입니다.

안녕하세요. 올해도 KOI 대회를 준비하는 학생들이 있어 문제풀이를 시간날 때 마다 포스팅하려 합니다.  풀이 결과가 100점이 아닌 경우도 있습니다. 여러분도 도전해보세요~😉 

개요 백준 단계별로 풀어보기 ➡️ 백트래킹 ➡️ 스도쿠 문제입니다. 사실 스도쿠게임에 관심이 없어 한번도 해 본적이 없었는데 문제를 풀다보니 어렵지만 재미있는 게임이라는 생각이 듭니다. 🤔

개요 늘 심심하면 진행하는 백준 문제풀이 시간입니다. 오늘은 백준 1654번 랜선자르기 문제 를 풀어보려 합니다. 정답율이 21.7% 라 왠지 승부욕을 자극하는군요. 😅 백준 단계별로 풀어보기 ➡️ 이분탐색 3번 문제입니다.

개요 안녕하세요. 오늘은 알고리즘문제에 자주 등장하는 순열 문제를 재귀호출 로 풀어보려 합니다. 순열은 조합과 비슷한 점이 많아 문제를 풀다 서로 혼동해 틀리는경우가 많습니다. 백준 ➡️ 단계별로 풀기 ➡️ 백트래킹 단계에 나온 2가지 순열 패턴 개념을 정리하고, 문제를 풀며 살펴보겠습니다. 

개요 우리가 작성한 코드는 실행시간이 얼마나 걸릴까요? 🤔 컴퓨터는 매우 빠르지만 계산이 복잡하거나 데이터의 양이 많다면 결과를 얻는 시간은 점차 길어질 것입니다. 

개요 NYPC 는 넥슨에서 개최하는 청소년 프로그래밍 대회입니다. 매년 여름방학 시즌에 진행되어 비교적 학업에 지장을 덜 받고 출전해 볼 수 있습니다. 학원생 중 이 대회를 준비하는 친구들이 많아 문제풀이를 지속적으로 업데이트할 계획입니다. 자세한 대회 세부 요강 및 기출문제는 NYPC 홈페이지 를 참조하기 바랍니다.

개요 안녕하세요. 중위 표기법(infix) 으로 표현된 수식을 후위 표기법(postfix) 로 바꾸는 C++ 계산기입니다.   1. 문자열로 중위표기법 입력 ( A-Z, a-z, 0~9,+,-,*,/,^,(,) )   2. 피연산자 (A-Z, a-z, 0~9) 는 후위식 문자열에 저장   3. 열리는 괄호 '(' 는 Stack에 저장   4. 닫기는 괄호 ')' 만나면 다음 '(' 만나기 전까지 Stack Pop 수행, 후위식 문자열에 저장   5. 연산자는 Stack에 추가 우선순위가 높은 연산자는 Stack Pop 수행, 후위식 문자열에 저장 개발 환경 C++17, Qt Creator 9.0.1, MinGW 11.2.0 64bit Windows 11 Pro   calc.h #ifndef CALC_H #define CALC_H #include <string> class Calc { public: Calc(const std::string& exp); ~Calc(); private: const unsigned int MAX; std::string infix; int priority(char c); public: std::string infixToPostfix(); int calcPostfix(const std::string& exp); }; #endif // CALC_H   calc.cpp #include "calc.h" #include <iostream> #include <cstring> #include <stack> #include <cmath> using namespace std; Cal...

개요 안녕하세요. C++ 자료구조 (Data Structure) 중 검색에 특화된 BST ( B inary S earch T ree)를 구현한 예제입니다. Root 기준으로 작은 값은 왼쪽, 큰값은 오른쪽, 중복허용X 연결리스트 (Linked List) 로 구성 삽입, 순회, 검색, 삭제 가능 노드 삭제 시 자식노드의 수 (0, 1, 2) 에 따라 삭제법이 다름에 유의   Visualization Link : https://www.cs.usfca.edu/~galles/visualization/Algorithms.html   개발 환경 C++17, Qt Creator 9.0.1, MinGW 11.2.0 64bit Windows 11 Pro   bst.h #ifndef BST_H #define BST_H struct Node { Node(int _v=0, Node *_L=nullptr, Node *_R=nullptr) : v(_v), L(_L), R(_R) {} int v; Node *L, *R; }; class BST { public: BST(); ~BST(); private: Node *pRoot; public: inline Node* root() {return pRoot;} void insert(int v); void preorder(Node *); void inorder(Node *p); void postorder(Node *p); Node* search(Node *p, int v); void remove(int v); private: Node* insert(Node *p, int v); void deleteNode(Node *p); ...

개요 안녕하세요. C++ 자료구조 (Data Structure) 의 가장 기본인 Stack 을 구현한 예제입니다. 마지막에 들어간 값이 먼저 나오는 LIFO (Last In First Out) 구조. 배열 (Array) 로 구성 Push, Pop 이 일어날 때 배열의 값이동(X), 인덱스 (top) 이동(O) 생성자에서 동적할당하는 클래스는 복사생성자, 대입연산자를 따로 정의 ( Queue 예제를 참조 하여 Do it yourself. 아래 예제에서 생략) 개발 환경 C++17, Qt Creator 9.0.1, MinGW 11.2.0 64bit Windows 11 Pro   stack.h #ifndef STACK_H #define STACK_H const int MAX = 5; class Stack { public: Stack(int _size=MAX); ~Stack(); public: void push(int v); int pop(); void print(); inline int length() {return size;} private: bool isFull(); bool isEmpty(); private: int top, size; int *p; }; #endif // STACK_H stack.cpp #include "stack.h" #include <iostream> #include <cstring> using namespace std; Stack::Stack(int _size) : top(0), size(_size), p(nullptr) { cout << "Contructor" << '\n'; p = new int[size]; ...

개요 안녕하세요. C++ 자료구조 (Data Structure) 의 가장 기본인 Queue 를 구현한 예제입니다. 먼저 들어간 값이 먼저 나오는 FIFO (First In First Out) 구조. 배열 (Array) 로 구성 Push, Pop 이 일어날 때 배열의 값이동(X), 인덱스 (head, tail) 이동(O) 생성자에서 동적할당하는 클래스는 복사생성자, 대입연산자를 따로 정의 개발 환경 C++17, Qt Creator 9.0.1, MinGW 11.2.0 64bit Windows 11 Pro   queue.h #ifndef QUEUE_H #define QUEUE_H const int MAX = 5; class Queue { public: Queue(int _size=MAX); ~Queue(); Queue(const Queue& other); Queue& operator=(const Queue& other); private: int size; int head, tail; int *p; public: void print(); void push(int v); int pop(); }; #endif // QUEUE_H queue.cpp #include "queue.h" #include <iostream> #include <cstring> using namespace std; Queue::Queue(int _size) : size(_size), head(0), tail(0), p(nullptr) { cout << "Constructor" << '\n'; p = new int[size]; memset(p, ...

개요 C++ 배열을 이용한 동적메모리 할당 (Dynamic Allocation) 구현 예제 입니다. 런타임 에 메모리를 어떻게 관리하는지 공부해 봅시다. 최초 5개의 정수형 배열을 Heap 영역에 동적할당하고, 저장공간이 부족한 경우 2배로 배열의 크기를 늘려가는 방식입니다. [배열의 동적할당] 동작 순서 1. 처음 배열 5개를 생성하고, 데이터를 삽입 2. 데이터가 5개를 초과하면 새로운 배열을 2배 크기(10개)로 동적할당     3. 기존 배열의 데이터를 새 배열로 복사 후 신규 데이터는 새 배열에 저장 4. 기존 배열 (5개) 을 삭제하고 새 배열의 주소를 포인터에 저장 소스코드 #include <iostream> #include <cstring> using namespace std; int main() { int size = 5; int pos = 0; int *p = new int[size]; memset(p, 0, sizeof(int)*size); while (true) { cout << "Input number(Exit:0): "; int n; cin >> n; if (n==0) break; if(pos>=size) { size *= 2; int *p2 = new int[size]; memset(p2, 0, sizeof(int)*size); for(int i=0; i<size/2; i++) p...

개요 안녕하세요.  학원생 중 정보올림피아드 대회를 준비하는 심화반 학생이 있어 같이 풀어본 문제입니다. 먼저 문제를 살펴보겠습니다. [출처 : 한국정보올림피아드, 2020년 중등부 2교시 문제]   예를 들어 입력 이 아래와 같다면, 12 1 HPHPHPHHPPHP 출력 은 아래와 같아야 합니다. 5   K가 2 라면 (햄거버를 먹을 수 있는 거리), 12 2 HPHPHPHHPPHP 출력 은 아래와 같아야 합니다. 6 문제풀이 1. 왼쪽부터 HPHPHP... 을 진행하며 P(사람)을 검색. 2. 사람(P)을 찾은 경우, 사람인덱스 기준 -K~+K 까지 햄버거 검색. 3. 햄버거가 있다면 (H를 만나면) 먹고, 햄버거 위치에 먹었다는 표시. (예, 'X') 4. 햄버거를 먹었다는 표시를 하는 이유는, 다음 P(사람)이 이미 먹은 햄버거를 또 먹는 것을 방지.  5. 전체적으로 테이블(HPHPHP...)을 반복하는 루프와 테이블 내 사람(P)를 만났을때 -K~+K를 반복하는 이중 루프로 구현. 6. 단, 테이블의 왼쪽에 사람이 있는 경우 -K가 0보다 작은 경우 , 테이블의 오른쪽 끝에 사람이 있는 경우, +K가 테이블의 길이를 초과 하는 경우를 주의. [햄버거 분배문제 해결 알고리즘]   소스코드 (파이썬) x = input('식탁길이, 선택거리:') y = input('햄버거, 사람 배치(H, P):') xx = x.split(' ') #n:식탁길이, k:거리 n = int(xx[0]) k = int(xx[1]) yy ...

파이썬으로 약수(divisor) 를 구하는 방법을 살펴보겠습니다. 만들다 보니 여러수를 입력해 공약수 와 최대 공약수 까지 구하도록 확장시켜 보았습니다. 예를 들면 12의 약수는 12를 1(n)부터 12(n)까지 나누기 한 후 나머지가 0이면 n은 약수 12 / 1 = 나머지 0 이므로 1은 약수 12 / 2 = 나머지 0 이므로 2도 약수...(반복)  따라서 12를 나누어 떨어지는 수는 1, 2, 3, 4, 6, 12 입니다. 만약 12와 16의 공약수를 구한다면 12의 약수 : 1, 2, 3, 4 , 6, 12 16의 약수 : 1, 2, 4 , 8, 16 12와 16의 공약수 : 1, 2, 4 따라서, 최대공약수는 4 [여러수의 약수, 공약수, 최대공약수 구하기] 조건  위 방식을 이용해 아래 미션을 수행해 보았습니다. 100,000,000의 약수를 구하라. (일억) 방법 1 : 단순하게 1부터 약수를 구하고자 하는 수까지 반복 import time cnt = int(input('약수를 구할 횟수 입력:')) divs = [] for i in range(cnt): n = int(input('숫자 입력:')) d = [] s = time.time() for i in range(1, n+1): if n%i == 0: d.append(i) divs.append(set(d)) print(n,'의 약수 : ', *d, '소요시간 : ', time.time()-s,'(sec)') print() if cnt>1: comdiv = set.inter...