Kwin's Development Diary.

큐 (Queue) - 스택과 마찬가지로 삽입과 삭제의 위치가 제한된 유한 순서 리스트 - 선입선출 구조(FIFO, First-In-First-Out) : 삽입 순으로 나열되어 가장 먼저 삽입한 원소가 가장 먼저 삭제된다. 삭제 ← front rear 삽입 ← 큐의 연산 과정 - 삽입 : enQueue 더보기 ① 공백 큐 생성 : 큐가 생성되지 않은 최초 상태에서만 실행 Q [0] [1] [2] ↑ front == rear == -1 ↑ ② 원소 A삽입 : enQueue(Q, A); Q [0] [1] [2] A ↑ front == -1 ↑ ↑ rear == 0 ↑ ③ 원소 B삽입 : enQueue(Q, B); Q [0] [1] [2] A B ↑ front == -1 ↑ ↑ rear == 1 ↑ - 삭제 :..

스택(stack) - 스택에 저장된 원소는 top으로 정한 곳만 접근이 가능하다. ㄴ 후입 선출 구조(LIFO, Last-In-First-Out) : 마지막에 삽입한 원소는 맨 위에 쌓여 있다가 가장 먼저 삭제된다. 스택의 연산 - 삽입(push) ① top의 위치를 하나 증가(∵ top은 스택에서 마지막 자료를 가리키기 때문) 이때, 만약 top의 위치가 스택의 크기보다 커지면 오버플로우가 발생하므로 연산 수행하지 않고 종료. ② 스택의 top이 가리키는 위치에 삽입 -①-> -②-> ←top C ←top B ←top B B A A A - 삭제(pop) ① 스택이 공백이 아니라면 top이 가리키는 원소를 먼저 반환 ② 스택의 top의 위치를 그 아래의 원소로 변경(top 위치 하나 감소) -①-> -②..

문제 666은 종말을 나타내는 숫자라고 한다. 따라서, 많은 블록버스터 영화에서는 666이 들어간 제목을 많이 사용한다. 영화감독 숌은 세상의 종말이라는 시리즈 영화의 감독이다. 조지 루카스는 스타워즈를 만들 때, 스타워즈 1, 스타워즈 2, 스타워즈 3, 스타워즈 4, 스타워즈 5, 스타워즈 6과 같이 이름을 지었고, 피터 잭슨은 반지의 제왕을 만들 때, 반지의 제왕 1, 반지의 제왕 2, 반지의 제왕 3과 같이 영화 제목을 지었다. 하지만 숨은 자신이 조지 루카스와 피터 잭슨을 뛰어넘는다는 것을 보여주기 위해서 영화 제목을 좀 다르게 만들기로 했다. 종말의 숫자란 어떤 수에 6이 적어도 3개 이상 연속으로 들어가는 수를 말한다. 제일 작은 종말의 숫자는 666이고, 그다음으로 큰 수는 1666, 26..

문제 지민이는 자신의 저택에서 MN개의 단위 정사각형으로 나누어져 있는 M×N 크기의 보드를 찾았다. 어떤 정사각형은 검은색으로 칠해져 있고, 나머지는 흰색으로 칠해져 있다. 지민이는 이 보드를 잘라서 8 × 8 크기의 체스판으로 만들려고 한다. 체스판은 검은색과 흰색이 번갈아서 칠해져 있어야 한다. 구체적으로, 각 칸이 검은색과 흰색 중 하나로 색칠되어 있고, 변을 공유하는 두 개의 사각형은 다른 색으로 칠해져 있어야 한다. 따라서 이 정의를 따르면 체스판을 색칠하는 경우는 두 가지뿐이다. 하나는 맨 왼쪽 위 칸이 흰색인 경우, 하나는 검은색인 경우이다. 보드가 체스판처럼 칠해져 있다는 보장이 없어서, 지민이는 8 × 8 크기의 체스판으로 잘라낸 후에 몇 개의 정사각형을 다시 칠해야겠다고 생각했다. 당..

문제 카지노에서 제일 인기 있는 게임 블랙잭의 규칙은 상당히 쉽다. 카드의 합이 21을 넘지 않는 한도 내에서, 카드의 합을 최대한 크게 만드는 게임이다. 블랙잭은 카지노마다 다양한 규정이 있다. 한국 최고의 블랙잭 고수 김정인은 새로운 블랙잭 규칙을 만들어 상근, 창영이와 게임하려고 한다. 김정인 버전의 블랙잭에서 각 카드에는 양의 정수가 쓰여 있다. 그다음, 딜러는 N장의 카드를 모두 숫자가 보이도록 바닥에 놓는다. 그런 후에 딜러는 숫자 M을 크게 외친다. 이제 플레이어는 제한된 시간 안에 N장의 카드 중에서 3장의 카드를 골라야 한다. 블랙잭 변형 게임이기 때문에, 플레이어가 고른 카드의 합은 M을 넘지 않으면서 M과 최대한 가깝게 만들어야 한다. N장의 카드에 써져 있는 숫자가 주어졌을 때, M..

문제 어떤 자연수 N이 있을 때, 그 자연수 N의 분해합은 N과 N을 이루는 각 자릿수의 합을 의미한다. 어떤 자연수 M의 분해합이 N인 경우, M을 N의 생성자라 한다. 예를 들어, 245의 분해합은 256(=245+2+4+5)이 된다. 따라서 245는 256의 생성자가 된다. 물론, 어떤 자연수의 경우에는 생성자가 없을 수도 있다. 반대로, 생성자가 여러 개인 자연수도 있을 수 있다. 자연수 N이 주어졌을 때, N의 가장 작은 생성자를 구해내는 프로그램을 작성하시오. 입력 첫째 줄에 자연수 N(1 ≤ N ≤ 1,000,000)이 주어진다. 출력 첫째 줄에 답을 출력한다. 생성자가 없는 경우에는 0을 출력한다. 문제 접근 방법 이번 문제는 분해 합의 결괏값이 입력되면 이 값이 원래 어떤 수였는지 찾아내..

문제 2차원 평면 위의 점 N개가 주어진다. 좌표를 x좌표가 증가하는 순으로, x좌표가 같으면 y좌표가 증가하는 순서로 정렬한 다음 출력하는 프로그램을 작성하시오. 입력 첫째 줄에 점의 개수 N (1 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 N개의 줄에는 i 번 점의 위치 xi와 yi가 주어진다. (-100,000 ≤ xi, yi ≤ 100,000) 좌표는 항상 정수이고, 위치가 같은 두 점은 없다. 출력 첫째 줄부터 N개의 줄에 점을 정렬한 결과를 출력한다. 문제 접근 방법 다음 문제는 2차원 리스트를 정렬하는 문제이다. x좌표 먼저 오름차순으로 만약 x좌표가 같다면 y좌표 오름차순으로 정렬을 해주면 된다. 이때, java내장 함수 중에 Arrays.sort() 함수를 이용해주면 쉽게 풀 수..

이중 연결 리스트(doubly linked list) - 양쪽 방향으로 순회할 수 있도록 노드를 연결한 리스트 - 이중 연결 리스트의 노드 구조 ㄴ 두 개의 링크 필드와 한 개의 데이터 필드로 구성 ㄴ llink(left link) 필드 : 왼쪽 노드와 연결하는 포인터 ㄴ rlink(right link) 필드 : 오른쪽 노드와 연결하는 포인터 llink data rlink ● ● // 노드 구조에 대한 구조체 정의 public class DblNode { DblNode llink; String data; DblNode rlink; }; - 리스트의 이중 연결 리스트 구성 1 ● → 1 → ← 2 null data1 2 ● 1 ● data2 null - 원형 이중 연결 리스트 1 ● ➥ ☇ 1 → ← 2 ..

리스트(List) - 자료를 나열한 목록 ex) 분식 = ['떡볶이', '김밥', '순대', '핫도그', '튀김', '어묵'] 수능 = ['국어', '수학', '영어', '사회', '과학', '외국어'] 나라 = ['대한민국', '미국', '중국', '일본'] 선형 리스트(Linear List) - 순서 리스트(Ordered List) - 자료들 간 순서를 갖는 리스트 선형 리스트의 저장 - 원소들의 논리적 순서와 같은 순서로 메모리에 저장 - 순차 자료구조의 원소 위치 계산 - 선형 리스트가 저장된 시작 위치 a - 원소의 길이 : l - i번째 원소의 위치 = a + (i-1) x l 선형 리스트에서의 원소 삽입 - 중간에 원소 삽입시 그 뒤 원소들은 한 자리씩 뒤로 이동하여 물리적 순서와 논리적 순..

행렬 (matrix) - m x n 행렬 ㄴ m : 행의 개수 ㄴ n : 열의 개수 ㄴ 원소의 개수 : (m xn) 개 행렬 A = a11 a12 ... a1n a21 a22 ... a2n . . . . . . . . am1 am2 ... amn 전치 행렬 - 행렬의 행과 열을 서로 교환하여 구성한 행렬 - 행렬 A의 모든 원소의 위치(i, j)를 (j, i)로 교환 - mxn 행렬을 nxm 행렬로 변환한 행렬 A'는 행렬 A의 전치 행렬 ex) A = 1 2 3 4 5 6 7 8 9 10 11 12 전치 행렬 변환↓ A' = 1 5 9 2 6 10 3 7 11 4 8 12 행렬의 순차 자료구조 표현 - 2차원 배열 사용 : mxn행렬을 m행 n열의 2차원 배열로 표현 ex) A = 1 2 3 4 5 6..