고양이 퍼레이드

버블 정렬 파트에서 나온 내용이니 버블 정렬로 풀어보려 한다. N의 최대 범위가 1000으로 매우 작기 때문에 O(n^2)의 시간복잡도를 가진 버블 정렬로 문제를 해결할 수 있다. 먼저 슈도코드를 작성하면 다음과 같다. 더보기 N(정렬할 수의 개수) A(수를 저장할 배열) for (i: 0 ~ N-1) { for (j: 0 ~ N-i-1) { 현재 A배열의 값보다 1칸 오른쪽 배열의 값이 더 작으면 swap } } 코드로 구현하면 다음과 같다. import java.util.*; public class P_2750 { public static void main(String[] args) { Scanner sc = new Scanner(System.in); int N = sc.nextInt(); int[]..

버블 정렬 두 인접한 데이터의 크기를 비교해 정렬하는 방법 루프를 돌면서 인접한 데이터 간의 swap 연산으로 정렬 시간복잡도 O(n^2) 정렬 과정 1) 비교 연산이 필요한 루프 범위를 설정 2) 인접한 데이터 값을 비교 3) swap 조건에 부합하면 swap 연산 수행 4) 루프 범위 끝날 때까지 2~3을 반복 5) 정렬 영역 설정, 다음 루프 실핼할 때 해당 영역 제외 6) 비교 대상이 없을 때까지 1~5를 반복 선택 정렬 대상 데이터에서 최대나 최소 데이터를 데이터가 나열된 순으로 찾아가며 선택하는 방법시간복잡도 O(n^2) 시간복잡도 O(n^2) 정렬 과정 1) 남은 정렬 부분에서 최솟값 또는 최댓값을 찾음 2) 남은 정렬 부분에서 가장 앞에 있는 데이터와 선택된 데이터를 swap 3) 가장 앞..

트리(Tree) 노드와 엣지로 연결된 그래프의 특수한 형태 -> 그래프의 일종 순환구조(cycle)를 가지고 있지 않고, 1개의 루트 노드 존재 루트 노드 제외 모두 단하나의 부모 노드 존재 연결된 트리의 경우 임의의 두 노드를 연결하는 경로는 유일 트리도 그래프의 일종이기에 그래프로 풀이 가능 -> 인접리스트로 표현(dfs, bfs) 트리만을 위한 문제 -> 이진트리, 인덱스트리, LCA(최소공통조상) 이진트리(Binary Tree) 각 노드의 자식 노드 개수(=차수)가 2 이하로 구성된 트리 일차원배열로 표한하기 위해서는 무조건 이진트리 포화이진트리 : 리프 노드가 모두 차있는 상태 완전이진트리 : 마지막 레벨은 왼쪽부터 채워져 있는 상태 왼쪽 자식 노드 = 현재 index*2 오른쪽 자식 노드 = ..

RAM의 특징과 종류 01. RAM의 특징 실행할 프로그램의 명령어와 데이터가 저장 전원을 끄면 저장된 내용이 사라지는 저장 장치 = 휘발성 저장 장치 -> '실행할 대상' 비휘발성 저장장치(하드디스크, CD-ROM, USB..) -> '보관할 대상' CPU가 프로그램을 실행하기 위해 보조기억장치 자료를 RAM으로 복사해 저장한 뒤 실행 02. RAM의 용량과 성능 RAM의 용량이 크다면 보조기억장치에서 실행할 프로그램을 가져오는 작업이 줄어 빠르게 실행 반대로 RAM의 용량이 작으면 보조기억장치에서 실행할 프로그램을 가져오는 작업이 늘어 느리게 실행 하지만, 일정 수준 이상의 용량은 프로그램 실행 속도가 그에 비례해 증가하지 않음 03. RAM의 종류 (1) DRAM Dynamic RAM -> 일반적 ..

ALU 다양한 계산 담당 레지스터로부터 피연산자를 받아들이고, 제어장치로부터 수행할 연산을 알려주는 제어 신호를 받아들임 연산결과(결과값)를 레지스터에 저장하고, 연산결과에 대한 추가적인 정보인 플래그를 플래그 레지스터에 저장 플래그 종류 - 부호 플래그 : 연산결과의 부호 -> 1(음수) or 0(양수) - 제로 플래그 : 연산결과가 0인지 여부 -> 1(연산결과 0) or 0(연산결과 0 아님) - 캐리 플래그 : 연산 결과 올림수 or 빌림수가 발생했는지 여부 -> 1(올림수나 빌림수 발생) or 0(발생 안 함) - 오버플로우 플래그 : 오버플로우 발생 -> 1(오버플로우 O) or 0(오버플로우 X) - 인터럽트 플래그 : 인터럽트 가능 여부 -> 1(인터럽트 가능) or 0(인터럽트 불가) -..

컴퓨터의 정보단위 비트(bit) : 0 또는 1로 표현되는 가장 작은 정보 단위 바이트(byte) : 8개의 bit를 묶은 정보 단위 -> 2^8(=256)개의 정보 표현 가능 킬로바이트(kB) : 1byte x 1000개 = 1000byte 메가바이트(MB) : 1kB x 1000개 = 1000kB 기가바이트(GB) : 1MB x 1000개 = 1000MB 테라바이트(TB) : 1GB x 1000개 = 1000GB 워드(word) : CPU가 한 번에 처리할 수 있는 데이터 크기 -> half word, full word, double word -> 인텔 x86 CPU는 32비트 word, 인텔 x64 CPU는 64비트 word 이진법 1을 넘어가는 시점에서 자리 올림을 하여 0과 1만으로 수를 표현하..

컴퓨터 구조 = 컴퓨터가 이해하는 정보(데이터&명령어) + 컴퓨터의 4가지 핵심부품(CPU, 메모리, 보조기억장치, 입출력장치) 데이터(Data) - 컴퓨터가 이해하는 숫자, 문자, 이미지, 동영상 등 정적인 정보 명령어(Instruction) - 데이터를 움직이고, 컴퓨터를 작동시키는 정보 1. 메모리(main memory) - 현재 실행되는 프로그램의 명령어와 데이터를 저장하는 장소 -> 프로그램 실행을 위해 반드시 이 곳에 저장!! - 빠른 작동을 위해 메모리 속 정보를 효율적으로 접근 -> 주소(address) 이용 - RAM(Random Access Memory)과 ROM(Read Only Memory)이 존재 -> 주기억 장치는 RAM이라 생각해도 무방 2. CPU(Central Process..

AWS 소개 aws란 amazone web service의 약자로, 아마존에서 운영하는 cloud computing platform이다. 처음 아마존은 단순한 온라인 쇼핑 산업에서 시작했지만 그 규모가 전세계로 확대되면서 엄청난 양의 데이터를 처리하고 보관해야 했기에 그들만의 서버를 구축해야 했다. 그러자 아마존은 해당 네트워크 서비스를 다른 개발자들 또한 필요할 것이라 생각해 이러한 서버를 클라우드로 구축할 수 있는 서비스를 제공하면서 aws는 개발자들에게 대체 불가한 클라우드 컴퓨팅 서비스가 되었다. aws 이전의 단순한 웹통신을 살펴보면 클라이언트는 특정 정보를 얻기 위해 회사의 서버에 직접 Request를 보내고, 회사 서버는 요청에 대한 Response를 보내 클라이언트가 정보를 브라우저에 렌더..

1. django가 무엇인지 설명하시오 파이썬을 기반으로 웹을 개발하기 위해 만들어진 웹 프레임워크 입니다. (프레임워크는 프로그램을 개발하기 위해 사용되는 틀을 제공하는 프로그램) (라이브러리는 개발자가 개발하는데 필요한 것들을 모아둔 도구들의 나열로 필요할 때 사용하는 방식) 웹 프레임워크는 웹 프로그램을 만들기 위한 스타터 키트 2. Django를 백엔드 스택으로 선정한 이유는 무엇입니까? 다른 언어들보다 직관적인 인터프리터 방식인 파이썬을 기반으로 하는 프레임워크중에서 가장 대표적으로 쓰이며, DB와 Admin페이지, ORM등 기본적으로 많은 기능들을 제공하고 기능들이 편리하여 개발에 유용하기 때문입니다. 3. Django에는 어떤 장점이 있습니까? ORM, Admin, permission등 내부..

자료구조 좋아하는 자료구조가 있다면 이유와 함께 설명해주실 수 있을까요? 스택, 큐에 대해 설명해주실 수 있을까요? 스택 - 쌓다의 의미를 가진 스택은 후입선출[LIFO (Last In First Out)] 입니다. 한 방향으로만 입력할 수 있으며 구조 중간에 값을 끼어 넣어 저장할 수 없는 한쪽이 막힌 상자와 같습니다. 같은 크기의 자료를 정해진 한 방향으로만 Push, Pop이 가능합니다. 자료를 넣을때가 Push이고, 자료를 뺄때가 Pop입니다.. 예를 들자면 웹 서핑을 한다는 가정하에 방문한 페이지에 로그가 남을 것입니다. 마지막에 방문한 페이지에서 뒤로가기를 했을때 바로 전 페이지로 이동하는게 스택 입니다. 무언가 실행취소(Ctrl+Z) 또한 같은 예 입니다. 큐 - 대기줄 이라는 의미를 가진 ..