본문 바로가기

Programming/Algorithm

(20)
[바킹독: 알고리즘] 배열 ※ (링크) 바킹독 유튜브 영상을 통해 학습한 내용을 정리한 것입니다. 본인은 JAVA를 활용해 학습하였습니다 비상업적 목적이며, 개인 복습을 위해 업로드한 글임을 다시 한 번 더 이야기드립니다. 본문의 모든 내용의 출처는 아래 명시된 링크와 같습니다. [목차] 정의와 성질, 기능과 구현, STL Vector, 연습 문제 [실전 알고리즘] 0x03강 - 배열 안녕하세요, 바킹독입니다.. 저번 단원의 내용인 코드 작성 요령 II는 순한 맛이었는데 오늘건 그냥 단맛입니다. 난이도가 굉장히 낮으니 긴장 푸시고 강의로 들어가겠습니다. 목차는 따로 설명 blog.encrypted.gg 출처: blog.encrypted.gg/927?category=773649 정의와 성질 배열은 메모리 상 원소를 연속하게 배치한 ..
[바킹독: 알고리즘] 기초 코드 작성 요령 2 ※ (링크) 바킹독 유튜브 영상을 통해 학습한 내용을 정리한 것입니다. 본인은 JAVA를 활용해 학습하였습니다. 비상업적 목적이며, 개인 복습을 위해 업로드한 글임을 다시 한 번 더 이야기드립니다. 본문의 모든 내용의 출처는 아래 명시된 링크와 같습니다. [목차] STL과 함수 인자, 표준 입출력, 코드 작성 팁 [실전 알고리즘] 0x02강 - 기초 코드 작성 요령 II 안녕하세요, 바킹독입니다. 이전 단원에서 오지고 지리게 고통받으셨을텐데 이번에는 훨씬 쉬우니까 걱정을 덜어내시고 마음 편하게 보시면 됩니다. 저 아직 0x18살이니까 급식체 써도 되는거 blog.encrypted.gg 출처: blog.encrypted.gg/923?category=773649 STL(Standard Template Lib..
[바킹독: 알고리즘] 기초 코드 작성 요령 1 - (2) 자료형 ※ (링크) 바킹독 유튜브 영상을 통해 학습한 내용을 정리한 것입니다. 본인은 JAVA를 활용해 학습하였습니다. 비상업적 목적이며, 개인 복습을 위해 업로드한 글임을 다시 한 번 더 이야기드립니다. [실전 알고리즘] 0x01강 - 기초 코드 작성 요령 I 안녕하세요, 바킹독입니다. 이번 단원에서는 기초 코드 작성 요령을 익혀보려고 합니다. 목차를 보셨으면 알겠지만 기초 코드 작성 요령이 두 강으로 나눠져있는데 앞으로 코드를 잘 짜기 위해 blog.encrypted.gg 출처: blog.encrypted.gg/922?category=773649 정수자료형 C언어에서 char 자료형은 1 byte = 8 bit 입니다. 즉, 1 byte의 값은 8개의 칸을 이용해 이진법으로 수가 표현된다는 이야기 입니다. ..
[바킹독: 알고리즘] 기초 코드 작성 요령 1 - (1) ※ (링크) 바킹독 유튜브 영상을 통해 학습한 내용을 정리한 것입니다. 본인은 JAVA를 활용해 학습하였습니다. 비상업적 목적임을 다시 알려드리며, 출처는 아래 링크와 같습니다. [실전 알고리즘] 0x01강 - 기초 코드 작성 요령 I 안녕하세요, 바킹독입니다. 이번 단원에서는 기초 코드 작성 요령을 익혀보려고 합니다. 목차를 보셨으면 알겠지만 기초 코드 작성 요령이 두 강으로 나눠져있는데 앞으로 코드를 잘 짜기 위해 blog.encrypted.gg 출처: blog.encrypted.gg/922?category=773649 시간/공간 복잡도 컴퓨터는 1초당 3 - 5억 번의 연산을 수행합니다. ( 더하기, 나누기 등의 연산도 고려하자면 추정치라 생각하자.) 만약 주어진 문제의 제한시간이 1초라면, 3 -..
[바킹독: 알고리즘] 오리엔테이션 ※ (링크) 바킹독 유튜브 영상을 통해 학습한 내용을 정리한 것입니다. 본인은 JAVA를 활용해 학습하였습니다. 비상업적 목적이며, 개인 복습을 위해 업로드한 글임을 다시 한 번 더 이야기드립니다. [실전 알고리즘] 0x00강 - 오리엔테이션 안녕하세요, 바킹독입니다. 리뉴얼을 완료해서 다시 강의를 올립니다. 혹시 코딩테스트를 대비하고자 하는 목적으로 검색하다가 이 강좌를 보게 된거라면 지금 이 강좌가 정말 큰 도움이 된다 blog.encrypted.gg 출처: blog.encrypted.gg/921?category=773649 [ 0x11강 ] 까지는 반드시 완벽하게 숙지하기 위해 노력할 것 각 강의당 관련 문제 3 ~ 5개는 풀어 볼 것 한 개의 테스트 케이스를 빼고 다른 테스트 케이스를 통과했다? ..
알고리즘: 재귀함수(6) 예제 - 멱집합 ( powerset ) 멱집합이란? S의 모든 부분집합을 원소로 하는 집합을 S의 멱집합이라 하며, P(A) 혹은 2의 S승으로 나타낸다. 만약 S의 원소 개수가 n개라면, 멱집합의 갯수는 2의 n승이다. 멱집합 예제 어떤 집합의 모든 부분집합의 집합을 멱집합이라고 함 ex ) 원소의 갯수가 n개인 집합의 모든 가능한 부분 갯수의 집합 갯수 : 2의 n승 즉, 2의 n승의 서로 다른 경우의 수가 존재함 그렇다면 크기가 n인 모든 부분 집합의 경우의 수는 어떻게 출력할 수 있을까? 예시 데이터 { a, b, c, d, e, f }의 모든 부분 집합을 나열하려면 a를 제외한 { b, c, d, e, f }의 모든 부분집합들을 나열하고 { b, c, d, e, f }의 모든 부분집합에 { a }를 추가한 집합들을 나열함 고등학교 수..
알고리즘: 재귀함수(5) 예제 N Queens ※ 두 가지 코드 형식을 학습해 업로드한 코드는 다름. 채스의 Queen을 생각하면 됨 말은 어떠한 대각선과 행, 열에서 절대 겹치면 안 됨 상태 공간 트리 찾는 해를 반드시 포함하고 있는 트리 이 트리는 모든 가능한 경우의 수를 놓은 것이기 때문에 반드시 노드에 찾는 해가 존재한다는 것임 즉, 해가 존재한다면 그것은 반드시 이 트리의 어떠한 노드에 해당한다는 것으로 이 트리를 체계적으로 탐색하면 해를 구할 수 있음 하지만 그렇다고 하여 모든 노드를 탐색해야 한다는 것은 아님. 만약 해의 조건을 만족하지 않는다면 해당 노드는 infeasible 하다고 체크하며, 가장 최근에 진행하였던 노드로 돌아가 다른 선택지의 노드를 체크함. 백트래킹 (Backtracking) 수행하다가 수행 방법이 잘못되었음을 확인..
알고리즘: 재귀함수(4) 예제 Counting cells in a Blob Counting cells in a Blob - 입력으로 하나의 Binary 이미지가 주어짐 - 각 픽셀은 Background pixel이거나 image pixel임 - blob : 서로 연결된 image pixel들의 집합을 blob이라고 부름 - 상하좌우, 대각방향으로도 연결된 것으로 간주함 - 색칠된 background pixel을 우리의 기준으로 잡는 것임 - 이미지상 좌표가 주어졌을 때, 그 점이 속해있는 blob의 크기를 계산하는 것임 - 만약 blob에 속하지 않을 때 0을 반환함 입력 N*M 크기의 2차원 그리드(grid)가 주어짐 하나의 좌표는 ( x, y )임 출력 픽셀 ( x, y )가 포함된 blob의 크기를 출력함 ( x, y )가 어떤 blob에도 속하지 않는 경우는 0을 반환함..