Full HD 화면상의 직사각형들이 차지하고 있는 총면적 문제 1920x1080 픽셀을 가진 Full HD 화면상에 수직선,수평선으로만 이루어진 직사각형들이 놓여 있습니다. 이 직사각형들은 홀로 떨어져 있거나, 일부 겹치거나, 변 또는 꼭지점이 접하거나, 포함관계에 있을 수 있습니다. 이 직사각형들이 차지하고 있는 총면적을 구하는 프로그램을 작성해서 보내주세요 작성하세요. 프로그래밍 언어는 가장 자신있는 것을 사용하세요. 예로 10x10 픽셀을 가진 화면상에 아래와 같은 직사각형들이 있을 수 있습니다. 입력 각각의 사각형이 하나의 입력줄이 되며, 각 줄은 직사각형의 위치를 나타내는 네 개의 정수로 주어집니다. 좌표는 왼쪽 위가 (0,0)이고 오른쪽 아래가 (1920, 1080) 입니다. 첫 두 정수는 사각형의 왼쪽 위 꼭지점의 x, y좌표이고 다음 두 정수는 오른쪽 아래 꼭지점의 x, y좌표입니다. 위 예는 아래와 같은 입력을 갖습니다. 입력은 별도 파일에서 읽어와도 되고 소스코…

암아존 배조스씨를 위한 계좌이체 한글 음성 안내 우리말을 쓰는 평범한 사람이라면 1억원 1조원을 일억원, 일조원이라 하지 억원, 조원이라 읽지는 않습니다. 반면에 1만원, 1천원, 1백원의 경우는 일만원, 일천원, 일백원이라 하지 않고 만원, 천원, 백원, 십원이라 읽습니다. 또한 ‘80,270원’처럼 금액의 표기는 천단위로 콤마를 찍지만 실제로 읽을 때는 ‘팔만 이백칠십원’처럼 만단위로 분리하여 읽습니다. “배조스님의 계좌에서 사이냅소프트님의 계좌로 일조 사천 일백 팔십 오억 원을 이체합니다. 동의하시면 1번을…” 계좌이체 음성안내의 부자연스러운 금액 표현과 띄어읽기가 거슬렸던 암아존 배조스씨를 위해 이체금액을 한글로 자연스럽게 읽을 수 있는 프로그램을 작성해서 보내주세요 작성하세요. 프로그래밍 언어는 가장 자신있는 것을 사용하세요. 입력 암아존 배조스님의 은행 이체한도는 100조원으로 설정돼 있으므로 입력 금액의 범위는 1원에서 100조원까지입니다. 모든 금액은 천단위 구분자인…

‘얼른 마스크’씨 회사 전기 자동차의 행복한 일련번호 마스크를 쓰지 않고는 밖을 다니면 안 되는 코로나19 시대입니다. 코로나19가 장기화되면서 코로나 블루라는 말이 나올 정도로 우울한 사람들이 많아지고 있습니다. 세계적인 전기자동차 회사 경영자인 **‘얼른 마스크’**씨는 자신의 전기자동차를 타는 고객들이 조금이라도 행복할 수 있기를 바라며 판매하는 전기자동차 번호판 일련번호 4자리를 **행복 수(happy number)**로 채우고자 합니다. 행복 수는 각 자릿수의 제곱의 합으로 변환하는 과정을 반복할 때 언젠가는 1에 도달하는 수입니다. 예로, 13 → 1x1 + 3x3 = 10 → 1x1 + 0x0 = 1이므로 13은 행복 수입니다. 행복 수가 아닌 것은 슬픈(sad) 수 또는 불행(unhappy) 수라고 불립니다. 예로, 4 → 4x4 = 16 → 1x1 + 6x6 = 37 → 3x3 + 7x7 = 58 → … → 4 로 순환하여 결코 1에 도달할 수 없으니 4는 슬픈 수…

n^2 배열 자르기 문제 설명 정수 , , 가 주어집니다. 다음 과정을 거쳐서 1차원 배열을 만들고자 합니다. 행 열 크기의 비어있는 2차원 배열을 만듭니다. 에 대해서, 다음 과정을 반복합니다. 1행 1열부터 행 열까지의 영역 내의 모든 빈 칸을 숫자 로 채웁니다. 1행, 2행, …, 행을 잘라내어 모두 이어붙인 새로운 1차원 배열을 만듭니다. 새로운 1차원 배열을 이라 할 때, , , …, 만 남기고 나머지는 지웁니다. 정수 , , 가 매개변수로 주어집니다. 주어진 과정대로 만들어진 1차원 배열을 return 하도록 solution 함수를 완성해주세요. 제한사항 1 ≤  ≤ 107 0 ≤  ≤  < n2  -  < 105 입출력 예 n left right result 3 2 5 4 7 14 입출력 예 설명 입출력 예 #1 입출력 예 #2 나의 풀이 최초에는 이중 for문을 활용하여 해당하는 경우의 숫자배열을 다 만들었다. 하지만 이러한 형태는 n의 값이 조금만 늘어도 시간 …

괄호 회전하기 리벤지 기존의 풀었던 방식은 테스트 코드에선 성공적이었으나, 실제 체점에서 엣지케이스를 잡지 못하여 다시 도전한다. 문제 설명 다음 규칙을 지키는 문자열을 올바른 괄호 문자열이라고 정의합니다. , ,  는 모두 올바른 괄호 문자열입니다. 만약 가 올바른 괄호 문자열이라면, , ,  도 올바른 괄호 문자열입니다. 예를 들어,  가 올바른 괄호 문자열이므로,  도 올바른 괄호 문자열입니다. 만약 , 가 올바른 괄호 문자열이라면,  도 올바른 괄호 문자열입니다. 예를 들어,  와  가 올바른 괄호 문자열이므로,  도 올바른 괄호 문자열입니다. 대괄호, 중괄호, 그리고 소괄호로 이루어진 문자열 가 매개변수로 주어집니다. 이 를 왼쪽으로 x (0 ≤ x < (의 길이)) 칸만큼 회전시켰을 때 가 올바른 괄호 문자열이 되게 하는 x의 개수를 return 하도록 solution 함수를 완성해주세요. 제한사항 s의 길이는 1 이상 1,000 이하입니다. 입출력 예 s result …

[PCCE 기출문제] 8번 / 창고정리 문제 설명 선빈이는 게임을 즐기던 중 가지고 있는 물건이 너무 많아 창고 정리를 하기로 했습니다. 선빈이가 보유한 게임 속 창고는 여러 칸으로 나누어져 있고 각 칸에는 물건들이 담겨있습니다. 창고를 정리할 방법을 고민하던 선빈이는 같은 물건이 여러 칸에 나누어 들어있는 것을 발견하고 우선 같은 물건끼리 최대한 겹쳐쌓는 방식으로 창고를 정리하기로 했습니다. 선빈이의 창고에 들어있는 물건의 이름과 개수는 리스트 형태로 주어지며, 한 칸에 겹쳐질 수 있는 물건의 개수에는 제한이 없다고 가정합니다. 예를 들어 창고의 각 칸에 담겨있는 물건의 이름이, 각 물건의 개수가 이라면 연필과 책을 한 칸에 각각 겹쳐 쌓아 간단하게 , 로 만들 수 있습니다. pencil book javacpp.jpg 주어진 solution 함수는 정리되기 전 창고의 물건 이름이 담긴 문자열 리스트 와 각 물건의 개수가 담긴 정수 리스트 이 주어질 때, 정리된 창고에서 개수가 가…

2016년 문제 설명 2016년 1월 1일은 금요일입니다. 2016년 a월 b일은 무슨 요일일까요? 두 수 a ,b를 입력받아 2016년 a월 b일이 무슨 요일인지 리턴하는 함수, solution을 완성하세요. 요일의 이름은 일요일부터 토요일까지 각각  입니다. 예를 들어 a=5, b=24라면 5월 24일은 화요일이므로 문자열 “TUE”를 반환하세요. 제한 조건 2016년은 윤년입니다. 2016년 a월 b일은 실제로 있는 날입니다. (13월 26일이나 2월 45일같은 날짜는 주어지지 않습니다) 입출력 예 a b result 5 24 “TUE” ```python # 내 마음데로 풀어보기 # 윤력은 2월 마지막이 29일 # 30, 31일 조심! 1, 3, 5, 7, 8, 10, 12월이 31일이가 def solution(a, b): 가운데 글자 가져오기 문제 설명 단어 s의 가운데 글자를 반환하는 함수, solution을 만들어 보세요. 단어의 길이가 짝수라면 가운데 두글자를 반환하면…

해시 > 포켓몬 문제 설명 당신은 폰켓몬을 잡기 위한 오랜 여행 끝에, 홍 박사님의 연구실에 도착했습니다. 홍 박사님은 당신에게 자신의 연구실에 있는 총 N 마리의 폰켓몬 중에서 N/2마리를 가져가도 좋다고 했습니다. 홍 박사님 연구실의 폰켓몬은 종류에 따라 번호를 붙여 구분합니다. 따라서 같은 종류의 폰켓몬은 같은 번호를 가지고 있습니다. 예를 들어 연구실에 총 4마리의 폰켓몬이 있고, 각 폰켓몬의 종류 번호가 [3번, 1번, 2번, 3번]이라면 이는 3번 폰켓몬 두 마리, 1번 폰켓몬 한 마리, 2번 폰켓몬 한 마리가 있음을 나타냅니다. 이때, 4마리의 폰켓몬 중 2마리를 고르는 방법은 다음과 같이 6가지가 있습니다. 첫 번째(3번), 두 번째(1번) 폰켓몬을 선택 첫 번째(3번), 세 번째(2번) 폰켓몬을 선택 첫 번째(3번), 네 번째(3번) 폰켓몬을 선택 두 번째(1번), 세 번째(2번) 폰켓몬을 선택 두 번째(1번), 네 번째(3번) 폰켓몬을 선택 세 번째(2번), 네 …

이진 변환 반복하기 문제 설명 0과 1로 이루어진 어떤 문자열 x에 대한 이진 변환을 다음과 같이 정의합니다. x의 모든 0을 제거합니다. x의 길이를 c라고 하면, x를 “c를 2진법으로 표현한 문자열”로 바꿉니다. 예를 들어, 이라면, x에 이진 변환을 가하면  이 됩니다. 0과 1로 이루어진 문자열 s가 매개변수로 주어집니다. s가 “1”이 될 때까지 계속해서 s에 이진 변환을 가했을 때, 이진 변환의 횟수와 변환 과정에서 제거된 모든 0의 개수를 각각 배열에 담아 return 하도록 solution 함수를 완성해주세요. 제한사항 s의 길이는 1 이상 150,000 이하입니다. s에는 ‘1’이 최소 하나 이상 포함되어 있습니다. 입출력 예 s result 입출력 예 설명 입출력 예 #1 “110010101001”이 “1”이 될 때까지 이진 변환을 가하는 과정은 다음과 같습니다. 회차 이진 변환 이전 제거할 0의 개수 0 제거 후 길이 이진 변환 결과 1 “11001…

드디어… 네이버 공채가 열렸다는 소식이 들렸다. 작년에도 1차 서류 통과는 했었고 드디어 때가 온 게 아닌가 싶다. 사실 대단한 일은 아니라고 생각한다. 아마 성실하게 하신 분들이라면 어렵지 않게 통과할 것이다. 작년 같은 경우에도 지금보다도 포트폴리오는 준비가 확실하지 않았으나 1차를 합격했었던 것으로 미루어 볼 때 진짜는 코딩 테스트를 통과 이후가 아닐까 싶다. 적성 검사까지 잘 맞을 수 있을지, 걱정 보단 조금이라도 손을 놀려서 파이썬 문제 풀이 방식을 익혀야지 ㅠ 코테.. 자신이 없긴 하지만 그래도 작년과는 다르다..! 마지막 스퍼트로 python 핵심 코테 기술들 위주로 정리하면서 학습 하려고 한다. 토요일 오전에 치는 시험… 목표는 3문제 중 2문제라도 맞추기다. 😂😂 알게된 핵심 내용 위주 사전 자료형에서 데이터를 찾아 탐색하는 것은 생각보다 시간 복잡도가 크지 않아 탐색 시 속도가 빠르다. 단 키가 주어질 때 이야기다 정규식을 활용하기 위해 re 라이브러리를 i…

나머지가 1이 되는 수 찾기 문제 설명 자연수 이 매개변수로 주어집니다. 을 로 나눈 나머지가 1이 되도록 하는 가장 작은 자연수 를 return 하도록 solution 함수를 완성해주세요. 답이 항상 존재함은 증명될 수 있습니다. 제한사항 3 ≤  ≤ 1,000,000 입출력 예 n result 10 3 12 11 입출력 예 설명 입출력 예 #1 10을 3으로 나눈 나머지가 1이고, 3보다 작은 자연수 중에서 문제의 조건을 만족하는 수가 없으므로, 3을 return 해야 합니다. 입출력 예 #2 12를 11로 나눈 나머지가 1이고, 11보다 작은 자연수 중에서 문제의 조건을 만족하는 수가 없으므로, 11을 return 해야 합니다. 음양 더하기 문제 설명 어떤 정수들이 있습니다. 이 정수들의 절댓값을 차례대로 담은 정수 배열 absolutes와 이 정수들의 부호를 차례대로 담은 불리언 배열 signs가 매개변수로 주어집니다. 실제 정수들의 합을 구하여 return 하도록 solu…

크레인 인형뽑기 게임 문제 설명 게임개발자인 “죠르디”는 크레인 인형뽑기 기계를 모바일 게임으로 만들려고 합니다. “죠르디”는 게임의 재미를 높이기 위해 화면 구성과 규칙을 다음과 같이 게임 로직에 반영하려고 합니다. crane_game_101.png 게임 화면은 “1 x 1” 크기의 칸들로 이루어진 “N x N” 크기의 정사각 격자이며 위쪽에는 크레인이 있고 오른쪽에는 바구니가 있습니다. (위 그림은 “5 x 5” 크기의 예시입니다). 각 격자 칸에는 다양한 인형이 들어 있으며 인형이 없는 칸은 빈칸입니다. 모든 인형은 “1 x 1” 크기의 격자 한 칸을 차지하며 격자의 가장 아래 칸부터 차곡차곡 쌓여 있습니다. 게임 사용자는 크레인을 좌우로 움직여서 멈춘 위치에서 가장 위에 있는 인형을 집어 올릴 수 있습니다. 집어 올린 인형은 바구니에 쌓이게 되는 데, 이때 바구니의 가장 아래 칸부터 인형이 순서대로 쌓이게 됩니다. 다음 그림은 [1번, 5번, 3번] 위치에서 순서대로 인형을…

실패율 실패율 failture_rate1.png 슈퍼 게임 개발자 오렐리는 큰 고민에 빠졌다. 그녀가 만든 프랜즈 오천성이 대성공을 거뒀지만, 요즘 신규 사용자의 수가 급감한 것이다. 원인은 신규 사용자와 기존 사용자 사이에 스테이지 차이가 너무 큰 것이 문제였다. 이 문제를 어떻게 할까 고민 한 그녀는 동적으로 게임 시간을 늘려서 난이도를 조절하기로 했다. 역시 슈퍼 개발자라 대부분의 로직은 쉽게 구현했지만, 실패율을 구하는 부분에서 위기에 빠지고 말았다. 오렐리를 위해 실패율을 구하는 코드를 완성하라. 실패율은 다음과 같이 정의한다. 스테이지에 도달했으나 아직 클리어하지 못한 플레이어의 수 / 스테이지에 도달한 플레이어 수 전체 스테이지의 개수 N, 게임을 이용하는 사용자가 현재 멈춰있는 스테이지의 번호가 담긴 배열 stages가 매개변수로 주어질 때, 실패율이 높은 스테이지부터 내림차순으로 스테이지의 번호가 담겨있는 배열을 return 하도록 solution 함수를 완성하라.…

비밀지도 비밀지도 네오는 평소 프로도가 비상금을 숨겨놓는 장소를 알려줄 비밀지도를 손에 넣었다. 그런데 이 비밀지도는 숫자로 암호화되어 있어 위치를 확인하기 위해서는 암호를 해독해야 한다. 다행히 지도 암호를 해독할 방법을 적어놓은 메모도 함께 발견했다. 지도는 한 변의 길이가 인 정사각형 배열 형태로, 각 칸은 “공백”(” ”) 또는 “벽”(”#”) 두 종류로 이루어져 있다. 전체 지도는 두 장의 지도를 겹쳐서 얻을 수 있다. 각각 “지도 1”과 “지도 2”라고 하자. 지도 1 또는 지도 2 중 어느 하나라도 벽인 부분은 전체 지도에서도 벽이다. 지도 1과 지도 2에서 모두 공백인 부분은 전체 지도에서도 공백이다. “지도 1”과 “지도 2”는 각각 정수 배열로 암호화되어 있다. 암호화된 배열은 지도의 각 가로줄에서 벽 부분을 , 공백 부분을 으로 부호화했을 때 얻어지는 이진수에 해당하는 값의 배열이다. secret map 네오가 프로도의 비상금을 손에 넣을 수 있도록, 비밀지도의…

part2. 알고리즘 유형 분석 - DFS, BFS, 백트레킹 그래프 자료구조 Graph Vertex(= node) edge 방향성 무방향 그래프 (= 양방향 그래프) 방향 그래프 순환 여부 순환 그래프(Cyclic Graph) 비순환 그래프(Acyclic Graph) 연결요소 Connected Component 정점 연결선(간선) 트리 자료구조(tree) 순환성이 없는 무방향 그래프 형태 트리는 특정하지 않는 한 어떤 노드이든 루트root 가 될 수 있다. 가장 바깥쪽 노드는 리프 노드 leaf node 라고 한다. node A에서 B로 가는 경로는 반드시 존재 하며 유일하다. (반드시 1개 존재) 노드개수 = 간선 개수 + 1 전산적으로 사용되는 구조에서는 이런 특징을 가진다. 자료구조에서의 트리는 부모 -> 자식 관계가 있는 방향 그래프이다. 루트 root 는 하나다 코드로 그래프를 나타내는 방법 1. 인접행렬 방향성이 있는 경우 같은 짝일 때 비대칭 구조가 되지만, …

part 2. 알고리즘 유형 분석 - 탐욕법 Greedy Algorithm 1 탐욕법 Greedy Algorithm 매 순간마다 최선의 경우만 골라서 선택하는 방식의 알고리즘 다른 경우는 고려하지 않고, 나중은 생각하지 않는다. 모든 경우를 다 보진 않아서, 완전탐색 알고리즘 보단 빠르다 어떤 경우가 최선인지 찾아야 하고, 규칙성을 발견하는게 포인트 당연한 말이지만 그렇다고 완벽하게 이상적인건 아니니 주의 2 동전 거스름돈 문제 A : 10, 50, 100, 500원 동전을 무한하게 갖고 있다. 손님에게 800원을 거슬러주려고 할 때 동전을 최소한으로 주는 방법은? 큰 단위부터 우선적으로 주는게 가장 효과적~ B: 만약 100, 400, 500원 동전을 무한하게 갖는경우? 400원짜리 2개 주는게 이득임(그리드로 풀수 없는 반례) 이러한 경우가 발생하는 이유는 A는 단위가 배수관계로 증대됨, B는 그렇지 않음. 배수의 관계로 B에서는 500원만으로 400원짜리 기준으로 만드는걸 만…

part 2. 알고리즘 유형 분석 - 완전탐색 Chapter 2. 완전탐색 - 브루트포스 완전탐색 장점 : 모든 경로를 본다 = 결국 답을 발견한다. 단점 : 모든 경로를 본다 = 리소스를 많이 먹고, 모든 연산을 끝내야만 한 브루트 포스 Brute-force (무차별 대입) 모든 경우의 수를 다 넣어 답을 맞추는 방식 무식하지만 확실히 쓰인다. 암호학, 수학 등 학계에서나 ProblemSolving(PS)에서도 널리쓰인다. 우선 이 방식으로 답을 찾고 최적화하는 방법을 쓰기도 한다. Chapter 2. 완전탐색 - 예제문제(1) 그냥 완전탐색으로 값을 구할 수 있다. 하지만 그냥 하게 된다고 하면 입력의 값의 크기로 인해 1초라는 시간 안에 해결이 안됨. () 고려해 볼 만한 방법 정렬을 사용해 본다. : 보통 의 시간 복잡도가 소요됨 가장 큰 값이 들어올 때마다 기록하고, 모든 입력이 마무리 되면 더한다 : 의 시간복잡도가 예상된다. Chapter 2. 완전탐색 - 순열 …

part 2. 알고리즘 유형 분석 - 자료구조 Chapter 1. 자료구조 - 배열, 벡터, 연결리스트 배열 Array 삽입 / 삭제 : O(N) - 삽입이나 삭제는 결국 내부 데이터를 옮기거나 하므로 최악의 경우를 상정하여 속도가 설정됨. 탐색 : O(1) - 메모리 상의 위치를 계산해서 접근하므로 접근의 속도가 매우 빠른 것이다. C++에서 사이즈 변경 불가 / Python은 리스트를 사용 벡터 Vector 삽입 / 삭제 : O(N) 탐색 : O(1) 동적 배열 : 사이즈 수정 가능 연결 리스트 Linked List 삽입 / 삭제 : O(1) 탐색 : O(N) - 노드 구조다 보니, 삽입이나 삭제는 노드들의 주소값 연결만으로 해결되지만 탐색은 모든 노드를 찾아 다녀야 한다. 자주 쓰이는 구조는 아니지만 다른 자료 구조들을 구현할 때 많이 쓰인다. Chapter 1. 자료구조 - 스택, 큐 스택 Stack(파이썬은 그냥 리스트로…) 큐 Queue Chapter 1. 자료…

part 0. 소개 강의 안내 강의 진행 언어 : python 가끔 C++ 섞을 예정 강의 구성 소개 part 1. 코딩테스트 준비 어떻게 해야 하나요 1. 코딩테스트란 2. 코딩 테스트 출제 경향 3. 코딩 테스트 채점 기준 4. 문제 해결 시작하기 part 2. 알고리즘 유형 분석 1. 자료구조 2. 완전탐색 3. 탐욕법 4. DFS, BFS, 백트래킹 5. 이분 탐색 6. 동적 계획법 part 1. 코딩 테스트 준비 어떻게 해야 하나요? chapter 1. 코딩테스트란? 온라인 저지를 꾸준하게 활용하는게 당연히 좋다. 본 강의는 백준을 주로 활용한다. << 나도 꾸준하게 풀긴 해야함 언어 고르기 무슨 언어로 문제를 풀어야 하는가? 3대장 : C++, java, python 본 강의는 파이썬 위주 진로가 확고하면 해당 언어로 연습하는 것이 좋다. 단, 마이너한 언어를 쓰면 문제 해결 시 난감할 수 있다. 기업 코텍에서는 언어 특성 차이로 인한 이슈는 없도록 내는 편 IT 기업들…

Introduction 본 포스트는 알고리즘 학습에 대한 정리를 재대로 하기 위하여 남기는 것입니다. 더불어 기본 내용은 나동빈 저의 〖이것이 취업을 위한 코딩 테스트다〗라는 교재 및 유튜브 강의의 내용에서 발췌했고, 그 외 추가적인 궁금 사항들을 검색 및 정리해둔 것입니다… 개발형 코딩 테스트 개념 정해진 목적에 따라서 동작하는 완성된 프로그램을 개발하는 것이 목표인 코딩테스트 유형입니다. 알고리즘 코딩 테스트 vs 개발형 코딩 테스트 알고리즘 형 시간 복잡도 분석 공간 복잡도 분석 개발 형 완성도 높은 하나의 프로그램을 개발 모듈을 적절히 조합하는 능력을 요구 일부 기업은 해커톤을 통해 채용을 진행하기도 합니다. 해커톤(Hackaton)이란 단 기간에 아이디어를 제품화 하는 프로젝트 이벤트 입니다. 대게 1 ~ 2일 정도 진행되며 다수의 해커톤이 대회 형식을 빌려 해커톤이 끝나면 프로그램을 시연하고 발표하고, 채점을 진행하는 형태입니다. 이러한 개발형 코딩테스트는 분야나 직군별…

Introduction 본 포스트는 알고리즘 학습에 대한 정리를 재대로 하기 위하여 남기는 것입니다. 더불어 기본 내용은 나동빈 저의 〖이것이 취업을 위한 코딩 테스트다〗라는 교재 및 유튜브 강의의 내용에서 발췌했고, 그 외 추가적인 궁금 사항들을 검색 및 정리해둔 것입니다… 기타 알고리즘 : 구간 합 빠르게 계산하기 구간 합(Interval Sum) 구간 합 문제 : 연속적으로 나열된 N개의 수가 있을 때 예를 들어 5개의 데이터로 구성된 수열 {10, 20, 30, 40, 50} 이 있다고 가정 시, 두 번째 수부터 네 번째 수까지의 합은? → 20 + 30 + 40 = 90 입니다. 선형 탐색이 가능하나, 이러한 요구가 여러번 들어올 때 처리하는 방법을 배워 봅시다. 구간 합 빠르게 계산하기 문제 설명 N개의 정수로 구성된 수열이 있습니다. M개의 쿼리(Query) 정보가 주어집니다. 각 쿼리는 왼쪽(left)과 오른쪽(right)으로 구성됩니다. 각 쿼리에 대하여 [left…

Introduction 본 포스트는 알고리즘 학습에 대한 정리를 재대로 하기 위하여 남기는 것입니다. 더불어 기본 내용은 나동빈 저의 〖이것이 취업을 위한 코딩 테스트다〗라는 교재 및 유튜브 강의의 내용에서 발췌했고, 그 외 추가적인 궁금 사항들을 검색 및 정리해둔 것입니다… 기타 알고리즘 : 투 포인터(Two Pointers) 개요 투 포인터 알고리즘은 리스트에 순차적으로 접근해야 할 때 두 개의 점의 위치를 기록하면서 처리하는 알고리즘을 의미합니다. 예를들어 2, 3, 4, 5, 6, 7번 학생을 지목한다고 할 때, 간단하게 2번부터 7번까지의 학생이라고 지목하면, 그 특정 범위 전체를 의미하게 됩니다. 리스트에 담긴 데이터에 순차적으로 접근해야할 때 시작점과 끝점 2개의 점으로 접근할 데이터의 범위를 표현할 수 있습니다. 특정한 합을 가지는 부분 연속 수열 찾기 문제 설명 N개의 자연수로 구성된 수열이 있다고 할 때, 합이 M인 부분 연속 수열의 개수를 구해보세요. 수행 시간…

Introduction 본 포스트는 알고리즘 학습에 대한 정리를 재대로 하기 위하여 남기는 것입니다. 더불어 기본 내용은 나동빈 저의 〖이것이 취업을 위한 코딩 테스트다〗라는 교재 및 유튜브 강의의 내용에서 발췌했고, 그 외 추가적인 궁금 사항들을 검색 및 정리해둔 것입니다… 기타 알고리즘 : 에라토스테네스의 체 다수의 소수 판별 하나의 수에 대해서 소수 여부를 판단하는 방법과 달리, 다수의 소수를 찾아야 하는 경우에는 알고리즘을 사용해야 합니다. 에라토스테네스의 체 알고리즘 다수의 자연수에 대하여 소수 여부 판별을 하는 대표적 알고리즘입니다. 에라토스테네스의 체는 N 보다 작거나 같은 모든 소수를 찾을 때 사용하면 됩니다. 구체적인 동작 과정은 다음과 같습니다. 2부터 N까지 모든 자연수를 나열합니다. 남은 수 중 아직 처리하지 않은 가장 작은 수 i를 찾습니다. 남은 수 중 i의 배수를 모두 제거합니다(i는 제거하지 않습니다.) 더 이상 반복할 수 없을 때까지 2, 3과정을 …

Introduction 본 포스트는 알고리즘 학습에 대한 정리를 재대로 하기 위하여 남기는 것입니다. 더불어 기본 내용은 나동빈 저의 〖이것이 취업을 위한 코딩 테스트다〗라는 교재 및 유튜브 강의의 내용에서 발췌했고, 그 외 추가적인 궁금 사항들을 검색 및 정리해둔 것입니다… 기타 알고리즘 : 소수 판별 알고리즘 소수(Prime Number) 소수란 1보다 큰 자연수이지만, 1과 자기자신을 제외한 자연수로 나누어 떨어지지 않는 자연수입니다. 예를 들어, 6은 1, 2, 3, 6으로 나누어 떨어지므로 소수가 아닙니다. 7은 1, 7을 제외하고 어떤 수로도 나누어 떨어지지 않으니 소수입니다. 코딩 테스트에서는 어떠한 자연수가 소수인지 아닌지 판별해야 하는 문제가 자주 출제 됩니다. 소수의 판별 : 기본적인 알고리즘 Python C++ 기본 알고리즘의 성능 분석 2부터 x - 1까지의 모든 자연수에 대해서 연산을 수행합니다. -> 모든 수를 하나씩 확인한다는 점에서 시간복잡도는 𝑂(𝑋)…

Introduction 본 포스트는 알고리즘 학습에 대한 정리를 재대로 하기 위하여 남기는 것입니다. 더불어 기본 내용은 나동빈 저의 〖이것이 취업을 위한 코딩 테스트다〗라는 교재 및 유튜브 강의의 내용에서 발췌했고, 그 외 추가적인 궁금 사항들을 검색 및 정리해둔 것입니다… 기타 그래프 이론 : 위상정렬 위상 정렬의 개요 사이클이 없는 방향의 그래프의 모든 노드를 방향성에 거스르지 않도록 순서대로 나열하는 것을 의미합니다. 예시) 선수과목을 고려한 학습 순서 설정 고급 알고리즘은 양쪽 과목을 모두 배운다는 조건이 성립되어야 한다. 위 세 과목을 모두 듣기 위한 적절한 학습 순서는? 자료구조 ➡︎ 알고리즘 ➡︎ 고급 알고리즘 (O) 자료구조 ➡︎ 고급 알고리즘 ➡︎ 알고리즘 (X) 진입차수와 진출차수 그래프 관련하여 알아두면 좋은 개념으로 먼저 소개하겠습니다. 진입차수(Indegree): 특정한 노드로 들어오는 간선의 개수 진출차수(Outdegree): 특정한 노드에서 나가는 간선의 개수…

Introduction 본 포스트는 알고리즘 학습에 대한 정리를 재대로 하기 위하여 남기는 것입니다. 더불어 기본 내용은 나동빈 저의 〖이것이 취업을 위한 코딩 테스트다〗라는 교재 및 유튜브 강의의 내용에서 발췌했고, 그 외 추가적인 궁금 사항들을 검색 및 정리해둔 것입니다. 기타 그래프 이론 : 크루스칼 알고리즘 신장 트리 그래프에서 모든 노드를 포함하면서 사이클이 존재하지 않는 부분 그래프를 의미합니다. 모든 노드가 서로 연결되면서 사이클이 존재하지 않는다는 조건의 트리 조건입니다. 이 특징을 요구하는 상황에서 효과적일 수 있습니다. 오른쪽은 1번 노드가 포함되지 않으므로 신장트리가 아니고, 사이클 발생하기에 신장트리가 아닙니다. 최소 신장 트리 위의 개념을 사용하는 경우는 어떤 경우일까요? 예시 ) N개의 도시가 존재하는 상황에서 두 도시 사이에 도로를 놓고 전체 도시가 서로 연결될 수 있게 도로를 설치해야 합니다. 최소에, 그러나 순환하지 않는 노드 연결을 요구할 때 쓰면 …

Introduction 본 포스트는 알고리즘 학습에 대한 정리를 재대로 하기 위하여 남기는 것입니다. 더불어 기본 내용은 나동빈 저의 〖이것이 취업을 위한 코딩 테스트다〗라는 교재 및 유튜브 강의의 내용에서 발췌했고, 그 외 추가적인 궁금 사항들을 검색 및 정리해둔 것입니다. 기타 그래프 이론 : 서로소 집합을 활용한 사이클 판별 개념 설명 사이클에 대한 내용은 그래프 개념에 대한 이해가 필요합니다. 이에 대한 개념관련 정보는 이 링크를 확인해 주세요. 사이클이란?(Cycle) : 어떤 정점에서 시작하여 다시 자신에게 돌아오는 경로가 있는 경우 이를 **사이클(cycle)**이라고 합니다. 서로소 집합은 무방향 그래프 내에서 사이클을 판별할 때 사용할 수 있습니다. 참고록 방향 그래프에서의 사이클 여부는 DFS를 이용하여 판별 할 수 있습니다. 사이클 판별 알고리즘은 다음과 같습니다. 각 선을 하나씩 확인하여 두 노드의 루트 노드를 확인합니다. 루트 노드가 서로 다르다면 두 노드의…

Introduction 본 포스트는 알고리즘 학습에 대한 정리를 재대로 하기 위하여 남기는 것입니다. 더불어 기본 내용은 나동빈 저의 〖이것이 취업을 위한 코딩 테스트다〗라는 교재 및 유튜브 강의의 내용에서 발췌했고, 그 외 추가적인 궁금 사항들을 검색 및 정리해둔 것입니다. 기타 그래프 이론 : 서로소 집합 자료구조 서로소 집합 서로소 집합(Disjoint Sets)란 공통 원소가 없는 두 집합을 의미합니다. 서로소 집합 자료구조 서로소 부분 집합들로 나누어지 원소들의 데이터를 처리하기 위한 자료구조입니다. 서로소 집합 자료구조는 두 종류의 연산을 지원합니다. 합집합(Union) : 두 집합의 원소들이 모두 포함된 하나의 집합으로 합치는 연산. 찾기(Find) : 특정 원소가 속한 집합을 알려주는 연산. 서로소 집합 자료구조는 합치기 찾기(Union Find) 자료구조라고도 불립니다. 여러 합치기 연산이 주어질 때 서로소 집합 자료구조의 동작 과과정 합집합 연산으로 연결된 두 …

Introduction 본 포스트는 알고리즘 학습에 대한 정리를 재대로 하기 위하여 남기는 것입니다. 더불어 기본 내용은 나동빈 저의 〖이것이 취업을 위한 코딩 테스트다〗라는 교재 및 유튜브 강의의 내용에서 발췌했고, 그 외 추가적인 궁금 사항들을 검색 및 정리해둔 것입니다. 전보 문제 설명 어떤 나라에 N개의 도시가 있습니다. 각 도시는 보내고자 하는 메시지가 있고, 다른 도시로 전보를 보내 다른 도시로 해당 메시지를 전송합니다. 하지만 X라는 도시에서 Y라는 도시로 전보를 보내고자 하면, 도시 X에서 Y로 향하는 통로가 설치되어있어야합니다. 예를 들어 X에서 Y로 향하는 통로는 있지만, Y에서 X로 향하는 통로가 없다면 Y는 X로 메시지를 보낼 수 없습니다. 또한 통로를 거쳐 메시지를 보낼 때는 일정 시간이 소요됩니다. 어느날 C라는 도시에서 위급 상황이 발생했습니다. 그래서 최대한 많은 도시로 메시지를 보내고자 합니다. 메시지는 도시 C에서 출발하여 각 도시 사이에 설치된 통…

Introduction 본 포스트는 알고리즘 학습에 대한 정리를 재대로 하기 위하여 남기는 것입니다. 더불어 기본 내용은 나동빈 저의 〖이것이 취업을 위한 코딩 테스트다〗라는 교재 및 유튜브 강의의 내용에서 발췌했고, 그 외 추가적인 궁금 사항들을 검색 및 정리해둔 것입니다. 플로이드 워셜 알고리즘 개요 개념 모든 노드에서 다른 모든 노드까지의 최단 경로를 모두 계산합니다. 플로이드 워셜(Floyd-Warshall) 알고리즘은 다익스트라 알고리즘과 마찬가지로 단계별로 거쳐가는 노드를 기준으로 알고리즘을 수행합니다. -> 매 단계마다 방문하지 않은 노드 중에 최단 거리를 갖는 노드를 찾는 과정이 필요하지 않습니다. 플로이드 워셜은 2차원 테이블에 최단 거리 정보를 저장합니다. 다이나믹 프로그래밍 유형에 속합니다. (점화식을 활용한 3중 반복문을 통해 구현이 이루어집니다.) 난이도는 쉽지만, 그만큼 시간 복잡도가 𝑂(𝑁³)가 되는 만큼, 노드의 개수가 많아지고, 간선의 개수가 많다면 …

Introduction 본 포스트는 알고리즘 학습에 대한 정리를 재대로 하기 위하여 남기는 것입니다. 더불어 기본 내용은 나동빈 저의 〖이것이 취업을 위한 코딩 테스트다〗라는 교재 및 유튜브 강의의 내용에서 발췌했고, 그 외 추가적인 궁금 사항들을 검색 및 정리해둔 것입니다. 최단 경로 알고리즘 개념 최단 경로 알고리즘은 가장 짧은 경로를 찾는 알고리즘을 의미합니다. 다양한 문제 상황 한 지점에서 다른 한 지점 까지의 최단 경로 한 지점에서 다른 모든 지점까지의 최단 경로 모든 지점에서 다른 모든 지점까지의 최단 경로 각 지점의 그래프에서 노드로 표현됩니다. 각 지점 간 연결된 도로는 그래프에서 간선으로 표현합니다. 노드 형태 예시 간단한 구현 방법의 성능 분석 지난 포스팅에서 정리했던 간단한 구현 방법의 경우 선형 탐색으로 하나씩 확인하는 방식이었습니다. 그러다보니 최단 경로 알고리즘으로써 시간 복잡도는 전체 원소 개수의 제곱으로 나타나게 되면서 상당한 코스트가 소모됨을 보여주었…

Introduction 본 포스트는 알고리즘 학습에 대한 정리를 재대로 하기 위하여 남기는 것입니다. 더불어 기본 내용은 나동빈 저의 〖이것이 취업을 위한 코딩 테스트다〗라는 교재 및 유튜브 강의의 내용에서 발췌했고, 그 외 추가적인 궁금 사항들을 검색 및 정리해둔 것입니다. 최단 경로 알고리즘 개념 최단 경로 알고리즘은 가장 짧은 경로를 찾는 알고리즘을 의미합니다. 다양한 문제 상황 한 지점에서 다른 한 지점 까지의 최단 경로 한 지점에서 다른 모든 지점까지의 최단 경로 모든 지점에서 다른 모든 지점까지의 최단 경로 각 지점의 그래프에서 노드로 표현됩니다. 각 지점 간 연결된 도로는 그래프에서 간선으로 표현합니다. 노드 형태 예시 다익스트라 최단 경로 알고리즘의 개요 특정한 노드에서 출발하여 다른 모든 노드로 가는 최단 경로를 계산합니다. 다익스트라 최단 경로 알고리즘은 음의 간선이 없을 때 정상 동작합니다. (현실세계 처럼 동작하며, 실 세계에서 사용 가능합니다.) 다익스트라 …

Introduction 본 포스트는 알고리즘 학습에 대한 정리를 재대로 하기 위하여 남기는 것입니다. 더불어 기본 내용은 나동빈 저의 〖이것이 취업을 위한 코딩 테스트다〗라는 교재 및 유튜브 강의의 내용에서 발췌했고, 그 외 추가적인 궁금 사항들을 검색 및 정리해둔 것입니다. 효율적인 화폐 구성 문제 설명 N가지 종류의 화폐가 있습니다. 이 화폐들의 개수를 최소한으로 이용해서 그 가치의 합이 M 원이 되도록 하려고 합니다. 이때 각 종류의 화폐는 몇 개라도 사용할 수 있습니다. 예를 들어 2원, 3원 단위 화폐가 있을 때는 15원을 만들기 위해 3원을 5개 사용하는 것이 가장 최소한의 화폐 개수 입니다. M원을 만들기 위한 최소한의 화폐 개수를 출력하는 프로그램을 작성하세요. 문제 조건 난이도 : 중상 풀이시간 : 30분 시간 제한 : 1초 메모리 제한 : 128MB 입력 조건 : 첫째 줄에 N, M이 주어진다. (1<= N <= 100, 1 <= M <= 10,000) 이후 N개…

Introduction 본 포스트는 알고리즘 학습에 대한 정리를 재대로 하기 위하여 남기는 것입니다. 더불어 기본 내용은 나동빈 저의 〖이것이 취업을 위한 코딩 테스트다〗라는 교재 및 유튜브 강의의 내용에서 발췌했고, 그 외 추가적인 궁금 사항들을 검색 및 정리해둔 것입니다. 개미 전사 문제 설명 개미 전사는 부족한 식량 창고를 몰래 공격하려고 합니다. 메뚜기 마을에는 여러 개의 식량창고가 있는데 식량창고는 일직선으로 이어져 있습니다. 각 식량창고에는 정해진 수의 식량을 저장하고 있으며, 개미 전사는 식량창고를 선택적으로 약탈하여 식량을 빼앗을 에정입니다. 이때 메뚜기 정찰병들은 일직선상에 존재하는 식량창고 중에서 서로 인접한 식량창고가 공격을 받으면 바로 알아 챌 수 있습니다. 따라서 개미 전사가 정찰병에게 들키지 않고 식량을 약탈하기 위해선 최소 한 칸 이상 떨어진 식량창고를 약탈해야 합니다. 예시 창고 0 창고 1 창고 2 창고 3 1 3 1 5 창고 0을 골라서 약탈을 한다…

Introduction 본 포스트는 알고리즘 학습에 대한 정리를 재대로 하기 위하여 남기는 것입니다. 더불어 기본 내용은 나동빈 저의 〖이것이 취업을 위한 코딩 테스트다〗라는 교재 및 유튜브 강의의 내용에서 발췌했고, 그 외 추가적인 궁금 사항들을 검색 및 정리해둔 것입니다. 다이나믹 프로그래밍 개념 다이나믹 프로그래밍이란 메모리를 적절히 사용하여 수행시간 효율성을 비약적으로 향상시키는 방법입니다. 이미 계산된 결과(작은문제)는 별도의 메모리 영역에 저장하고, 다시 계산하지 않도록 합니다. 다이나믹 프로그래밍 구현은 일반적으로 , 의 두 가지 방식으로 구성됩니다. 다이나믹 프로그래밍은 동적 계획법이라고도 부릅니다. 일반적으로 동적(Dynamic)이란 단어의 프로그래밍 분야에서의 의미는? 자료구조에서 동적 할당(Dynamic Allocation)이란 ‘프로그램 실행 도중에 실행에 필요한 메모리를 할당하는’ 기법을 의미합니다. 이에 비해 다이나믹 프로그래밍에서 ‘다이나믹’은 별다른 의…

Introduction 본 포스트는 알고리즘 학습에 대한 정리를 재대로 하기 위하여 남기는 것입니다. 더불어 기본 내용은 나동빈 저의 〖이것이 취업을 위한 코딩 테스트다〗라는 교재 및 유튜브 강의의 내용에서 발췌했고, 그 외 추가적인 궁금 사항들을 검색 및 정리해둔 것입니다. 이진 탐색 알고리즘 기초문제 풀이 떡볶이 떡 만들기 문제 설명 오늘 동빈이는 여행 가신 부모님을 대신해서 떡집 일을 하기로 했습니다. 오늘은 떡볶이 떡을 만드는 날입니다. 동빈이네 떡볶이 떢은 재밌게도 떡볶이 떡의 길이가 일정하지 않습니다. 대신 한 봉지 안에 들어가는 떡의 총 길이는 절단기로 잘라서 맞춰줍니다. 절단기 높이(H)를 지정하면 줄지어진 떡을 한 번에 절단합니다. 높이가 H보다 긴 떡은 H 위의 부분이 잘릴 것이고, 낮은 떡은 잘리지 않습니다. 예를 들어 높이가 19, 14, 10, 17cm 떡이 나란히 있고 절단기 높이를 15cm 로 지정하면 자른 뒤 떡의 높이는 15, 14, 10, 15cm가…

Introduction 본 포스트는 알고리즘 학습에 대한 정리를 재대로 하기 위하여 남기는 것입니다. 더불어 기본 내용은 나동빈 저의 〖이것이 취업을 위한 코딩 테스트다〗라는 교재 및 유튜브 강의의 내용에서 발췌했고, 그 외 추가적인 궁금 사항들을 검색 및 정리해둔 것입니다. 이진 탐색 알고리즘 개념 순차 탐색 : 리스트 안에 있는 특정한 데이터를 찾기 위해 앞에서부터 데이터를 하나씩 확인하는 방법 이진 탐색 : 정렬되어 있는 리스트에서 탐색 범위를 절반씩 좁혀가며 데이터를 탐색하는 방법 (시작점, 끝점, 중간점을 이용하여 탐색 범위 설정 방법) ➡︎ 이렇게 탐색을 구현할 경우, 탐색 연산의 시간복잡도를 로그단위로 떨어뜨릴 수 있어 탐색 시 유효합니다. 이진 탐색 동작 예시 이미 정렬된 10개의 데이터 중에서 값이 4인 원소를 찾는 예시 ⬇︎ 0 2 6 8 10 12 14 16 18 step 1 : 시작점(0), 끝점(9), 중간점(4, 소수점 이하는 제거)로 설정합…

덧! 중간에 공부한 내용을 빼먹고 진도를 나가(…) 순서를 맞추기 위해 부득이하게 data를 수정했습니다 ㅠ.. 실제 학습일 : 2022.05.06 Introduction 본 포스트는 알고리즘 학습에 대한 정리를 재대로 하기 위하여 남기는 것입니다. 더불어 기본 내용은 나동빈 저의 〖이것이 취업을 위한 코딩 테스트다〗라는 교재 및 유튜브 강의의 내용에서 발췌했고, 그 외 추가적인 궁금 사항들을 검색 및 정리해둔 것입니다. 정렬 알고리즘 비교하기 비교 앞서 다룬 네 가지의 정렬 알고리즘을 비교하면 아래와 같습니다. 추가적으로 대부분의 프로그래밍 언어에서는 지원하는 표준 정렬 라이브러리는 최악의 경우에도 O(NlogN)을 보장하도록 설계되어있습니다. 정렬 알고리즘 평균 시간 복잡도 공간 복잡도 특징 선택 정렬 O(N^2) O(N) 아이디어가 매우 간단합니다. 삽입 정렬 O(N^2) O(N) 데이터가 거의 정렬되어 있을 때는 가장 빠릅니다. 퀵 정렬 O(NlogN) O(N) 대부분의 경…

덧! 중간에 공부한 내용을 빼먹고 진도를 나가(…) 순서를 맞추기 위해 부득이하게 data를 수정했습니다 ㅠ.. 실제 학습일 : 2022.05.05 Introduction 본 포스트는 알고리즘 학습에 대한 정리를 재대로 하기 위하여 남기는 것입니다. 더불어 기본 내용은 나동빈 저의 〖이것이 취업을 위한 코딩 테스트다〗라는 교재 및 유튜브 강의의 내용에서 발췌했고, 그 외 추가적인 궁금 사항들을 검색 및 정리해둔 것입니다. 계수정렬 개념 특정 조건이 부합한 경우에만 사용 가능한 정렬로, 매우 빠른 동작의 정렬 알고리즘입니다. 계수 정렬은 데이터의 크기 범위가 제한되어 로 표현할 수 있을 때까지만 사용 가능합니다. 데이터의 개수가 N, 데이터(양수)중 최대값이 K일 때 최악의 경우에도 수행시간은 O(N + K)를 보장합니다. 공간복잡도 면에서는 데이터의 범위만큼 배열을 만들어 기록해놔야 하므로 비효율적일 순 있으나, 조건만 만족한다면 매우 빠른 속도로 처리가 가능하다는 장점을 갖고 있…

Introduction 본 포스트는 알고리즘 학습에 대한 정리를 재대로 하기 위하여 남기는 것입니다. 더불어 기본 내용은 나동빈 저의 〖이것이 취업을 위한 코딩 테스트다〗라는 교재 및 유튜브 강의의 내용에서 발췌했고, 그 외 추가적인 궁금 사항들을 검색 및 정리해둔 것입니다. 덧 중간에 뻬먹어서 재 포스팅합니다 ㅎㅎ! 퀵정렬 개념 기준 데이터를 설정하고, 그 기준보다 큰 데이터와 작은 데이터의 위치를 바꾸는 방법입니다. 일반적인 상황에서 가장 많이 사용되는 정렬 알고리즘 중 하나입니다. 병합정렬과 더불어 프로그래밍 언어 정렬 라이브러리의 근간이 되는 알고리즘입니다. 가장 기본적인 퀵 정렬은 **첫 번째 데이터를 기준 데이터(Pivot)**으로 설정합니다. 퀵 정렬 동작 예시 Step 0 피봇 값은 5, 왼쪽 부터 큰 데이터를 선택하므로 7이 되고 오른쪽부터 5보다 작은 값을 선택하므로 두 데이터 위치를 서로 변경합니다. pivot ➡︎ ⬅︎ 9 0 3 1 6 2 8 …

Introduction 본 포스트는 알고리즘 학습에 대한 정리를 재대로 하기 위하여 남기는 것입니다. 더불어 기본 내용은 나동빈 저의 〖이것이 취업을 위한 코딩 테스트다〗라는 교재 및 유튜브 강의의 내용에서 발췌했고, 그 외 추가적인 궁금 사항들을 검색 및 정리해둔 것입니다. 삽입정렬 개념 처리되지 않은 데이터를 하나씩 골라 적절한 위치에 삽입합니다. 선택 정렬에 비해 구현 난이도가 높은 편이지만, 일반적으로 더 효율적으로 동작합니다. 삽입 정렬 동작 예시 step 0 : 0번 데이터 ‘7’은 정렬되어 있다고 판단, 두 번째 데이터 ‘5’ 가 어떤 위치로 들어갈지 판단합니다. ⇒ 7을 기준으로 왼쪽, 오른쪽 두 경우 중 어느 경우인지 판단합니다. step 1: 이어서 9가 어떤 위치로 들어갈지 판단합니다. ⇒ 차례대로 왼쪽 데이터와 비교하여 더 작으면 자리를 바꿉니다. step 2 : 0을 값의 왼쪽가 비교하여 위치를 확인하고, 원소를 바꿔가면서 들어갈 자릴 판단합니다. 이러…

Introduction 본 포스트는 알고리즘 학습에 대한 정리를 재대로 하기 위하여 남기는 것입니다. 더불어 기본 내용은 나동빈 저의 〖이것이 취업을 위한 코딩 테스트다〗라는 교재 및 유튜브 강의의 내용에서 발췌했고, 그 외 추가적인 궁금 사항들을 검색 및 정리해둔 것입니다. 선택정렬 정렬 정렬(sorting)이란 데이터를 특정 기준에 따 순서대로 나열한 것을 말합니다. 일반적으로 문제 상황에 따라서 적절한 정렬 알고리즘이 공식처럼 사용됩니다. 선택 정렬 처리되지 않은 데이터 중에서 가장 작은 데이터를 선택해 맨 앞에 있는 데이터와 바꾸는 것을 반복합니다. 동작 순서 처리되지 않은 데이터 중 가장 작은 데이터를 선택해, 최상단으로 옮깁니다. 처리 되지 않은 데이터 중 가장 작은 데이터를 선택해서, 이전에 정렬된 가장 작은데이터를 제외하고, 그 다음 위치와 자리를 바꿉니다. … 이런 식으로 계속 반복하여 정렬되지 않은 데이터의 배열의 끝 - 1 까지 정렬을 마무리 지으면 정렬이 마…

Introduction 본 포스트는 알고리즘 학습에 대한 정리를 재대로 하기 위하여 남기는 것입니다. 더불어 기본 내용은 나동빈 저의 〖이것이 취업을 위한 코딩 테스트다〗라는 교재 및 유튜브 강의의 내용에서 발췌했고, 그 외 추가적인 궁금 사항들을 검색 및 정리해둔 것입니다. 자료구조 추가 학습 본 내용은 정리를 하던 도중 파이썬 내장 함수들 및 추가적으로 알아야 할 것들을 정리 할 겸, 쉴 겸 겸사겸사 작성해보는 포스트입니다. 위키 및 파이썬 공식문서들을 참조하여 정리한 내용입니다. 더불어 기본 개념은 16번 포스트를 참조 부탁드립니다 ㅎㅎ; 주된 참고 링크는 여기 입니다. 큐 개념 설명 스택처럼, 큐는 일렬의 구조체이며, 이것은 작업이 수행되는 특정 순서에 따라 구성되어 있습니다. 선입선출(FIFO)의 구조를 갖고 있으며, 최초의 주문이 처음으로 손님에게 제공되는 것과 같은 구조라고 보시면 됩니다. 스택과 큐의 차이점은 제거하는 것에 있어서 차이를 보입니다. 스택 자료구조는 가…

Introduction 본 포스트는 알고리즘 학습에 대한 정리를 재대로 하기 위하여 남기는 것입니다. 더불어 기본 내용은 나동빈 저의 〖이것이 취업을 위한 코딩 테스트다〗라는 교재 및 유튜브 강의의 내용에서 발췌했고, 그 외 추가적인 궁금 사항들을 검색 및 정리해둔 것입니다. 음료수 얼려먹기 N × M 크기의 얼음 틀이 있습니다. 구멍이 뚫려 있는 부분은 0, 칸막이가 존재하는 부분은 1로 표시됩니다. 구멍이 뚫려있는 부분끼리 상, 하, 좌, 우로 붙어 있는 경우 서로 연결되어 있는 것으로 간주합니다. 이때 얼음틀의 모양이 주어졌을 때 생성되는 총 아이스크림의 개수를 구하는 프로그램을 작성하세요. 다음 4 × 5 얼음틀의 예시에서는 아이스크림이 총 3개 생성됩니다. 연결요소 찾기의 유형과 유사합니다. 해당 그림을 참고하면 덩이는 총 3덩이가 구성될 수 있다. 문제 조건 난이도 : 중 풀이시간 : 30분 시간제한 : 1초 메모리 제한 : 128MB 입력조건 : 첫번째 줄에 얼음 틀의…

Introduction 본 포스트는 알고리즘 학습에 대한 정리를 재대로 하기 위하여 남기는 것입니다. 더불어 기본 내용은 나동빈 저의 〖이것이 취업을 위한 코딩 테스트다〗라는 교재 및 유튜브 강의의 내용에서 발췌했고, 그 외 추가적인 궁금 사항들을 검색 및 정리해둔 것입니다. BFS (Breadth-First Search) 개념 BFS는 너비 우선 탐색이라고도 부르며, 그래프에서 가까운 노드부터 우선적으로 탐색하는 알고리즘입니다. 대기업 코딩테스트에서 보통 주요하게 쓰이며, 최단 경로 구하는 문제에서 활용이 됩니다. 큐 자료구조를 사용하는 만큼, 각 언어마다 어떤 식으로 사용될 수 있는지 알아두는게 중요합니다. BFS는 큐 자료구조를 이용하며 구체적인 동작과정은 다음과 같습니다. 탐색 시작 노드를 큐에 삽입하고 방문 처리합니다. 큐에서 노드를 꺼낸 뒤에 해당 노드의 인접 노드 중 방문하지 않은 노드를 모두 큐에 삽입하고 방문 처리합니다. 더 이상 2번의 과정을 수행할 수 없을 때 …

Introduction 본 포스트는 알고리즘 학습에 대한 정리를 재대로 하기 위하여 남기는 것입니다. 더불어 기본 내용은 나동빈 저의 〖이것이 취업을 위한 코딩 테스트다〗라는 교재 및 유튜브 강의의 내용에서 발췌했고, 그 외 추가적인 궁금 사항들을 검색 및 정리해둔 것입니다. DFS(Depth-First Search) 개념 DFS는 깊이 우선 탐색이라고 부르며 그래프에서 깊은 부분을 우선적으로 탐색하는 알고리즘 입니다. DFS는 스택 자료구조(혹은 재귀함수)를 이용하며, 구체적인 동작과정은 다음과 같습니다. 탐색 시작 노드를 스택에 삽입하고 방문을 처리합니다. 스택의 최상단 노드에 방문하지 않은 인접한 노드가 하나라도 있으면 그 노드를 스택에 넣고 방문 처리합니다. 방문하지 않은 인접 노드가 없으면 스택에서 최상단 노드를 꺼냅니다. 더이상 2번의 과정을 수행할 수 없을 때까지 반복합니다. DFS 동작 예시 스텝 0 : 그래프를 준비합니다. (방문 기준 : 번호 가 낮은 인접 노드 …

Introduction 본 포스트는 알고리즘 학습에 대한 정리를 재대로 하기 위하여 남기는 것입니다. 더불어 기본 내용은 나동빈 저의 〖이것이 취업을 위한 코딩 테스트다〗라는 교재 및 유튜브 강의의 내용에서 발췌했고, 그 외 추가적인 궁금 사항들을 검색 및 정리해둔 것입니다. 자료구조 추가 학습 본 내용은 정리를 하던 도중 파이썬 내장 함수들 및 추가적으로 알아야 할 것들을 정리 할 겸, 쉴 겸 겸사겸사 작성해보는 포스트입니다. 위키 및 파이썬 공식문서들을 참조하여 정리한 내용입니다. 더불어 기본 개념은 16번 포스트를 참조 부탁드립니다 ㅎㅎ; 주된 참고 링크는 여기 입니다. 스택과 함께 사용되는 함수 : 아래의 개념들이 필요하다는 의미로 보시면 됩니다. : 스택이 비어있는지 여부를 판단합니다. 시간 복잡도 O(1) : 스택의 사이즈를 반환합니다. 시간 복잡도 O(1) : 스택의 가장 위의 요소의 참조를 반환합니다. 시간 복잡도 O(1) : ‘a’ 라는 요소를 삽입합니다. …

Introduction 본 포스트는 알고리즘 학습에 대한 정리를 재대로 하기 위하여 남기는 것입니다. 더불어 기본 내용은 나동빈 저의 〖이것이 취업을 위한 코딩 테스트다〗라는 교재 및 유튜브 강의의 내용에서 발췌했고, 그 외 추가적인 궁금 사항들을 검색 및 정리해둔 것입니다. 재귀함수 개요 재귀함수(Recursive Function)란 자기 자신을 다시 호출하는 함수를 의미합니다. DFS 구현 시 일반적으로 자주 사용하는 방법 중 하나이므로 이렇게 소개를 하고자 합니다. 재귀 함수의 종료 조건 재귀함수를 문젶 풀이에서 사용할 때는 재귀 함수의 종료 조건을 반드시 명시하도록 합니다. 이는 함수의 무한 호출을 야기하기 때문입니다. 팩토리얼 구현 예제 n! = 1 × 2 × 3 × … × (n - 1) × n 수학적으로 0! = 1! = 1 이 성립합니다. 최대 공약수 계산(유클리드 호제법)예제 유클리드 호제법 : 두 개의 자연수에 대한 최대 공약수를 구하는 대표적인 알고리즘 두 자연수…

Introduction 본 포스트는 알고리즘 학습에 대한 정리를 재대로 하기 위하여 남기는 것입니다. 더불어 기본 내용은 나동빈 저의 〖이것이 취업을 위한 코딩 테스트다〗라는 교재 및 유튜브 강의의 내용에서 발췌했고, 그 외 추가적인 궁금 사항들을 검색 및 정리해둔 것입니다. 그래프 탐색 알고리즘: DFS/BFS을 위한 자료구조 개념 탐색(Search)이란 많은 양의 데이터 중 원하는 데이터를 찾는 과정을 말합니다. 대표적인 그래프 탐색 알고리즘으로 DFS, BFS 가 있습니다. DFS/BFS는 코딩테스트에서 매우 자주 등장하는 유형이므로 반드시 숙지할 필요가 있습니다. 위 내용을 알아보기 위해 스택과 큐 자료구조에 대해 먼저 알아볼 것입니다. 스택 자료구조 개념 선입된 자료가 나중에 나가는 형식 (선입후출)의 자료구조 입니다. 입구와 출구가 동일한 형태로 스택을 시각화 할 수 있습니다. 해당 자료구조는 다양한 곳에 쓰일 수 있습니다. 스택 자료 구조 동작 예시 해당 자료구조는 삽…

Introduction 본 포스트는 알고리즘 학습에 대한 정리를 재대로 하기 위하여 남기는 것입니다. 더불어 기본 내용은 나동빈 저의 〖이것이 취업을 위한 코딩 테스트다〗라는 교재 및 유튜브 강의의 내용에서 발췌했고, 그 외 추가적인 궁금 사항들을 검색 및 정리해둔 것입니다. 시각 문제 설명 정수 N이 입력되면 00시 00분 00초부터 N시 59분 59초까지의 모든 시각 중에서 3이 하나라도 포함되는 모든 경우의 수를 구하는 프로그램을 작성하십시오. 예를 들어 1을 입력했을 때 다음은 3이 하나라도 포함되어 있으므로 세어야 하는 시각입니다. 00시 00분 03초 00시 13분 30초 반면에 다음은 3이 하나도 포함되어 있지 않으므로 세면 안되는 시각입니다.. 00시 02분 55초 01시 27분 45초 문제 조건 난이도 : 하 풀이시간 : 15분 시간제한 : 2초 메모리 제한 : 128MB 입력 조건 : 첫째 줄에 정수 N이 입력됩니다. (0<= N <= 23) 출력 조건 : 00시…

Introduction 본 포스트는 알고리즘 학습에 대한 정리를 재대로 하기 위하여 남기는 것입니다. 더불어 기본 내용은 나동빈 저의 〖이것이 취업을 위한 코딩 테스트다〗라는 교재 및 유튜브 강의의 내용에서 발췌했고, 그 외 추가적인 궁금 사항들을 검색 및 정리해둔 것입니다. 구현: 시뮬레이션과 완전 탐색 구현(Implementation) 구현이란 머릿속에 알고리즘을 소스코드로 바꾸는 과정입니다. 알고리즘을 알면서 머릿속에서만 돌린다는 것은 당연히 자신의 실력의 성장에 한계를 만드는 거 아니겠습니까 ㅎㅎ.. 단, 코딩 테스트라는 상황에서 해당 부분을 본다면, 문제의 유형으로써 특징은 어느정도 숙지하고 있는게 중요합니다. 구현 ver.코테 풀이를 떠올리는 것은 쉽지만. 소스코드로 옮기기 어려운 문제를 지칭합니다. 구현 유형의 예시는 다음과 같습니다. 알고리즘은 간단한데 코드가 지나칠 만큼 길어질수 있는 문제 실수 연산을 다루고, 특정 소수점 자리까지 출력해야 하는 문제 문자열을 특정…

Introduction 본 포스트는 알고리즘 학습에 대한 정리를 재대로 하기 위하여 남기는 것입니다. 더불어 기본 내용은 나동빈 저의 〖이것이 취업을 위한 코딩 테스트다〗라는 교재 및 유튜브 강의의 내용에서 발췌했고, 그 외 추가적인 궁금 사항들을 검색 및 정리해둔 것입니다. 문제 : 1이 될 때까지 문제 설명 어떠한 수 N이 1이때될 때까지 다음의 두 과정 중 하나를 반복적으로 선택하여 행하려고 합니다. 단, 두번째 연산은 N이 K로 나누어 떨어질때만 선택할 수 있습니다. N에서 1을 뺍니다. N을 K로 나눕니다. 예를 들어 N이 17, K가 4라고 가정합시다. 이때 1번의 과정을 한 번 수행하면 N은 16이 됩니다. 이후에 2번의 과정을 두 번 수행하면 N은 1이 됩니다. 결과적으로 이 경우 전체 과정을 실행한 횟수는 3이 됩니다. 이는 N을 1로 만드는 최소 횟수입니다. N과 K가 주어질 때 N이 1이 될 때까지 1번 혹은 2번의 과정을 수행해야 하는 최소 횟수를 구하는 프로…

Introduction 본 포스트는 알고리즘 학습에 대한 정리를 재대로 하기 위하여 남기는 것입니다. 더불어 기본 내용은 나동빈 저의 〖이것이 취업을 위한 코딩 테스트다〗라는 교재 및 유튜브 강의의 내용에서 발췌했고, 그 외 추가적인 궁금 사항들을 검색 및 정리해둔 것입니다. 그리디 알고리즘 개념 그리디 알고리즘(탐욕법)은 현재 상황에서 지금 당장 좋은 것만 고르는 방법을 의미합니다. 일반적인 그리디 알고리즘은 문제를 풀기 위한 최소한의 아이디어를 떠올릴 수 있는 능력을 요구합니다. 그리디 해법은 그 정당성 분석이 중요합니다. 단순히 가장 좋아 보이는 것을 반복적으로 선택해도 최적의 해를 구할 수 있는 지, 그 가능성을 검토합니다. 그리디 알고리즘 : 예시 문제 상황 문제상황 : 루트 노드부터 시작하여 거쳐 가는 노드 값의 합을 최대로 만들고 싶습니다. Q. 최적의 해는 무엇인가요? 단순히 현재 노드 위치에서 최대값을 찾아가면 합은 19가 됩니다. 실제 최대값인 ‘21’에는 미치지…

Introduction 본 포스트는 알고리즘 학습에 대한 정리를 재대로 하기 위하여 남기는 것입니다. 더불어 기본 내용은 나동빈 저의 〖이것이 취업을 위한 코딩 테스트다〗라는 교재 및 유튜브 강의의 내용에서 발췌했고, 그 외 추가적인 궁금 사항들을 검색 및 정리해둔 것입니다. 실전에서 유용한 표준 라이브러리 라이브러리들 내장 함수 : 기본 입출력 함수부터 정렬함수까지 기본적인 함수들을 제공합니다. 필수적인 기능들을 제공하고 있는 만큼 반드시 숙지하고 있어야 합니다. itertools : 반복되는 형태의 데이터를 처리하기 위한 기능들을 제공 합니다. (순열, 조합 라이브러리는 코딩테스트에서 자주 사용됩니다.) heapq : 힙 자료구조를 제공합니다. 일반적으론 우선순위 큐 기능을 구현하기 위해 사용됩니다. bisect : 이진탐색(Binary search) 기능을 제공합니다. Collections : 덱(deque), 카운터(Counter) 등의 유용한 자료구조를 포함합니다. mat…

Introduction 본 포스트는 알고리즘 학습에 대한 정리를 재대로 하기 위하여 남기는 것입니다. 더불어 기본 내용은 나동빈 저의 〖이것이 취업을 위한 코딩 테스트다〗라는 교재 및 유튜브 강의의 내용에서 발췌했고, 그 외 추가적인 궁금 사항들을 검색 및 정리해둔 것입니다. 함수 함수(Function)란 특정한 작업을 하나의 단위로 묶어 놓은 것을 의미합니다. 함수를 사용하면 불필요한 소스코드의 반복을 줄일 수 있습니다. 함수의 종류 내장 함수 : 파이썬 자체적으로 제공하는 함수입니다. 프로그램 전반에서 사용될만한 공통된 사용 도구들로 보시면 좋습니다. 사용자 정의 함수 : 개발자가 직접 정의한 역할을 수행하는 함수입니다. 개발 과정에서 필요시 되는 작업이 다양할 수 있는데, 그런 것들을 직접 만들어내는 경우를 의미 합니다. 함수 정의하기 프로그램에는 똑같은 코드를 여러 번 사용해야 할 때가 있는데, 그런 경우 함수화 시키면 소스 코드의 길이를 줄일수 있습니다. 매개변수(Para…

Introduction 본 포스트는 알고리즘 학습에 대한 정리를 재대로 하기 위하여 남기는 것입니다. 더불어 기본 내용은 나동빈 저의 〖이것이 취업을 위한 코딩 테스트다〗라는 교재 및 유튜브 강의의 내용에서 발췌했고, 그 외 추가적인 궁금 사항들을 검색 및 정리해둔 것입니다. 반복문 개념 트정한 소스 코드를 반복적으로 실행하고자 할 때 사용합니다. 파이썬에서는 while 문과 for 문이 있고, 어느 쪽이든 사용에 큰 차이는 없지만, 실제 사용 예시를 보면 for 문 쪽을 활용하는 경우가 더 많습니다.(좀더 간편합니다) while문 예제 반복문에서의 무한루프 무한 루프(infinite loop)란 반복문의 조건이 무조건 ‘참’이 되어 루프를 벗어나지 못하는 경우를 말합니다. 코딩 테스트 문제 유형에서 이런 구현 유형이 거의 없습니다. 하지만 반복문을 쓰는 과정에서 종종 조건을 정확하게 짜지 않면 문제가 생길 수 있습니다. 따라서 항상 반복문을 작성 뒤 탈출 가능 여부는 확인해야 합…

Introduction 본 포스트는 알고리즘 학습에 대한 정리를 재대로 하기 위하여 남기는 것입니다. 더불어 기본 내용은 나동빈 저의 〖이것이 취업을 위한 코딩 테스트다〗라는 교재 및 유튜브 강의의 내용에서 발췌했고, 그 외 추가적인 궁금 사항들을 검색 및 정리해둔 것입니다. 조건문 개념 프로그래밍 언어를 배우면서 진행하셨던 많은 분들이라면, 조건이라는 개념에 익숙하실 겁니다. 하지만 처음 시작하는 사람 입장에선 딱히 그렇지만도 않죠. 이에 대해 개념을 정리해보면 다음과 같습니다. “컴퓨터 과학에서 조건문(條件文, conditional)이란 프로그래머가 명시한 불린 자료형 조건이 참인지 거짓인지에 따라 달라지는 계산이나 상황을 수행하는 프로그래밍 언어의 특징이다. -위키백과” 조건문의 핵심은 행동을 결정하는데 있다고 생각합니다. 어떤 특정 데이터나, 데이터를 활용한 수식, 그 수식이 참(True)이나 거짓(False)이냐에 따라 다음 할 일을 결정지어주고, 그것들이 쌓이고 쌓이면 …

Introduction 본 포스트는 알고리즘 학습에 대한 정리를 재대로 하기 위하여 남기는 것입니다. 더불어 기본 내용은 나동빈 저의 〖이것이 취업을 위한 코딩 테스트다〗라는 교재 및 유튜브 강의의 내용에서 발췌했고, 그 외 추가적인 궁금 사항들을 검색 및 정리해둔 것입니다. 기본 입출력 개념 모든 프로그램은 적절한 입출력 양식을 갖고 있습니다. 특히나 코딩 테스트 등 요구사항이 있을 때 이를 어떤 식으로 출력하는가는 해당 요구 사항을 충족하나 안 하나를 결정 지을 수 있는 것입니다. 따라서 프로그램 동작의 첫 단계이자 마지막이 입출력이라고 보시면 됩니다. 자주 사용되는 표준 입력 방식 : 한줄의 문자열을 입력받는 함수 : 리스트의 모든 원소에 각각 특정한 함수를 적용할 때 사용하는 함수 예시 ) 공백 기준으로 구분된 데이터를 입력 받을 때 예시 ) 공백 기준으로 구분된 데이터의 개수가 많지 않다면 단순히 다음과 같이 사용한다. 입력을 위한 전형적인 소스코드 빠르게 입력 받…

Introduction 본 포스트는 알고리즘 학습에 대한 정리를 재대로 하기 위하여 남기는 것입니다. 더불어 기본 내용은 나동빈 저의 〖이것이 취업을 위한 코딩 테스트다〗라는 교재 및 유튜브 강의의 내용에서 발췌했고, 그 외 추가적인 궁금 사항들을 검색 및 정리해둔 것입니다. 사전 자료형 개념 사전 자료형은 키와 값의 쌍으로 이루어진 자료형입니다. 앞서 다룬 자료형인 리스트나 튜플이 값을 순차적으로 저장하고, 인덱싱을 하는것 과는 대비됩니다. 사전 자료형은 키와 값의 쌍으로 데이터를 가지면서, 원하는 ‘변경 불가능한(Immutable) 자료형’을 키로 사용 가능합니다. 사전 자료형은 해시 테이블을 이용하므로 데이터 조회 및 수정에 있어서 O(1) 의 시간 처리를 할 수 있습니다. 자료의 사용에 있어서 상당히 빠른 타이밍으로 확인이 가능합니다. 표로 표현하면 아래의 형태를 구현 한다고 보시면 됩니다. key value 사과 Apple 바나나 Banana 코코넛 Coconut 사용 방…

Introduction 본 포스트는 알고리즘 학습에 대한 정리를 재대로 하기 위하여 남기는 것입니다. 더불어 기본 내용은 나동빈 저의 〖이것이 취업을 위한 코딩 테스트다〗라는 교재 및 유튜브 강의의 내용에서 발췌했고, 그 외 추가적인 궁금 사항들을 검색 및 정리해둔 것입니다. 문자열 자료형 문자열 자료형의 개요 Python 은 문자열을 사용하는 부분에서 다른 프로그램 언어로 사용하는 것과 다르게 굉장히 강력한 기능들을 갖고 있습니다. 문자열 변수의 초기화 : 다른 프로그램 언어 중 큰 따옴표("")와 작은 따옴표(”) 를 구분하여 의미를 부여하는 경우가 있으나, Python은 큰 구분이 없습니다. 단, 문자열 안에 다른 따옴표를 넣는 부분에선 사용에 구분이 필요합니다. 전체 문자열을 감싸는 따옴표가 큰 따옴표이면 작은 따옴표를 사용해야 하며, 그 반대는 동일하게 반대로 생각하면 됩니다. 혹은 백슬래쉬(\)를 사용하면 됩니다.(이러한 부분은 다른 프로그램 언어와 유사합니다.) 문자열…

Introduction 본 포스트는 알고리즘 학습에 대한 정리를 재대로 하기 위하여 남기는 것입니다. 더불어 기본 내용은 나동빈 저의 〖이것이 취업을 위한 코딩 테스트다〗라는 교재 및 유튜브 강의의 내용에서 발췌했고, 그 외 추가적인 궁금 사항들을 검색 및 정리해둔 것입니다. 리스트 자료형 리스트 자료형의 개념 여러개의 연속적 데이터 처리용인 자료형 입니다. C나 자바의 배열(Array)의 기능및 연결리스트와 유사한 기능을 지원합니다. C++ 의 STL vector 와 기능적으로 유사합니다. 리스트 대신 배열 혹은 테이블 이라고도 합니다. 형태에 따라 단일 차원~ 다차원 리스트가 존재할 수 있습니다. 리스트 초기화 리스트의 인덱싱과 슬라이싱(Indexing and Slicing) 인덱스 값을 입력하여 리스트의 특정 원소 접근하는 것을 인덱싱(Indexing)이라고 합니다. 파이썬에선 인덱스의 값은 양, 음 모두 사용할 수 있다는 점이 매우 특이한 부분입니다. 음의 정수를 넣으면 0…

Introduction 본 포스트는 알고리즘 학습에 대한 정리를 재대로 하기 위하여 남기는 것입니다. 더불어 기본 내용은 나동빈 저의 〖이것이 취업을 위한 코딩 테스트다〗라는 교재 및 유튜브 강의의 내용에서 발췌했고, 그 외 추가적인 궁금 사항들을 검색 및 정리해둔 것입니다. 자료형 모든 프로그래밍 언어는 결국 데이터를 다루는 행위입니다. ⇒ 따라서 들어오는 자료를 어떻게 처리하는지를 이해하는 것은 프로그래밍의 첫 걸음이라 할 수 있습니다. Python 의 자료형 : 정수형, 실수형, 복소수형, 문자열, 리스트, 튜플, 사전 등 ⇒ 저수준의 언어들과 비교하면 매우 다양한 기능 지원하며 자료형 마다의 특징을 이해함은 코딩시 매우 편리합니다. 정수형 정수형(integer)은 정수를 다루는 자료형입니다. (양의 정수, 0, 음의 정수 포함) 코딩 테스트의 많은 유형이 정수 자료형을 다룹니다. 기본적으로 대부분의 프로그램과 수치는 실수보단 정수형으로 사용합니다. 실수형 실수형은 소수점 아…

Introduction 본 포스트는 알고리즘 학습에 대한 정리를 재대로 하기 위하여 남기는 것입니다. 더불어 기본 내용은 나동빈 저의 〖이것이 취업을 위한 코딩 테스트다〗라는 교재 및 유튜브 강의의 내용에서 발췌했고, 그 외 추가적인 궁금 사항들을 검색 및 정리해둔 것입니다. 복잡도 복잡도의 개념 복잡도는 알고리즘의 을 나타내는 척도입니다. 우리는 쉽게 눈에 보이는 코드의 복잡도로 코드를 판가름 할 수 있지만, 사실 컴퓨터 시스템에서의 복잡도라는 것은 사람과는 다르게 작동하고, 자원을 효율적으로 사용해야하는 필연적인 상황 상 컴퓨터의 복잡도를 알고 접근하냐 모르냐는 매우 중요한 부분이라 할 수 있습니다. 시간 복잡도 : 특정한 크기의 입력에 대하여 알고리즘 수행 시간을 분석합니다. 공간 복잡도 : 특정 크기의 입력에 대해 알고리즘 메모리 사용량을 분석합니다. 동일한 기능을 수행하는 알고리즘이 있다면, 일반적으로 복잡도가 낮을 수록 좋은 알고리즘이라고 보시면 됩니다. 빅오 표기법(B…

Introduction 본 포스트는 알고리즘 학습에 대한 정리를 재대로 하기 위하여 남기는 것입니다. 더불어 기본 내용은 나동빈 저의 〖이것이 취업을 위한 코딩 테스트다〗라는 교재 및 유튜브 강의의 내용에서 발췌했고, 그 외 추가적인 궁금 사항들을 검색 및 정리해둔 것입니다. 코딩테스트란 무엇인가? 코딩 테스트란? 기업, 기관에서 직원이나 연수생을 선발하기 위한 목적으로 시행되는 시험입니다. 공채를 하는 기업에서 코딩을 주로 이용합니다. 문제 해결 역량을 평가하며 채점 시스템을 통해 응시자 수를 줄이는 효과를 갖고 있습니다. 코딩 테스트의 유형 온라인 코딩 테스트 인터넷을 활용해 프로그래밍 역량을 평가하여 응시자를 선별하는 방식입니다. 대체로 타인과 문제풀이를 공유하지 않는 선에서 인터넷 검색을 허용합니다. 오프라인 코딩테스트 시험장에 방문하여 치르는 시험입니다. 대체로 인터넷 검색이 허용 되지 않고, 회사에서 제공하는 환경에서 진행됩니다. 온라인 저지란? 체력을 키우기 좋은 훈련…

Introduction 본 포스트는 알고리즘 학습에 대한 정리를 재대로 하기 위하여 남기는 것입니다. 더불어 기본 내용은 나동빈 저의 〖이것이 취업을 위한 코딩 테스트다〗라는 교재 및 유튜브 강의의 내용에서 발췌했고, 그 외 추가적인 궁금 사항들을 검색 및 정리해둔 것입니다. 🧑🏻‍💻 알고리즘 박살내기 시리즈🧑🏻‍💻 00. INDEX 01. 코딩테스트란 무엇인가 02. 알고리즘 성능평가 03. 파이썬 기초(수 자료형) 04. 파이썬 기초(리스트 자료형) 05. 파이썬 기초(문자열, 튜플형) 06. 파이썬 기초(사전, 집합형) 07. 파이썬 기초(기본 입출력) 08. 파이썬 기초(조건문) 09. 파이썬 기초(반복문) 10. 파이썬 기초(함수와 람다 표현식) 11. 파이썬 기초(자주 사용되는 표준 라이브러리) 12. 그리디 알고리즘 개요 13. 그리디 알고리즘 유형 문제 풀이 14. 구현 유형 개요 15. 구현 유형 문제 풀이 16. DFS/BFS(스택과 큐 자료구조) 16-1. DFS/BFS(…