키자드에 등록된 shinefilm1의 네이버 블로그 포스트 목록

shinefilm1의 등록된 링크

shinefilm1로 등록된 네이버 블로그 포스트 수는 187건입니다.

[Algorithm] 마스터 정리(Master Method) [내부링크]

마스터 정리(Master Method)란? 마스터 정리는 재귀식이 다음과 같은 형태일 때 적용될 수 있는 분석방법입니다. 마스터 정리는 f(n)과 nlogba를 서로 비교해서 해결하는 방법입니다. 주어진 문제에 따라 a, b, f(n) 를 nlogba 구하고 후술할 3가지 경우에 따라 답을 구하면 됩니다. 마스터 정리는 3가지 경우로 나눠서 적용할 수 있습니다. 마스터 정리의 3가지 경우 Case1 Case2 Case3 마스터 정리 예제 예제 1번 T(n)=4T(n/2)+n 예제 2번 T(n)=4T(n/2)+n2 예제 3번 T(n)=4T(n/2)+n3 예제 4번 T(n)=4T(n/2)+n2/logn 마무리 마스터 정리는 주어진 재귀식의 형태에 따라 적용 유무가 결정되는 매우 특이한 정리입니다. 그렇다 보니 모든 경우에 적용될 수 있는 풀이법이 되지는 못합니다. 하지만, 적용만 된다면 매우 빠르게 재귀식을 분석할 수 있다는 특징이 있어 알아둬야 하는 방법 중 하나입니다.

[Data Structure]AVL TREE [내부링크]

AVL TREE란? AVL 트리는 Adelson-Velsky와 Evgenii Landis가 발명한 자가 균형 이진 탐색 트리입니다. AVL 트리는 BST가 편향 이진 트리에 가까워질수록 연산의 시간복잡도가 O(n)에 가까워진다는 문제점에 입각해서 발명되었습니다. 핵심은 BST를 균형 이진 트리로 유지시킨다는 것입니다. 균형 이진 트리로 유지시킨다는 것은 루트 노드를 기준으로 좌우 서브 트리의 높이차를 1 이하로 유지시킨다는 것입니다. 만약 이 조건을 만족시키지 못한다면 노드 위치 재조정을 수행해야 할 것입니다. 모든 노드에 대해 |HL - HR| ≤ 1 만족시킨다면 트리는 균형 잡혀있다. AVL 트리는 좌우 서브 트리의 높이차를 기준으로 균형 잡혀 있는지를 확인합니다. 따라서 모든 노드 N에 대해 Height(RightSubtree(N)) - Height(LeftSubtree(N)) ∈ {-1, 0, 1}을 만족시킬 경우 주어지는 이진 트리는 AVL 트리입니다. AVL TREE의 구

[Data Structure]해싱(Hashing) [내부링크]

해싱(Hashing)이란? 해시 함수(Hash Function)는 임의의 크기를 갖는 값에 대해 고정된 크기를 갖는 해시값을 매핑하는 것을 의미합니다. 예를 들면, 이러한 해시 함수를 이용해서 O(1)의 시간복잡도로 원소를 찾는 데 사용할 수 있습니다. 예를 들면 해시 함수를 "h(x) = x mod 10"이라고 하고 원소 1, 14, 27를 해싱을 사용한 자료구조에 저장한다고 해봅시다. 그러면 이 해시 함수에 의해서 0부터 9까지의 정수가 해시값으로 나올 수 있을 것입니다. 그리고 그 해시값에 대응되는 해시 테이블(Hash Table)을 만듭니다. 이제 해시값을 위치 정보로 사용해서 원래의 값을 저장합니다. 해싱 깊이 보기 충돌(Collision) 해싱은 들어오는 입력값에 따라서 중복되는 해시값을 반환할 수 있다는 문제점이 있습니다. 위 예시를 이용해서 "h(x)= x mod 10" 해시 함수는 x = 1, 11, 21 ... 등에 대해서 1이라는 공통된 해시값을 반환합니다. 좋은

Ubuntu Server에서 Desktop까지(CLI to GUI) [내부링크]

이전에 맥북에서 VMWare를 이용해서 Ubuntu 22.04 Desktop을 설치하는 방법에 대한 포스팅을 작성한 적이 있었습니다. 당시에는 ARM 아키텍처에 맞는 Desktop ISO 파일이 있어 해당 파일을 이용해서 설치하면 됐습니다. 그런데, 대학 과제를 진행하기위해 Ubuntu 20.04 Desktop이 필요해서 찾아보는데 ARM 아키텍처로는 Server ISO 파일밖에 없었습니다. 그래서 조금 더 찾아보니 Server ISO 파일을 이용해서 Ubuntu Server 가상환경을 먼저 구축하고, 그 가상환경에 Desktop 파일을 추가적으로 다운로드해 ARM 아키텍처 Ubuntu 20.04 Desktop을 가상환경을 구축할 수 있었습니다. 오늘은 Ubuntu Server를 Ubuntu Desktop으로 변경하는 방법에 대해서 알아보겠습니다. Ubuntu 20.04 Server 다운로드 및 설치 먼저 Ubuntu 20.04 Server ISO 파일을 다운로드해야 합니다. 다음

[Algorithm] 병합 정렬(Merge Sort) [내부링크]

병합 정렬(Merge Sort)이란? 병합 정렬은 정렬 알고리즘 중 하나로 O(nlogn)의 시간복잡도로 수행되는 알고리즘으로 알려져 있습니다. 병합 정렬은 분할 정복 알고리즘(Divide and Conquer)을 기반으로 만들어진 정렬 알고리즘입니다. 병합 정렬은 대량의 데이터를 효과적으로 정렬할 수 있으며 지금도 많이 사용되는 정렬 알고리즘입니다. "병합"이라는 이름은 주어진 데이터를 나눠서 정렬한 뒤 후에 그 결과를 합친다는 의미에서 붙은 이름입니다. 원리 병합 정렬은 다음과 같은 세 단계를 통해 주어진 데이터를 정렬합니다. 병합 정렬의 주요한 특징 중 하나는 데이터를 나누고 정렬하는 단계에서 추가적인 배열이 필요하다는 것입니다. 분할 (Divide): 주어진 배열을 반으로 나눕니다. 정복 (Conquer): 각각의 작은 배열에 대해 재귀적으로 정렬합니다. 이때 충분히 작다는 것은 배열의 크기가 1인 경우를 의미합니다. 병합 (Merge): 정렬된 작은 배열들을 하나로 합칩니다

[Algorithm] 점근 성능 분석(Asymptotic Analysis) [내부링크]

점근 성능 분석(Asymptotic Analysis)이란? 실행시간과 입력값(Running Time & Input) 점근 성능에 대해서 자세히 알기 전에 실행시간과 입력값 사이의 관계에 대해서 알아봅시다. 알고리즘의 실행시간은 input에 영향을 받습니다. 예를 들면, 이미 정렬된 배열은 좀 더 쉽게 정렬할 수 있습니다. 알고리즘의 실행시간은 input의 크기에 영향을 받습니다. 예를 들면, 4개의 원소를 갖는 배열보다 10개의 원소를 갖는 배열이 정렬하는 데 더 오래 걸립니다. 일반적으로 이러한 input에 대한 실행시간의 상한선을 구해 최악의 경우에도 보장되는 성능을 구하는 것이 알고리즘 분석의 주 목적입니다. 길이가 n인 input에 대한 알고리즘의 실행시간을 T(n)이라고 표현합니다. 이러한 input에 영향받는 수행시간을 경우에 따라 3가지로 나눠서 분석합니다. 최악의 경우(Worst Case) - 알고리즘 분석을 한다고 할 때 반드시 분석해야 하는 경우로 어떠한 크기의 i

[Algorithm] 브루트포스(Brute Force) [내부링크]

브루트포스(Brute Force)란? 브루트포스(Brute Force) 알고리즘은 다른 말로는 "전수조사"라고 표현할 수 있는 방법으로 모든 가능성을 직접적으로 탐색하여 원하는 답을 찾는 알고리즘입니다. 다양한 문제에 적용되며, 모든 경우의 수를 고려해야 하는 문제에서 특히 유용합니다. 브루트포스는 전적으로 컴퓨터의 연산 속도에 의지해서 수행되는 방법입니다. 그렇다보니 컴퓨터 리소스를 전력으로 사용하더라도 오랜 시간이 걸리는 경우에는 해결이 어려울 수 있습니다. 예를 들어 길이가 n인 영어 대소문자와 숫자로 조합될 수 있는 비밀번호를 전수조사하기 찾기 위해서는 O(62n)라는 지수시간의 시간복잡도가 필요합니다. n=10인 경우만 하더라도 839,299,365,868,340,224의 수행연산이 필요한데 이걸 걸리는 시간으로 변환하면 약 266년입니다. 장단점 장점 보편성과 간단성: 브루트포스는 문제에 대한 직관적이고 단순한 해결책을 제공합니다. 어떤 경우에도 적용 가능하며, 구현이 간

백준9251: LCS [내부링크]

9251번: LCS 9251번 제출 맞힌 사람 숏코딩 재채점 결과 채점 현황 강의 질문 게시판 LCS 시간 제한 메모리 제한 제출 정답 맞힌 사람 정답 비율 0.1 초 ( 하단 참고 ) 256 MB 84801 34911 25588 40.600% 문제 LCS(Longest Common Subsequence, 최장 공통 부분 수열)문제는 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다. 예를 들어, ACAYKP와 CAPCAK의 LCS는 ACAK가 된다. 입력 첫째 줄과 둘째 줄에 두 문자열이 주어진다. 문자열은 알... www.acmicpc.net 이 문제는 최장 공통 부분 수열(LCS)를 이해하고 있는지를 묻는 문제입니다. 1. Problem Analysis 구해야하는 것은 두 수열의 최장 공통 부분 수열의 길이입니다. 이 문제의 제한조건은 다음과 같습니다. 각 문자열의 길이는 1,000 이하의 자연수이다. 각 문자열은 알파벳 대문자로만 이루어져

백준1987: 알파벳 [내부링크]

1987번: 알파벳 문제 세로 $R$칸, 가로 $C$칸으로 된 표 모양의 보드가 있다. 보드의 각 칸에는 대문자 알파벳이 하나씩 적혀 있고, 좌측 상단 칸 ($1$행 $1$열) 에는 말이 놓여 있다. 말은 상하좌우로 인접한 네 칸 중의 한 칸으로 이동할 수 있는데, 새로 이동한 칸에 적혀 있는 알파벳은 지금까지 지나온 모든 칸에 적혀 있는 알파벳과는 달라야 한다. 즉, 같은 알파벳이 적힌 칸을 두 번 지날 수 없다. 좌측 상단에서 시작해서, 말이 최대한 몇 칸을 지날 수 있는지를 구하는 프로그램을 작성하시오. 말이 지나는 칸은 좌측 상단의 칸도 포함된... www.acmicpc.net 이 문제는 대표적인 그래프 탐색 문제입니다. 깊이 우선 탐색을 이용하면 PyPy3로는 통과지만 Python3로든 시간 초과가 나서 여러 방면으로 생각하느라 고민 좀 했던 문제입니다. 1. Problem Analysis 구해야하는 것은 (R, C) 크기의 알파벳이 적힌 보드판에서 (1, 1)에서 말을 움

백준1991: 트리순회 [내부링크]

1991번: 트리 순회 문제 이진 트리를 입력받아 전위 순회(preorder traversal), 중위 순회(inorder traversal), 후위 순회(postorder traversal)한 결과를 출력하는 프로그램을 작성하시오. 예를 들어 위와 같은 이진 트리가 입력되면, 전위 순회한 결과 : ABDCEFG // (루트) (왼쪽 자식) (오른쪽 자식) 중위 순회한 결과 : DBAECFG // (왼쪽 자식) (루트) (오른쪽 자식) 후위 순회한 결과 : DBEGFCA // (왼쪽 자식) (오른쪽 자식) (루트) 가 된다. 입력 첫째 줄에는 이진 트리의... www.acmicpc.net 이 문제는 이진 트리의 개념을 이해하고 트리의 순회를 구현할 수 있는지를 묻는 간단한 문제입니다. 1. Problem Analysis 구해야하는 것은 주어진 이진 트리의 전위 순회, 중위 순회, 후위 순회 결과입니다. 이 문제의 제한조건은 다음과 같습니다. 트리의 노드의 개수 n은 26 이하의 자연

백준2096: 내려가기 [내부링크]

2096번: 내려가기 문제 N줄에 0 이상 9 이하의 숫자가 세 개씩 적혀 있다. 내려가기 게임을 하고 있는데, 이 게임은 첫 줄에서 시작해서 마지막 줄에서 끝나게 되는 놀이이다. 먼저 처음에 적혀 있는 세 개의 숫자 중에서 하나를 골라서 시작하게 된다. 그리고 다음 줄로 내려가는데, 다음 줄로 내려갈 때에는 다음과 같은 제약 조건이 있다. 바로 아래의 수로 넘어가거나, 아니면 바로 아래의 수와 붙어 있는 수로만 이동할 수 있다는 것이다. 이 제약 조건을 그림으로 나타내어 보면 다음과 같다. 별표는 현재 위치이고, 그 아랫 줄의 파란 동그라미는 원룡이가... www.acmicpc.net 이 문제는 메모리제한을 주의해야하는 다이나믹 프로그래밍 문제입니다. 1. Problem Analysis 구해야하는 것은 n개의 줄로 이루어진 숫자표가 주어져 있을 때, 얻을 수 있는 최대 점수, 최소 점수입니다. 이때 숫자표를 내려가는 내려가는 규칙은 다음과 같습니다. 처음에 적혀 있는 세 개의 숫자

백준2206: 벽 부수고 이동하기 [내부링크]

2206번: 벽 부수고 이동하기 2206번 제출 맞힌 사람 숏코딩 재채점 결과 채점 현황 강의 질문 게시판 벽 부수고 이동하기 시간 제한 메모리 제한 제출 정답 맞힌 사람 정답 비율 2 초 192 MB 137504 35937 22483 23.293% 문제 N×M의 행렬로 표현되는 맵이 있다. 맵에서 0은 이동할 수 있는 곳을 나타내고, 1은 이동할 수 없는 벽이 있는 곳을 나타낸다. 당신은 (1, 1)에서 (N, M)의 위치까지 이동하려 하는데, 이때 최단 경로로 이동하려 한다. 최단경로는 맵에서 가장 적은 개수의 칸을 지나는 경로를 말하는데, 이때 시작하는 칸과... www.acmicpc.net 이 문제는 경로 저장에 대해서 생각을 해봐야하는 그래프 탐색 문제입니다. 1. Problem Analysis 구해야하는 것은 크기가 nxm인 맵에서 (1, 1) 위치에서 (n, m)으로 이동하는 최단 경로입니다. 이 문제의 제한조건은 다음과 같습니다. 맵의 크기 n, m은 1,000 이하의

백준2448: 별 찍기 - 11 [내부링크]

2448번: 별 찍기 - 11 2448번 제출 맞힌 사람 숏코딩 재채점 결과 채점 현황 강의 질문 게시판 별 찍기 - 11 시간 제한 메모리 제한 제출 정답 맞힌 사람 정답 비율 1 초 256 MB 37147 16396 11759 42.194% 문제 예제를 보고 규칙을 유추한 뒤에 별을 찍어 보세요. 입력 첫째 줄에 N이 주어진다. N은 항상 3×2 k 수이다. (3, 6, 12, 24, 48, ...) (0 ≤ k ≤ 10, k는 정수) 출력 첫째 줄부터 N번째 줄까지 별을 출력한다. 예제 입력 1 복사 24 예제 출력 1 복사 * ... www.acmicpc.net 이 문제는 대표적인 재귀 문제입니다. 1. Problem Analysis 이 문제에서 구해야하는 것은 주어진 예제를 보고 규칙을 유추해서 별을 찍는 방법입니다. // 예제 > Input: 24 > Output: * * * ***** * * * * * * ***** ***** * * * * * * ***** *****

백준2638: 치즈 [내부링크]

2638번: 치즈 문제 N×M의 모눈종이 위에 아주 얇은 치즈가 <그림 1>과 같이 표시되어 있다. 단, N 은 세로 격자의 수이고, M 은 가로 격자의 수이다. 이 치즈는 냉동 보관을 해야만 하는데 실내온도에 내어놓으면 공기와 접촉하여 천천히 녹는다. 그런데 이러한 모눈종이 모양의 치즈에서 각 치즈 격자(작 은 정사각형 모양)의 4변 중에서 적어도 2변 이상이 실내온도의 공기와 접촉한 것은 정확히 한시간만에 녹아 없어져 버린다. 따라서 아래 <그림 1> 모양과 같은 치즈(회색으로 표시된 부분)라면 C로 표시된 모든 치즈 격자는 한 시간 후에 사라진... www.acmicpc.net 이 문제는 구현에 대해서 고민을 해봐야하는 시뮬레이션 문제입니다. 1. Problem Analysis 구해야하는 것은 크기가 NxM인 모눈종이 위에 치즈가 올려져 있을 때 이 치즈가 모두 녹는데 걸리는 시간입니다. 이때, 치즈가 녹은 경우는 상하좌우 4방향 중 2개 이상이 실내 온도의 공기와 맞닿았을 때

[Algorithm] 퀵 정렬(Quick Sort) [내부링크]

퀵 정렬(Quick Sort)이란? 퀵 정렬은 정렬 알고리즘 중 하나로 일반적으로 O(nlogn)의 시간복잡도로 수행된다고 알려져 있습니다. 퀵 정렬은 분할 정복(Divide and Conquer) 방법을 기반으로 만들어진 정렬 알고리즘입니다. "퀵"이라는 이름은 시행될 경우 다른 로그선형시간 정렬 알고리즘 대비 빠르게 수행되기 때문에 붙은 이름입니다. 하지만, 최악의 경우에는 O(n2)의 시간복잡도가 필요해서 사용에 주의해야합니다. 원리 퀵 정렬은 분할 정복(divide and conquer) 방법을 기반으로 합니다. 알고리즘은 다음과 같은 단계로 진행됩니다. 피벗(Pivot) 선택: 배열에서 하나의 요소를 피벗으로 선택합니다. 파티션(Partitioning): 피벗을 기준으로 배열을 두 개의 부분 배열로 나눕니다. 피벗을 기준으로 작은 값은 왼쪽으로, 큰 값은 오른쪽으로 이동시킵니다. 재귀적인 정렬: 각 부분 배열에 대해 재귀적으로 퀵 정렬을 수행합니다. 결합(Combine):

백준5639: 이진 검색 트리 [내부링크]

5639번: 이진 검색 트리 문제 이진 검색 트리는 다음과 같은 세 가지 조건을 만족하는 이진 트리이다. 노드의 왼쪽 서브트리에 있는 모든 노드의 키는 노드의 키보다 작다. 노드의 오른쪽 서브트리에 있는 모든 노드의 키는 노드의 키보다 크다. 왼쪽, 오른쪽 서브트리도 이진 검색 트리이다. 전위 순회 (루트-왼쪽-오른쪽)은 루트를 방문하고, 왼쪽 서브트리, 오른쪽 서브 트리를 순서대로 방문하면서 노드의 키를 출력한다. 후위 순회 (왼쪽-오른쪽-루트)는 왼쪽 서브트리, 오른쪽 서브트리, 루트 노드 순서대로 키를 출력한다. 예를 들어, 위의 이진 검색 트리의 전위 ... www.acmicpc.net 이 문제는 이진 검색 트리에서 재귀적인 규칙을 찾아내야하는 문제입니다. 또한 배열의 indexing을 주의해야하는 문제입니다. 1. Problem Analysis 구해야하는 것은 주어진 이진 검색 트리의 전위 순회 결과를 후위 순회 결과로 변경한 결과입니다. 이 문제의 제한조건은 다음과 같습니

백준1753: 최단경로 [내부링크]

1753번: 최단경로 1753번 제출 맞힌 사람 숏코딩 재채점 결과 채점 현황 강의 질문 게시판 최단경로 시간 제한 메모리 제한 제출 정답 맞힌 사람 정답 비율 1 초 256 MB 196682 58999 30132 25.418% 문제 방향그래프가 주어지면 주어진 시작점에서 다른 모든 정점으로의 최단 경로를 구하는 프로그램을 작성하시오. 단, 모든 간선의 가중치는 10 이하의 자연수이다. 입력 첫째 줄에 정점의 개수 V와 간선의 개수 E가 주어진다. (1 ≤ V ≤ 20,000, 1 ≤ E ≤ 300,000) 모든 정점에는 1부터 V까지 번호가 매겨져 있... www.acmicpc.net 이 문제는 대표적인 가중 그래프에서 최단 거리를 구하는 문제입니다. 1. Problem Analysis 구해야하는 것은 방향 가중 그래프 G=(V,E)에 대해 주어진 시작점에서 다른 모든 정점으로의 최단 경로입니다. 이 문제의 제한조건은 다음과 같습니다. 정점의 개수는 20,000 이하의 자연수이다.

백준1865: 웜홀 [내부링크]

1865번: 웜홀 1865번 제출 맞힌 사람 숏코딩 재채점 결과 채점 현황 강의 질문 게시판 웜홀 다국어 시간 제한 메모리 제한 제출 정답 맞힌 사람 정답 비율 2 초 128 MB 49438 11607 7221 21.524% 문제 때는 2020년, 백준이는 월드나라의 한 국민이다. 월드나라에는 N개의 지점이 있고 N개의 지점 사이에는 M개의 도로와 W개의 웜홀이 있다. (단 도로는 방향이 없으며 웜홀은 방향이 있다.) 웜홀은 시작 위치에서 도착 위치로 가는 하나의 경로인데, 특이하게도 도착을 하게 되면 시작을 하였을 때보다 시간이 뒤로 가게 된다. ... www.acmicpc.net 이 문제는 가중치가 음수일 수 있는 그래프의 탐색 문제입니다. 1. Problem Analysis 여기서 구해야하는 것은 n개의 지점과 m개의 도로, 그리고 w개의 웜홀을 갖고 있는 국가에서 여행을 할 때 시간이 줄어들면서 출발 지점으로 돌아오는 것이 가능한지를 확인하는 문제입니다. 이 문제의 제한조건은

[Algorithm] 분할 정복(Divide and Conquer) [내부링크]

분할 정복(Divide and Conquer)이란? 분할 정복은 복잡한 문제를 작은 부분 문제로 나누어 해결하는 알고리즘 디자인 패러다임 중 하나입니다. 이 방법은 큰 문제를 해결하는 것을 작은 부분 문제들로 나누어 해결하고, 그 결과들을 다시 합쳐서 큰 문제의 해를 얻는 방식으로 작동합니다. 일반적으로 재귀를 이용해 연산의 크기를 줄여 그 연산의 단위를 점차 줄여가는 방식으로 구현됩니다. 분할(Divide): 주어진 문제를 작은 부분으로 나눕니다. 정복(Conquer): 각각의 작은 부분 문제를 재귀적으로 해결합니다. 조합(Combine): 작은 부분 문제들의 해를 합쳐 원래 문제의 해를 얻습니다. 이러한 단계를 통해 분할 정복은 주어진 문제를 단순화하고, 작은 문제를 해결함으로써 전체 문제를 해결하는 데 기여합니다. 분할 정복 알고리즘의 시간 복잡도는 주로 부분 문제의 개수와 각 부분 문제의 크기에 따라 결정됩니다. 일반적으로 많은 경우에 분할 정복은 효율적인 알고리즘으로 알려져

백준1916: 최소비용 구하기 [내부링크]

1916번: 최소비용 구하기 1916번 제출 맞힌 사람 숏코딩 재채점 결과 채점 현황 강의 질문 게시판 최소비용 구하기 시간 제한 메모리 제한 제출 정답 맞힌 사람 정답 비율 0.5 초 128 MB 89210 28927 19046 32.391% 문제 N개의 도시가 있다. 그리고 한 도시에서 출발하여 다른 도시에 도착하는 M개의 버스가 있다. 우리는 A번째 도시에서 B번째 도시까지 가는데 드는 버스 비용을 최소화 시키려고 한다. A번째 도시에서 B번째 도시까지 가는데 드는 최소비용을 출력하여라. 도시의 번호는 1부터 N까지이다. 입력 첫째 줄에 도시의 개수 N(... www.acmicpc.net 이 문제는 대표적인 가중 그래프의 탐색 문제입니다. 1. Problem Analysis 구해야하는 것은 N개의 도시와 M개의 버스가 있을 때, A도시에서 B도시로 가는 최단 비용입니다. 이 문제의 제한조건은 다음과 같습니다. 도시의 개수 N은 1,000 이하의 자연수이다. 버스의 개수 M은 1

백준1918: 후위 표기식 [내부링크]

1918번: 후위 표기식 문제 수식은 일반적으로 3가지 표기법으로 표현할 수 있다. 연산자가 피연산자 가운데 위치하는 중위 표기법(일반적으로 우리가 쓰는 방법이다), 연산자가 피연산자 앞에 위치하는 전위 표기법(prefix notation), 연산자가 피연산자 뒤에 위치하는 후위 표기법(postfix notation)이 그것이다. 예를 들어 중위 표기법으로 표현된 a+b 는 전위 표기법으로는 +ab 이고, 후위 표기법으로는 ab+ 가 된다. 이 문제에서 우리가 다룰 표기법은 후위 표기법이다. 후위 표기법은 위에서 말한 법과 같이 연산자가 피연산자 뒤에 위치... www.acmicpc.net 이 문제는 스택을 이용해서 풀어야하는 다소 난이도 있는 문제입니다. 중위 표기식을 후위 표기식으로 바꾸는 규칙을 찾느라 다소 고생한 문제이기도 합니다. 1. Problem Analysis 구해야하는 것은 주어진 중위 표기식을 후위 표기식으로 변환하는 알고리즘입니다. 이 문제의 제한조건은 다음과 같

백준1932: 정수 삼각형 [내부링크]

1932번: 정수 삼각형 1932번 제출 맞힌 사람 숏코딩 재채점 결과 채점 현황 강의 질문 게시판 정수 삼각형 다국어 시간 제한 메모리 제한 제출 정답 맞힌 사람 정답 비율 2 초 128 MB 91019 53106 40137 59.645% 문제 7 3 8 8 1 0 2 7 4 4 4 5 2 6 5 위 그림은 크기가 5인 정수 삼각형의 한 모습이다. 맨 위층 7부터 시작해서 아래에 있는 수 중 하나를 선택하여 아래층으로 내려올 때, 이제까지 선택된 수의 합이 최대가 되는 경로를 구하는 프로그램을 작성... www.acmicpc.net 이 문제는 간단한 다이나믹 프로그래밍 문제입니다. 1. Problem Analysis 구해야하는 것은 크기가 n인 정수 삼각형에서 맨 위층부터 시작해서 아래에 있는 수 중 하나를 선택하여 아래층으로 내려올 때, 이제까지 선택된 수의 합이 최대가 되는 경우입니다. 이 문제의 제한조건은 다음과 같습니다. 삼각형의 크기 n은 500이하의 자연수이다. 삼각형을

백준1967: 트리의 지름 [내부링크]

1967번: 트리의 지름 문제 트리(tree)는 사이클이 없는 무방향 그래프이다. 트리에서는 어떤 두 노드를 선택해도 둘 사이에 경로가 항상 하나만 존재하게 된다. 트리에서 어떤 두 노드를 선택해서 양쪽으로 쫙 당길 때, 가장 길게 늘어나는 경우가 있을 것이다. 이럴 때 트리의 모든 노드들은 이 두 노드를 지름의 끝 점으로 하는 원 안에 들어가게 된다. 이런 두 노드 사이의 경로의 길이를 트리의 지름이라고 한다. 정확히 정의하자면 트리에 존재하는 모든 경로들 중에서 가장 긴 것의 길이를 말한다. 입력으로 루트가 있는 트리를 가중치가 있는 간선들로 줄 때, ... www.acmicpc.net 이 문제는 백준1167 트리의 지름과 입력의 형식이 다르지만 동일한 내용을 묻고 있는 문제입니다. 정확한 내용은 다음 포스팅을 확인해보시기 바랍니다. 백준1167: 트리의 지름 이 문제는 대표적인 가중 그래프 탐색 문제입니다. 1. Problem Analysis 이 문제는 노드의 개수가 v개인 .

백준1167: 트리의 지름 [내부링크]

1167번: 트리의 지름 1167번 제출 맞힌 사람 숏코딩 재채점 결과 채점 현황 강의 질문 게시판 트리의 지름 시간 제한 메모리 제한 제출 정답 맞힌 사람 정답 비율 2 초 256 MB 52602 19232 13847 34.016% 문제 트리의 지름이란, 트리에서 임의의 두 점 사이의 거리 중 가장 긴 것을 말한다. 트리의 지름을 구하는 프로그램을 작성하시오. 입력 트리가 입력으로 주어진다. 먼저 첫 번째 줄에서는 트리의 정점의 개수 V가 주어지고 (2 ≤ V ≤ 100,000)둘째 줄부터 V개의 줄에 걸쳐 간선의 정보가 다음과 같이 주어진다. 정점 번호... www.acmicpc.net 이 문제는 대표적인 가중 그래프 탐색 문제입니다. 1. Problem Analysis 이 문제는 노드의 개수가 v개인 양방향 가중 트리에서 트리의 지름을 구하는 문제입니다. 이때 트리의 지름은 "임의의 두 점 사이의 거리 중 가장 긴 것"을 의미합니다. 이 문제의 제한조건은 다음과 같습니다. 노드

[Algorithm] 버블 정렬(Bubble Sort) [내부링크]

버블 정렬(Bubble Sort)이란? 버블 정렬은 정렬 알고리즘의 일종으로 O(n2)의 시간복잡도로 수행가능한 알고리즘으로 알려져 있습니다. 시간복잡도 상으로는 느리지만, 구현이 간단하다는 특징이 있습니다. 개발에 입문해서 정렬을 생각할 때 가장 먼저 접하는 정렬 알고리즘이기도 합니다. '버블'이라는 이름은 원소가 거품이 수면 위로 올라오는 것과 같다고 해서 붙여졌습니다. 원리 버블 정렬의 원리는 서로 인접해있는 두 원소를 비교하면서 정렬되어 있다면 서로 위치를 바꾸고(swap), 아니라면 넘어가는(skip) 알고리즘입니다. 리스트의 첫 번째 원소부터 마지막 원소까지 순차적으로 비교합니다. 인접한 두 원소를 비교하여 순서가 잘못되어 있다면 위치를 교환합니다. 리스트의 끝까지 이 과정을 반복합니다. 한 번의 순회가 끝나면 가장 큰 원소가 마지막 자리로 정렬됩니다. 다시 처음부터 마지막 바로 앞까지 위의 과정을 반복합니다. 정렬이 완료될 때까지 이를 반복합니다. 위 과정을 마치면 정렬

백준1238: 파티 [내부링크]

1238번: 파티 1238번 제출 맞힌 사람 숏코딩 재채점 결과 채점 현황 질문 게시판 파티 다국어 시간 제한 메모리 제한 제출 정답 맞힌 사람 정답 비율 1 초 128 MB 45392 23060 15470 48.459% 문제 N개의 숫자로 구분된 각각의 마을에 한 명의 학생이 살고 있다. 어느 날 이 N명의 학생이 X (1 ≤ X ≤ N)번 마을에 모여서 파티를 벌이기로 했다. 이 마을 사이에는 총 M개의 단방향 도로들이 있고 i번째 길을 지나는데 T i (1 ≤ T i ≤ 100)의 시간을 소비한다. 각각의 학생들은 파티에 참석하기 위해 걸어가서... www.acmicpc.net 이 문제는 생각을 한 번 뒤집어야하는 가중 그래프에서의 탐색 문제입니다. 1. Problem Analysis 이 문제는 n개의 마을 중 x번째 마을에서 파티가 열릴 때 각 마을에서 x마을에 왔다가 다시 본인이 살던 마을로 돌아가는 최단 경로들 중 최댓값을 구하는 문제입니다. 이때 마을들을 잇는 도로는 총

[Algorithm] 선택 정렬(Selection Sort) [내부링크]

선택 정렬(Selection Sort)이란? 선택 정렬은 정렬 알고리즘 중 하나로 O(n2)의 시간복잡도로 수행되는 알고리즘으로 널리 알려져 있습니다. 선택 정렬은 시간복잡도상으로는 빠르다고 할 수는 없지만, 매우 단순한 아이디어를 이용해 이해가 쉽고 구현이 매우 간결하다는 장점이 있습니다. '선택'이라는 이름은 주어진 데이터에서 원소를 선택하는 방식으로 정렬하기 때문에 붙은 이름입니다. 원리 선택 정렬은 주어진 배열에서 가장 작은 원소를 선택하여 해당 위치로 이동시키는 과정을 반복하여 정렬을 수행하는 알고리즘입니다. 각 단계에서 최솟값을 찾아서 맨 앞의 원소와 교환하는 방식으로 동작합니다. 리스트에서 최솟값을 찾습니다. 최솟값을 현재 검사 중인 위치의 값과 교환합니다. 다음 위치로 이동하여 위의 과정을 반복합니다. 리스트의 끝까지 이를 반복하여 정렬을 완료합니다. // C++ Style Code void selection_sort(int* arr, const int n){ int

백준1504: 특정한 최단 경로 [내부링크]

1504번: 특정한 최단 경로 1504번 제출 맞힌 사람 숏코딩 재채점 결과 채점 현황 강의 질문 게시판 특정한 최단 경로 시간 제한 메모리 제한 제출 정답 맞힌 사람 정답 비율 1 초 256 MB 82423 21974 14891 24.995% 문제 방향성이 없는 그래프가 주어진다. 세준이는 1번 정점에서 N번 정점으로 최단 거리로 이동하려고 한다. 또한 세준이는 두 가지 조건을 만족하면서 이동하는 특정한 최단 경로를 구하고 싶은데, 그것은 바로 임의로 주어진 두 정점은 반드시 통과해야 한다는 것이다. 세준이는 한번 이동했던 정점은 물론, 한번 이동했던 간선도 ... www.acmicpc.net 이 문제는 가중 그래프 탐색 알고리즘을 정확히 이해하고 있는지를 확인하는 문제입니다. 1. Problem Analysis 문제에서 구하는 것은 양방향 가중 그래프 G=(n,e)에 대해, 1번 정점에서 n번 정점까지의 경로 중 서로 다른 두 정점 v1과 v2을 지나는 최단 거리를 구하는 문제입

[Algorithm] 삽입 정렬(Insertion Sort) [내부링크]

삽입 정렬(Insertion Sort)이란? 삽입 정렬은 정렬 알고리즘 중 하나로써 O(n2)의 시간복잡도로 수행되는 정렬 알고리즘으로 널리 알려져 있습니다. 삽입 정렬은 간단하면서도 직관적인 정렬 알고리즘으로, 특히 작은 규모의 데이터에 대해 효과적으로 동작합니다. '삽입'이라는 이름은 주어진 데이터를 순차적으로 적절한 위치에 삽입하기에 붙은 이름입니다. 원리 삽입 정렬은 주어진 리스트를 정렬 영역과 비정렬 영역으로 구분해 비정렬 영역에 있는 원소를 정렬 영역 내 적절한 위치에 순차적으로 삽입하는 방식으로 동작합니다. 리스트의 두 번째 원소부터 시작하여 현재 원소를 이미 정렬 영역과 비교합니다. 적절한 위치를 찾을 때까지 현재 원소를 계속해서 앞으로 이동시킵니다. 적절한 위치를 찾으면 현재 원소를 해당 위치에 삽입합니다. 리스트의 끝까지 위의 과정을 반복하여 정렬을 완료합니다. // c++ style code void insertionSort(int *arr, const int n

백준1629: 곱셈 [내부링크]

1629번: 곱셈 1629번 제출 맞힌 사람 숏코딩 재채점 결과 채점 현황 강의 질문 게시판 곱셈 시간 제한 메모리 제한 제출 정답 맞힌 사람 정답 비율 0.5 초 (추가 시간 없음) 128 MB 117102 32831 23941 27.010% 문제 자연수 A를 B번 곱한 수를 알고 싶다. 단 구하려는 수가 매우 커질 수 있으므로 이를 C로 나눈 나머지를 구하는 프로그램을 작성하시오. 입력 첫째 줄에 A, B, C가 빈 칸을 사이에 두고 순서대로 주어진다. A, B, C는 모두 2,147,483,647 이하의 자연수이다. 출력 첫째 줄에 A를 B번 ... www.acmicpc.net 이 문제는 분할 정복을 이용한 거듭제곱을 배울 수 있는 중요한 문제입니다. 1. Problem Analysis 이 문제는 자연수 a를 b번 곱한 수를 c로 나눈 나머지를 구해야합니다. 이 문제의 제한조건은 다음과 같습니다. a, b, c는 모두 2,147,483,647 이하의 자연수이다. 시간제한 0.5

백준18870: 좌표 압축 [내부링크]

18870번: 좌표 압축 18870번 제출 맞힌 사람 숏코딩 재채점 결과 채점 현황 질문 게시판 좌표 압축 시간 제한 메모리 제한 제출 정답 맞힌 사람 정답 비율 2 초 512 MB 86086 36314 27497 39.634% 문제 수직선 위에 N개의 좌표 X 1 , X 2 , ..., X N 이 있다. 이 좌표에 좌표 압축을 적용하려고 한다. X i 를 좌표 압축한 결과 X' i 의 값은 X i > X j 를 만족하는 서로 다른 좌표 X j 의 개수와 같아야 한다. X 1 , X 2 , ..., X N 에 좌표 압축을 적용한 결과 X' 1 , X' 2 ... www.acmicpc.net 이 문제는 대표적인 정렬과 탐색 문제입니다. 1. Problem Analysis 이 문제는 수직선 위에 N개의 좌표 X1, X2, ..., XN에 대해 좌표압축을 한 결과를 구하는 문제입니다. 이때 좌표압축은 수직선상 좌표 Xi를 Xi > Xj를 만족하는 서로 다른 좌표 Xj의 개수 X'i로 바꾸

백준20529: 가장 가까운 세 사람의 심리적 거리 [내부링크]

20529번: 가장 가까운 세 사람의 심리적 거리 문제 여러분은 요즘 유행하는 심리검사인 MBTI에 대해 들어보았는가? MBTI(Myers-Briggs Type Indicator)는 C.G.Jung의 심리유형론을 근거로 하여 Katharine Cook Briggs와 Isabel Briggs Myers가 보다 쉽고 일상생활에 유용하게 활용할 수 있도록 고안한 자기보고식 성격유형지표이다. (출처: 위키백과) MBTI는 아래와 같이 네 가지 척도로 사람들의 성격을 구분한다. 외향(E) / 내향(I) 감각(S) / 직관(N) 사고(T) / 감정(F) 판단(J) / 인식(P) 각 척도마다 ... www.acmicpc.net 이 문제는 대표적인 비둘기집 원리를 이용한 최적화 문제입니다. 1. Problem Analysis MBTI 성격 유형 검사 결과를 이용해 두 사람 사이의 심리적인 거리는 각 사람의 MBTI 유형에서 서로 다른 분류에 속하는 척도의 수로 정의됩니다. 이때 n명의 학생들의 M

백준21736: 헌내기는 친구가 필요해 [내부링크]

21736번: 헌내기는 친구가 필요해 문제 2020년에 입학한 헌내기 도연이가 있다. 도연이는 비대면 수업 때문에 학교에 가지 못해 학교에 아는 친구가 없었다. 드디어 대면 수업을 하게 된 도연이는 어서 캠퍼스 내의 사람들과 친해지고 싶다. 도연이가 다니는 대학의 캠퍼스는 $N \times M$ 크기이며 캠퍼스에서 이동하는 방법은 벽이 아닌 상하좌우로 이동하는 것이다. 예를 들어, 도연이가 ($x$, $y$)에 있다면 이동할 수 있는 곳은 ($x+1$, $y$), ($x$, $y+1$), ($x-1$, $y$), ($x$, $y-1$)이다. 단, 캠퍼스의 밖으로 이동... www.acmicpc.net 이 문제는 대표적인 그래프탐색 문제입니다. 1. Problem Analysis 이 문제는 크기가 (n, m)인 캠퍼스를 탐색할 때 만날 수 있는 사람 수를 구하는 문제입니다. 이 문제의 제한조건은 다음과 같습니다. 캠퍼스의 크기 n, m은 각각 600이하의 자연수이다. 캠퍼스 지도에는

[Algorithm] 정렬(Sort) [내부링크]

정렬(Sort)이란? 정렬이란 임의의 수열 <a1,a2, ..., an>을 a'1≤a'2≤ ... ≤a'n을 만족하는 수열 <a'1, a'2, ..., a'n>로 변환하는 과정을 의미합니다. 컴퓨터 공학에서 정렬 알고리즘 하면 꼭 따라붙는 시각화 동영상이 있습니다. 한번 확인해보시는 것도 좋을 거 같습니다. 정렬 자세히 보기 정렬은 여러 가지 기준에 의해서 분류할 수 있습니다. 안정 정렬(Stable Sort)과 불안정 정렬(Unstable Sort) 안정 정렬은 중복된 값을 입력 순서와 동일하게 정렬입니다. 불안정 정렬은 중복된 값을 입력 순서와 동일하게 정렬하지 않는 정렬입니다. 당연하게도 안정 정렬이 불안정 정렬보다 유용하게 사용될 것을 예상할 수 있을 겁니다. O(n2) 시간복잡도와 O(nlogn) 시간복잡도 일반적으로 다뤄지는 정렬 알고리즘은 O(n2)의 시간복잡도가 필요한 것과 O(nlogn)의 시간복잡도가 필요한 것으로 나눠집니다. O(n2) 시간복잡도 정렬에 해당하는

백준1043: 거짓말 [내부링크]

1043번: 거짓말 문제 지민이는 파티에 가서 이야기 하는 것을 좋아한다. 파티에 갈 때마다, 지민이는 지민이가 가장 좋아하는 이야기를 한다. 지민이는 그 이야기를 말할 때, 있는 그대로 진실로 말하거나 엄청나게 과장해서 말한다. 당연히 과장해서 이야기하는 것이 훨씬 더 재미있기 때문에, 되도록이면 과장해서 이야기하려고 한다. 하지만, 지민이는 거짓말쟁이로 알려지기는 싫어한다. 문제는 몇몇 사람들은 그 이야기의 진실을 안다는 것이다. 따라서 이런 사람들이 파티에 왔을 때는, 지민이는 진실을 이야기할 수 밖에 없다. 당연히, 어떤 사람이 어떤 파티에서는... www.acmicpc.net 이 문제는 대표적인 유니온-파인드 알고리즘, 분리 집합(DIsjoint Set) 문제입니다. 1. Problem Analysis n명의 사람들이 중복해서 m개의 파티에 참여할 수 있다. 그중 몇 명은 어떠한 일의 진실을 알고 있을 때, 거짓말쟁이로 알려지지 않으면서, 그 일의 과장된 이야기를 할 수 있

백준1149: RGB 거리 [내부링크]

1149번: RGB거리 문제 RGB거리에는 집이 N개 있다. 거리는 선분으로 나타낼 수 있고, 1번 집부터 N번 집이 순서대로 있다. 집은 빨강, 초록, 파랑 중 하나의 색으로 칠해야 한다. 각각의 집을 빨강, 초록, 파랑으로 칠하는 비용이 주어졌을 때, 아래 규칙을 만족하면서 모든 집을 칠하는 비용의 최솟값을 구해보자. 1번 집의 색은 2번 집의 색과 같지 않아야 한다. N번 집의 색은 N-1번 집의 색과 같지 않아야 한다. i(2 ≤ i ≤ N-1)번 집의 색은 i-1번, i+1번 집의 색과 같지 않아야 한다. 입력 첫째 줄에 집의 수 N(2 ≤ N ... www.acmicpc.net 이 문제는 대표적인 다이나믹 프로그래밍 문제입니다. 1. Problem Analysis 이 문제는 n개의 집을 R, G, B 중 하나의 색칠하되, 바로 옆집하고는 다른 색으로 칠할 때 모든 집을 칠하는 최소 비용을 구하는 문제입니다. 이 문제의 제한조건은 다음과 같습니다. n은 1,000이하의 자연

백준11724: 연결 요소의 개수 [내부링크]

11724번: 연결 요소의 개수 11724번 제출 맞힌 사람 숏코딩 재채점 결과 채점 현황 강의 질문 게시판 연결 요소의 개수 시간 제한 메모리 제한 제출 정답 맞힌 사람 정답 비율 3 초 512 MB 121938 55002 36146 42.100% 문제 방향 없는 그래프가 주어졌을 때, 연결 요소 (Connected Component)의 개수를 구하는 프로그램을 작성하시오. 입력 첫째 줄에 정점의 개수 N과 간선의 개수 M이 주어진다. (1 ≤ N ≤ 1,000, 0 ≤ M ≤ N×(N-1)/2) 둘째 줄부터 M개의 줄에 간선의 양 끝점 u와 v가 주어진다. (... www.acmicpc.net 이 문제는 대표적인 그래프 탐색 문제입니다. 1. Problem Analysis 이 문제에서 구해야 하는 것은 방향 없는 그래프에서 연결 요소(Connected Component)의 개수를 구하는 문제입니다. 이 문제의 제한 조건은 다음과 같습니다. 정점의 개수 n은 1,000이하의 자연수

백준11726: 2xn 타일링 [내부링크]

11726번: 2×n 타일링 11726번 제출 맞힌 사람 숏코딩 재채점 결과 채점 현황 강의 질문 게시판 2×n 타일링 시간 제한 메모리 제한 제출 정답 맞힌 사람 정답 비율 1 초 256 MB 164135 63404 47042 36.580% 문제 2×n 크기의 직사각형을 1×2, 2×1 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오. 아래 그림은 2×5 크기의 직사각형을 채운 한 가지 방법의 예이다. 입력 첫째 줄에 n이 주어진다. (1 ≤ n ≤ 1,000) 출력 첫째 줄에 2×n 크기의 직사각형을 채우는 방법의 수를 10,007로 나눈 나머지를 ... www.acmicpc.net 이 문제는 대표적인 다이나믹 프로그래밍 문제입니다. 1. Problem Analysis 이 문제는 2×n 크기의 직사각형을 1×2, 2×1 타일로 채우는 방법의 수를 구하는 문제입니다. 이 문제의 제한조건은 다음과 같습니다. n은 1,000이하의 자연수이다. 구한 방법의 수를 10,007로 나

백준11727: 2xn 타일링 2 [내부링크]

11727번: 2×n 타일링 2 11727번 제출 맞힌 사람 숏코딩 재채점 결과 채점 현황 강의 질문 게시판 2×n 타일링 2 시간 제한 메모리 제한 제출 정답 맞힌 사람 정답 비율 1 초 256 MB 72012 42784 34437 58.839% 문제 2×n 직사각형을 1×2, 2×1과 2×2 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오. 아래 그림은 2×17 직사각형을 채운 한가지 예이다. 입력 첫째 줄에 n이 주어진다. (1 ≤ n ≤ 1,000) 출력 첫째 줄에 2×n 크기의 직사각형을 채우는 방법의 수를 10,007로 나눈 나머지를 출력한다. ... www.acmicpc.net 이 문제는 대표적인 다이나믹 프로그래밍 문제입니다. 추가적으로 백준 11726: 2xn 타일링 문제의 발전 문제입니다. 관련 포스팅을 먼저 읽고 오시는 것을 추천드립니다. 백준11726: 2xn 타일링 이 문제는 대표적인 다이나믹 프로그래밍 문제입니다. 1. Problem Analysis

백준14500: 테트로미노 [내부링크]

14500번: 테트로미노 문제 폴리오미노란 크기가 1×1인 정사각형을 여러 개 이어서 붙인 도형이며, 다음과 같은 조건을 만족해야 한다. 정사각형은 서로 겹치면 안 된다. 도형은 모두 연결되어 있어야 한다. 정사각형의 변끼리 연결되어 있어야 한다. 즉, 꼭짓점과 꼭짓점만 맞닿아 있으면 안 된다. 정사각형 4개를 이어 붙인 폴리오미노는 테트로미노라고 하며, 다음과 같은 5가지가 있다. 아름이는 크기가 N×M인 종이 위에 테트로미노 하나를 놓으려고 한다. 종이는 1×1 크기의 칸으로 나누어져 있으며, 각각의 칸에는 정수가 하나 쓰여 있다. 테트로미노 하나를 적... www.acmicpc.net 이 문제는 약간 난이도 있는 브루트포스 알고리즘 문제입니다. 1. Problem Analysis 이 문제는 각 칸에 숫자가 적혀있는 크기가 nxm인 종이 위에 테트로미노를 올려서 테트로미노가 올려진 칸들에 적힌 수의 합이 최대가 되는 경우를 구하는 문제입니다. 이 문제의 제한조건은 다음과 같습니다

백준14940: 쉬운 최단거리 [내부링크]

14940번: 쉬운 최단거리 14940번 제출 맞힌 사람 숏코딩 재채점 결과 채점 현황 질문 게시판 쉬운 최단거리 시간 제한 메모리 제한 제출 정답 맞힌 사람 정답 비율 1 초 128 MB 21480 8543 6953 37.304% 문제 지도가 주어지면 모든 지점에 대해서 목표지점까지의 거리를 구하여라. 문제를 쉽게 만들기 위해 오직 가로와 세로로만 움직일 수 있다고 하자. 입력 지도의 크기 n과 m이 주어진다. n은 세로의 크기, m은 가로의 크기다.(2 ≤ n ≤ 1000, 2 ≤ m ≤ 1000) 다음 n개의 줄에 m개의 숫자가 주어진다. 0은 갈 수 없... www.acmicpc.net 이 문제는 대표적인 그래프탐색 문제입니다. 1. Problem Analysis 이 문제는 크기가 (n, m)인 지도에서 가로나 세로로만 이동할 수 있을 때 각 지점으로부터 목표지점으로까지의 최단거리를 구하는 문제입니다. 이 문제의 제한조건은 다음과 같습니다. 지도의 크기 n, m 은 [2, 1

백준16928: 뱀과 사다리 게임 [내부링크]

16928번: 뱀과 사다리 게임 문제 뱀과 사다리 게임 을 즐겨 하는 큐브러버는 어느 날 궁금한 점이 생겼다. 주사위를 조작해 내가 원하는 수가 나오게 만들 수 있다면, 최소 몇 번만에 도착점에 도착할 수 있을까? 게임은 정육면체 주사위를 사용하며, 주사위의 각 면에는 1부터 6까지 수가 하나씩 적혀있다. 게임은 크기가 10×10이고, 총 100개의 칸으로 나누어져 있는 보드판에서 진행된다. 보드판에는 1부터 100까지 수가 하나씩 순서대로 적혀져 있다. 플레이어는 주사위를 굴려 나온 수만큼 이동해야 한다. 예를 들어, 플레이어가 i번 칸에 있고, 주사위를 굴려 ... www.acmicpc.net 이 문제는 다소 주의해야 하는 BFS 문제입니다. 1. Problem Analysis 이 문제는 크기가 (10, 10)인 보드판에서 뱀과 사다리 게임을 할 때 최소 몇 번 주사위를 던져야 목표지점에 도착할 수 있는지를 구하는 문제입니다. 이 문제의 제한조건은 다음과 같습니다. 사다리의 개수

[Algorithm] 재귀식(Recurrence) [내부링크]

재귀식(Recurrence)란? 재귀식은 작은 입력에 대한 값으로 함수를 설명하는 방정식 또는 부등식입니다. 조금 다른 관점에서 접근하면 수열의 점화식과 동일한 내용입니다. 형태로는 기저 사례와 재귀 사례로 구분해서 표현합니다. 재귀식과 실행 시간 재귀 알고리즘을 분석할 때 재귀식은 자연스럽게 나타납니다. 하단 Merge Sort는 분석할 때 자연스럽게 재귀식 형태로 호출하는 것을 볼 수 있습니다. 하지만 알고리즘을 분석할 때 이러한 재귀식은 어떻게 해야할지 난감하다는 문제가 있습니다. 재귀식과 점근 성능 분석 결과 예시 몇몇 대표적인 재귀식과 해당 재귀식의 점근 성능 분석 결과가 있습니다. 재귀식의 점근 성능 분석 위와 같은 재귀식의 점근 성능 분석은 다음과 같은 방법으로 할 수 있습니다. 치환법(Substitution Method) 재귀 트리법(Recursion Tree Method) 마스터 정리(Master Method) 마무리 재귀식은 컴퓨터공학에서 사용자가 무슨 의미인지 해

[Algorithm] 치환법(Substitutions Method) [내부링크]

치환법이란? 치환법은 주어진 재귀식의 한계점을 예상하고 그것이 유효하다는 것을 수학적 귀납법을 이용해서 증명하는 방법입니다. 치환법은 다음과 같은 구조로 진행됩니다. 치환법 예제 예제 1번 T(n)=T(n/2)+d 예제 2번 T(n)=T(n-1)+1 예제 3번 T(n)=2T(n/2)+n 예제 4번 T(n)=2T(n1/2)+logn 마무리 치환법을 이용하면 분석하려는 재귀식의 성능이 예상과 동일한지를 확인할 수 있습니다. 하지만, 그 예상치보다 더 성능이 좋을 수도 나쁠 수도 있기에 어려가지를 고려해야 합니다. 핵심은 이미 널리 알려진 재귀식 분석 결과를 이용해서 구하려는 재귀식을 변형해야 하는 것입니다.

백준17626: Four Squares [내부링크]

17626번: Four Squares 17626번 제출 맞힌 사람 숏코딩 재채점 결과 채점 현황 질문 게시판 Four Squares 다국어 시간 제한 메모리 제한 제출 정답 맞힌 사람 정답 비율 0.5 초 (추가 시간 없음) 512 MB 26610 11680 9154 43.854% 문제 라그랑주는 1770년에 모든 자연수는 넷 혹은 그 이하의 제곱수의 합으로 표현할 수 있다고 증명하였다. 어떤 자연수는 복수의 방법으로 표현된다. 예를 들면, 26은 5 2 과 1 2 의 합이다; 또한 4 2 + 3 2 + 1 2 으로 표현할 수도 있다. 역사적으로 암산의 명수들에게 공... www.acmicpc.net 이 문제는 대표적인 다이나믹 프로그래밍 문제이자 브루트포스 알고리즘 문제입니다. 1. Problem Analysis 이 문제는 자연수 n에 대해 합이 n과 같게 되는 제곱수들의 최소 개수를 구하는 문제입니다. 이 문제의 제한조건은 다음과 같습니다. 모든 자연수는 4개 이하의 제곱수의 합

[Algorithm] 재귀 트리법(Recursion Tree Method) [내부링크]

재귀 트리법(Recursion Tree Method)이란? 재귀 트리법은 알고리즘에서 재귀적인 호출이 일어나는 과정을 트리 구조로 나타내는 방법입니다. 재귀 트리 변환법 재귀적 호출을 트리 구조로 나타냅니다. 각각의 노드는 하나의 호출을 나타내며, 간선은 호출 간의 관계를 나타냅니다. 재귀적인 호출이 일어나며 트리가 계속해서 생성됩니다. 각 레벨에서의 호출 수행이 어떻게 전개되는지를 확인합니다. 각 노드는 다양한 레벨의 재귀에서 발생하는 비용을 나타냅니다. 모든 레벨의 비용을 합칩니다. 재귀 트리법은 치환법에 사용할 검증할 해를 예측할 때 유용합니다. 재귀 트리법으로 나온 결과는 무조건적으로 신뢰하기는 어렵습니다. 재귀 트리법을 이용하면 알고리즘을 시각적으로 볼 수 있어 직관력을 증진하는데 유용합니다. 재귀 트리법 예제 T(n)=T(n/4)+T(n/2)+n2=ϴ(n2) 마무리 재귀 트리법은 재귀식을 분석하는 가장 직관적인 방법입니다. 다만 정확한 분석에는 적합하지 않으며 그림을 이용

백준11399: ATM [내부링크]

11399번: ATM 11399번 제출 맞힌 사람 숏코딩 재채점 결과 채점 현황 강의 질문 게시판 ATM 시간 제한 메모리 제한 제출 정답 맞힌 사람 정답 비율 1 초 256 MB 106259 72260 57609 68.397% 문제 인하은행에는 ATM이 1대밖에 없다. 지금 이 ATM앞에 N명의 사람들이 줄을 서있다. 사람은 1번부터 N번까지 번호가 매겨져 있으며, i번 사람이 돈을 인출하는데 걸리는 시간은 P i 분이다. 사람들이 줄을 서는 순서에 따라서, 돈을 인출하는데 필요한 시간의 합이 달라지게 된다. 예를 들어, 총 5명이 있고, P 1 = ... www.acmicpc.net 이 문제는 대표적인 그리디 알고리즘 문제입니다. 1. Problem Analysis 이 문제는 1번부터 n번까지 번호가 부여되어 있는 n명의 사람이 ATM에서 돈을 인출하는데 각각 Pi의 시간이 필요하다면, 이 사람들이 ATM 1대에서 모두 돈을 인출할 때 걸리는 시간의 합의 최소를 구하는 문제입니다

[Algorithm] 알고리즘의 개요 [내부링크]

알고리즘(Algorithm)이란? 알고리즘(Algorithm)은 컴퓨터 공학 및 정보과학 분야에서 핵심적인 개념 중 하나로, 어떠한 문제를 해결하기 위한 명확하고 체계적인 절차나 규칙의 집합입니다. 컴퓨터 프로그래밍에서 알고리즘은 입력을 받아 원하는 출력을 얻기 위한 과정을 단계적으로 명확하게 정의한 것으로 볼 수 있습니다. 추가적으로 자료구조와 알고리즘은 보통 세트를 이루기도 합니다. 특정 알고리즘들은 특정 자료구조들을 이해하고 있어야만 사용할 수 있는 경우가 있습니다. 알고리즘의 특징 모든 알고리즘은 다음 특징들을 만족시켜야 합니다. 입력: 알고리즘에는 0개 이상의 입력값들이 제공된다. 출력: 알고리즘에는 최소 1개 이상의 출력값들이 제공된다. 명확성: 알고리즘에서 각 과정은 명확하고 모호하지 않다. 유한성: 모든 경우에 대해 유한한 숫자의 과정을 마치고 알고리즘이 종료된다. 무한 루프와 같은 불확실한 동작을 방지하기 위해 필수적이다. 효과성: 알고리즘은 충분히 단순하고, 제한된

백준11403: 경로 찾기 [내부링크]

11403번: 경로 찾기 11403번 제출 맞힌 사람 숏코딩 재채점 결과 채점 현황 강의 질문 게시판 경로 찾기 시간 제한 메모리 제한 제출 정답 맞힌 사람 정답 비율 1 초 256 MB 46410 28473 21029 61.248% 문제 가중치 없는 방향 그래프 G가 주어졌을 때, 모든 정점 (i, j)에 대해서, i에서 j로 가는 길이가 양수인 경로가 있는지 없는지 구하는 프로그램을 작성하시오. 입력 첫째 줄에 정점의 개수 N (1 ≤ N ≤ 100)이 주어진다. 둘째 줄부터 N개 줄에는 그래프의 인접 행렬이 주어진다. i번째 줄의 j번째 숫자가 1인 ... www.acmicpc.net 이 문제는 대표적인 그래프 탐색 문제입니다. 1. Problem Analysis 정점의 개수가 n개인 무가중 방향 그래프가 인접행렬 형태로 주어졌을 때 모든 정점i로부터 정점j로 가는 경로가 있는지 구하는 문제입니다. 이 문제의 제한조건은 다음과 같습니다. 정점의 개수 n은 100이하의 자연수이다

백준11659: 구간 합 구하기 4 [내부링크]

11659번: 구간 합 구하기 4 11659번 제출 맞힌 사람 숏코딩 재채점 결과 채점 현황 강의 질문 게시판 구간 합 구하기 4 시간 제한 메모리 제한 제출 정답 맞힌 사람 정답 비율 1 초 256 MB 103012 42360 31538 39.008% 문제 수 N개가 주어졌을 때, i번째 수부터 j번째 수까지 합을 구하는 프로그램을 작성하시오. 입력 첫째 줄에 수의 개수 N과 합을 구해야 하는 횟수 M이 주어진다. 둘째 줄에는 N개의 수가 주어진다. 수는 1,000보다 작거나 같은 자연수이다. 셋째 줄부터 M개의 줄에는 합을 구해야 하는 구간 i와 j가 주어진다.... www.acmicpc.net 이 문제는 기본적인 누적합 문제입니다. 또한 이런 누적합 개념은 ps에서 종종 사용되는 개념으로 숙지가 필요합니다. 1. Problem Analysis 이 문제는 n개의 수가 차례대로 주어질 때, m개의 구간 (i, j)에 대해 i번째 수부터 j번째 수까지의 합을 구하는 문제입니다. 이

백준11723: 집합 [내부링크]

11723번: 집합 문제 비어있는 공집합 S가 주어졌을 때, 아래 연산을 수행하는 프로그램을 작성하시오. add x : S에 x를 추가한다. (1 ≤ x ≤ 20) S에 x가 이미 있는 경우에는 연산을 무시한다. remove x : S에서 x를 제거한다. (1 ≤ x ≤ 20) S에 x가 없는 경우에는 연산을 무시한다. check x : S에 x가 있으면 1을, 없으면 0을 출력한다. (1 ≤ x ≤ 20) toggle x : S에 x가 있으면 x를 제거하고, 없으면 x를 추가한다. (1 ≤ x ≤ 20) all : S를 {1, 2, ..., 20} ... www.acmicpc.net 이 문제는 대표적인 비트마스킹 문제입니다. 1. Problem Analysis M개의 집합 연산에 대해 수행한 각 결과를 문제 조건에 맞게 출력한다. 이 문제의 제한조건은 다음과 같습니다. 집합에 저장될 수 있는 원소는 20 이하의 자연수이다. 수행해야 하는 집합 연산의 수 M은 3,000,000 이하

백준9375: 패션왕 신해빈 [내부링크]

9375번: 패션왕 신해빈 9375번 제출 맞힌 사람 숏코딩 재채점 결과 채점 현황 질문 게시판 패션왕 신해빈 다국어 시간 제한 메모리 제한 제출 정답 맞힌 사람 정답 비율 1 초 128 MB 36947 20430 17243 55.107% 문제 해빈이는 패션에 매우 민감해서 한번 입었던 옷들의 조합을 절대 다시 입지 않는다. 예를 들어 오늘 해빈이가 안경, 코트, 상의, 신발을 입었다면, 다음날은 바지를 추가로 입거나 안경대신 렌즈를 착용하거나 해야한다. 해빈이가 가진 의상들이 주어졌을때 과연 해빈이는 알몸이 아닌 상태로 며칠동안 밖에 돌아다닐 수 있을까? ... www.acmicpc.net 이 문제는 간단한 수학 문제입니다. 1. Problem Analysis 이 문제는 매일 다른 스타일로 옷을 입을 때, 즉 중복되는 스타일로 입지 않을 때 최대 며칠 입을 수 있는지 구하는 문제입니다. 이 문제의 제한 조건은 다음과 같습니다. 의상의 수는 [0,30] 범위 내의 정수이다. 각 의상

백준9461: 파도반 수열 [내부링크]

9461번: 파도반 수열 9461번 제출 맞힌 사람 숏코딩 재채점 결과 채점 현황 질문 게시판 파도반 수열 다국어 시간 제한 메모리 제한 제출 정답 맞힌 사람 정답 비율 1 초 128 MB 97834 43695 35905 43.309% 문제 오른쪽 그림과 같이 삼각형이 나선 모양으로 놓여져 있다. 첫 삼각형은 정삼각형으로 변의 길이는 1이다. 그 다음에는 다음과 같은 과정으로 정삼각형을 계속 추가한다. 나선에서 가장 긴 변의 길이를 k라 했을 때, 그 변에 길이가 k인 정삼각형을 추가한다. 파도반 수열 P(N)은 나선에 있는 정삼각형의 변의 길이이다. P(... www.acmicpc.net 이 문제는 대표적인 다이나믹 프로그래밍 문제입니다. 1. Problem Analysis 파도반 수열은 길이가 1인 정삼각형으로부터 나선형으로 해당 나선에 가장 긴 길이를 갖는 정삼각형을 추가했을 때의 길이를 나타내는 수열입니다. 주어진 문제에서는 n번째 추가한 정삼각형의 한 변의 길이(P(n))를

백준10026: 적록색약 [내부링크]

10026번: 적록색약 10026번 제출 맞힌 사람 숏코딩 재채점 결과 채점 현황 강의 질문 게시판 적록색약 다국어 시간 제한 메모리 제한 제출 정답 맞힌 사람 정답 비율 1 초 128 MB 62052 35601 27065 56.329% 문제 적록색약은 빨간색과 초록색의 차이를 거의 느끼지 못한다. 따라서, 적록색약인 사람이 보는 그림은 아닌 사람이 보는 그림과는 좀 다를 수 있다. 크기가 N×N인 그리드의 각 칸에 R(빨강), G(초록), B(파랑) 중 하나를 색칠한 그림이 있다. 그림은 몇 개의 구역으로 나뉘어져 있는데, 구역은 같은 색으로 이루어져 ... www.acmicpc.net 이 문제는 대표적인 그래프 탐색 문제입니다. 1. Problem Analysis 이 문제는 NxN 크기의 각 위치에 'R, 'G', 'B' 3가지 색 중 하나로만 색칠되어 있는 그림을 적록색약이 아닌 사람이 봤을 때와 적록색약인 사람이 봤을 때 같은 색으로 나눠진 구역이 총 몇 개인지 각각 구하는

백준11047: 동전 0 [내부링크]

11047번: 동전 0 문제 준규가 가지고 있는 동전은 총 N종류이고, 각각의 동전을 매우 많이 가지고 있다. 동전을 적절히 사용해서 그 가치의 합을 K로 만들려고 한다. 이때 필요한 동전 개수의 최솟값을 구하는 프로그램을 작성하시오. 입력 첫째 줄에 N과 K가 주어진다. (1 ≤ N ≤ 10, 1 ≤ K ≤ 100,000,000) 둘째 줄부터 N개의 줄에 동전의 가치 A i 가 오름차순으로 주어진다. (1 ≤ A i ≤ 1,000,000, A 1 = 1, i ≥ 2인 경우에 A i 는 A i-1 의 배수) 출력 첫째 줄에 K원을 만드는데 필요한 동전 개... www.acmicpc.net 이 문제는 대표적인 그리디 알고리즘 문제입니다. 1. Problem Analysis 이 문제는 n종류의 동전을 이용해서 k원을 만들려고 할 때 최소 동전 개수를 구하는 문제입니다. 이 문제의 제한조건은 다음과 같습니다. n은 10 이하의 자연수이다. k는 100,000,000 이하의 자연수이다. 각

[Data Structure]이진 탐색 트리(Binary Search Tree, BST) [내부링크]

이진 탐색 트리(BST)란? 각 원소들이 중복되지 않는 key를 갖고 있고, 각 노드들에 대해 key(왼쪽 서브트리) < key(루트 노드) < key(오른쪽 서브트리)를 만족하는 이진 트리를 의미합니다. BST는 선형 자료구조에서 연산들이 O(n)의 시간복잡도로 수행되는 것이 매우 느리다고 판단되어 고안된 자료구조입니다. 이진 탐색 트리의 구현 BST는 기본적으로 이진 트리의 확장이므로 그 구조는 이진 트리와 동일합니다. typedef struct _BSTNode { Key key; struct _BSTNode *left_child; struct _BSTNode *right_child; } BSTNode; 이진 탐색 트리는 기본적으로 다음과 같은 연산들을 갖고 있습니다. 대부분 이진 트리가 갖고 있는 연산들의 변형입니다. BSTNode* createNode(Key key); // 새 노드를 생성한다. void destroyNode(BSTNode* node); // 노드를 삭제한다.

백준7576: 토마토 [내부링크]

7576번: 토마토 문제 철수의 토마토 농장에서는 토마토를 보관하는 큰 창고를 가지고 있다. 토마토는 아래의 그림과 같이 격자 모양 상자의 칸에 하나씩 넣어서 창고에 보관한다. 창고에 보관되는 토마토들 중에는 잘 익은 것도 있지만, 아직 익지 않은 토마토들도 있을 수 있다. 보관 후 하루가 지나면, 익은 토마토들의 인접한 곳에 있는 익지 않은 토마토들은 익은 토마토의 영향을 받아 익게 된다. 하나의 토마토의 인접한 곳은 왼쪽, 오른쪽, 앞, 뒤 네 방향에 있는 토마토를 의미한다. 대각선 방향에 있는 토마토들에게는 영향을 주지 못하며, 토마토가 혼자 저... www.acmicpc.net 이 문제는 백준 7569: 토마토와 구조적으로 동일하나 창고가 2차원인 문제입니다. 백준7569: 토마토 이 문제는 bfs를 잘 활용해야 하는 문제입니다. 2차원 정보에서 BFS를 이용해 문제를 해결하는 것에는 ... blog.naver.com 1. Problem Analysis 크기나 (M, N)인

백준7662: 이중 우선순위 큐 [내부링크]

7662번: 이중 우선순위 큐 문제 이중 우선순위 큐(dual priority queue)는 전형적인 우선순위 큐처럼 데이터를 삽입, 삭제할 수 있는 자료 구조이다. 전형적인 큐와의 차이점은 데이터를 삭제할 때 연산(operation) 명령에 따라 우선순위가 가장 높은 데이터 또는 가장 낮은 데이터 중 하나를 삭제하는 점이다. 이중 우선순위 큐를 위해선 두 가지 연산이 사용되는데, 하나는 데이터를 삽입하는 연산이고 다른 하나는 데이터를 삭제하는 연산이다. 데이터를 삭제하는 연산은 또 두 가지로 구분되는데 하나는 우선순위가 가장 높은 것을 삭제하기 위한 것이고 다... www.acmicpc.net 이 문제는 우선순위 큐에 대한 깊은 이해를 바탕으로 이중 우선순위 큐를 구현하는 문제입니다. 생각보다 고민할 부분이 많아서 문제 해결에 오랜 시간이 걸린 문제이기도 합니다. 1. Problem Analysis 우선순위 큐는 우선순위가 큰 값부터 dequeue하는 자료구조입니다. 반면, 이중

백준9019: DSLR [내부링크]

9019번: DSLR 문제 네 개의 명령어 D, S, L, R 을 이용하는 간단한 계산기가 있다. 이 계산기에는 레지스터가 하나 있는데, 이 레지스터에는 0 이상 10,000 미만의 십진수를 저장할 수 있다. 각 명령어는 이 레지스터에 저장된 n을 다음과 같이 변환한다. n의 네 자릿수를 d 1 , d 2 , d 3 , d 4 라고 하자(즉 n = ((d 1 × 10 + d 2 ) × 10 + d 3 ) × 10 + d 4 라고 하자) D: D 는 n을 두 배로 바꾼다. 결과 값이 9999 보다 큰 경우에는 10000 으로 나눈 나머지를 취한다. 그 결... www.acmicpc.net 이 문제는 대표적인 BFS 문제입니다. 1. Problem Analysis 이 문제는 숫자 A를 D, S, L, R 4가지 연산을 이용해서 숫자 B로 만들려고 할 때 필요한 최소 연산들의 나열을 구하는 문제입니다. 각각의 연산 DSLR은 다음과 같습니다. 연산 D는 n을 두 배로 바꾼다. 결과 값이

백준9095: 1, 2, 3 더하기 [내부링크]

9095번: 1, 2, 3 더하기 9095번 제출 맞힌 사람 숏코딩 재채점 결과 채점 현황 강의 질문 게시판 1, 2, 3 더하기 다국어 시간 제한 메모리 제한 제출 정답 맞힌 사람 정답 비율 1 초 (추가 시간 없음) 512 MB 114940 75799 52309 64.456% 문제 정수 4를 1, 2, 3의 합으로 나타내는 방법은 총 7가지가 있다. 합을 나타낼 때는 수를 1개 이상 사용해야 한다. 1+1+1+1 1+1+2 1+2+1 2+1+1 2+2 1+3 3+1 정수 n이 주어졌을 때, n을 1, 2, 3의 합으로 나타내는 방법의 수를 구하는 프로그램을 작성... www.acmicpc.net 이 문제는 대표적인 다이나믹 프로그래밍 문제입니다. 1. Problem Analysis 이 문제는 주어지는 자연수를 1, 2, 3의 순서가 있는 합으로 표현할 때 몇 가지 경우로 표현할 수 있는지를 구하는 문제입니다. 제한 조건은 다음과 같습니다. 주어지는 자연수 n은 10이하의 자연수이

백준6064: 카잉 달력 [내부링크]

6064번: 카잉 달력 6064번 제출 맞힌 사람 숏코딩 재채점 결과 채점 현황 강의 질문 게시판 카잉 달력 다국어 시간 제한 메모리 제한 제출 정답 맞힌 사람 정답 비율 1 초 256 MB 67166 17272 12909 26.506% 문제 최근에 ICPC 탐사대는 남아메리카의 잉카 제국이 놀라운 문명을 지닌 카잉 제국을 토대로 하여 세워졌다는 사실을 발견했다. 카잉 제국의 백성들은 특이한 달력을 사용한 것으로 알려져 있다. 그들은 M과 N보다 작거나 같은 두 개의 자연수 x, y를 가지고 각 년도를 <x:y>와 같은 형식으로 표현하였다. 그들은 이 세... www.acmicpc.net 이 문제는 나머지 연산에서 주의해야 하는 문제입니다. 1. Problem Analysis 이 문제는 <M:N>을 마지막 해로 갖는 달력에서 <x:y>는 몇 번째 해인지 구하는 문제입니다. 이때 달력의 해는 다음과 같은 규칙으로 증가합니다. 이때 이 문제의 제한조건은 다음과 같습니다. M, N은 40

[Data Structure]그래프(Graph) [내부링크]

그래프(Graph)란? 그래프는 정점(Vertex)과 간선(Edge)의 집합으로 표현하는 자료구조를 의미합니다. 이를 기호적으로 G=(V, E)로 표현합니다. 그래프의 기본 용어는 다음과 같은 것들이 있습니다. 정점(Vertex, Node, Point): 그래프에서 정보를 갖고 있는 최소단위. 간선(Edge, Arc, Link): 그래프에서 두 정점의 연결. 인접 정점(Adjacent vertex): 간선으로 직접 연결되어 있는 두 정점 경로(Path): 그래프에서 정점 u에서 정점 v로 가는 길 경로의 길이(Length of Path): 정점 u에서 정점 v로 가는 간선의 수 단순 경로(Simple Path): 불필요한 간선이 없는 경로 순환(Cycle): 시작 정점과 도착 정점이 똑같은 경로 평행 간선(Parallel Edge): 동일한 시작 정점과 도착 정점을 갖는 서로 다른 간선 셀프 루프(Self Loop): 자기 자신을 가리키는 간선 단순 그래프(Simple Graph):

백준7569: 토마토 [내부링크]

7569번: 토마토 문제 철수의 토마토 농장에서는 토마토를 보관하는 큰 창고를 가지고 있다. 토마토는 아래의 그림과 같이 격자모양 상자의 칸에 하나씩 넣은 다음, 상자들을 수직으로 쌓아 올려서 창고에 보관한다. 창고에 보관되는 토마토들 중에는 잘 익은 것도 있지만, 아직 익지 않은 토마토들도 있을 수 있다. 보관 후 하루가 지나면, 익은 토마토들의 인접한 곳에 있는 익지 않은 토마토들은 익은 토마토의 영향을 받아 익게 된다. 하나의 토마토에 인접한 곳은 위, 아래, 왼쪽, 오른쪽, 앞, 뒤 여섯 방향에 있는 토마토를 의미한다. 대각선 방향에 있는 토마... www.acmicpc.net 이 문제는 bfs를 잘 활용해야 하는 문제입니다. 2차원 정보에서 BFS를 이용해 문제를 해결하는 것에는 익숙할 수 있지만, 이 문제는 3차원 정보에서 풀어야 하므로 조금 더 신경 써서 코드를 작성해야 합니다. 물론 그 구조는 상통합니다. 1. Problem Analysis 크기가 (M, N, H)인

백준2805: 나무 자르기 [내부링크]

2805번: 나무 자르기 2805번 제출 맞힌 사람 숏코딩 재채점 결과 채점 현황 강의 질문 게시판 나무 자르기 다국어 시간 제한 메모리 제한 제출 정답 맞힌 사람 정답 비율 1 초 256 MB 185457 54347 33770 26.021% 문제 상근이는 나무 M미터가 필요하다. 근처에 나무를 구입할 곳이 모두 망해버렸기 때문에, 정부에 벌목 허가를 요청했다. 정부는 상근이네 집 근처의 나무 한 줄에 대한 벌목 허가를 내주었고, 상근이는 새로 구입한 목재절단기를 이용해서 나무를 구할것이다. 목재절단기는 다음과 같이 동작한다. 먼저, 상근이는 절단기에 높이... www.acmicpc.net 이 문제는 대표적인 매개변수탐색 문제입니다. 유사 문제로 백준1654: 랜선 자르기가 있습니다. 1. Problem Analysis 이 문제는 n개의 나무를 절단기를 이용해서 만든 나무토막들을 길이 m 이상만큼 얻으려고 할 때, 설정할 절단기의 최대 높이를 구하는 문제입니다. 이 문제의 제한 조건

9. 장고 테스트 [내부링크]

테스트란? 테스트란 코드 작동이 오류 없이 정상적으로 작동하는지 확인하는 하나의 루틴입니다. 테스트는 다양한 수준에서 작동할 수 있습니다. 세부 기능이 정상적으로 작동하는지부터 전반적인 소프트웨어가 정상적으로 작동하는지까지 작동할 수 있습니다. 개인적으로 직접 데이터를 생성해서 정상적으로 생성되고 저장되는지 확인할 수도 있지만, 일반적으로 테스트는 시스템이 자동적으로 할 수 있도록 합니다. 테스트 작성은 사실 매우 번거로울 수 있는 작업입니다. 테스트 작성을 위해서는 매번 개발한 새로운 기능이 어떤 오류를 발생할 수 있고, 그 오류를 어떻게 검증할지를 고민해야만 합니다. 하지만, 그 프로젝트의 크기가 커져갈수록 테스트는 오히려 이점이 커집니다. 수많은 구성요소들이 상호작용하고 있는 소프트웨어에서 어떤 부분을 수정했을 때 어떤 일이 일어날지 알 수 없습니다. 이런 경우에 미리 테스트를 작성해뒀다면, 단순히 테스트를 통과하는지 만으로 어떻게 수정해야 하는지 방향성을 잡을 수 있습니다.

백준5430: AC [내부링크]

5430번: AC 문제 선영이는 주말에 할 일이 없어서 새로운 언어 AC를 만들었다. AC는 정수 배열에 연산을 하기 위해 만든 언어이다. 이 언어에는 두 가지 함수 R(뒤집기)과 D(버리기)가 있다. 함수 R은 배열에 있는 수의 순서를 뒤집는 함수이고, D는 첫 번째 수를 버리는 함수이다. 배열이 비어있는데 D를 사용한 경우에는 에러가 발생한다. 함수는 조합해서 한 번에 사용할 수 있다. 예를 들어, "AB"는 A를 수행한 다음에 바로 이어서 B를 수행하는 함수이다. 예를 들어, "RDD"는 배열을 뒤집은 다음 처음 두 수를 버리는 함수이다. 배열... www.acmicpc.net 이 문제는 덱 자료구조를 사용할 것을 유추하고, 입출력 형식에 유의해야 하는 문제입니다. 1. Problem Analysis 이 문제는 T개의 테스트케이스에 대해 배열 X에서 연산 P들의 연산 결과를 출력하는 문제입니다. 연산 P는 배열 X를 뒤집는 연산 'R'과 배열 X의 첫 번째 원소를 제거하는 연산

10. 장고 Rest Framework [내부링크]

장고 Rest Framework란? 장고 REST Framwork(Django Rest Framework 또는 DRF)는 장고를 사용하여 RESTful API를 쉽게 개발할 수 있게 해주는 확장 프레임워크입니다. REST는 Representational State Transfer의 약자로, 자원을 URI로 표현하고 HTTP 메서드(GET, POST, PUT, DELETE 등)를 이용해 자원에 대한 행위를 정의하는 아키텍처 스타일을 나타냅니다. 장고는 자체적인 웹 템플릿을 이용해서 웹 서비스를 제공할 때 사용되지만, DRF는 백엔드 API 개발에 개발에 주목적이 있습니다. 구조적으로도 장고는 html형식으로 응답을 하지만, DRF는 json 형식으로 응답을 합니다. 즉, DRF를 백엔드 API로 사용하고 React나 Flutter와 같이 프론트엔드 기술스택을 목적에 맞게 선택할 수 있습니다. 클라이언트가 DRF 서버에 요청을 하면 DRF서버가 json형식으로 응답을 하고 프론트엔드단에

VMWare로 Ubuntu 설치하기, SSH 연결까지 [내부링크]

노트북을 맥으로 변경하면서 지금까지 크게 필요성을 못했지만, 추후 통일된 개발 환경을 위해서라도 우분투 가상환경을 설치해야 한다고 느껴서 정리해 봅니다. 가상환경 프로그램 설치하기 맥에서 가상머신하면 대표적으로 패레럴즈, UTM, VMware가 있습니다. 패레럴즈는 사용자 친화적이지만 유료 서비스이기 때문에 구입을 해야만 합니다. 그러면 UTM과 VMware가 남는데, 개인적으로 VMware를 사용해 본 경험이 있기 때문에 VMware를 사용하기로 결정했습니다. VMware는 현재 개인용으로 사용할 시 무료로 사용할 수 있습니다. 다만, 직접 개인용 라이센스를 만들고 하는 과정이 다소 번거롭긴 합니다. 아무튼 하단 링크에 들어가서 회원가입을 해줍니다. Download VMware Fusion | VMware Fusion 13 Player and Fusion 13 Pro are the best way to run Windows, Linux and more on the latest Ma

백준5525: IOIOI [내부링크]

5525번: IOIOI 문제 N+1개의 I 와 N개의 O 로 이루어져 있으면, I 와 O 이 교대로 나오는 문자열을 P N 이라고 한다. P 1 IOI P 2 IOIOI P 3 IOIOIOI P N IOIOI...OI ( O 가 N개) I 와 O 로만 이루어진 문자열 S와 정수 N이 주어졌을 때, S안에 P N 이 몇 군데 포함되어 있는지 구하는 프로그램을 작성하시오. 입력 첫째 줄에 N이 주어진다. 둘째 줄에는 S의 길이 M이 주어지며, 셋째 줄에 S가 주어진다. 출력 S에 P N 이 몇 군데 포함되어 있는지 출력한다. 제한 1 ≤ N ≤ 1,000,0... www.acmicpc.net 이 문제는 문제조건을 유의해서 풀어야 하는 문제입니다. 1. Problem Analysis 이 문제는 길이가 m인 문자열 s에 n+1개의 'I'와 n개의 'O'로 이루어진 pn이 몇 개 있는지 확인하는 문제입니다. 이 문제에서 pn은 짝수 위치에 'I'가, 홀수 위치에 'O'가 위치해있는 문자열입니

백준2630: 색종이 만들기 [내부링크]

2630번: 색종이 만들기 문제 아래 <그림 1>과 같이 여러개의 정사각형칸들로 이루어진 정사각형 모양의 종이가 주어져 있고, 각 정사각형들은 하얀색으로 칠해져 있거나 파란색으로 칠해져 있다. 주어진 종이를 일정한 규칙에 따라 잘라서 다양한 크기를 가진 정사각형 모양의 하얀색 또는 파란색 색종이를 만들려고 한다. 전체 종이의 크기가 N×N(N=2 k , k는 1 이상 7 이하의 자연수) 이라면 종이를 자르는 규칙은 다음과 같다. 전체 종이가 모두 같은 색으로 칠해져 있지 않으면 가로와 세로로 중간 부분을 잘라서 <그림 2>의 I, II, III, IV와 같이... www.acmicpc.net 이 문제는 백준1074: Z와 상당한 유사한 문제입니다. 과거 포스팅을 올린 적이 있는데 문제 풀이에 공통된 아이디어를 사용하고 있으니 한 번 읽고 오시는 것도 좋을 거 같습니다. 백준1074 : Z 이 문제는 재귀 알고리즘을 이용하면 정말 손쉽게 해결 가능한 문제입니다. 1. Problem A

8. 장고 제네릭 뷰 [내부링크]

제네릭 뷰(Generic View)란? 장고 제네릭 뷰는 그 단어 뜻 그대로 일반화된 장고 뷰를 의미합니다. 정확히는 웹 개발에서 일반적으로 자주 사용되는 뷰들을 매번 구현하는 것을 방지하기 위한 재사용 가능한 뷰 구현을 위한 클래스 기반의 뷰 시스템입니다. 제너릭 뷰는 일반적인 웹 개발 패턴을 따르며, 코드의 재사용성과 효율성을 높이기 위해 설계되었습니다. 제너릭 뷰는 일반적인 작업을 수행하는 데 필요한 기능을 미리 구현해 놓은 추상화된 뷰 클래스를 제공합니다. 제네릭 뷰 사용하기 제네릭 뷰로 한 번 장고앱의 index뷰, detail뷰 함수를 클래스로 교체해 보겠습니다. 제네릭 뷰를 사용하기 위해서는 'from django.views import generic'을 명시해서 제네릭 라이브러리를 불러와야 합니다. 제네릭 라이브러리에는 다양한 View 클래스를 제공하고 있으며, 상황에 맞게 상속해서 사용하면 됩니다. ListView는 데이터의 목록을 표시하는데 적합한 제네릭 뷰입니다.

백준 2667: 단지번호붙이기 [내부링크]

2667번: 단지번호붙이기 2667번 제출 맞힌 사람 숏코딩 재채점 결과 채점 현황 강의 질문 게시판 단지번호붙이기 시간 제한 메모리 제한 제출 정답 맞힌 사람 정답 비율 1 초 128 MB 173418 77040 48929 42.316% 문제 <그림 1>과 같이 정사각형 모양의 지도가 있다. 1은 집이 있는 곳을, 0은 집이 없는 곳을 나타낸다. 철수는 이 지도를 가지고 연결된 집의 모임인 단지를 정의하고, 단지에 번호를 붙이려 한다. 여기서 연결되었다는 것은 어떤 집이 좌우, 혹은 아래위로 다른 집이 있는 경우를 말한다. 대각선상에 집이 있는 경우는 연결... www.acmicpc.net 이 문제는 대표적인 그래프 탐색 문제 중 하나입니다. 1. Problem Analysis n*n크기의 정사각형 지도에는 각 좌표마다 집이 있습니다. 이때 상하좌우로 집이 붙어 있으면 단지라고 부를 수 있는데, 주어진 지도에는 몇 개의 단지가 있고, 각 단지에는 몇 개의 집이 있는지 구하는 문제입

백준2579: 계단 오르기 [내부링크]

2579번: 계단 오르기 문제 계단 오르기 게임은 계단 아래 시작점부터 계단 꼭대기에 위치한 도착점까지 가는 게임이다. <그림 1>과 같이 각각의 계단에는 일정한 점수가 쓰여 있는데 계단을 밟으면 그 계단에 쓰여 있는 점수를 얻게 된다. <그림 1> 예를 들어 <그림 2>와 같이 시작점에서부터 첫 번째, 두 번째, 네 번째, 여섯 번째 계단을 밟아 도착점에 도달하면 총 점수는 10 + 20 + 25 + 20 = 75점이 된다. <그림 2> 계단 오르는 데는 다음과 같은 규칙이 있다. 계단은 한 번에 한 계단씩 또는 두 계단씩 오를 수 있다. 즉, 한 계단을... www.acmicpc.net 이 문제는 다이나믹 프로그래밍의 기본적인 구조를 배울 수 있는 문제입니다. 1. Problem Analysis 이 문제는 숫자가 적혀있는 n개의 계단에서 맨 밑에서 n번째 계단을 밟을 때 그 숫자의 합이 최대가 되도록 하는 문제입니다. 이때 현재 밟고 있는 계단의 바로 위 칸이나, 한 칸 건너뛴

백준2606: 바이러스 [내부링크]

2606번: 바이러스 문제 신종 바이러스인 웜 바이러스는 네트워크를 통해 전파된다. 한 컴퓨터가 웜 바이러스에 걸리면 그 컴퓨터와 네트워크 상에서 연결되어 있는 모든 컴퓨터는 웜 바이러스에 걸리게 된다. 예를 들어 7대의 컴퓨터가 <그림 1>과 같이 네트워크 상에서 연결되어 있다고 하자. 1번 컴퓨터가 웜 바이러스에 걸리면 웜 바이러스는 2번과 5번 컴퓨터를 거쳐 3번과 6번 컴퓨터까지 전파되어 2, 3, 5, 6 네 대의 컴퓨터는 웜 바이러스에 걸리게 된다. 하지만 4번과 7번 컴퓨터는 1번 컴퓨터와 네트워크상에서 연결되어 있지 않기 때문에 영향을 받... www.acmicpc.net 이 문제는 직관적인 그래프 탐색 문제입니다. 1. Problem Analysis 이 문제는 n대의 컴퓨터에 대해 1번 컴퓨터가 감염되면 네트워크에 의해 연결되어 있는 모든 컴퓨터가 감염될 때, 감염되는 컴퓨터 수가 얼마인지 구하는 문제입니다. 이때 제한시간은 다음과 같습니다. 컴퓨터는 100 이하의

10. C++의 표준 템플릿 라이브러리(Standard Template Library, STL) [내부링크]

표준템플릿 라이브러리(STL)란? C++에서 표준템플릿 라이브러리(STL)은 C++ 프로그래밍 언어의 표준 라이브러리로서, 데이더 구조와 알고리즘을 포함하는 많은 기능을 제공하는 라이브러리를 의미합니다. 코딩을 하다보면 다양한 자료구조가 필요할 때가 있을 것입니다. 스택이나 큐 같은 자료구조를 C에서는 직접 만들어서 사용해야 했을 겁니다. 하지만, C++은 내장 라이브러리에 이러한 자료구조를 다양한 상황에 적용할 수 있도록 만들어놔서 단지 구현되어 있는 것을 갖다가 사용하면 됩니다. STL은 컨테이너(Container), 어답터(Adaptor), 반복자(iterator), 알고리즘(algorithm) 4가지 요소로 구성되어 있습니다. 이중 컨테이너와 어답터는 자료구조를 담당합니다. STL의 효율성 C++에서 STL은 효율적으로 설계되었습니다. 이는 일반적인 상황에서 최적의 성능을 내기 위한 형태로 설계되었다는 의미입니다. 예를 들면, 집합 자료형과 같은 경우 정렬된 순서로 저장되도록

자바(Java)의 기본 [내부링크]

자바(Java)란? 자바는 오늘날 웹과 모바일 프로그래밍에 널리 사용되고 있는 프로그래밍 언어입니다. 그 시작은 1991년 가전제품에 사용할 목적으로 개발되었으며 1995년 발표된 언어입니다. 가전제품에는 정말 다양한 컴퓨터 프로세서가 사용될 수 있다 보니 그러한 실행 환경에 구애받지 않도록 설계된 것이 큰 특징입니다. 자세히 보면, 자바로 작성된 코드를 자바 컴파일러가 바이트 코드로 변환시키고 이를 자바 가상 머신(Java Virtual Machine, JVM)라는 공통된 환경에서 실행시킨다는 특징이 있어 이 JVM이 실행될 수 있는 환경이라면 어느 곳이든지 실행이 가능합니다. 자바는 대표적인 객체지향 프로그래밍 언어로 모든 것이 클래스로서 관리가 된다는 특징이 있습니다. 다만 다중 상속은 지원하지 않습니다. 또한 C언어에 영향을 받았음에도 포인터가 없다는 특징이 있습니다. 그 이외에도 객체의 사용 여부에 따라 자동으로 메모리에서 제거, 관리하는 특징이 있고, 함수적 스타일 코딩

백준1931: 회의실 배정 [내부링크]

1931번: 회의실 배정 1931번 제출 맞힌 사람 숏코딩 재채점 결과 채점 현황 강의 질문 게시판 회의실 배정 시간 제한 메모리 제한 제출 정답 맞힌 사람 정답 비율 2 초 128 MB 198655 64357 44721 30.274% 문제 한 개의 회의실이 있는데 이를 사용하고자 하는 N개의 회의에 대하여 회의실 사용표를 만들려고 한다. 각 회의 I에 대해 시작시간과 끝나는 시간이 주어져 있고, 각 회의가 겹치지 않게 하면서 회의실을 사용할 수 있는 회의의 최대 개수를 찾아보자. 단, 회의는 한번 시작하면 중간에 중단될 수 없으며 한 회의가 끝나는 것과 ... www.acmicpc.net 이 문제는 대표적인 그리디 알고리즘 및 정렬 문제입니다. 1. Problem Analysis 이 문제는 한 개의 회의실을 사용하려는 예약 n개가 있을 때, 최대한 많은 회의를 진행할 수 있는 경우 몇 개의 회의가 진행될 수 있는지 구하는 문제입니다. 이 문제의 제한조건은 다음과 같습니다. 회의의

8. C++의 연산자 오버로딩(Operator overloading) [내부링크]

연산자 오버로딩의 기본(Basic of Operator Overloading) 연산자(Operator)는 보통 프로그래밍 언어에서 사칙연산이나 논리연산을 위해 지원하는 내장된 기능을 의미합니다. 그런데 C++에서 '+'연산자가 (int)+(int), (double)+(double) 뿐만 아니라 (string)+(string)에서도 작동하는 것을 문자열 부분에서 다루었습니다. 이걸 보면 무언가 떠오르시는 게 있으실 수도 있습니다. 함수명은 같지만 매개변수는 다른 오버로딩(Overloading)말입니다. 즉, C++에서 연산자는 사실 함수이며 오버로딩을 할 수 있습니다. 연산자를 일반적인 함수 형식으로 표현한다면 다음과 같이 표현할 수 있을 것입니다. x + y = operator+(x, y). 그렇다면 연산자 오버로딩은 어떤 경우 사용할 수 있을까요? 일반적인 자료형들에 대한 연산은 이미 지원하기에 개발자로 새로 만든 자료형에 대해 계산할 때 유용할 것입니다. 예를 들면 Money 클

백준2178: 미로 탐색 [내부링크]

2178번: 미로 탐색 문제 N×M크기의 배열로 표현되는 미로가 있다. 1 0 1 1 1 1 1 0 1 0 1 0 1 0 1 0 1 1 1 1 1 0 1 1 미로에서 1은 이동할 수 있는 칸을 나타내고, 0은 이동할 수 없는 칸을 나타낸다. 이러한 미로가 주어졌을 때, (1, 1)에서 출발하여 (N, M)의 위치로 이동할 때 지나야 하는 최소의 칸 수를 구하는 프로그램을 작성하시오. 한 칸에서 다른 칸으로 이동할 때, 서로 인접한 칸으로만 이동할 수 있다. 위의 예에서는 15칸을 지나야 (N, M)의 위치로 이동할 수 있다. 칸을 셀 때에는 시작 위치와 ... www.acmicpc.net 이 문제는 대표적인 유형의 BFS를 이용한 최소 거리 찾기 문제입니다. 1. Problem Analysis 가로 m, 세로 n 크기의 미로에서 (0, 0)에서 시작해 (m-1, n-1)로 이동하고 싶을 때 최소 이동 칸수를 구하는 문제입니다. 미로 탐색 문제는 대표적인 그래프 문제로 인지되고 있습니

9. C++의 템플릿(Templates) [내부링크]

템플릿(Template)이란? C++에서 템플릿(Template)은 함수나 클래스의 일반적인 정의를 가능하게 하는 것입니다. 여기서 '일반적인'의 의미는 실제 자료형 대신 템플릿을 사용해서 정확한 자료형이 런타임에 정해지도록 하는 특별한 툴입니다. 함수 템플릿(Function Template) 기존에 다양한 자료형에 대응되도록 함수를 만들기 위해서는 함수 오버로딩(Function Overloading) 기능을 사용했었습니다. 하지만 함수 템플릿을 사용하면 단 하나의 함수만으로 다양한 자료형에서 작동할 수 있습니다. 템플릿 기능을 사용하기 위해서는 템플릿 전위문(Template Prefix)를 명시해야 합니다. 컴파일러에게 템플릿을 사용할 것이니 자료형을 런타임에 정할게라고 말해주는 것입니다. 'templae<class T>'나 'template<typename T>'형태로 작성해야 합니다. 템플릿 전위문에서 'class'는 자료형을 의미하고 'T'는 자료형 이름을 의미합니다. 즉,

7 C++의 다형성(Polymorphism) [내부링크]

가상함수의 기본(Basic of Virtual Functions) 다형성(Polymorphism) 하나의 함수에 다양한 의미를 연결 짓는 것을 의미합니다. 이는 객체지향 프로그래밍의 근본이 되는 원리입니다. 가상 함수는 다형성을 제공하는 방법입니다. 가상함수(Virtual Function) 가상이라는 말은 실제로는 존재하지 않지만, 본질적으로는 존재한다는 의미입니다. 즉, 가상함수는 정의되기도 전에 사용될 수 있는 함수를 의미합니다. 예를 들면, 도형이라는 클래스가 있다고 합시다. 그리고 여기서 파생된 원이라는 객체와 사각형이라는 객체가 있다고 합니다. 도형을 그린다는 개념은 매우 추상적이고 표현하기 어렵습니다. 하지만, 여기서 파생된 원이나 사각형에서 그린다라는 개념은 머릿속으로 바로 떠올릴 수 있을 정도로 직관적이게 됩니다. 하지만 서로의 그린다는 개념은 완전히 다른 결과를 야기합니다. class Figure{ void draw(); }; 핵심은 바로 도형 객체에서의 그린다는 개

4. C++의 클래스(Classes) [내부링크]

구조체(Structures) 구조체는 서로 다른 자료형을 하나로 묶어서 다룰 수 있게 구조화한 것을 말합니다. 구조체 정의는 global하게 정의합니다. 단지 해당 구조체의 구조를 설명하는 것이기 때문에 메모리 할당을 하거나 하지는 않습니다. 구조체를 정의하면 그 자체를 일종의 자료형처럼 사용이 가능합니다. 구조체 정의 블록이 끝나면 반드시 ';'으로 표시해 줘야 합니다. 구조체 내부 변수를 멤버변수(Member Variable)라고 부르며, 이는 구조체 변수에 '.'으로 연결해서 접근할 수 있습니다. struct Person{ // "Person"이라는 이름의 구조체 전역 정의 string name; double height; double weight; }; // ';'으로 반드시 구조체 정의가 완료되었음을 명시 int main(){ Person person = { "Mr.Kim", 180.0, 70.0 }; // 구조체 자료형을 갖는 변수 person 선언 및 초기화 person

5. C++의 생성자와 소멸자, 그리고 기타 기능들(Constructors, Destructors, and etc) [내부링크]

생성자(Constructors, Ctors) 생성자(Constructors) 객체가 선언될 때 자동으로 호출되는 멤버함수입니다. 명시적으로 호출하는 방법은 허용되지 않습니다. 멤버변수를 초기화할 때 사용됩니다. 생성자를 통해 멤버변수가 초기화되므로 공백이나 쓰레기 값으로 인한 오류 발생을 해결합니다. C++에서 생성자는 클래스명과 동일한 멤버함수를 이용해 만듭니다. 반환형은 정의하지 않습니다. class Person{ private: string name; double height; double weight; public: Person(string name, double height, double weight){ // 생성자 this->name = name; this->height = height; this->weight = weight; } }; Person person("Mr.Hong", 180.0, 70.0); // 기본적인 생성자 호출 Person* pperson = new

백준1927: 최소 힙 [내부링크]

1927번: 최소 힙 문제 널리 잘 알려진 자료구조 중 최소 힙이 있다. 최소 힙을 이용하여 다음과 같은 연산을 지원하는 프로그램을 작성하시오. 배열에 자연수 x를 넣는다. 배열에서 가장 작은 값을 출력하고, 그 값을 배열에서 제거한다. 프로그램은 처음에 비어있는 배열에서 시작하게 된다. 입력 첫째 줄에 연산의 개수 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 N개의 줄에는 연산에 대한 정보를 나타내는 정수 x가 주어진다. 만약 x가 자연수라면 배열에 x라는 값을 넣는(추가하는) 연산이고, x가 0이라면 배열에서 가장 작은 값을 출력하고 그 값을... www.acmicpc.net 이 문제는 최소 힙에 대해서 이해하고 있는지 확인하고, 그 구현 방법을 어떻게 할 것인지에 대한 문제입니다. 1. Problem Analysis 이 문제에서 최소힙은 2가지 연산을 정의합니다. 배열에 원소 x를 삽입 배열에서 최솟값을 삭제하고 반환한다. 이때 제한조건은 다음과 같다. 연산의 개수는 1

6. C++의 상속(Inheritance) [내부링크]

상속의 기본(Basics of Inheritance) 일상적으로 상속은 사람의 사망에 의한 재산 및 신분상의 지위의 포괄적인 승계를 의미합니다. 즉 부모의 것을 자식이 물려받는다는 개념을 의미합니다. 한편, 객체지향 프로그래밍(OOP)에서도 상속이란 것이 있으며 매우 중요한 기능으로서 사용됩니다. OOP에서 상속은 추상화 차원에서 어떤 클래스의 일반적인 특성들을 다른 클래스가 상속받아 사용하는 것을 의미합니다. 이때 상속해 주는 클래스를 부모 클래스(Parent Class) 혹은 상위 클래스(Super Class), 상속받는 클래스를 자식 클래스(Child Class) 혹은 하위 클래스(Sub Class)라고 부릅니다. 객체로서의 상속에 대한 예시는 다음과 같습니다. 세상에는 다양한 종류의 자동차들이 있습니다. 오토바이도 있고, 승용차, 승합차도 있고, 특수 목적의 스포츠카나 트럭도 있습니다. 이런 자동차들에는 공통점이 있습니다. 엔진, 바퀴, 브레이크 등이 모두 있고 가속, 정지와

백준1697: 숨바꼭질 [내부링크]

1697번: 숨바꼭질 1697번 제출 맞힌 사람 숏코딩 재채점 결과 채점 현황 강의 질문 게시판 숨바꼭질 다국어 시간 제한 메모리 제한 제출 정답 맞힌 사람 정답 비율 2 초 128 MB 228950 66821 42280 25.649% 문제 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 때 걷는다면 1초 후에 X-1 또는 X+1로 이동하게 된다. 순간이동을 하는 경우에는 1초 후... www.acmicpc.net 이 문제는 BFS의 유용한 활용에 대해서 알 수 있는 문제입니다. 1. Problem Analysis 이 문제는 위치가 n인 점에서 위치가 k인 점으로 이동할 때 걸리는 최소 시간을 구하는 문제입니다. 이동 방법은 다음과 같습니다. 1초 동안 좌우로 1칸 이동한다. x+1 or x-1. 1초 동안 현

2. C++의 함수들(Functions) [내부링크]

함수의 기본(Basics) 함수는 그룹화되어 이름이 붙여진 하나의 구문을 의미합니다. 기능적으로는 어떠한 입력값에 일정한 결괏값을 내는 관계이자 규칙을 의미합니다. 하나의 프로그램을 여러 개의 조각으로 나눌 때의 기본 단위 중 하나입니다. 함수는 구문이기 때문에 가독성이 좋아야 합니다. 함수 내에 정의된 매개변수의 이름은 기본적으로 해당 함수 내에서만 유효합니다. 코드는 기본적으로 함수의 정의 부분과 함수의 호출 부분이 있습니다. // 함수 정의 int function(int n){ // caller: the value of n, callee: the return of function return n + 1; } int x = 0; // 함수 호출 y = function(x); // caller: the return of function, callee: x Call by Value Call by value는 전달인자로 전해진 실제 값의 복사본을 의미합니다. 함수 내에서 지역변수로 인

3. C++의 문자열(Strings) [내부링크]

문자열의 기본(Basics) C언어에서 문자열은 문자배열을 활용하여 표현하였습니다. 그 특성상 문자열의 마지막을 반드시 '\0'로 끝냈었습니다. C언어에서 문자열을 다뤄본 사람들은 알겠지만 잘못 다루면 바로 오류가 발생해 조심해서 다뤄야 하는 것이 문자열입니다. // C 스타일 문자열 // 배열의 주소 : 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 // 배열에 저장 : H e l l o W o r l d \0 ? ? ? ? char s[15] = "Hello World"; printf("%s\n", s); 하지만 C++에 와서는 문자열을 하나의 객체로서 사용해 훨씬 쉽게 다룰 수 있습니다. 문자열 클래스(String Class) C++에서는 C에서와는 달리 문자열만을 위한 'string'이라는 별도의 자료형이 있습니다. string 자료형은 std 이름영역 내에 정의되어 있고, 이는 <string> 헤더파일에 정의되어 있습니다. 물론 <string> 헤더파일

백준1764: 듣보잡 [내부링크]

1764번: 듣보잡 1764번 제출 맞힌 사람 숏코딩 재채점 결과 채점 현황 강의 질문 게시판 듣보잡 시간 제한 메모리 제한 제출 정답 맞힌 사람 정답 비율 2 초 256 MB 97138 41531 32261 41.026% 문제 김진영이 듣도 못한 사람의 명단과, 보도 못한 사람의 명단이 주어질 때, 듣도 보도 못한 사람의 명단을 구하는 프로그램을 작성하시오. 입력 첫째 줄에 듣도 못한 사람의 수 N, 보도 못한 사람의 수 M이 주어진다. 이어서 둘째 줄부터 N개의 줄에 걸쳐 듣도 못한 사람의 이름과, N+2째 줄부터 보도 못한 사람의 이름이 순서대로... www.acmicpc.net 이 문제는 간단한 집합론에 대한 문제입니다. 1. Problem Analysis 본인이 들은 적이 없는 명단과 본 적이 없는 명단, 두 명단 내의 사람들 중에서 대해서 두 명단에 동시에 속한 사람이 누구인지에 대한 문제입니다. 이때 제한조건은 다음과 같습니다. 듣도 못한 사람의 수 N, 보도 못한 사람

백준1389: 케빈 베이컨의 6단계 법칙 [내부링크]

1389번: 케빈 베이컨의 6단계 법칙 문제 케빈 베이컨의 6단계 법칙에 의하면 지구에 있는 모든 사람들은 최대 6단계 이내에서 서로 아는 사람으로 연결될 수 있다. 케빈 베이컨 게임은 임의의 두 사람이 최소 몇 단계 만에 이어질 수 있는지 계산하는 게임이다. 예를 들면, 전혀 상관없을 것 같은 인하대학교의 이강호와 서강대학교의 민세희는 몇 단계만에 이어질 수 있을까? 천민호는 이강호와 같은 학교에 다니는 사이이다. 천민호와 최백준은 Baekjoon Online Judge를 통해 알게 되었다. 최백준과 김선영은 같이 Startlink를 창업했다. 김선영과 김도현은 같은 ... www.acmicpc.net 이 문제는 전형적인 그래프 탐색 문제입니다. 1. Problem Analysis 케빈 베이컨의 6단계 법칙은 모든 사람들은 6명 이내에서 서로 알고 있는 사이라는 법칙입니다. 쉽게 말하면 건너건너 6명 안쪽에서 전 세계 사람들은 서로를 알고 있다는 것이죠. 이때, 케빈 베이컨의 수는

[Data Structure]힙(Heap) [내부링크]

힙(Heap)이란? 완전이진트리(Complete Binary Tree)의 일종으로 최댓값이나 최솟값을 빠르게 구하는데 최적화된 자료구조입니다. 이때 힙은 최댓값이나 최솟값을 트리의 루트 노드에 갖습니다. 전자를 최대힙(max heap), 후자를 최소힙(min heap)이라고 부릅니다. 최대힙일 경우에는 key(부모 노드) >= key(자식 노드)를 반드시 만족하고, 최소힙일 경우에는 key(부모노드) <= key(자식 노드)를 만족합니다. (좌) 최대 힙 / (우) 최소 힙 힙의 구현(C언어) Based on Array 여기서는 최대힙을 구현하겠습니다. 최소힙은 최대힙구조에 삽입하는 원소에 -를 붙여서 삽입하면 기능상 최소힙과 동일합니다. 힙은 이진트리의 일종이므로 배열 기반으로 작성할 경우 그 구조는 배열 기반의 이진트리와 동일합니다. typedef enum { false, true } bool; typedef int HData; typedef struct { HData data;

백준1463: 1로 만들기 [내부링크]

1463번: 1로 만들기 1463번 제출 맞힌 사람 숏코딩 재채점 결과 채점 현황 강의 질문 게시판 1로 만들기 시간 제한 메모리 제한 제출 정답 맞힌 사람 정답 비율 0.15 초 ( 하단 참고 ) 128 MB 287491 97629 62227 32.867% 문제 정수 X에 사용할 수 있는 연산은 다음과 같이 세 가지 이다. X가 3으로 나누어 떨어지면, 3으로 나눈다. X가 2로 나누어 떨어지면, 2로 나눈다. 1을 뺀다. 정수 N이 주어졌을 때, 위와 같은 연산 세 개를 적절히 사용해서 1을 만들려고 한다. 연산을 사용하는 횟수의 최솟값을 출력하시오.... www.acmicpc.net 이 문제는 섣부르게 판단하면 틀릴 수 있는 문제입니다. 1. Problem Analysis 이 문제는 주어진 n을 다음 3가지 연산만을 이용해서 1로 만들 때, 최소 연산 횟수를 구하는 문제입니다. X가 3으로 나누어 떨어지면, 3으로 나눈다. X가 2로 나누어 떨어지면, 2로 나눈다. 1을 뺀다.

백준1541: 잃어버린 괄호 [내부링크]

1541번: 잃어버린 괄호 1541번 제출 맞힌 사람 숏코딩 재채점 결과 채점 현황 강의 질문 게시판 잃어버린 괄호 시간 제한 메모리 제한 제출 정답 맞힌 사람 정답 비율 2 초 128 MB 80870 43729 34256 53.467% 문제 세준이는 양수와 +, -, 그리고 괄호를 가지고 식을 만들었다. 그리고 나서 세준이는 괄호를 모두 지웠다. 그리고 나서 세준이는 괄호를 적절히 쳐서 이 식의 값을 최소로 만들려고 한다. 괄호를 적절히 쳐서 이 식의 값을 최소로 만드는 프로그램을 작성하시오. 입력 첫째 줄에 식이 주어진다. 식은 ‘0’~‘9’, ‘+’, ... www.acmicpc.net 이 문제는 최솟값을 만드는 경우가 무엇인지만 찾으면 풀 수 있는 문제입니다. 1. Problem Analysis +, - 연산자만으로 이루어진 식에 괄호를 적절히 칠 때 그 연산식의 결괏값이 최소가 되는 경우를 찾는 문제입니다. 이 문제의 제한조건은 다음과 같습니다. 0으로 식이 시작할 수는 없

[Data Structure]우선순위 큐(Priority Queue) [내부링크]

우선순위 큐(Priority Queue)란? 큐는 FIFO의 규칙을 준수하는 자료구조입니다. [Data Structure]큐(Queue) 큐(Queue)란? 큐는 대표적인 자료구조 중 하나로 한쪽에서는 데이터의 삽입만, 다른 한쪽에서는 데이터의 ... blog.naver.com 우선순위 큐는 여기서 각 원소에 우선순위(Priority)가 있어 dequeue를 할 때, 우선순위에 따라서 dequeue를 하는 큐를 의미합니다. 예를 들면, 도로에서 일반 차량보다 구급차나 소방차가 먼저 지나가야 하는 원리와 같습니다. 우선순위 큐의 구현(C언어) 우선순위 큐는 다양한 방식으로 구현할 수 있습니다. 배열이나 연결리스트를 이용해서도 구현할 수 있지만, 여기서 핵심은 Heap 구조를 이용해서 구현하는 것입니다. 정렬되지 않은 배열 기반 우선순위 큐 구현 데이터의 삽입 시에는 무조건 마지막 위치에 삽입하면 됩니다. 데이터의 삭제 시에는 먼저 최댓값을 찾아야 합니다. 그리고 그 최댓값을 삭제하고

C++의 기본 [내부링크]

C++이란? C++은 C언어를 기반으로 1985년 발표되어 지금까지도 사장되지 않고 발전되고 있는 프로그래밍 언어입니다. 2023년이 되어서도 세계에서 인기 있는 프로그래밍언어 순위를 매기면 열 손가락에는 반드시 들어오는 언어입니다. C언어는 프로그래밍 영역에 거대한 영향을 미친 언어인데, 너무 low-level system programming에 적합한 나머지 규모가 큰 프로젝트에서의 사용이 어렵습니다. 그래서 이를 보완하려는 목적으로 C언어를 기반으로 만든 다양한 언어들이 있습니다. 그중 하나가 바로 C++입니다. C++은 그 용어 자체로 C언어에 부가적인 기능들이 추가된, 플러스된 언어를 의미합니다. 그중 가장 중요한 특징은 객체지향 프로그래밍(Objective Programming)입니다. 하지만, 그렇다고 C언어의 특징을 잃어버린 것도 아닙니다. C언어의 문법을 그대로 사용이 가능합니다. 즉 C++은 C언어를 포함하는 상위 집합의 개념이라고 이해하는 것이 좋습니다. 하지만

1. C++의 기본들(Basics) [내부링크]

개요(Intro) C++은 C의 상위집합입니다. C언어에서 할 수 있는 것들은 모두 C++에서도 가능합니다. C에서 사용되던 자료형과 제어 흐름은 모두 C++에서도 적용됩니다. 따라서, C언어에 익숙하면 그 차이점만 공부해 C++도 쉽게 숙달할 수 있습니다. 자료형(Data Type) 기본적으로 C/C++에서 지원하는 자료형은 다음과 같습니다. x86 아키텍처 기반으로 작성하였습니다. 타입명 메모리 사용 크기 범위 정밀도(Precision) short / short int 2byte [-32,768, 32,767] X int 4byte [-2,147,483,648, 2,147,483,647] X long / long int 4byte [-2,147,483,648, 2,147,483,647] X float 4byte [10^(-38), 10^(38)] 7digit double 8byte [10^(-308), 10^(308)] 15digit long double 10byte [10^(-

[선형대수학1-8]The Matrix of a Linear Transformation(선형변환 행렬) [내부링크]

선형변환 행렬(Matrix of a Linear Transformation) ▷ 선형 변환의 기준 행렬(Standard Matrix for the linear transformation) - Let T: Rn->Rm, T(x)=Ax Then, A=[T(e1) T(e2) ... T(en)]이다. - T(ei)의 값은 알지만 A을 알고싶을 때 위 정의를 사용한다. (Example) Find the standard matrix A for the dilation trasformation T(x)=3x, for x in R2 2차원 상에서 기하학적 선형변환(Geometric Linear Transformation of R2) - e1, e2를 선형변환시킨 결과의 관계. ▷ 다양한 선형변환 반사 축소와 팽창 전단 투영 존재성과 유일성(Existence and Uniqueness) ▷ onto의 정의 - If: T(x)가 최소 하나의 x에 대해 대응된다면, Then: T: Rn->Rm은 o

IT 면접 준비는 여기서? - Awesome Interview Questions [내부링크]

GitHub - DopplerHQ/awesome-interview-questions: :octocat: A curated awesome list of lists of interview questions. Feel free to contribute! :octocat: A curated awesome list of lists of interview questions. Feel free to contribute! :mortar_board: - GitHub - DopplerHQ/awesome-interview-questions: :octocat: A curated awesome list of list... github.com 오늘은 매우 유용한 깃허브 라이브러리를 가지고 왔습니다. 놀랍게도 6만개의 별을 받은 라이브러리입니다! 바로 'Awesome Interview Questions, 놀라운 면접 질문들'이라는 깃허브 라이브러리입니다. 개발자로서 IT기업에 취업하기 위해서는 서류전형을 통

[선형대수학2-3]Characterizations of Invertible Matrices(가역행렬의 특징) [내부링크]

가역행렬 정리(Invertible Matrix Theorem) - Let A는 nxn행렬. Then 다음 문장들은 상등하다. a. A는 가역행렬이다. b. A는 I와 행상등이다. c. A는 n개의 pivot 위치를 갖고 있다. d. Ax=0은 자명해만 갖고 있다. e. A의 열들은 선형 독립 집합을 형성한다. f. x |→ Ax는 one-to-one이다. g. Ax=b는 최소 1개의 해를 갖고 있다. h. A의 열들은 spanRn이다. i. x |→ Ax는 Rn onto Rn이다. j. CA=I를 만족하는 C가 있다. k. AD=I를 만족하는 D가 있다. l. AT는 가역행렬이다. 가역 선형 변환(Invertible Linear Transformations) - 선형변환 T: Rn → Rn이 있다. If 함수 S: Rn → Rn에 대해 S(T(x))=x and T(S(x))=x이다. Then T는 가역 선형 변환이다. 선변 변환 관점에서 역행렬은 역함수로 해석된다. - If T:

WSL2(Windows Subsystems for Linux 2) 설치 [내부링크]

컴퓨터 공학에 입문을 하고 시간이 지나다보면 Linux계열 운영체제를 사용해야만 하는 경우가 있습니다. 하지만 Linux는 일반인들에게는 생소한 운영체제(Operating System, OS)입니다. 우리나라같은 경우 완화되어 가고 있지만, 많은 공기관 웹사이트 이용을 위해서는 windows 사용이 강제됩니다. 그렇다보니 보통 Linux를 사용하기 위해서는 가상머신(Virtual Machine, VM)을 사용하곤 합니다. 대표적으로 사용되는 VM은 Virtual Box와 VMware같은 것들이 있습니다. 저도 이 프로그램들을 사용해봤는데 VM 특유의 불편함이 있습니다. 그래서 대안을 찾아보니 windows에서 지원하는 매우 강력한 기능이 있었습니다. 바로 Linux용 Windows 하위 시스템(Windows Subsystems for Linux, WSL)입니다. 한번 WSL을 맛보면 다른 VM은 사용할 생각을 못하게 됩니다. 그래서 이 글에서는 WSL을 설치하고 WSL2로 업데이트하

[Data Structure]덱(Deq, Deque) [내부링크]

덱(Deq, Deque)이란? 덱은 "Double-ended Queue"의 약자로, 큐의 변형입니다. 덱은 큐와 동일하게 전면(front), 후면(rear)가 있습니다. 하지만, 덱은 큐와 달리 전면과 후면 모두에서 데이터의 추가, 삭제, 조회 기능을 수행할 수 있습니다. 덱의 구조 덱의 구현(C언어) Based on Array 기본적인 정적 덱의 구조는 다음과 같습니다. C언어에는 불대수가 따로 없기 때문에 열거형으로 불대수를 직접 정의해 구현하였습니다 전처리기 지시자로 덱의 최대 크기를 100으로 정의해 주었습니다. 이 부분은 당연히 수정이 가능합니다. 그리고 구조체를 이용해 덱의 원소들을 저장할 배열과 덱의 front, rear을 가리키는 front와 rear를 구현하였습니다. #define MAX_DEQ 100 typedef enum { false, true } bool; typedef int Data; typedef struct{ Data items[MAX_DEQ]; int

[Data Structure]트리(Tree) [내부링크]

트리(Tree)란? 트리(Tree)란 부모-자식 관계라는 계층적인 구조를 갖는 노드들의 집합을 의미합니다. 특징으로는 그 구조를 그림으로 그려보면 나무처럼 생겼습니다. 추가적으로 순환이 없는 그래프를 트리라고 부릅니다. 트리에서 사용되는 다양한 기본 용어 노드(node): 데이터를 갖고 있는 트리의 가장 기본적인 요소 엣지(edge): 서로 다른 두 노드 사이의 연결 루트(root): 트리의 최상단 노드 내부 노드(internal node): 한 개 이상의 차수를 갖는 노드 잎 노드, 말단 노드(leaf node, terminal node): 차수가 없는 노드들 레벨(level): 루트 노드로부터 떨어진 거리, 루트 노드의 레벨은 0이다. 높이, 깊이(height, depth): 루트 노드로부터 가장 멀리 떨어진 잎 노드까지의 노드의 개수, 가장 큰 레벨 + 1과 값이 같다. 차수(degree): 노드가 갖는 서브 트리의 수 부모(parent): 하나 이상의 서브 트리를 갖는 노드

백준1107: 리모컨 [내부링크]

1107번: 리모컨 문제 수빈이는 TV를 보고 있다. 수빈이는 채널을 돌리려고 했지만, 버튼을 너무 세게 누르는 바람에, 일부 숫자 버튼이 고장났다. 리모컨에는 버튼이 0부터 9까지 숫자, +와 -가 있다. +를 누르면 현재 보고있는 채널에서 +1된 채널로 이동하고, -를 누르면 -1된 채널로 이동한다. 채널 0에서 -를 누른 경우에는 채널이 변하지 않고, 채널은 무한대 만큼 있다. 수빈이가 지금 이동하려고 하는 채널은 N이다. 어떤 버튼이 고장났는지 주어졌을 때, 채널 N으로 이동하기 위해서 버튼을 최소 몇 번 눌러야하는지 구하는 프로그램을 작성하시... www.acmicpc.net 이 문제는 쉽게 생각할수록 쉬워지고 복잡하게 생각할수록 복잡해지는 문제입니다. 가장 먼저 나이브하게 생각해 보고 그 방법이 제한조건에 의해 안된다면 배운 적이 있는지, 배운 적도 없는 거 같다면 규칙을 찾아보는 방식으로 접근을 해봐야 합니다. 1. Problem Analysis 이 문제는 0~9까지의

[Data Structure]이진트리(Binary Tree) [내부링크]

이진트리(Binary Tree)란? 각각의 노드가 최대 두 개의 자식 노드를 가지는 트리 자료 구조를 의미합니다. 그 각각의 자식 노드를 왼쪽 자식 노드(Left child node), 오른쪽 자식 노드(Right child node)라고 부릅니다. 이 자식 노드들을 서브트리로 볼 수 있습니다. 이진트리는 트리의 일부분이므로 트리에서 사용하는 용어를 동일하게 사용합니다. 크기가 9이고, 높이가 3인 이진 트리 이진트리의 구현(C언어) 이진트리는 트리의 구현을 그대로 차용해서 구현이 가능합니다. 다만 여기서는 배열기반 이진트리는 개요와 한계에 대해서 설명하고 연결리스트 기반 이진트리를 상세히 구현하겠습니다. 배열기반 이진트리의 구현 배열기반 이진트리는 각 노드에 번호를 매겨서 이를 배열에 매핑하는 방식으로 구현합니다. 이에 따라 각 노드들은 규칙성이 있게 배열에 있게 됩니다. 노드 i의 부모 노드는 floor((i-1)/2)에 위치합니다. 노드 i의 왼쪽 자식 노드는 2(i+1)-1에

백준1260: DFS와 BFS [내부링크]

1260번: DFS와 BFS 문제 그래프를 DFS로 탐색한 결과와 BFS로 탐색한 결과를 출력하는 프로그램을 작성하시오. 단, 방문할 수 있는 정점이 여러 개인 경우에는 정점 번호가 작은 것을 먼저 방문하고, 더 이상 방문할 수 있는 점이 없는 경우 종료한다. 정점 번호는 1번부터 N번까지이다. 입력 첫째 줄에 정점의 개수 N(1 ≤ N ≤ 1,000), 간선의 개수 M(1 ≤ M ≤ 10,000), 탐색을 시작할 정점의 번호 V가 주어진다. 다음 M개의 줄에는 간선이 연결하는 두 정점의 번호가 주어진다. 어떤 두 정점 사이에 여러 개의 간선이 있을 수 있다.... www.acmicpc.net 이 문제는 DFS와 BFS를 구현해보는 간단한 구현문제입니다. 1. Problem Analysis 양방향 그래프에서 시작 정점이 주어질 때, DFS와 BFS 탐색을 할 때 탐색 결과를 반환하는 문제입니다. 이때 제한조건은 다음과 같습니다. 정점의 개수 n는 1,000이하의 양의 정수, 간선의

[Data Structure]큐(Queue) [내부링크]

큐(Queue)란? 큐는 대표적인 자료구조 중 하나로 한쪽에서는 데이터의 삽입만, 다른 한쪽에서는 데이터의 삭제만 이루어지는 선형 자료구조를 의미합니다. 이때, 데이터의 삽입(enqueue)이 발생하는 쪽은 후면(rear), 데이터의 삭제(dequeue)가 발생하는 쪽은 전면(front)라고 합니다. 그리고 큐에 저장되는 각 데이터들을 원소(element)라고 부릅니다. 이와 같이 큐에서 꺼내지는 원소는 가장 먼저 삽입된 원소로 먼저 들어간 게 먼저 나온다고 해서 선입선출, FIFO(First in First out) 구조라고 부릅니다. 이는 매우 직관적인 구조로 식당 웨이팅과 동일한 구조라고 생각하시면 됩니다.(예약이 아닌 순수 웨이팅은 무조건 먼저 온 사람이 들어가야만 하죠.) 큐의 대표적인 형태 - 위키피디아 예를 들어, 비어있는 큐에서 2, 7을 enqueue 하고, dequeue를 하면 먼저 삽입한 2가 반환됩니다. 큐 연산의 예시 큐의 구현(C언어) Based on Arr

[Data Structure]스택(Stack) [내부링크]

스택(Stack)이란? 스택은 대표적인 자료구조 중 하나로 목록의 끝에서만 데이터 접근이 가능한 선형 자료구조를 의미합니다. 이때 데이터의 접근이 가능한 부분은 스택의 탑(Top)이라고 부르고, 데이터의 삽입을 밀어 넣는다는 의미에서 푸시(Push), 데이터를 꺼내는 것을 팝(Pop)이라고 부릅니다. 그리고 스택에 저장된 각 데이터들을 원소(Element)라고 부릅니다. 이와 같이 스택에서 꺼내지는 데이터는 가장 최근에 Push한 데이터부터 나온다고 해서 후입선출, LIFO(Last in First Out) 구조라고 부릅니다. 하단의 그림을 보면 쌓인 책과 같은 구조라고 생각하시면 됩니다.(책도 위에 쌓고 위에서 빼죠) 스택의 대표적인 형태 - wikipedia 예를 들어, 비어있는 스택에서 5, 2, 3을 순서대로 Push하고 Pop을 1회 하면 3이 반환됩니다. 그리고 7을 삽입하면 하단과 같은 그림이 나오게 됩니다. 스택 연산 예시 스택의 구현(C언어) Based on Arra

스마트한 터미널 사용 - The Art of Command Line [내부링크]

GitHub - jlevy/the-art-of-command-line: Master the command line, in one page Master the command line, in one page. Contribute to jlevy/the-art-of-command-line development by creating an account on GitHub. github.com 오늘은 재미있는 깃허브 라이브러리를 들고 왔습니다. 이전 문서화 관련 포스트에서 발견한 아주 유용한 포스트입니다. 바로 The Art of Command Line라는 라이브러리입니다. 터미널에서 작업할 때 정말 유용한 명령어나 기능들을 설명하고 있는 오픈소스 라이브러리입니다. 23.12.19 기준 별을 14만 개나 받은 이미 유명한 라이브러리입니다. 그리고 놀랍게도 한국어 번역본도 있습니다. 개발자에게 터미널 개발자가 되기로 했으면 터미널은 뗄레야 뗄 수 없는 관계입니다. 사실 대부분의 사용자가 사용하는

백준1074 : Z [내부링크]

1074번: Z 문제 한수는 크기가 2 N × 2 N 인 2차원 배열을 Z모양으로 탐색하려고 한다. 예를 들어, 2×2배열을 왼쪽 위칸, 오른쪽 위칸, 왼쪽 아래칸, 오른쪽 아래칸 순서대로 방문하면 Z모양이다. N > 1인 경우, 배열을 크기가 2 N-1 × 2 N-1 로 4등분 한 후에 재귀적으로 순서대로 방문한다. 다음 예는 2 2 × 2 2 크기의 배열을 방문한 순서이다. N이 주어졌을 때, r행 c열을 몇 번째로 방문하는지 출력하는 프로그램을 작성하시오. 다음은 N=3일 때의 예이다. 입력 첫째 줄에 정수 N, r, c가 주어진다. 출력 r... www.acmicpc.net 이 문제는 재귀 알고리즘을 이용하면 정말 손쉽게 해결 가능한 문제입니다. 1. Problem Analysis 이 문제는 2^n x 2^n 크기의 정사각형 2차원 배열에서 재귀적으로 탐색해가면서 특정 좌표는 몇 번째로 방문하는지 확인하는 문제입니다. 이때 방문 규칙은 다음과 같습니다. N은 1인 경우 왼쪽

7. 장고 폼 [내부링크]

폼 6. 장고 데이터 저장 부분에서 이미 html 상에서 <form> 태그로 보내진 데이터를 장고 서버에서 다루는 법에 대해서 다뤘었습니다. 이와 같이 클라이언트에서 서버로 데이터를 보내게 하는 것이 바로 폼의 역할입니다. 그런데 장고에서도 폼이라는 기능이 있습니다. 이에 대해서 알아보도록 하겠습니다. 6. 장고 데이터 저장 장고 데이터 저장 사실 장고에서 데이터를 생성하고 저장하는 부분은 3. 장고 모델 부분에서 이미 다뤘었습... blog.naver.com 장고 폼 장고 폼은 쉽게 말해 페이지 요청 시 전달되는 파라미터들을 쉽게 관리하기 위해 사용하는 클래스를 의미합니다. 여기서 핵심은 파라미터들을 쉽게 관리한다, 다시 말해 모델 필드에 대한 값들을 쉽게 관리한다는 것입니다. 간단한 사용 예제와 함께 확인해 보겠습니다. 사용하기 전에 장고 폼을 사용하려는 장고 앱에서 forms.py 파일을 생성해야 합니다. 그리고 폼 클래스를 생성해 폼이 다룰 모델과 필드들을 지정해 줍니다. 다

백준1012: 유기농 배추 [내부링크]

1012번: 유기농 배추 문제 차세대 영농인 한나는 강원도 고랭지에서 유기농 배추를 재배하기로 하였다. 농약을 쓰지 않고 배추를 재배하려면 배추를 해충으로부터 보호하는 것이 중요하기 때문에, 한나는 해충 방지에 효과적인 배추흰지렁이를 구입하기로 결심한다. 이 지렁이는 배추근처에 서식하며 해충을 잡아 먹음으로써 배추를 보호한다. 특히, 어떤 배추에 배추흰지렁이가 한 마리라도 살고 있으면 이 지렁이는 인접한 다른 배추로 이동할 수 있어, 그 배추들 역시 해충으로부터 보호받을 수 있다. 한 배추의 상하좌우 네 방향에 다른 배추가 위치한 경우에 서로 인접해있는 것... www.acmicpc.net 이 문제는 유명한 탐색 문제이다. 1. Problem Analysis 이 문제는 nxm 크기의 밭에서 유기농법으로 배추를 키울 때 해충을 잡아잡아먹는 지렁이를 최소 몇마리 키워야 하는지를 구해야하는 문제이다. 이때 지렁이를 키우는 조건은 다음과 같다. 지렁이는 상하좌우 한 칸에 인접한 배추로 이동

6. 장고 데이터 저장 [내부링크]

장고 데이터 저장 사실 장고에서 데이터를 생성하고 저장하는 부분은 3. 장고 모델 부분에서 이미 다뤘었습니다. 여기서 알아볼 부분은 관리자 입장에서 생성한 데이터가 아니라 클라이언트가 브라우저를 통해 생성한 데이터를 장고 데이터베이스에 저장하는 방법에 대해서 알아볼 것입니다. 사실 웹 개발에 대해서 아는 사람들은 html 상에 <form> 태그를 사용하면 되는 것을 알 겁니다. 그렇다면 한 번 Answer 데이터를 생성하는 폼을 만들어보겠습니다.  <h3>{{ question.subject }} 답변생성</h3> <form action="{% url 'my_django_app1:answer_create' question.id %}" method="post"> {% csrf_token %} # POST 요청에서의 보안 문제 처리 <textarea name="content" id="content" rows="15"></texta

개발자의 덕목 - Documetation, 문서화 [내부링크]

흥미로운 깃허브 Topic - Documentation 깃허브 문서화 주제 오늘 깃허브를 둘러보다가 Documentation Topic이 있는 것을 보고 흥미롭다는 생각을 갖고 접근했다. 원래 Documentation은 개발자에게 매우 소중한 덕목 중 하나이다. 아무리 본인이 코드를 잘 짠다고 하더라도 이를 남들에게 알리지 않는 한 이는 개인 소장용일뿐이다. 작성한 코드를 공개한다고 하더라도 이에 대해서 잘 설명해 주지 않는 이상 남들이 내 코드가 어떤 기능을 하는지, 무슨 목적이 있는지 등을 알기란 어렵다. 이런 점에서 이 코드가 다른사람들에게 사용되기란 요원하다. 그리고 세상에 발을 내디디려는 개발자로서는 내가 만든 프로그램이 어떤 목적을 갖고 만들어졌는지, 어떤 기능들이 있는지, 어떻게 사용해야 하는지, 어떤 기술을 기반으로 작성되었는지 등을 상세히 작성해 줘야지만 다른 사람들이 이 코드를 보고 리뷰를 해주고 어떤 부분에서는 본인보다 뛰어난 실력자가 나타나 도움을 줄 수도 있다

aaa092dbea724aa1be083907060a0536 [내부링크]

5. 장고 템플릿 [내부링크]

템플릿 웹에서 템플릿은 사용자에게 보이는 웹 페이지의 구조와 내용 정도를 의미한다고 보면 됩니다. 예를 들자면 웹 개발에서 html 문서 작성 부분을 생각하면 됩니다. 웹에서 html은 빼놓을 수 없는 핵심적인 부분입니다. 장고 템플릿 장고에서 템플릿은 기본 웹에서의 템플릿과 유사합니다. 다만, 장고가 파이썬으로 작성된 것을 감안해 장고가 해석하는 html 문서 내에서는 파이썬 스타일의 코드 실행이 가능합니다. 다시 말해, 조건문, 반복문 같은 것이 사용 가능하다는 의미입니다. 장고 템플릿은 'config/settings.py'에 관련 설정이 있는 것을 확인할 수 있습니다. 추가로 DIRS 키에 대한 값으로 템플릿 파일들을 관리하는 경로를 설정할 수 있습니다. 기본적으로는 공백인데, 이는 각 장고 앱의 templates 폴더를 의미합니다. 'my_django_app1/templates' 폴더를 의미합니다. 다시 말해 기본 설정은 각 장고 앱에 대한 템플릿 파일들을 각각 관리하는 것입

1. 장고 시작하기 [내부링크]

장고 설치하기 개인적인 추천으로는 본인의 스타일에 맞는 파이썬 가상환경을 설치한 이후, 가상환경을 실행한 뒤 다음 명령어를 터미널에 입력해 장고 라이브러리를 설치해 주도록 합니다. > pip install django // 장고 라이브러리 설치 > python -m django --version // 설치된 라이브러리 버전 확인 x.x.x // 좌측과 같은 출력이 나오면 정상적으로 설치 완료. 장고 프로젝트 만들기 장고 라이브러리를 설치한 이후, 장고 프로젝트를 생성하기 위해서 다음과 같은 명령어를 터미널에 입력해 주면 됩니다. // 장고 프로젝트 생성하기 > mkdir <django_project_name> // 장고 프로젝트를 시작할 폴더 생성 > cd <django_project_name> // 장고 프로젝트를 시작할 폴더로 이동 > django-admin startproject config . // 장고 프로젝트 폴더 내에 config 폴더 생성 위 명령어를 이용하면 다음과

2. 장고 URL과 View [내부링크]

URL URL은 웹주소라고도 부릅니다. 이는 URL에 따라서 다른 건물, 즉 다른 기능을 한다는 의미로 받아들일 수 있습니다. 웹 개발은 이 각 URL에 따라서 작동해야 하는 기능, 웹페이지 등을 설계하고 작동하도록 만드는 것을 의미합니다. 다시 말해, 각 URL에 따라서 어떤 기능을 해야 하는지를 각각 연결해 줘야 합니다. 이를 URL 매핑이라고 합니다. 장고 View 장고 앱 폴더에 있는 'views.py'가 바로 해당 장고 앱에 맞는 웹페이지를 만드는 곳입니다. 현재로서는 파일 내에 아무것도 작성되어 있지 않습니다. 가장 먼저 웹페이지에 "Hello Django"를 출력해 봅시다. # my_django_app1/views.py from django.shortcuts import HttpResponse def index(request): return HttpResponse('Hello Django') 위는 장고 서버에서 index view를 요청하면 'Hello Django'를

3. 장고 모델 [내부링크]

장고 데이터베이스 장고는 기본 데이터베이스로 SQLite3를 사용하고 있습니다. 이는 'config/settings.py'를 확인해 보면 알 수 있습니다. # config/settings.py 일부분 DATABASES = { 'default': { 'ENGINE': 'django.db.backends.sqlite3', 'NAME': BASE_DIR / 'db.sqlite3', } } SQLite3는 이름 그대로 가볍게 사용하기 좋은 데이터베이스입니다. 메모리 사용 면에서, 용량적인 면에서, 그리고 무료로 사용 가능하다는 점에서도 이점입니다. 심지어는 파이썬에서는 내장 라이브러리에서 splite3를 지원하기 때문에 별도 설치의 과정도 필요 없습니다. 하지만, 장고 공식 문서에 따르면 주후 데이터베이스 교체를 용이하게 하기 위해서라도 좀 더 확장성 있는 데이터베이스 사용을 권장하고 있습니다. 단순 권장할 뿐만 아니라 PostgreSQL, MariaDB, MySQL, Oracle, 그리고

4. 장고 관리자 [내부링크]

관리자 사이트 관리자 사이트란 해당 웹사이트의 관리자가 사이트를 설정하고, 회원관리, 주문/배송 관리, 도메인 연결, 전자결제(PG) 설정 등을 관리하는 사이트를 의미합니다. 장고 공식 문서에 따르면 이런 관리자 사이트를 만드는 것은 창의적이지 못한 지루한 작업이라고 얘기하고 있습니다. 이런 철학을 배경으로 장고는 기본적으로 모델에 대한 관리용 인터페이스를 자동으로 생성합니다. 장고 관리자 먼저 관리자 계정을 생성해 보겠습니다. 다음과 같은 명령어를 터미널에 입력하면 생성할 수 있습니다. // 관리자 계정 생성하기 > python manage.py createsuperuser Username: admin Email address: [email protected] Password: ************* Password (again): ************* Superuser created successfully. 이제 장고 서버를 실행해 관리자 페이지로 이동해 보겠습니다. 로컬 서버

백준1003: 피보나치 함수 [내부링크]

1003번: 피보나치 함수 문제 다음 소스는 N번째 피보나치 수를 구하는 C++ 함수이다. int fibonacci(int n) { if (n == 0) { printf("0"); return 0; } else if (n == 1) { printf("1"); return 1; } else { return fibonacci(n‐1) + fibonacci(n‐2); } } fibonacci(3) 을 호출하면 다음과 같은 일이 일어난다. fibonacci(3) 은 ... www.acmicpc.net 이 문제는 주어진 소스코드를 이용해서 규칙을 찾아 푸는 문제입니다. 1. Problem Analysis 이 문제는 피보나치 수열을 재귀적으로 구하는 함수에서 n 번째 원소를 구하기 위해 n=0, n=1 인 경우가 호출된 횟수를 구하는 문제입니다. 추가적으로 이 문제는 다음과 같은 제한조건을 갖습니다. 각 테스트케이스는 T 개의 하위 테스트케이스를 갖는다. 각 하위 테스트케이스는 n(0<=n<=

백준2609: 최대공약수와 최소공배수 [내부링크]

2609번: 최대공약수와 최소공배수 2609번 제출 맞힌 사람 숏코딩 재채점 결과 채점 현황 강의 질문 게시판 최대공약수와 최소공배수 시간 제한 메모리 제한 제출 정답 맞힌 사람 정답 비율 1 초 128 MB 103983 59918 48716 57.858% 문제 두 개의 자연수를 입력받아 최대 공약수와 최소 공배수를 출력하는 프로그램을 작성하시오. 입력 첫째 줄에는 두 개의 자연수가 주어진다. 이 둘은 10,000이하의 자연수이며 사이에 한 칸의 공백이 주어진다. 출력 첫째 줄에는 입력으로 주어진 두 수의 최대공약수를, 둘째 줄에는 입력으로 주어진 두 수의 최소 공배... www.acmicpc.net 이 문제는 프로그래밍 언어에 따라 내장함수가 있어 쉽게 풀 수도 있는 문제입니다. 하지만, 공부하는 단계에서는 직접 구현해 보는 것이 좋은 문제입니다. 1. Problem Analysis 이 문제를 풀기 위해서는 최대공약수와 최소공배수가 무엇인지 알아야 합니다. 최대공약수 : 여러 수의

백준2775: 부녀회장이 될테야 [내부링크]

2775번: 부녀회장이 될테야 2775번 제출 맞힌 사람 숏코딩 재채점 결과 채점 현황 질문 게시판 부녀회장이 될테야 시간 제한 메모리 제한 제출 정답 맞힌 사람 정답 비율 0.5 초 (추가 시간 없음) 128 MB 97389 54622 46451 57.219% 문제 평소 반상회에 참석하는 것을 좋아하는 주희는 이번 기회에 부녀회장이 되고 싶어 각 층의 사람들을 불러 모아 반상회를 주최하려고 한다. 이 아파트에 거주를 하려면 조건이 있는데, “a층의 b호에 살려면 자신의 아래(a-1)층의 1호부터 b호까지 사람들의 수의 합만큼 사람들을 데려와 살아야 한다” 는 ... www.acmicpc.net 이 문제는 수학적 관계식이 문제에 드러나있어 이를 구현하기만 하면 되는 문제입니다. 1. Problem Analysis 이 문제는 어떤 아파트 n층 k호실에는 사람이 몇 명 사는지를 구하는 문제입니다. 이때, 이 아파트에는 다음과 같은 규칙으로 사람이 살고 있다고 합니다. 0층 i호실에는 i

백준18110: solved.ac [내부링크]

18110번: solved.ac 문제 solved.ac 는 Sogang ICPC Team 학회원들의 알고리즘 공부에 도움을 주고자 만든 서비스이다. 지금은 서강대뿐만 아니라 수많은 사람들이 solved.ac의 도움을 받아 알고리즘 공부를 하고 있다. ICPC Team은 백준 온라인 저지에서 문제풀이를 연습하는데, 백준 온라인 저지의 문제들에는 난이도 표기가 없어서, 지금까지는 다양한 문제를 풀어 보고 싶더라도 난이도를 가늠하기 어려워 무슨 문제를 풀어야 할지 판단하기 곤란했기 때문에 solved.ac가 만들어졌다. solved.ac가 생긴 이후 전국에서 200명 ... www.acmicpc.net 이 문제는 프로그래밍 언어상에서 구현된 반올림을 주의해야 하는 문제입니다. 관련하여 하단의 포스팅을 확인해 보시기 바랍니다. 백준2108: 통계학 이 문제는 컴퓨터상에서 반올림을 주의해야 하는 문제입니다. 1. Problem Analysis 이 문제는 주어지는 ... blog.naver.c

백준18111: 마인크래프트 [내부링크]

18111번: 마인크래프트 문제 팀 레드시프트는 대회 준비를 하다가 지루해져서 샌드박스 게임인 ‘마인크래프트’를 켰다. 마인크래프트는 1 × 1 × 1(세로, 가로, 높이) 크기의 블록들로 이루어진 3차원 세계에서 자유롭게 땅을 파거나 집을 지을 수 있는 게임이다. 목재를 충분히 모은 lvalue는 집을 짓기로 하였다. 하지만 고르지 않은 땅에는 집을 지을 수 없기 때문에 땅의 높이를 모두 동일하게 만드는 ‘땅 고르기’ 작업을 해야 한다. lvalue는 세로 N , 가로 M 크기의 집터를 골랐다. 집터 맨 왼쪽 위의 좌표는 (0, 0)이다. 우리의 목적은 이... www.acmicpc.net 이 문제는 문제 풀이에 사용한 알고리즘에 따라 구현이 까다로울 수 있는 문제입니다. 1. Problem Analysis 이 문제는 (m, n) 크기의 영역에 집을 짓기 위한 땅고르기 작업(영역의 땅의 높이를 동일하게 만드는 작업)을 할 때 걸리는 최소 시간과 그때의 높이를 구하는 문제입니다. 이

장고(Django) [내부링크]

장고란? 장고는 웹 프로그램을 쉽게 만들 수 있게 해주는 파이썬 웹프레임워크 중 하나이다. 간단하게 설명하자면, 웹프레임워크는 웹페이지 구현에 필요한 기본적인 기능들이 내장되어 있는 키트를 의미한다. 예를 들자면, 쿠키처리, 로그인 처리, 로그아웃 처리, 데이터베이스 처리, 그 이외에도 관리자페이지 등등이 기본적으로 구현이 되어 있다. 즉, 장고를 사용한다면 웹페이지의 필수기능들을 조금 더 쉽게 구현이 가능할 수 있다. 장고는 보안에 대해서 여러가지 기능을 갖고 있어, 보안 공격에 대한 안정성을 보장하려 하고 있다. 크로스 사이트 스크립팅(XSS) 보호 교차 사이트 요청 위조(CSRF) 보호 SQL 삽입(SQL Injection) 방지 클릭재킹(Clickjacking) 방지 SSL/HTTPS 호스트 헤더 유효성 검사 장고 서버의 원리 장고 서버는 다음 그림과 같은 방식으로 작동한다. 목차 장고 시작하기 장고 URL과 뷰 장고 모델 장고 관리자 장고 템플릿 장고 데이터 저장 장고 폼

백준1929: 소수 구하기 [내부링크]

1929번: 소수 구하기 1929번 제출 맞힌 사람 숏코딩 재채점 결과 채점 현황 강의 질문 게시판 소수 구하기 시간 제한 메모리 제한 제출 정답 맞힌 사람 정답 비율 2 초 256 MB 260286 76089 53493 27.278% 문제 M이상 N이하의 소수를 모두 출력하는 프로그램을 작성하시오. 입력 첫째 줄에 자연수 M과 N이 빈 칸을 사이에 두고 주어진다. (1 ≤ M ≤ N ≤ 1,000,000) M이상 N이하의 소수가 하나 이상 있는 입력만 주어진다. 출력 한 줄에 하나씩, 증가하는 순서대로 소수를 출력한다. 예제 입력 1 복사 3 16 예제 ... www.acmicpc.net 이 문제는 소수와 관련된 매우 유명한 문제입니다. 1. Problem Analysis - 이 문제는 [m, n] 범위의 자연수 중에서 소수인 수들을 출력해야 하는 문제입니다. - 먼저 소수의 정의는 수학적으로 "1과 자기 자신만을 약수로 갖는 1보다 큰 수"를 의미합니다. 이때 소수는 정의에 약수

백준2108: 통계학 [내부링크]

2108번: 통계학 문제 수를 처리하는 것은 통계학에서 상당히 중요한 일이다. 통계학에서 N개의 수를 대표하는 기본 통계값에는 다음과 같은 것들이 있다. 단, N은 홀수라고 가정하자. 산술평균 : N개의 수들의 합을 N으로 나눈 값 중앙값 : N개의 수들을 증가하는 순서로 나열했을 경우 그 중앙에 위치하는 값 최빈값 : N개의 수들 중 가장 많이 나타나는 값 범위 : N개의 수들 중 최댓값과 최솟값의 차이 N개의 수가 주어졌을 때, 네 가지 기본 통계값을 구하는 프로그램을 작성하시오. 입력 첫째 줄에 수의 개수 N(1 ≤ N ≤ 500,000)이 주어... www.acmicpc.net 이 문제는 컴퓨터상에서 반올림을 주의해야 하는 문제입니다. 1. Problem Analysis 이 문제는 주어지는 숫자로부터 4가지 통계학적 수치를 구하는 문제입니다. 문제 조건에 의하면 다음을 구하면 됩니다. 산술평균(Mean) : N개의 수들의 합을 N으로 나눈 값을 소수 첫째 자리에서 반올림한 수

백준2292: 벌집 [내부링크]

2292번: 벌집 2292번 제출 맞힌 사람 숏코딩 재채점 결과 채점 현황 질문 게시판 벌집 시간 제한 메모리 제한 제출 정답 맞힌 사람 정답 비율 2 초 128 MB 165790 74928 63751 44.756% 문제 위의 그림과 같이 육각형으로 이루어진 벌집이 있다. 그림에서 보는 바와 같이 중앙의 방 1부터 시작해서 이웃하는 방에 돌아가면서 1씩 증가하는 번호를 주소로 매길 수 있다. 숫자 N이 주어졌을 때, 벌집의 중앙 1에서 N번 방까지 최소 개수의 방을 지나서 갈 때 몇 개의 방을 지나가는지(시작과 끝을 포함하여)를 계산하는 프로그램을 ... www.acmicpc.net 위 문제는 수수께끼를 풀듯이 접근해야 하는 문제입니다. 이런 문제는 규칙을 찾는 것이 핵심입니다. 이를 찾으면 해결할 수 있지만, 찾지 못하면 풀지 못합니다. 1. Problem Analysis 이 문제는 각각의 벌집칸에 번호가 규칙에 따라 주어질 때, 이때 n번 벌집칸으로 가는 최소이동칸 수를 구하는

백준1920: 수 찾기 [내부링크]

1920번: 수 찾기 1920번 제출 맞힌 사람 숏코딩 재채점 결과 채점 현황 질문 게시판 수 찾기 시간 제한 메모리 제한 제출 정답 맞힌 사람 정답 비율 1 초 128 MB 235921 72104 47945 29.827% 문제 N개의 정수 A[1], A[2], …, A[N]이 주어져 있을 때, 이 안에 X라는 정수가 존재하는지 알아내는 프로그램을 작성하시오. 입력 첫째 줄에 자연수 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 줄에는 N개의 정수 A[1], A[2], …, A[N]이 주어진다. 다음 줄에는 M(1 ≤ M ≤ 100,000)이 주어... www.acmicpc.net - 이 문제는 대표적인 탐색문제입니다. 1. Problem Analysis - 이 문제는 2개의 정수 배열이 주어지는데, 나중에 주어지는 정수배열에 있는 원소들이 먼저 주어지는 정수배열에 포함되어있는지를 확인하는 문제입니다. 이는 탐색과 관련된 문제입니다. - 먼저 브루트포스 스타일로 생각해봅시다.

백준1546: 평균 [내부링크]

1546번: 평균 문제 세준이는 기말고사를 망쳤다. 세준이는 점수를 조작해서 집에 가져가기로 했다. 일단 세준이는 자기 점수 중에 최댓값을 골랐다. 이 값을 M이라고 한다. 그리고 나서 모든 점수를 점수/M*100으로 고쳤다. 예를 들어, 세준이의 최고점이 70이고, 수학점수가 50이었으면 수학점수는 50/70*100이 되어 71.43점이 된다. 세준이의 성적을 위의 방법대로 새로 계산했을 때, 새로운 평균을 구하는 프로그램을 작성하시오. 입력 첫째 줄에 시험 본 과목의 개수 N이 주어진다. 이 값은 1000보다 작거나 같다. 둘째 줄에 세준이의 현... www.acmicpc.net 백준 1546은 부동소수점 출력과 관련된 간단한 연산문제입니다. 1. Problem Analysis 이 문제는 어려운 문제는 아닙니다. 점수들 중 최댓값을 찾고, 이를 100점으로 가정했을 때의 상대적인 점수를 계산하고 결론적으로 이 점수들의 평균을 출력하는 문제입니다. 상대적인 점수는 문제에 주어진 바

백준1654: 랜선 자르기 [내부링크]

1654번: 랜선 자르기 1654번 제출 맞힌 사람 숏코딩 재채점 결과 채점 현황 강의 질문 게시판 랜선 자르기 시간 제한 메모리 제한 제출 정답 맞힌 사람 정답 비율 2 초 128 MB 198784 46723 31606 21.220% 문제 집에서 시간을 보내던 오영식은 박성원의 부름을 받고 급히 달려왔다. 박성원이 캠프 때 쓸 N개의 랜선을 만들어야 하는데 너무 바빠서 영식이에게 도움을 청했다. 이미 오영식은 자체적으로 K개의 랜선을 가지고 있다. 그러나 K개의 랜선은 길이가 제각각이다. 박성원은 랜선을 모두 N개의 같은 길이의 랜선으로 만들고 싶었기 때... www.acmicpc.net 위 문제는 문제 제한조건에 의해서 선형탐색 알고리즘을 사용하지 못하는 문제입니다. 그러므로 다른 방법을 생각해봐야하는 문제입니다. 1. Problem Analysis 이 문제는 주어진 랜선들을 잘라 목표 개수 이상으로 만들 때, 최대 랜선의 길이를 구하는 문제입니다. 여기서 다름과 같은 관계를 찾

백준1874: 스택 수열 [내부링크]

1874번: 스택 수열 문제 스택 (stack)은 기본적인 자료구조 중 하나로, 컴퓨터 프로그램을 작성할 때 자주 이용되는 개념이다. 스택은 자료를 넣는 (push) 입구와 자료를 뽑는 (pop) 입구가 같아 제일 나중에 들어간 자료가 제일 먼저 나오는 (LIFO, Last in First out) 특성을 가지고 있다. 1부터 n까지의 수를 스택에 넣었다가 뽑아 늘어놓음으로써, 하나의 수열을 만들 수 있다. 이때, 스택에 push하는 순서는 반드시 오름차순을 지키도록 한다고 하자. 임의의 수열이 주어졌을 때 스택을 이용해 그 수열을 만들 수 있는지 없는지... www.acmicpc.net 위 문제는 직접 그림 그리면서 주어진 예제를 풀어보면 쉽게 풀 수 있는 문제입니다. 1. Problem Analysis 이 문제는 스택 자료구조를 이용해 1부터 n까지의 수를 차례대로 넣고 뺏을 때 주어진 수열이 나올 수 있는지에 대한 문제입니다. 먼저 브루트포스를 생각해봅시다. n개의 정수에 대해

백준1436: 영화감독 숌 [내부링크]

1436번: 영화감독 숌 문제 666은 종말을 나타내는 수라고 한다. 따라서, 많은 블록버스터 영화에서는 666이 들어간 제목을 많이 사용한다. 영화감독 숌은 세상의 종말 이라는 시리즈 영화의 감독이다. 조지 루카스는 스타워즈를 만들 때, 스타워즈 1, 스타워즈 2, 스타워즈 3, 스타워즈 4, 스타워즈 5, 스타워즈 6과 같이 이름을 지었고, 피터 잭슨은 반지의 제왕을 만들 때, 반지의 제왕 1, 반지의 제왕 2, 반지의 제왕 3과 같이 영화 제목을 지었다. 하지만 숌은 자신이 조지 루카스와 피터 잭슨을 뛰어넘는다는 것을 보여주기 위해서 영화 제목을 좀 ... www.acmicpc.net 백준 1436번은 생각을 복잡하게 할 수록 어려워지는 문제입니다. 언제나 브루트포스를 가장 먼저 생각해봅시다. 1. Problem analysis - 이 문제는 666이라는 숫자가 중간에 들어가는 숫자들(666, 1666, 2666, ...), 종말의 수들을 오름차순으로 찾았을 때 n번째 숫자를

[선형대수학2-2]행렬의 역(The Inverse of a Matrix) [내부링크]

역행렬(Inverse of Matrix) ▷ 가역행렬(Invertible Matrix) - If: nxn행렬 A, C가 AC=I, CA=I이면, Then: 행렬 A는 가역행렬이다. 이때 C=A-1로 A의 역행렬이다. - 가역행렬은 다른 말로 비특이행렬(nonsingular matrix)라고 부른다. (Example) ▷ 2x2 가역행렬(2x2 Invertible) - 이때 ad-bc를 행렬식(determinant)라고 부른다.det(A)=ad-bc ▷ 가역행렬의 유일성 - If A가 가역행렬이다. Then Ax=b는 유일해 x=A-1b를 갖는다. (Example) Use the inverse of a matrix to solve the system 3x1+4x2=3 5x1+6x2=7 ▷ 가역행렬의 특성 a. If A는 가역행렬이다. Then A-1은 가역행렬. and (A-1)-1=A b. If A, B는 nxn 가역행렬이다. Then (AB)-1=B-1A-1 c. If A는 가역

백준1018: 체스판 다시 칠하기 [내부링크]

1018번: 체스판 다시 칠하기 문제 지민이는 자신의 저택에서 MN개의 단위 정사각형으로 나누어져 있는 M×N 크기의 보드를 찾았다. 어떤 정사각형은 검은색으로 칠해져 있고, 나머지는 흰색으로 칠해져 있다. 지민이는 이 보드를 잘라서 8×8 크기의 체스판으로 만들려고 한다. 체스판은 검은색과 흰색이 번갈아서 칠해져 있어야 한다. 구체적으로, 각 칸이 검은색과 흰색 중 하나로 색칠되어 있고, 변을 공유하는 두 개의 사각형은 다른 색으로 칠해져 있어야 한다. 따라서 이 정의를 따르면 체스판을 색칠하는 경우는 두 가지뿐이다. 하나는 맨 왼쪽 위 칸이 흰색인 경우, 하나... www.acmicpc.net 문제 1018은 단순히 읽어보고 고민만 해서 푸는 문제가 아니라 일단 무식하게 도전해보면 풀 수 있는 문제입니다. 1. Problem analysis - 이 문제는 임의의 보드판을 8x8 사이즈 체스보드판으로 만들 때 최소 색칠 cost가 얼마인지 찾는 문제입니다. 어떻게 풀지를 단순하게

백준1181: 단어 정렬 [내부링크]

1181번: 단어 정렬 1181번 제출 맞힌 사람 숏코딩 재채점 결과 채점 현황 질문 게시판 단어 정렬 시간 제한 메모리 제한 제출 정답 맞힌 사람 정답 비율 2 초 256 MB 165123 69103 51798 40.339% 문제 알파벳 소문자로 이루어진 N개의 단어가 들어오면 아래와 같은 조건에 따라 정렬하는 프로그램을 작성하시오. 길이가 짧은 것부터 길이가 같으면 사전 순으로 단, 중복된 단어는 하나만 남기고 제거해야 한다. 입력 첫째 줄에 단어의 개수 N이 주어진다. (1 ≤ N ≤ 20,000) 둘째 줄부터 N개의 줄에 걸쳐 알파벳 소문자로 이루... www.acmicpc.net 문제 1181은 문제에 적혀있는 정렬과 관련된 문제입니다. 정확히는 정렬기준에 대한 문제입니다. 1. Problem analysis - 문제는 다음과 같은 조건을 만족하도록 입력받는 단어들을 정렬하면 된다고 합니다. 1. 길이가 짧은 것부터 2. 길이가 같으면 사전 순으로 - 즉, 길이를 기준으로

백준1259: 팰린드롬 수 [내부링크]

1259번: 팰린드롬수 1259번 제출 맞힌 사람 숏코딩 재채점 결과 채점 현황 질문 게시판 팰린드롬수 다국어 시간 제한 메모리 제한 제출 정답 맞힌 사람 정답 비율 1 초 128 MB 55531 31591 27864 57.178% 문제 어떤 단어를 뒤에서부터 읽어도 똑같다면 그 단어를 팰린드롬이라고 한다. 'radar', 'sees'는 팰린드롬이다. 수도 팰린드롬으로 취급할 수 있다. 수의 숫자들을 뒤에서부터 읽어도 같다면 그 수는 팰린드롬수다. 121, 12421 등은 팰린드롬수다. 123, 1231은 뒤에서부터 읽으면 다르므로 팰린드롬수가 아니다. ... www.acmicpc.net - 백준 1259는 주어지는 문자열이 뒤집어도 처음과 동일한지 아닌지를 확인하는 문제입니다. 1. Problem analysis - 이 문제는 입력으로 수가 주어집니다. 그런데, 앞과 뒤가 같은지를 쉽게 비교하기 위해서 이를 숫자로 저장하면 불편할 것으로 예상됩니다.(몇 자리 수인지, 맨 앞과 맨

[선형대수학2-1]Matrix Operations(행렬 연산) [내부링크]

▷ 대각 행렬(Diagonal Matrix) - 정사각형 행렬에서 대각원소를 제외한 모든 원소가 0인 행렬 - 이때 영이 아닌 원소들을 대각 원소(diagonal entry)라고 부른다. - 대각 행렬에서 대각 원소들을 주대각선(main diagonal)이라 부른다. 합과 스칼라 배(Sums and Scalar Multiples) ▷ 행렬의 동치(equal) - 행렬의 크기가 같고 대응되는 원소들이 같은 경우 ▷ 행렬의 합(sum) - 두 행렬의 크기가 같을 경우 두 행렬의 합은 대응되는 원소들의 합으로 구성된다. (Example) ▷ 스칼라 배(scalr multiple) - 행렬 A에 스칼라 r을 곱하면 A의 각각의 원소에 r을 곱한 것과 같다. (Example) Let A, B, and C be matrices of the same size, and let r and s be scalars. a. A+B = B+A d. r(A+B) = rA+rB b. (A+B)+C = A+(

[선형대수학1-6]Linear Independence(선형 독립) [내부링크]

선형 독립(Linear Independence) Let {v1, ... , vp}는 Rn상의 벡터 집합이다. ▷ 선형 종속(Linear Dependence) - 동차 행렬(homogeneous matrix)의 해가 비자명해인 경우 벡터 집합은 선형 종속이다. x1v1+x2v2+...+xpvp=0의 해가 자명해 ▷ 선형 독립(Linear Independence) - 동차 행렬의 해가 자명해인 경우 벡터 집합은 선형 독립이다. x1v1+x2v2+...+xpvp=0의 해가 비자명해, =>c1v1+c2v2+...+cpvp=0, where xi=ci for i∈[1,p] ▷ 선형 종속 관계 - 벡터 집합이 선형 종속일 때 동차 행렬의 벡터 방정식 꼴 'c1v1+c2v2+...+cpvp=0'을 선형 종속 관계라 부른다. (Example) Let v1=[1 2 3]T, v2=[4 5 6]T, and v3=[2 1 0]T. a) Determine if the set {v1, v2, v3} is

[선형대수학1-7]Introduction to Linear Transformations(선형 변환 개론) [내부링크]

선형 변환 용어(Basic Terminology of Linear Transformation) ▷ 변환 T(Transformation T) Let 행렬 방정식 Ax=b, where A의 크기는 (mxn)이다. Then, Rn에서 Rm으로 가는 변환 T는 Rn인 벡터 x에서 Rm인 벡터 T(x)를 의미한다. ▷ 정의역(Domain) - 위 정의에서 집합 Rn ▷ 공역(Codomain) - 위 정의에서 집합 Rm ▷ 이미지(Image) - 위 정의에서 x에 대한 벡터 T(x) ▷ 치역(Range) - 모든 이미지 T(x)의 집합 행렬 변환 - T(x)=Ax(= x |-> Ax)로 변하는 변환을 행렬변환이라 부른다. 선형 변환 ▷ 선형 변환의 정의(Definition of Linear Transformation) - vector addition과 scalar multiplication이 성립하면 변환 T는 선형변환이다. * vector addition: T(u+v)=T(u)+T(v)

[선형대수학1-4]The Matrix Equation(행렬 방정식) [내부링크]

행렬 방정식(Matrix Equation) - mxn 행렬 A와 n차원 벡터 x의 곱은 선형결합으로 표현할 수 있다. - 이때 Ax=b꼴을 행렬 방정식이라 부른다. (example) Ax=b의 3가지 표현 형식 ▷ 행렬 방정식 ▷ 벡터 방정식 ▷ 선형 방정식 시스템 해의 존재성(Existence of Solution) - Matrix equation Ax=b가 해 집합을 갖고 있다 ⇔ b는 A의 열에 대한 선형 결합이다. (Example) ▷ Theorem Let A는 mxn 행렬. Then, 다음 문장들은 논리적으로 상등하다. 1. m차원 벡터 b에 대해, Ax=b는 해를 갖는다. 2. m차원 벡터 b는 A의 열의 선형결합이다. 3. A의 열들은 SpanRm이다. 4. A는 모든 행에 피벗 위치를 갖는다. Ax의 계산(Computation of Ax) ▷ Ax 계산에서의 행-벡터 법칙(Row-Vector Rule for Computing Ax) - If Ax의 곱이 정의되었

[Data Structure]연결 리스트(Linked List) [내부링크]

연결 리스트 - 같은 타입의 원소들을 저장하는 선형 집합 - 간단하게 각각의 원소들을 저장하는 구조체들의 연속으로 이해하면 된다. 데이터 구조체 - 데이터를 담는 구조체 node와, 그 구조체들을 가리키는 구조체 LinkedList가 필요하다. typedef int Data; typedef struct _node { Data item; struct _node *next; } Node; typedef struct { Node *head; int len; } LinkedList; 연결 리스트 연산 ▷ initList - 리스트 구조체의 값들을 초기화한다. void initList(LinkedList *plist) { // make a list empty // // create a dummy node // plist->head = (Node *)malloc(sizeof(Node)); plist->head->next = NULL; plist->len = 0; } ▷ isEmpty -

[선형대수학1-5]Solution Sets of Linear Systems(선형시스템의 해 집합) [내부링크]

동차 선형 시스템(Homogeneous Linear Systems) - Ax=b에서 b=0인 선형 시스템, 즉 Ax=0인 시스템 ▷ 자명해 - 동차 선형 시스템에서 x=0인 해 ▷ 바자명해 - 동차 선형 시스템에서 x≠0인 해 ▷ Theorem - 동차 선형 시스템은 항상 자명해를 가지고 있으며 비자명해도 갖고 있다. ⇔ 최소 1개의 자유 변수를 갖고 있다. (Example) Determine if the following homogeneous system has a nontrivial solution. Then describe the solution set. 매개변수의 벡터 꼴(Parametric Vector Form) - 동차 시스템에서 해집합은 원점을 지나는 도형으로 표현할 수 있다. (Example) A single linear equation can be treated as a very simple system of equations. Describe all soluti

[Data Structure]연결 리스트 발전편(Linked List Advanced) [내부링크]

순환 연결 리스트(Circular Linked List) - 마지막 노드가 첫번째 노드를 가리키는 형태의 연결 리스트. - 위의 그림과 같은 구조를 생각하실 수 있을 겁니다. 그런데, dummy 노드가 있는 형태에 익숙하시다면, 위 구조물은 오히려 다루기 어려우실 수 있습니다. 그래서 생각한게 tail 포인터 입니다. 아래와 같은 방식으로 구현하면 tail포인터는 마지막 노드를 dummy 노드로 사용하는 것을 생각하실 수 있습니다. typedef struct { int len; Node *tail; } LinkedList; 양방향 연결 리스트(Double Linked List) - 앞선 연결 리스트의 구현방식에서 next포인터가 있어 다음 노드를 가리켰습니다. 그런데, 그런 구현방식을 이용하면 이전 노드로 돌아가려면 다시 처음부터 탐색을 해야만 합니다. 따라서 prev포인터를 추가하면 다음과 같습니다. typedef struct _node { Data item; struct _n

[선형대수학1-3]Vector Equations(벡터 방정식) [내부링크]

2차원 상의 벡터(Vectors in R2) ▷ 열 벡터(Column Vector) - 1개의 열로만 이루어진 행렬 ▷ 벡터의 상등(equal) - 두 벡터에서 각 entry의 값이 모두 같은 경우 서로 벡터가 상등하다고 한다. ▷ 벡터의 합(sum) - 두 벡터의 합은 각 행의 entry끼로 더한다. ▷ 벡터의 실수 배(scalar multiple) - 벡터의 실수배는 각 행의 entry에 scalr c를 곱한다. 2차원 상의 기하학적 묘사(Geometric Dexcriptions of R2) - 2차원 상의 점 (a, b)는 열 벡터 [a b]T로 표현할 수 있다. ※여기서 uT는 전치행렬로 행과 열을 서로 뒤바꾼 것이다. ▷ 덧셈의 평행사변형법 - 벡터 u, v의 합 u+v는 평행사변형의 네 번째 꼭짓점에 해당한다. n차원 상의 벡터(Vectors in Rn) - (nx1) 크기를 같는 열 벡터 - ordered n-tuples로 표현되기도 한다. - 모든 entry에 0

[선형대수학0-0]contents [내부링크]

1. Linear Equations in Linear Algebra(선형대수학의 선형방정식) 2. Matrix Algebra(행렬대수학) 3. Determinants(행렬식) 4. Vector Spaces(벡터 공간) 5. Eigenvalues and Eigenvectors(고유값과 고유벡터) 6. Orthogonality and Least Squares(직교와 최소제곱법) 7. Symmetric Matrix and Quadratic Forms(대칭 행렬과 이차형식)

[선형대수학1-1]Systems of Linear Equations(선형방정식 시스템) [내부링크]

기본 용어(Basic Terminology of Linear Algebra) ▷ 선형방정식(Linear Equation) - xk의 변수들로 작성될 수 있는 방정식 ▷ 계수(Coefficients) - 선형방적식에서 미지수에 곱해진 수. - 선형방정식의 ak ▷ 상수(Constants) - 선형방정식에서 값 b를 의미한다. ▷ 선형 시스템(System of Linear Equation, Linear System) - 동일 변수를 갖는 선형방정식의 모임 - 연립방정식이란 표현을 쓰기도 한다. ▷ 해(Solution) - 방정식을 참으로 만드는 값 ▷ 해집합(Solution Set) - 선형 시스템을 참으로 만드는 모든 값 ▷ 동등성(Equivalence) - 두 선형시스템의 해 집합이 값으면, 두 선형시스템은 동등하다고 한다. 행렬 표기법(Matrix Notation) - 선형 시스템을 사각형의 배열로 표현하는 방식 ▷ 계수 행렬(Coefficient Matrix) - 선형 시스템

[선형대수학1-2]Row Rediction and Echelon Forms(행 줄임과 사다리꼴) [내부링크]

기본 정의(Basic Definition) ▷ 이끔 원소(Leading Entry) - 각 행에서 가장 왼쪽에 있는 nonzero element. ▷ 행 사다리꼴(Row Echelon Form, REF) - 다음 조건들을 만족하는 행렬 1. Nonzero 행은 All-zero 행보다 위에 있다. 2. 각 행의 leading entry는 윗 행의 leading entry보다 우측에 있어야 한다. 3. leading entry의 아래는 모두 0이어야 한다. ▷ 기약 행 사다리꼴(Reduced Row Echelon Form, RREF) - 다음 조건들을 만족하는 행렬 1. REF의 모든 조건들을 만족해야한다. 2. Nonzero 행의 leading entry는 1이어야한다. 3. leading entry 1을 갖는 열의 나머지 원소들은 모두 0이어야 한다. ▷ RREF의 유일성 정리 (Uniqueness of the REFF) - 각 행렬은 단 하나의 RREF와 행 상등하다. (Exam

백준3036: 링 [내부링크]

3036번: 링 문제 상근이는 창고에서 링 N개를 발견했다. 상근이는 각각의 링이 앞에 있는 링과 뒤에 있는 링과 접하도록 바닥에 내려놓았다. 상근이는 첫 번째 링을 돌리기 시작했고, 나머지 링도 같이 돌아간다는 사실을 발견했다. 나머지 링은 첫 번째 링 보다 빠르게 돌아가기도 했고, 느리게 돌아가기도 했다. 이렇게 링을 돌리다 보니 첫 번째 링을 한 바퀴 돌리면, 나머지 링은 몇 바퀴 도는지 궁금해졌다. 링의 반지름이 주어진다. 이때, 첫 번째 링을 한 바퀴 돌리면, 나머지 링은 몇 바퀴 돌아가는지 구하는 프로그램을 작성하시오. 입력 첫째 줄에... www.acmicpc.net 문제 3036은 숫자에 의미부여를 하면서 문제를 꾸민 케이스입니다. 사실 그 안에 담겨있는 수학적 본질은 기약분수라는 개념입니다. 1. Problem analysis - 이 문제는 여러가지 접근법이 있을 거로 예상됩니다. 저는 먼저 input을 int로 받았습니다. float으로 받을 수도 있지만, 잘 생각

[시스템프로그래밍1-1-3]주소 지정과 바이트 순서(Addressing and Byte Ordering) [내부링크]

(1.1.3) 주소 지정과 바이트 순서(Addressing and Byte Ordering) - 다양한 byte를 사용하는 프로그램 객체는 2가지 규칙을 고려해야만 합니다. 1. 프로그램 객체의 주소가 어떻에 지정되어 있는지 2. 메모리 상에서 바이트 순서가 어떻게 되어 있는지 - 사실 대부분의 컴퓨터에서는 가장 작은 주소를 잡고 프로그램의 크기만큼 연속으로 주소를 할당합니다. 예를 들자면 4byte 프로그램이 있다고 할 때, 0x100을 시작 주소로 잡으면 이어서 0x101 0x102 0x103까지 이 프로그램에 주소가 할당되어 있는 것입니다. - 물론 여러가지 주소에 마구잡이로 할당할 수도 있습니다. 이 경우에는 hashing과 같은 방법을 통해서 그 주소로 direct로 갈 수 있게 해야겠지요. 안 그러면 매번 전체탐색을... - 프로그램 객체의 바이트 순서를 결정하는 방법에는 보통 2가지가 있습니다. 1. Big Endian(빅 엔디안) - most significant by

[시스템프로그래밍1-1-4]문자열 표현(Representing Strings) [내부링크]

(1.1.4) 문자열 표현(Representing Strings) - C 문자열은 null(\n) 문자로 끝나는 문자 배열로 인코딩됩니다. 각 문자는 표준 인코딩 규격을 따르며 대표적인 적이 ASCII code입니다. (1-1-3)에서 정의한 show_bytes()를 사용해 show_bytes("12345")를 실행하면 31 32 33 34 35 00라는 결과가 나옵니다. 하단 ASCII 표를 확인하면 1은 0x31에 대응되는 것을 확인할 수 있습니다. 또한 쌍따옴표를 사용해 문자열이므로 마지막에 '\n'이 숨겨져 있는 것입니다. - 바이트 순서 및 워드 크기 규칙에 관계없이 ASCII를 문자 코드로 사용하는 모든 시스템에서 동일한 결과를 얻을 수 있습니다. 따라서 텍스트 데이터는 이진 데이터보다 플랫폼에 더 독립적입니다. - 물론 ASCII code를 모두 암기할 필요는 없습니다. 다만 '\n'(0x00), '0'(0x30), 'A'(0x41), 'a'(0x61) 정도는 알아두면

[시스템프로그래밍1-1-5]코드 표현하기(Representing Code) [내부링크]

(1-1-5)코드 표현하기(Representing Code) - 다음과 같은 code가 있다고 생각해 봅시다. int sum(int x, int y) { return x + y; } 이 code를 compile 해보면 다음과 같은 machine code을 얻을 수 있습니다. 여기서 각각의 machine에 따라 machine code가 다름을 확인할 수 있습니다. 즉, 컴퓨터 유형에 따라서 machine code가 서로 다르며 서로 호환이 되지 않는 다는 것을 알 수 있습니다. 같은 intel machine이라고 하더라도 운영체제가 다를 경우에는 encoding 규칙에 차이가 있어 호환이 되지 않습니다. 다시 말해, binary code는 기계와 운영체제의 서로 다른 조합마다 다르게 생성됩니다. 그렇다면 이 결과가 의미하는 것은 무엇일까요? 컴퓨터마다 encoding 방식이 다르다? 이것도 맞습니다만, 본질적인 것은 결국 컴퓨터는 Byte의 연속으로 작동한다는 것을 알 수 있습니다.

선형대수학(Linear Algebra) [내부링크]

선형대수학은 근래 머신러닝, 인공지능이 인기를 끌면서 필수적으로 공부해야만하는 과목이되었습니다. 선형(Linear)이라는 관점과 대수학(Algebra)이라는 두 관점에 대해서 배우며 고등과정에서의 수학을 행렬과 여러 관점에서 해석하는 방법을 배울 수 있습니다. 이 카테고리에서 다루는 내용은 위 책을 기반으로 작성됩니다. 제목: Linear Algebra: and its applications - 5th edition 저자: Steven R. Lay, Judi J. McDonald ISBN 10: 0-321-98238-X ISBN 13: 978-0-321-98238-4

[알고스팟] FESTIVAL [내부링크]

algospot.com :: FESTIVAL 록 페스티벌 문제 답안 제출 통계 문제 정보 문제 ID 시간 제한 메모리 제한 제출 횟수 정답 횟수 (비율) FESTIVAL 20000 ms 65536 kb 16860 3931 ( 23 %) 출제자 출처 분류 JongMan 알고리즘 문제 해결 전략 보기 문제 커다란 공연장을 빌려서 록 페스티벌을 개최하려고 합니다. 이 페스티벌은 여러 날 동안 진행되며, 하루에 한 팀의 밴드가 공연장에서 콘서트를 하게 됩니다. 전체 밴드를 몇 팀 섭외할 지는 아직 결정하지 않았지만, 페스티벌의 간판 스타인 L개의 팀은 이미 섭외가 끝난 상태입니다. ... algospot.com 문제 커다란 공연장을 빌려서 록 페스티벌을 개최하려고 합니다. 이 페스티벌은 여러 날 동안 진행되며, 하루에 한 팀의 밴드가 공연장에서 콘서트를 하게 됩니다. 전체 밴드를 몇 팀 섭외할 지는 아직 결정하지 않았지만, 페스티벌의 간판 스타인 L개의 팀은 이미 섭외가 끝난 상태입니다.

[시스템프로그래밍1-1-1]16진법(Hexadecimal Notation) [내부링크]

1-1 Information Storage - 컴퓨터에서는 컴퓨터 자원을 1byte(8bit)단위로 나눠서 사용합니다. 이는 accessable한 가장 작은 메모리 단위입니다. 그리고 이는 각각의 memory address를 갖습니다. - C언어에는 다양한 datatype들이 있지만, 이것이 machine-level로 내려가면 datatype을 구별하는 정보는 존재하지 않습니다. 단지, Compiler가 이러한 정보를 가지고 사용할 뿐입니다. 이제 자세한 내용을 알아보도록 하겠습니다. (1.1.1) 16진법(Hexadecimal Notation) 사용 이유: 컴퓨터는 binary notation을 기본으로 사용합니다. 1byte단위로 잘라 사용하는 특성상 000000002 이런방식으로 사용될 것입니다. 하지만, int type을 사용하면 4byte로 000000000000000000000000000000002 이런식으로 길게 늘어지게 됩니다. 사람이 이를 보고 사용하기에는 너무나도

[시스템프로그래밍1-1-2]데이터 크기(Data Sizes) [내부링크]

(1.1.2) 데이터 크기(Data Sizes) - 모든 컴퓨터는 word size라는 것이 있습니다. Word Size란 pointer data의 normal size를 의미합니다. 또한 Word size를 통해 Virtual address space의 maximum size를 결정합니다. w-bit word size는 virtual address 0~2w-1를 갖습니다. - 이렇게 들으면 조금 어렵게 들리실 수 있지만, 사실 흔히 들어보셨을 겁니다. 32bit/64bit운영체제에서 사용되는 말과 같은 말입니다. 즉, 32bit 운영체제는 virtual memory의 size가 232=4*230, 즉 약 4GB를 의미합니다. 이는 곧 DRAM의 공간도 4GB밖에 사용하지 못한다는 의미죠. 반면, 64bit 운영체제는 264=16*260, 즉 16 Exabyte라는 현재 제작되는 DRAM으로는 모두 사용하기조차 어려운 크기입니다. - 여기서 생각할 수 있는 부분은 보통 64bit 운

백준문제 [내부링크]

안녕하세요. 이 블로그는 개인적인 공부와 이후 코딩에 관심을 가지는 사람들을 위해 작성하는 블로그입니다. 백준문제풀이에서는 다음과 같은 형식으로 글을 쓸 예정입니다. 혹시라도 관심있으신 분은 읽어보시길 바랍니다. 1. Problem analysis 2. Data structure analysis 3. Algorithm explanation 4. Source code 이 카테고리에 작성된 코드들은 개인적인 풀이를 기준으로 작성된 것입니다. 최고의 효율을 보이는 코드가 아닐 수 있으니 이 부분은 양해바랍니다.

백준2557: Hello World [내부링크]

2557번: Hello World 2557번 제출 맞은 사람 숏코딩 재채점 채점 현황 강의 Hello World 분류 시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율 1 초 128 MB 415738 174831 130279 42.058% 문제 Hello World!를 출력하시오. 입력 없음 출력 Hello World!를 출력하시오. 예제 입력 1 복사 예제 출력 1 복사 Hello World! www.acmicpc.net 백준 2557은 프로그래밍 언어를 처음 접할 때 만나볼 수 있는 문제입니다. 1. Problem analysis - Console창에 string "Hello World"를 출력하는 문제. 2. Data structure analysis - 이 문제에서는 굳이 사용할 필요 없지만, 사용한다면 string을 사용한다. - 출력값이 string이므로 string type을 사용하는 것이 가장 용이하다. 3. Algorithm explanation - <iostr

시스템프로그래밍 [내부링크]

시스템프로그래밍은 실력있는 프로그래머가 되기 위해서 알아야만하는 컴퓨터의 작동방식에 관한 내용을 다룹니다. 대략적으로 설명하자면 프로그래머가 컴퓨터의 작동방식을 이해해 bug를 예방하거나 debug하고, 컴퓨터가 좀 더 효율적이게 작동하도록 만드는 초석을 닦는 과목입니다. 이 카테고리에서 다루는 내용은 위 책을 기반으로 작성됩니다. 제목: Computer Systems: A Programmer's Perspective -3rd global edition 저자: Randal E. Bryant/ David R, O'Hallaron ISBN 10: 1-292-10176-8 ISBN 13: 978-1-292-10176-7

자료구조 [내부링크]

자료구조는 알면 알수록, 익숙하면 익숙할수록 프로그래머에게 귀한 재산이 되는 개념입니다. Introduction처럼 얘기해보자면, 프로그램(Program)은 자료구조(Data Structrue)와 알고리즘(Algorithm)의 집합체입니다. Program = Data Structure + Algorithm 이때, 각각을 살펴보면 * Data Structure - How to store data in computer memory. = 컴퓨터 메모리에 데이터를 저장하는 방법. * Algorithm - How to handle the stored data. = 저장된 데이터를 다루는 방법. 위와같이 정의됩니다. 이때 자료구조에따라 알고리즘을 다르게 짜게되는데, 데이터마다 적합한 자료구조가 있고, 이 적합한 자료구조를 찾으면 상대적으로 알고리즘을 쉽게 짤 수 있게됩니다. 이 카테고리에서는 자료구조에 집중하여 다룰예정입니다. 관심있으신 사람들은 한 번씩 읽어보시면 귀한 자산이 될 것입니다.

[Data Structure]리스트(List) [내부링크]

python을 사용해보셨다면 List를 다뤄보신 적이 있으실 겁니다. C언어에서는 리스트를 지원하지는 않지만, Array(배열)을 기본적으로 지원합니다. 매우 유사하게 사용되지만, 같은 것은 아닙니다. 혹시 관심이 있으시다면 구글에 검색해보시길 바랍니다. 그래서 리스트가 뭐냐, 다음과 같습니다. * Definition - A linear collection of storing elements of the same types. = 같은 타입의 원소들을 저장하는 직선형의 모임. array를 기반으로 만들면 위와같은 그림처럼 만들어지게 됩니다. 이를 C언어에서 구현하면 다음과 같습니다. #define MAX_LIST 1000 typedef int Data; typedef struct list { Data items[MAX_LIST]; int len; } ArrayList; * Operations - initList : make a list empty. = list를 초기화하는 함수. vo

이산수학(Discrete Mathematics) [내부링크]

이산수학은 현대사회에서 컴퓨터를 이용해서 다양한 문제를 해결하기 위해 탄생한 수학입니다. 'Discrete'라는 단어는 '구별된, 분리된'이라는 의미를 가진 영어단어로 마치 컴퓨터의 binary representation을 떠오르게 합니다. 간단하게 설명하자면 이산수학은 컴퓨팅 수학정도로 이해할 수 있고, 이 카탈로그에서는 일반인과 전공인 모두에게 유의미한 내용을 다룰 예정입니다. 이 카테고리에서 다루는 내용은 위 책을 기반으로 작성됩니다. 제목: Discrete mathematics – Eighth edition. 저자: Johnsonbaugh, Richard ISBN 10: 0-321-96468-3 ISBN 13: 978-0-321-96468-7

백준10171: 고양이 [내부링크]

10171번: 고양이 10171번 제출 맞은 사람 숏코딩 재채점 채점 현황 강의 고양이 출처 다국어 분류 시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율 1 초 256 MB 184135 58961 52258 34.887% 문제 아래 예제와 같이 고양이를 출력하시오. 입력 없음. 출력 고양이를 출력한다. 예제 입력 1 복사 예제 출력 1 복사 \ /\ ) ( ') ( / ) \(__)| 출처 High School > PLU High School Programming Contest > PLU 2014 - Novice 2번 www.acmicpc.net 10171은 특수문자를 이용해서 출력과 같은 고양이를 만들어보는 문제이다. 1. Problem analysis - 몇몇 특수문자들은 그 자체로 keyword이기 때문에 앞에 '\'을 추가해줘야한다. 2. Data structure analysis - 출력 형식이 string이므로 string을 사용한다. 3. Algorithm ana

[이산수학0-0]Contents [내부링크]

1. Set and Logic(집합과 논리) - 집합과 명제논리에 대해서 다룰 예정입니다. [이산수학1-1]Sets(집합) 집합의 정의(The Definition of Set) - 여러 객체들의 집합. - 이때 객체들은 달라도 된다.(Examp... blog.naver.com [이산수학1-2]Propositions(명제) 명제(Proposition) - 참, 거짓을 판별할 수 있는 문장. - 참, 거짓 중 하나만 가져야만 한다.(Examp... blog.naver.com [이산수학1-3]Conditional Propositions and Logical Equivalence(조건 명제와 논리적 동치) 조건 명제(Conditional Proposition) - 조건이 있는 형태의 명제.(Example)If the Mathematics De... blog.naver.com [이산수학1-4]Arguments and Rules of Inference(논증과 추론 규칙) 연역적 추론(D

[시스템프로그래밍0-0]Contents [내부링크]

교재의 목차는 다음과 같습니다. 1. A Tour of Computer Systems 2. Representing and Manipullating Information 3. Machine-Level Representation of Program 4. Processor Architecture 5. Optimizing Program Performance 6. The Memory Hierarchy 7. Linking 8. Exceptional Control Flow 9. Virtual Memory 10. System-Level I/O 11. Network Programming 12. Concurrent Programming 이중에서 다룰 목차는 2. Representing and Manipullating Information 3. Machine-Level Representation of Program 5. Optimizing Program Performance 이 3가지 입니다.

[이산수학1-1]Sets(집합) [내부링크]

집합의 정의(The Definition of Set) - 여러 객체들의 집합. - 이때 객체들은 달라도 된다. (Example) A = {1, 2, 3, 4 } B = {a, b, c, d} C = {1, a, Jack, {1, 3}} 집합의 표현방식 ▷ 원소 나열법 - 원소들을 나열해서 집합을 표현하는 방법. - 보통 원소의 개수가 유한하거나, 적을 때 사용. -> 이때 나열 순서는 중요하지 않다. ▷ 조건 제시법 - 원소들의 공통된 규칙을 찾아 표현하는 방법 - 보통 원소의 개수가 무한하거나, 매우 많을 때 사용 ▷ 벤다이어그램(Vehn diagram) - 집합을 그림으로 표현하는 방법 - 시각적으로 한 눈에 들어온다는 장점이 있음. - 정식적인 증명방법으로서는 사용할 수 없음. 여러가지 집합 ▷ 공집합(Empty set) - 원소가 없는 집합. 공집합 특정 숫자들을 원소로 갖는 집합들. 집합의 크기(The Cardinality of Set) - 집합의 크기가 유한할 때,

[이산수학1-2]Propositions(명제) [내부링크]

명제(Proposition) - 참, 거짓을 판별할 수 있는 문장. - 참, 거짓 중 하나만 가져야만 한다. (Example) Which of sentences are either true of false? and Choose the propositions. (a) The only positive integers that divide 7 are 1 and 7 itself (b) For every positive integer n, there is a prime number larger than n. (c) x + 4 = 6. (Sol) (a) is true, therefore (a) is proposition. (b) is true, therefore (b) is also true. (c) is depends on the value of the variable. So, it cannot be determined. Therefore, (c) is not proposition. 진리

[이산수학1-3]Conditional Propositions and Logical Equivalence(조건 명제와 논리적 동치) [내부링크]

조건 명제(Conditional Proposition) - 조건이 있는 형태의 명제. (Example) If the Mathematics Department gets an additional $60,000, then it will hire one new faculty member. -> hypothesis(p): The Mathematics Department gets and additional $60,000. -> conclusion(q): The Mathematics Department will hire one new faculty member. ▷ 조건 명제의 진리표(Truth Table of Conditional Table) ▷ 공허한 참(Vacuously True) - 조건 명제의 진리표를 보면, 가정이 거짓이면 결론이 어떻든, 조건 명제는 자동적으로 참이다. - 이 부분을 생각해본적이 없다면 당연히 의문이 들 것이다. 하지만, 가정이 거짓이면 애초에 논의할 필요가 없다.

백준2884: 알람 시계 [내부링크]

2884번: 알람 시계 문제 상근이는 매일 아침 알람을 듣고 일어난다. 알람을 듣고 바로 일어나면 다행이겠지만, 항상 조금만 더 자려는 마음 때문에 매일 학교를 지각하고 있다. 상근이는 모든 방법을 동원해보았지만, 조금만 더 자려는 마음은 그 어떤 것도 없앨 수가 없었다. 이런 상근이를 불쌍하게 보던, 창영이는 자신이 사용하는 방법을 추천해 주었다. 바로 "45분 일찍 알람 설정하기"이다. 이 방법은 단순하다. 원래 설정되어 있는 알람을 45분 앞서는 시간으로 바꾸는 것이다. 어차피 알람 소리를 들으면, 알람을 끄고 조금 더 잘 것이기 때문이다. 이 방법... www.acmicpc.net 백준 2884번은 입력받은 시간에서 45분을 빼는 문제입니다. 1. Problem analysis - 현대사회에서 시간은 24/60진법을 기준으로 사용된다. 따라서 24/60진법을 기준으로 내림/올림이 필요할 수 있다. 2. Data structure analysis - 굳이 자료구조를 사용할 필요

[이산수학1-4]Arguments and Rules of Inference(논증과 추론 규칙) [내부링크]

연역적 추론(Deductive Reasoning) - 여러 명제들로 부터 결론을 이끌어내는 과정. 논증(Arguments) 추론 규칙(Rules of inference) - 기타 다른 증명들도 위의 modus ponens 증명과정과 같이 truth table을 이용하면 쉽게 증명가능. ▷ 추론의 오류(Fallacy) 이 카테고리에서 다루는 내용은 다음 책을 기반으로 작성됩니다. 제목: Discrete mathematics – Eighth edition. 저자: Johnsonbaugh, Richard ISBN 10: 0-321-96468-3 ISBN 13: 978-0-321-96468-7

백준10951: A+B - 4 [내부링크]

10951번: A+B - 4 10951번 제출 맞은 사람 숏코딩 재채점 결과 채점 현황 강의 A+B - 4 분류 시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율 1 초 256 MB 129845 45294 38774 35.785% 문제 두 정수 A와 B를 입력받은 다음, A+B를 출력하는 프로그램을 작성하시오. 입력 입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스는 한 줄로 이루어져 있으며, 각 줄에 A와 B가 주어진다. (0 < A, B < 10) 출력 각 테스트 케이스마다 A+B를 출력한다. 예제 입력 1 복사 1 1 2 3 3 4... www.acmicpc.net 백준 10951번은 입력이 없을 때까지 입력받는 두 수의 합을 출력하는 프로그램입니다. 1. Problem analysis - 입력값 없어야만 작동이 끝난다. 이를 어떻게 구현할 것인가. 2. Data structure analysis - int 변수 2개를 이용한다. 3. Algorithm

[이산수학1-5]Quantifiers(한정사) [내부링크]

명제함수와 논의영역 ▷ 명제함수(Propositional function) - 변수 x를 포함하는 명제 P를 P(x)라고 쓰고 이를 명제함수라고 부른다. ▷ 논의영역(Domain of discourse) - 명제함수의 변수 x의 범위 D를 의미한다. (x∈D) (Example) n은 홀수이다. 이를 해석하면 다음과 같다. P(n): n은 홀수이다. n∈N 한정문 ▷ 전체 한정문(Universally quantified statement) - for every x, P(x)와 같은 형태의 명제를 의미한다. - 이때 'for every'는 기호 '∀'로 작성한다. ▷ 존재 한정사(Existential quantified statement) - for some x, P(x)와 같은 형태의 명제를 의미한다. - 이때 'for some'는 기호 '∃'로 작성한다. ∃x, P(x) (example) ∃x, (x/(x^2+1)=2/5) P(1)=(1/2=2/5): false. 반례(Coun

[이산수학2-1]Mathematical Systems, Direct Proofs, and Counterexamples(수학적 시스템, 직접 증명, 그리고 반례) [내부링크]

수학적 시스템(Mathematical Systems) ▷공리(Axiom) - 당연하게 True로 간주되는 것. ▷정의(Definition) - 기존의 존재하는 것으로부터 새로운 개념을 창조하기위해 사용되는 것 ▷미정의 부분(Undefined terms) - 명확하게 정의되지 못한 부분. ▷정리(Theorem) - True라고 증명된 명제. ▷보조정리(Lemma) - 그자체로 관심가질 만한 것은 아니지만, 다른 정리를 증명하는데 유용한 정리 ▷따름정리(Corollary) - 다른 정리로부터 쉽게 이끌어낼 수 있는 정리. 직접 증명법(Direct Proofs) - ∀x, if P(x), then Q(x)라는 정리를 증명하는 방법. - 논의 영역의 모든 x에 대해 P(x)가 참이라고 가정할 때, Q(x)가 참인 것을 "공리, 정의, 정리, 추론 규칙"과 같은 것들을 사용해 증명하는 방법. (Example) For all integers n and m, if m is odd and n

[이산수학2-2]More Methods of Proof(다양한 증명법) [내부링크]

귀류법(Proof by Contradiction) - 결론을 부정하여 모순을 찾아내 본 명제가 참임을 증명하는 방법. - 본명제 p->q를 증명하고 싶을 때, p->~q가 참임을 가정하고 모순(contradiction)을 찾아 거짓임을 확인해 p->q가 참임을 간접적으로 증명한다. 대우 증명법(Proof by Contrapositive) - 대우 명제는 본 명제와 논리적 동치인 특징을 이용하여 대우 명제의 참/거짓 여부 판별을 통해 본 명제를 증명하는 방법. 사례별 증명(Proof by Cases) - 어떤 문제는 수학적으로 case들을 나눠야 하는 경우가 있는데, 이럴 때 각각의 case들에 대해 증명하는 방법을 의미한다. 동치 증명(Proofs of Equivalence) - 대우 명제와 유사하게 논리적 동치를 이용하여 간접적으로 증명하는 방법(대우 증명법을 포함하는 개념으로 이해할 수 있다.) 존재 증명(Existence Proofs) - 어떤 변수 x에 의해서 명제가

[이산수학2-3]Mathmetical Induction(수학적 귀납법) [내부링크]

수학적 귀납법의 원리 ▷ 기본 과정(Basis Step) - P(n=1) 이 참임을 증명 - 이때 무조건 n=1이 아니여도 된다. ▷ 추론 과정(Inductive Step) - n>=1일 때, if S(n)이 참이면, then S(n+1)이 참임을 증명. - 기본과정과 추론 과정이 증명되면 기본 과정에서 연쇄적으로 무한대까지 참인 결과를 얻어낼 수 있다. Factorial을 귀납적으로 표현하면 다음과 같다. 수학적 귀납법의 예시 ▷ 등비수열의 합(Geometric Sum) - 등비수열의 합은 등비수열의 n번째 항까지의 합을 의미한다. ▷ 멱집합의 크기 ▷ 타일링 문제(A Tiling Problem) Q) k * k size의 정사각형 공간에서 1 * 1 size의 타일을 제거한 것을 trimino로만 구현이 가능한가? (이때 k는 2의 거듭제곱이다.) Trimino 루프 불변자(loop invariant) - 루프가 실행되기 직전에 참이고 루프의 각 반복 후에 참인 프로그램 변

[이산수학2-4]Strong Form of Induction and the Well-Ordering Property(강한 귀납법과 자연수 정렬성) [내부링크]

강한 수학적 귀납법(Strong Form of Mathematical Induction) (example) Use mathematical induction to show that postage of 4 cents or more can be achieved by using only 2-cent and 5-cent stamps. (pf) Basis steps: n=4, n=5 4-cents postage는 2개의 2-cent stamps와 1개의 5-cent stamp를 통해 지불될 수 있다. Inductive step: n>=6 postage of k cents나 그 이상은 2-cent stamps와 5-cent stamps를 통해 지불 될 수 있다고 가정한다. (for 4 <= k < n) Conclusion: Basis steps와 Inductive assumption에 의해 (n - 2)cents를 지불할 수 있고, 2-cent stamp를 추가하여 n-cents postage

[이산수학3-1]Functions(함수) [내부링크]

함수(Functions) - 두 개의 집합 X와 Y가 있다. 이 때 X×Y Cartesian product를 진행한다. 그 Cartesian product로 생성된 집합의 부분집합 중 x∈X가 단 하나의 y∈Y에 대응 되는 것을 (x,y)∈f라고 표현한다. 이 때 f를 함수라 하고 f : X→Y라고 쓰기도 한다.(function f from X to Y.) ▷ 정의역(domain) - 위 정의에서 X를 정의역이라 부른다. ▷ 공역(codomain) - 위 정의에서 Y를 공역이라 부른다. ▷ 치역(range) - 공역중에서 특별히 x∈X에 의해 대응되는 원소들의 집합을 치역이라 부른다. - 공역의 부분집합이기도 하다. 함수의 표현 방법(Representation of functions) ▷ 화살표 그림(arrow diagram) ▷ 함수의 그래프(graph of a function) 해쉬 함수(Hash Functions) - 컴퓨터에서 memory같은 자원들을 빠르고 효율적으로

[이산수학3-2]Sequences and String(수열과 문자열) [내부링크]

수열(Sequence) - Domain이 양의 정수인 일종의 function이다. - 이때 Domain의 elements를 index라고 부른다. 수열의 경향성(Types of sequences) ▷ Increasing - index가 증가할 수록 수열의 값도 증가. ▷ Decreasing - index가 증가할 수록 수열의 값도 감소. ▷ Non-increasing - index가 증가할 수록 수열의 값도 감소나 유지. ▷ Non-decreasing - index가 증가할 수록 수열의 값도 증가나 유지. 부분 수열(subsequence) - 수열의 일부분만을 가져온 수열이다. - 기존 수열을 집합으로 이해하면 부분집합으로 이해 가능하다. (Example) sequense x = a, b, c, c, d sequense y = c, c y는 x의 부분 수열이다. 수열의 연산자(Operator of sequences) ▷ 합 연산자(adding) sigma notation ▷

[이산수학3-3]Relations(관계) [내부링크]

관계(Relation) - relation R from a set X to Y is a subset of Cartesian product X x Y - function은 relation의 특별한 부분이다. 유향 그래프(Digraph) ▷ 정점(vertics) - X와 Y의 원소들을 표시한다. ▷ 화살표(directed edge) - Relation R from X to Y를 화살표로 표시한다. ▷ 루프(loop) - 화살표로 표시된 것 중, 특별하게 x to x인 것을 의미한다. (x,y)∈R, if x ≤ y.where x,y∈X={1,2,3,4} Relation의 여러 성질 ▷ 반사성(reflexive) - 모든 x in X에 대해서, (x,x)∈R이면, R은 반사적(reflexive)이다. ▷ 대칭성(symmetric) - 모든 x,y in X에 대해서, (x,y)∈R이면, (y,x)∈R이다 ▷ 반대칭성(anti-symmetric) - 모든 x,y in X에 대해서, (x

[이산수학3-4]Equivalence Relations(동치관계) [내부링크]

동치 관계 - relation R이 reflexive, symmetric, and transitive on a set X이면 X는 "동치 관계 on X"라고 불린다. Theorem1 ▷ 분할(partition)은 relation으로 정의될 수 있다. Let S be a partition of a set X. Define xRy to mean that for some set s in S, both x and y belong to s. Then R is reflexive, symmetric, and transitive. Theorem2 Let R be an equivalence relation on a set X. For each a ∈ X, let [a] = {x ∈ X | xRa}. (In words, [a] is the set of all elements in X that are related to a.) Then S = {[a] | a ∈ X} is a partition o

[이산수학3-5]Matrices of Relations(관계 행렬) [내부링크]

관계 행렬(matrix of the relation) - 행렬은 Relation R from X to Y( = x R y)를 표현하는 방법 중 하나이다. 관계 행렬 곱(matrix product) - 행렬 곱은 m×n행렬과 n×r행렬의 곱일 때, m×r행렬이 나오는 연산을 의미한다. (Example) - 그렇다면 관계 행렬 곱은 무슨 의미를 가지고 있는 것일까? - 이를 활용해서 relation R의 관계 행렬 A와 그 자신의 행렬곱을 한 결과에서 기존의 nonzero elements in A가 A*A에서도 nonzero elements이면, relation R은 transitive하다는 결과를 얻을 수 있다. 이 카테고리에서 다루는 내용은 다음 책을 기반으로 작성됩니다. 제목: Discrete mathematics – Eighth edition. 저자: Johnsonbaugh, Richard ISBN 10: 0-321-96468-3 ISBN 13: 978-0-321-96468-

[이산수학4-1]Algorithm Introduction(알고리즘의 개요) [내부링크]

알고리즘의 기본요소(characteristics of Algorithm) - 알고리즘이란 문제를 해결하는 일련의 과정을 의미한다. ▷ 입력(Input) - 알고리즘이 받는 input값. ▷ 결과(Output) - 알고리즘이 생산하는 output값. ▷ 명확성(Precision) - 알고리즘의 각 step이 명확하게 표현될 수 있는 정도. ▷ 결정성(Determinism) - 각 실행 단계의 중간 결과는 고유하고 이전 단계의 입력과 결과에 의해서만 결정되는가. ▷ 유한성(Finiteness) - 알고리즘이 종료되는가. 즉, 일련의 step을 거친 후에 명확히 종료되는가. ▷ 정확도(Correctness) - 알고리즘의 output이 정확한가. 기대하는 output이 나오는가. 알고리즘이 잘 작동하는가. ▷ 대표성(Generality) - 알고리즘이 다양한 input set에도 적용이 되는가. (Example1) 3개의 수 중 최대값 찾기 - 3개의 수를 각각 a, b, c라고 하자.

[시스템프로그래밍0-1]사전작업 [내부링크]

컴퓨터는 다양한 방식으로 작동할 수 있습니다. 좀 더 자세히 보자면, OS, PL와 같은 요소들에 의해 정해진 규칙을 따르게 됩니다. 먼저 OS를 살펴보면, Linux와 Windows는 매우 다른 방식을 취합니다. 실제로 다음은 gcc 컴파일러를 통해 c파일을 assembly code로 바꾼 것입니다. // C code int swap(int *x, int *y){ int tmp = *x; *x = *y; *y = tmp; return 1; // proper opration } // Assembly code in Linux swap: .LFB0: .cfi_startproc endbr64 movl (%rdi), %eax movl (%rsi), %edx movl %edx, (%rdi) movl %eax, (%rsi) movl $1, %eax ret .cfi_endproc // Assembly code in Windows swap: .seh_endprologue movl (%rcx), %

[이산수학4-2]Examples of Algorithms [내부링크]

탐색(Searching) - 컴퓨터에서 searching은 매우 중요합니다. 네이버, 다음, 구글 등의 많은 포털 사이트에서 검색 기능을 지원합니다. 여기서 일단 searching이 사용됩니다. 컴퓨터에서 파일 찾기 기능을 하는 것에서도 searching이 사용됩니다. 이외에도 정말 많은 곳에서 탐색이 사용됩니다. - 이와 같이 컴퓨터에서 searching이란 매우 중요하며, 다양한 searching 알고리즘이 존재합니다. ▷ 문자 탐색(Text Search) - length가 n인 string t에서 length가 m인 string p를 찾는 알고리즘. - t의 elements를 하나하나 탐색해 가다가 p(n=0)와 똑같은 문자를 만나면 그 뒤로 p와 똑같은 문자인지 확인하는 알고리즘. - string p를 찾으면 시작점의 index를 반환하고, 만약 없으면 0을 반환한다. - 이렇게 sequential하게 찾는 방법은 기초적인 방법입니다.(근래에는 이 방법이 직접 사용되지는 않

[이산수학4-3]Analysis of Algorithms(알고리즘 분석) [내부링크]

시간 복잡도(Time complexity) - 세상에는 다양한 알고리즘이 있지만, 그중에는 무의미한 알고리즘도 있습니다. Program으로 작성해 돌리기에는 time이 너무 오래 걸리거나 사용하는 컴퓨터 자원이 하드웨어 스펙을 뛰어 넘는 경우가 있습니다. 이러한 경우를 예측하고 피하기 위해서 알고리즘 분석은 매우 중요합니다. 시간 복잡도와 input의 크기에 따라 현실에서 걸리는 시간. - 위 표에서 가장 큰 것을 살펴보면 한평생 output을 내지 못하는 알고리즘도 있는 것을 확인할 수 있습니다. - 위 표에서 주목해야 할 점은 Θ(n)인 알고리즘이 n=10^6일 때 1sec가 걸린다는 것입니다. ▷ Best-case time - 모든 크기 n의 inputs에서 알고리즘이 종료되는 최소 시간. ▷ Worst-case time - 모든 크기 n의 inputs에서 알고리즘이 종료되는 최대 시간. ▷ Average-case time - 모든 크기 n의 inputs에서 알고리즘이 종료되

[이산수학4-4]Recursive Algorithms(재귀 알고리즘) [내부링크]

재귀 알고리즘(Recursive algorithm) - 재귀 함수를 사용하는 알고리즘이다. 이때, 재귀함수란 정의될 때 자기자신을 정의하는 함수를 의미한다. - 재귀 알고리즘은 수학적 귀납법이랑 그 궤를 같이하기 때문에 매우 직관적이면서도 powerful한 알고리즘입니다. 다만, Computer에서 사용할 때는 그 stack overflow같은 issue가 있어 한계가 명확합니다. 재귀 알고리즘의 예시(Examples of recursive algorithm) ▷ 팩토리얼(Computing n Factorial) - 팩토리얼은 n! = n * (n-1) * (n-2) * ... * 1의 규칙을 따릅니다. - 이때 n! = n * (n-1)!인 것은 자명한 사실입니다. 이러한 규칙을 따라 재귀 알고리즘을 작성하면 다음과 같습니다. ▷ 타일링 문제(Tiling a Deficient Board with Trominoes) - 과거 수학적 귀납법을 다루면서 언급했던 A tiling pr

[시스템프로그래밍1-0]Representing and Manipulating Information(정보를 표현하고 다루기) [내부링크]

Introduction - 현대 컴퓨터는 근본적으로 정보를 저장하고 처리하는데 2개의 signal만을 사용합니다. 흔히 0, 1로 표현되는 2진수를 사용합니다. 일반적인 사람들은 긴 역사를 갖고 사용해온 10진법, 12진법, 60진법과 같은 것에 더욱 익숙할 것입니다. 하지만, 기계에게는 2진법이 더욱 효과적입니다. 전기를 사용하는 기계 특성상 기준 이상 전압을 1, 기준 이하 전압은 0으로 표현하는 것이 대표적입니다. - 하지만 single bit는 그 자체로는 너무나도 단위가 낮아 사용이 어렵습니다. 그래서 grouping을 해서 1byte(=8bit)단위로 사용을 하기로 했습니다. - 이런식으로 bit를 기본으로 사용함으로서 3가지의 숫자 표현법: unsigned interger, signed integer, floating-point들을 나타낼 수 있습니다. 상세 내용은 이후에 다루게 될 것입니다. 이 Chapter에서 다룰 내용은 다음과 같습니다. 1.1 Informati