공부 정리

문제 출처 - http://jungol.co.kr/bbs/board.php?bo_table=pbank&wr_id=788&sca=2050 JUNGOL www.jungol.co.kr 문제 임의의 문장을 입력받아 각 단어별로 나눈 후에 단어들의 중복되는 개수를 구하는 프로그램을 작성하시오. (1) 입력된 스트링은 글자의 제한은 없다. 즉, 알파벳 대.소문자, 공백, ', ' 등도 입력으로 들어 올 수 있다. (2) 입력된 문장에서 각 단어사이의 구분은 공백으로 한다. (3) 단어에는 공백을 제외한 모든 문자들이 포함된다.​ 입력형식 임의의 문장을 입력받는다.(문장의 길이는 200 이하) 하나의 결과가 나온 후에도 계속 새로운 입력을 받다가, "END"가 입력되면 프로그램을 종료한다. (문장의 개수를 30을 넘..

* Stack area? 함수의 호출과 관계되는 지역 변수와 매개 변수가 저장되는 영역이다. 스택은 함수의 호출과 동시에 할당된다. 함수 호출이 완료되면 알아서 소멸한다. 기본 타입(정수타입(byte, char, short, int), 실수타입(float, double), 논리타입(boolean))등이 스택 공간에 저장된다. 크기가 정해져 있는 타입이고 메모리 할당시 시 컴파일할 때 계산이 이루어진다. 해당 메소드가 종료되면 메모리가 해제된다. * Heap area? Heap 메모리 영역과 관련 있는 단어 - 동적 메모리 할당/메모리 동적 할당 (컴퓨터 프로그래밍에서 실행 시간 동안 사용할 메모리 공간을 할당하는 것. 해당 메모리의 사용이 끝나면 반납하고 다시 필요하면 재할당받는다. 동적으로 할당된 메모..

* 3rd party(써드 파티)란? 써드 파티 또는 써드 파티 개발자는 일반적으로 하드웨어 생산자와 소프트웨어 개발자의 관계를 나타낼 때 사용한다. 하드웨어 생산자와 소프트웨어 개발자의 관계 하드웨어 생산자 = 소프트웨어 개발자 (직접) 하드웨어 생산자인 기업과 소프트웨어 개발자가 어떤 관계가 있음 아무 관계 없음 분류 퍼스트 파티 개발자 세컨드 파티 개발자 써드 파티 개발자 업체별 분야별로 약간씩 서로 다른 사례나 관례를 가지고 있지만, 보통 하드웨어 생산자와 소프트웨어 개발자가 같은 경우(하드웨어 생산자가 직접 소프트웨어 개발도 함) 퍼스트 파티(개발자) 하드웨어 생산자인 기업과 소프트웨어 개발자가 모종의 관계를 맺고 있을 경우(모기업 - 자사, 하청 등) 세컨드 파티 (개발자) 아무 관련 없이 소..

* Divide and Conquer Algorithm (분할 정복)? 해결할 수 없는 문제를 더 이상 나눌 수 없는 작은 문제로 분할하여 문제를 해결하는 방법이나 알고리즘이다. Quicksort, Merge sort, Closest Pair of Points 등의 알고리즘이 이 분할 정복 알고리즘에 해당한다. 분할 정복 알고리즘은 3 부분으로 나뉠 수 있다. 나누기 (Divide): 문제를 더 작은 문제로 나눈다. 정복 (Conquer): 하위 문제가 해결될 때까지 재귀적으로 호출하여 하위 문제를 해결한다. 결합(Combine): 하위 문제가 해결되었기 때문에 문제 해결을 할 수 있다. 보통 재귀적으로 함수를 호출하여 문제를 해결하지만, 재귀적으로 함수 호출이 잦게 되면 함수 호출 스택 오버헤드 때문에..

* Binary Search Algorithm(이진 탐색 알고리즘) 오름차순으로 정렬된 리스트에서 특정한 값의 위치를 찾는 알고리즘이다. 이진 탐색 알고리즘을 사용하기 위해선 반드시 오름차순으로 정렬이 되어 있는 리스트라는 전제 조건이 필요하다. 1. 중앙 원소와 찾고자 하는 X를 비교한다. 2-1. 만약 중앙 원소가 찾고자 하는 원소와 같다면 해당 원소 리턴 2-2. X가 중앙 원소보다 크다면 배열의 우측을 대상으로 탐색 재실행, 작다면 좌측을 대상으로 탐색 재실행 * 시간 복잡도 탐색하고자 하는 원소가 N개라면, 첫 시도에는 N개의 원소를, 두번째 시도에는 N/2개의 원소를, 세번째 시도에는 N/4의 원소를 탐색할 것이다. 자료의 갯수가 N개라면 시행 횟수는 밑이 2인 log2N이다. 따라서 시간복잡..

문제 출처 - https://www.acmicpc.net/problem/16922 16922번: 로마 숫자 만들기 2, 6, 10, 11, 15, 20, 51, 55, 60, 100을 만들 수 있다. www.acmicpc.net 문제 로마 숫자에서는 수를 나타내기 위해서 I, V, X, L을 사용한다. 각 문자는 1, 5, 10, 50을 의미하고, 이 문제에서 다른 문자는 사용하지 않는다. 하나 또는 그 이상의 문자를 이용해서 수를 나타낼 수 있다. 문자열이 나타내는 값은, 각 문자가 의미하는 수를 모두 합한 값이다. 예를 들어, XXXV는 35, IXI는 12를 의미한다. 실제 로마 숫자에서는 문자의 순서가 중요하지만, 이 문제에서는 순서는 신경쓰지 않는다. 예를 들어, 실제 로마 숫자에서 IX는 9를..

나는 엽떡에서 떡볶이보다 계란찜을 더 좋아한다. 엽떡을 먹을 때마다 계란찜에 감탄하며 엄청난 비밀이 숨겨져있을 것이라고 생각했다. 집에서 엽떡 계란찜의 환상적인 맛을 재현하고자 여러 차례 노력해보았다. 멸치 육수, 다시마 육수, 녹차물(사실 이건 전혀 상관 없는 건데 그냥 해봤다), 채수 등을 넣고 만들어보았으나 오리지널의 맛을 재현하기엔 무리였다. 엽떡 계란찜에는 육향이 어느정도 느껴지는데, 나는 이게 고기 육수일 것이라고 생각했다. 양지로 낸 육수 같은? 근데 엽떡 계란찜 하나 만들자고 양지 사다가 육수 내기엔 좀 그렇고... 그래서 그냥 이건 안했었다. 아무튼 이런 저런 실패 끝에 이건 엄청난 비밀이 숨겨져 있나보다하고 포기했었다. 그런데 누가 엽떡 계란찜 맛은 그냥 소고기 다시다 넣고 만들면 된다..

문제 출처 - https://www.acmicpc.net/problem/1789 1789번: 수들의 합 첫째 줄에 자연수 S(1 ≤ S ≤ 4,294,967,295)가 주어진다. www.acmicpc.net 문제 서로 다른 N개의 자연수의 합이 S라고 한다. S를 알 때, 자연수 N의 최댓값은 얼마일까? 입력 첫째 줄에 자연수 S(1 ≤ S ≤ 4,294,967,295)가 주어진다. 출력 첫째 줄에 자연수 N의 최댓값을 출력한다. 문제 유형 구현 import java.util.Scanner; public class BJ1789_수들의합 { static int res; static long S; static long sum; public static void main(String[] args) { Scan..

문제 출처 - https://www.acmicpc.net/problem/2303 2303번: 숫자 게임 N명이 모여 숫자 게임을 하고자 한다. 각 사람에게는 1부터 10사이의 수가 적혀진 다섯 장의 카드가 주어진다. 그 중 세 장의 카드를 골라 합을 구한 후 일의 자리 수가 가장 큰 사람이 게임을 이 www.acmicpc.net 문제 N명이 모여 숫자 게임을 하고자 한다. 각 사람에게는 1부터 10사이의 수가 적혀진 다섯 장의 카드가 주어진다. 그 중 세 장의 카드를 골라 합을 구한 후 일의 자리 수가 가장 큰 사람이 게임을 이기게 된다. 세 장의 카드가 (7, 8, 10)인 경우에는 합은 7+8+10 = 25가 되고 일의 자리 수는 5가 된다. 어떤 사람이 받은 카드가 (7, 5, 5, 4, 9)인 경..

Priority Queue (우선순위 큐)? - 우선순위를 가지고 있는 큐 - 우선순위에 따라서 처리된다. (Not FIFO) - 우선순위 큐가 힙인 것이 아니라 우선순위 큐를 구현하는 것 중 대표적이고 효율적인 방법이 힙인 것 - 노드 하나의 추가/삭제가 시간 복잡도가 O(logN)이고 최대값/최소값을 O(1)에 구할 수 있다. - 완전 정렬보다 관리 비용이 적다. - 배열을 통해 트리 형태를 쉽게 구현할 수 있다. - 부모나 자식 노드를 O(1)연산으로 쉽게 찾을 수 있다. - n위치에 있는 노드의 자식은 2^n과 2^(n+1) 사이에 위치한다. - 완전 이진 트리의 특성에 의해 삽입/삭제의 위치는 자료의 시작과 끝 인덱스로 쉽게 판단할 수 있다. 힙 정렬 힙 정렬은 힙 자료구조를 이용해서 이진트리와..