본문 바로가기

분류 전체보기

나만의 알고리즘 문제 설계방식 * 나만의 알고리즘 문제 설계방식 1. 종이에 해당하는 조건들을 꼼꼼히 적는다. 2. 처음에는 가장 쉬운 완전탐색부터 생각한다. 3. 시간복잡도를 고려하였을 때, 가능한지 생각해본다. 4. 불가능하다고 생각되면 다른 알고리즘을 생각해보고... 5. 가능하다고 생각되면, 디테일한 풀이는 적는다. 6. 풀이의 항목 별로 함수화 시켜서, 구현한다. 동적분석을 통해, 코드를 확인하고, 올바르게 작동하지 않는다면 풀이대로 작동하게 만들어졌는지, 정적분석을 한다. 만약, 이렇게 코드 디버깅 하는 시간이 1시간이 넘어간다면, 질문 또는 다시 설계를 진행하는 것이 좋다. 더보기
[알고리즘] Binary Search란? * 이름이 붙여진 것처럼 Search하는 알고리즘인데, binary의 방법으로 진행한다. =>binary 방법이라는 것은 하나의 배열을 반으로 나누어서, 둘 중 한쪽을 선택하고, 또 반으로 나누고를 반복하는 방식이다. * 전제 조건 => 정렬되어 있어야 한다. * 과정 => 정렬이 되어있다는 전제하에 진행한다. (실제로 정렬이 되어있지 않다면, 정렬 후 진행해야 한다.) 1. 숫자 n을 찾는다고 가정 하였을 때, 중간 값 middle을 정한다. 2. middle보다 n이 크다면, middle보다 큰 쪽을 본다. 3. middle보다 큰 쪽에서 1과 2를 반복적으로 진행하여, 숫자를 찾는다. * 애니메이션 http://www.cs.armstrong.edu/liang/animation/web/BinarySe.. 더보기
[알고리즘/시간복잡도] log이란?? * 컴퓨터 공학에서 log를 쓰는 경우 그 밑이 2이므로, 보통 밑을 생략한다. log 32 = 5log 64 = 6log 32 < log 50 < log 64 * 숫자 n이 있을 때, log를 취하게 되면 엄청나게 작아지게 된다. * log n은 숫자가 크지 않기 때문에 속도에 영향이 적음 * 따라서 log n이 들어간 시간복잡도는 매우 빠른 편에 속한다고 할 수 있다. 더보기
[알고리즘] 정렬(sort)이란?? * 정렬 알고리즘이란? n개의 숫자가 입력으로 주어졌을 때, 사용자가 원하는 대로 크기 순으로 정렬하는 것이다. * 정렬 방식 정렬에는 보통 오름차순과 내림차순 두 가지 방식이 존재한다. => 오름차순 : 작은 수부터 점차 큰 수 순서대로 정렬 => 내림차순 : 큰 수부터 점차 작은 수 순서대로 정렬 * 정렬은 구현 및 시간복잡도 등 디테일 하게 아는 것이 중요하다. => 위 사항을 알아야 하는 이유? 단순히 정해진 알고리즘에 정해진 코드를 짜는 사람이 아니라, 주도적으로 코드의 알고리즘 설계, 분석 / 문제점 파악 등을 명확히 하려면, 아래의 정렬 정도는 손쉽게 짜고, 시간복잡도 또한 분석할 줄 알아야 한다고 생각합니다. 또한, 초기에 어떤 순서대로 되어있느냐에 따라, 정렬 시간이 달라집니다. * 정렬.. 더보기
[C++] string 클래스 사용법!! ** c++ Reference를 참고하여 만들었습니다 ** - string 클래스에 대해 공부할 이유...!! 알고리즘 문제 풀이 및 개발을 하다가 보면, 문자열을 다뤄야 할 경우들이 굉장히 많다. 그럴 때, String 클래스를 잘 사용한다면, 알고리즘 문제 풀이 속도 및 개발 속도를 많이 올릴 수 있다. JAVA의 String과 다르다는 것은 미리 염두에 두고, 봐주시길 바랍니다. - 선언 : #include - 함수 종류 s1. size() (= length() ) : 문자열의 글자 수를 반환한다. s1.find(string s2) : 이것의 반환형이 std::string::npos 와 같지 않다면, 찾은 문자열의 첫번째 위치를 반환한다. 만약 std::string::npos와 같다면, 찾는 문자열.. 더보기
[시스템 프로그래밍] Semaphore란?? ** 본 게시물은 광운대학교 컴퓨터공학과 김태석 교수님의 시스템 프로그래밍 강의를 참고하여 만들어졌습니다. ** * 목차- Race Condition이란? - Critical Section이란? - Semaphore란?ㄴ semaphore의 두 가지 연산ㄴ semaphore case - 결론 - Race Condition이란? 경쟁 상태(Race Condtion)이란 공유 자원에 대해 여러 개의 프로세스가 동시에 접근을 시도할 때 접근의 타이밍이나 순서 등이 결과값에 영향을 줄 수 있는 상태를 말한다. 동시에 접근할 때 자료의 일관성을 해치는 결과가 나타날 수 있다. 이를 방지하기 위해서는 프로세스 협력 기법이 필요하다. ㄴ 입출금 예제를 통해, 자료의 일관성에 대해 설명하겠다. 잔고가 105달러일 때,.. 더보기
모두의 딥러닝 (Session 0 - 3) * Machine Learning : 개발자가 일일이 정하지 않고, 학습해서 무엇을 배우는 영역을 갖는 프로그램 - Arthur Samuel(1959) 학습 방식에 따라 두 가지 Learning으로 분류된다. 1. Supervised Learning Training Set(분류된 데이터)을 통해 학습을 한다. - 종류 >>regresssion 0~100처럼 범위가 넓은 예측 >>binary classification pass 또는 non pass 와 같이 두 가지 분류 >>multi-label classification A, B, C, D, F와 같이 여러 종류의 분류 2. Unsupervised Learning 분류되지 않은 데이터를 스스로 학습하여 판단한다. ex) Google news groupin.. 더보기
BOJ 7577번 1. 문제 해석 - 직선 도로 = 일차원 배열=> 숫자: 번호 / ▲ 기호 : 찾아낼 물체 - Probe[x,y] = r ( x x부터 y까지의 구간에 물체가 r개 있다. ex) Probe[2,7] = 3, Probe[2,2] = 0 - 제시된 탐사작업의 결과가 모두 만족되는 구간을 재구성하는 프로그램을 작성 - 입력 데이터 첫 줄 : 전체 구간의 길이(K) 와 Probe[x,y] = r 결과의 개수(N)첫 줄 아래 각 줄 : Probe[x,y] = r의 x,y,r 3 더보기
Tree(트리) Tree - Definition : root를 가지고, Cycle을 만들지 않는 Graph를 Tree라고 한다. * 특징 - Root가 아닌 모든 노드들은 parent와 child를 가진다. // ex) president 노드를 제외한 모든 노드 - children이 존재하지 않는 노드를 leaves라고 한다. // ex) leaves : Manager1, Manger2, Worker Bee, Manager - level은 계층 구조를 나타낸다.// root부터 낮은 level로 시작하여 leaves에서 가장 높은 level로 끝을 낸다. - 빈 Tree란 존재할 수 없다. Binary Tree - Definition : 두 개의 child를 가지는 Tree * 특징 - 두 child를 left chil.. 더보기
Backjoon1405/탐색/DFS(깊이 우선 탐색) * Part 01 문제 분석 포인트 : 로봇이 같은 곳을 한 번보다 많이 이동하지 않을 때, 로봇의 이동 경로가 단순하다고 한다. ex ) EENE와 ENW는 단순하지만, ENWS와 WWWWSNE는 단순하지 않다. (E는 동, W는 서, N은 북, S는 남) 로봇의 이동 경로가 단순할 확률을 출력하는 것이기에 단순하지 않은 경로는 빼고 출력한다. * Part 02 문제 설계 1) 경로를 계산하는 것인데 문제에 이동횟수 N>=14인 자연수라고 했으니, 나는 28*28 이차원 배열을 판으로 만든다. 중심을 시작점으로 둔다. 2) 동,서,남,북의 percentage를 저장할 배열 / walking 하는 횟수 / 총 percentage 3가지 변수 선언 3) 재귀함수(recursive function)을 통해 .. 더보기

티스토리툴바