Kwin's Development Diary.

문제 선영이는 주말에 할 일이 없어서 새로운 언어 AC를 만들었다. AC는 정수 배열에 연산을 하기 위해 만든 언어이다. 이 언어에는 두 가지 함수 R(뒤집기)과 D(버리기)가 있다. 함수 R은 배열에 있는 수의 순서를 뒤집는 함수이고, D는 첫 번째 수를 버리는 함수이다. 배열이 비어있는데 D를 사용한 경우에는 에러가 발생한다. 함수는 조합해서 한 번에 사용할 수 있다. 예를 들어, "AB"는 A를 수행한 다음에 바로 이어서 B를 수행하는 함수이다. 예를 들어, "RDD"는 배열을 뒤집은 다음 처음 두 수를 버리는 함수이다. 배열의 초기값과 수행할 함수가 주어졌을 때, 최종 결과를 구하는 프로그램을 작성하시오. 입력 첫째 줄에 테스트 케이스의 개수 T가 주어진다. T는 최대 100이다. 각 테스트 케이..

벨만-포드 알고리즘(Bellman-Ford Algorithm) : 음수인 가중치가 포함되어 있는 그래프에서 최단 거리를 구하는 알고리즘 음수 간선이 존재하지 않는다면 [알고리즘] 다익스트라 알고리즘 (Dijkstra Algorithm) - JAVA / 자바를 사용하여 문제를 해결하는 것이 실행 시간이 더 빠르다. 특징 ① 음수인 사이클을 찾을 수 있다 ② 매번 모든 간선을 확인하기에 연산 시간이 느리다 알고리즘 ① 출발 노드 설정 ② 최단 거리를 저장할 배열을 초기화 ③ 전체 간선을 하나씩 확인 ④ 각 간선을 거쳐 다른 노드로 가는 비용을 계산하여 최단 거리 테이블 갱신 ⑤ 모든 노드에 연결되어 있는 모든 간선을 확인할 때까지 ③ ~ ④반복수행 ⑤-1 이때, 마지막 반복에서 최단 거리 테이블이 갱신된다면..

0-1 너비 우선 탐색 (0-1 Breath First Search, 0-1 BFS) : 가중치가 0과 1만 존재하는 그래프에서 최단 경로를 찾는 알고리즘 [알고리즘] 다익스트라 알고리즘 (Dijkstra Algorithm) - JAVA / 자바를 사용하여 풀 수도 있는 문제이지만, 가중치가 0과 1만 존재하는 그래프라면 0-1 BFS 알고리즘이 보다 효율적으로 문제풀이가 가능하다. 특징 ① 큐(Queue) 대신 덱(Deque)을 사용 ② 가중치가 0과 1만 존재할 때 사용 알고리즘 1. 덱(Deque)의 front에서 이동할 다음 경로를 꺼낸다. 2. 현재 위치에서 연결된 다음 경로를 탐색한다. 3. if(출발 지점부터 현재 위치까지 누적된 가중치 + 다음 경로와 연결된 간선의 가중치 < 다음 경로까지..

문제 비어있는 공집합 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}으로 바꾼다. empty: S를 공집합으로 바꾼다. 입력 첫째 줄에 수행해야 하는 연산의 수 M (1 ≤ M ≤ 3,000,000)이 주어진다. 둘째 줄부터 M개의 줄에 수행해야 하는 연산..

문제 김진영이 듣도 못한 사람의 명단과, 보도 못한 사람의 명단이 주어질 때, 듣도 보도 못한 사람의 명단을 구하는 프로그램을 작성하시오. 입력 첫째 줄에 듣도 못한 사람의 수 N, 보도 못한 사람의 수 M이 주어진다. 이어서 둘째 줄부터 N개의 줄에 걸쳐 듣도 못한 사람의 이름과, N+둘째 줄부터 보도 못한 사람의 이름이 순서대로 주어진다. 이름은 띄어쓰기 없이 알파벳 소문자로만 이루어지며, 그 길이는 20 이하이다. N, M은 500,000 이하의 자연수이다. 듣도 못한 사람의 명단에는 중복되는 이름이 없으며, 보도 못한 사람의 명단도 마찬가지이다. 출력 듣보잡의 수와 그 명단을 사전 순으로 출력한다. 문제 접근 방법 이번 문제는 들도 못한 사람의 명단과 보도 못한 사람의 명단에 둘 다 포함되어 있는..

문제 한수는 크기가 2N × 2N인 2차원 배열을 Z 모양으로 탐색하려고 한다. 예를 들어, 2 × 2 배열을 왼쪽 위칸, 오른쪽 위칸, 왼쪽 아래칸, 오른쪽 아래칸 순서대로 방문하면 Z 모양이다. N > 1인 경우, 배열을 크기가 2N-1 × 2N-1로 4등분 한 후에 재귀적으로 순서대로 방문한다. 다음 예는 22 × 22 크기의 배열을 방문한 순서이다. N이 주어졌을 때, r행 c열을 몇 번째로 방문하는지 출력하는 프로그램을 작성하시오. 다음은 N=3일 때의 예이다. 입력 첫째 줄에 정수 N, r, c가 주어진다. 1 ≤ N ≤ 15 0 ≤ r, c < 2N 출력 r행 c열을 몇 번째로 방문했는지 출력한다. 문제 접근 방법 이번 문제는 분할 정복(Divide and Conquer) 문제이다. z모양으..

문제 폴리오미노란 크기가 1 ×1인 정사각형을 여러 개 이어서 붙인 도형이며, 다음과 같은 조건을 만족해야 한다. 정사각형은 서로 겹치면 안 된다. 도형은 모두 연결되어 있어야 한다. 정사각형의 변끼리 연결되어 있어야 한다. 즉, 꼭짓점과 꼭짓점만 맞닿아 있으면 안 된다. 정사각형 4개를 이어 붙인 폴리오미노는 테트로미노라고 하며, 다음과 같은 5가지가 있다. 아름이는 크기가 N×M인 종이 위에 테트로미노 하나를 놓으려고 한다. 종이는 1 ×1 크기의 칸으로 나누어져 있으며, 각각의 칸에는 정수가 하나 쓰여 있다. 테트로미노 하나를 적절히 놓아서 테트로미노가 놓인 칸에 쓰여 있는 수들의 합을 최대로 하는 프로그램을 작성하시오. 테트로미노는 반드시 한 정사각형이 정확히 하나의 칸을 포함하도록 놓아야 하며,..

문제 적록색약은 빨간색과 초록색의 차이를 거의 느끼지 못한다. 따라서, 적록색약인 사람이 보는 그림은 아닌 사람이 보는 그림과는 좀 다를 수 있다. 크기가 N×N인 그리드의 각 칸에 R(빨강), G(초록), B(파랑) 중 하나를 색칠한 그림이 있다. 그림은 몇 개의 구역으로 나뉘어 있는데, 구역은 같은 색으로 이루어져 있다. 또, 같은 색상이 상하좌우로 인접해 있는 경우에 두 글자는 같은 구역에 속한다. (색상의 차이를 거의 느끼지 못하는 경우도 같은 색상이라 한다) 예를 들어, 그림이 아래와 같은 경우에 RRRBB GGBBB BBBRR BBRRR RRRRR 적록색약이 아닌 사람이 봤을 때 구역의 수는 총 4개이다. (빨강 2, 파랑 1, 초록 1) 하지만, 적록색약인 사람은 구역을 3개 볼 수 있다. ..

마치면서 2021년 8월 23일 ~ 2021년 10월 20일까지 약 2달 동안의 여정이 끝이 났다. 지금 생각해보면 정말 많은 일이 있었다는걸 실감할 수 있었다. 나의 첫 대외활동이었고, 협업이라는 것을 처음 해보았고, 단순 코드 공부만이 아닌 창작물을 만들어 보았고, 학교에서 만들라고 해서 만들어만 놓았던 Github를 처음 사용해보았고, Slack / Notion / Figma 등 개발자들이 사용하는 프로그램도 처음 사용해보았고, Flutter / Dart / 마크다운 등 새로운 언어를 접해보는 등의 모든 활동이 최근 2달간 이루어졌다는 게 신기하다. 정말 많은 경험을 하였고, 정말 많은것을 배웠고, 정말 많은 것을 느꼈다. 이래서 대외활동, 대외활동하는구나 라는 것을 깨달을 수 있었다. 정말 처음 ..

0-1 배낭 문제 (Knapsack Problem) : 담을 수 있는 무게의 최댓값이 정해진 배낭에 일정한 가치와 무게가 정해져 있는 짐들을 골라 배낭에 담기는 최대의 가치를 구하는 문제 특징 ① 동적 계획법(다이나믹 프로그래밍, DP : Dynamic Programming)으로 해결할 수 있다. ② 다른 버전으로는 물건을 쪼갤 수 있는 Fraction Knapsack Problem이 있다. 알고리즘 ① 물건의 정보를 표에 저장해둔다 ② DP배열을 만든다 (열은 물건 0~i번까지 넣을 수 있음을 의미하고 행은 0~n까지 넣을 수 있음을 의미한다) - i, j에서 i번째 물건까지 중에 배낭에 넣을 수 있는지 없는지 판단하여 최적의 방법을 저장한다. ㄴ 넣는 것이 최적 = [i - 1][j - i번째 물건 ..