Archive

그래프노드와 간선을 이용한 비선형 데이터 구조`노드`: 데이터`간선`: 노드 간의 관계나 흐름`가중치`: 관계나 흐름에서 정도 표현 그래프 종류`방향 그래프`: 방향이 있는 간선을 포함한 그래프`무방향 그래프`: 방향이 없는 간선을 포함한 그래프`가중치 그래프`: 가중치가 있는 그래프`순환 그래프`: 특정 노드에서 시작해 간선을 따라 다시 돌아오는 경로가 있는 순환이 존재하는 그래프`비순환 그래프`: 순환이 존재하지 않는 그래프 그래프 구현(1) 인접 행렬 활용int graph[][] = new int[][]{{0, 400},{0, 0}};희소 그래프 (노드 수에 비해 간선 수가 매우 적은 그래프) 효현하는 경우 비효율노드들의 값의 차이가 매우 큰 그래프 표현하는 경우 비효율간선 정보 확인 시 시간 ..

01. 개념노드(node): 트리를 구성하는 요소루트 노드: 노드 중 가장 위에 있는 노드부모 노드: 상대적으로 위에 있는 노드자식 노드: 상대적으로 아래에 있는 노드형제 노드: 같은 부모 노드를 갖는 노드리프 노드: 자식이 없는 리프 노드간선(edge): 노드와 노드 사이를 이어주는 선차수(degree): 특정 노드에서 아래로 향하는 간선의 개수 표현배열이나 포인터로 구현 가능(1) 배열로 표현하기배열 = 선형 자료구조, 트리 = 계층 자료구조자식이 없거나 쓰지 않는 인덱스들은 모두 빈 값이므로 메모리가 낭비배열로 트리를 표현하기 위한 3가지 규칙루트 노드는 배열 인덱스 1번에 저장왼쪽 자식 노드의 배열 인덱스는 부모 노드의 배열 인덱스 * 2오른쪽 자식 노드의 배열 인덱스는 부모 노드의 배열 인덱스 ..

https://school.programmers.co.kr/learn/courses/30/lessons/92343 프로그래머스SW개발자를 위한 평가, 교육의 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.kr 1. 노드 정의각 노드의 자식을 관리하기 위해 `Node` 클래스를 정의하였다. `id`는 노드 번호이고, `value`는 양(0)과 늑대(1)를 나타내며, `childList`에 자식 노드를 담는다.static class Node { int id; int value; List childList; Node(int id, int value) { this.id = id; this.value = value; ..

01 . 개념해시는 해시 함수를 사용해서 변환한 값을 인덱스로 삼아 키와 값을 저장해서 빠른 데이터 탐색을 제공하는 자료 구조이다. 해시는 키를 활용해 데이터 탐색을 빠르게 한다.특징단방향 동작: 키 통해 값 찾기만 가능시간 복잡도 O(1): 해시함수 덕분에 탐색 과정 필요 X해시 함수를 활용해서 특정 값이 있는 위치를 바로 찾기 가능해시 테이블: 키와 대응한 값이 저장되어 있는 공간버킷: 해시 테이블의 각 데이터값을 인덱스로 활용하려면 변환과정 필요활용 분야비밀번호 관리데이터베이스 인덱싱블록체인 02. 해시 함수자바에서는 해시셋 혹은 해시맵이라는 표준 API를 제공해시 함수 구현시 고려사항해시 함수가 변환한 값은 인덱스로 활용해야 하므로 해시 테이블의 크기를 넘으면 안 된다.해시 함수가 변환한 값의..

문제수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 때 걷는다면 1초 후에 X-1 또는 X+1로 이동하게 된다. 순간이동을 하는 경우에는 1초 후에 2*X의 위치로 이동하게 된다.수빈이와 동생의 위치가 주어졌을 때, 수빈이가 동생을 찾을 수 있는 가장 빠른 시간이 몇 초 후인지 구하는 프로그램을 작성하시오.입력첫 번째 줄에 수빈이가 있는 위치 N과 동생이 있는 위치 K가 주어진다. N과 K는 정수이다.출력수빈이가 동생을 찾는 가장 빠른 시간을 출력한다.예제 입력 / 출력5 17 4힌트수빈이가 5 → 10 → 9 → 18 → 17 순..

문제n개의 음이 아닌 정수들이 있습니다.이 정수들을 순서를 바꾸지 않고 적절히 더하거나 빼서 타겟 넘버를 만들려고 합니다.예를 들어, [1, 1, 1, 1, 1]로 숫자 3을 만들려면 다음 다섯 가지 방법이 있습니다.-1 + 1 + 1 + 1 + 1 = 3+1 - 1 + 1 + 1 + 1 = 3+1 + 1 - 1 + 1 + 1 = 3+1 + 1 + 1 - 1 + 1 = 3+1 + 1 + 1 + 1 - 1 = 3사용할 수 있는 숫자가 담긴 배열 numbers, 타겟 넘버 target이 매개변수로 주어질 때,숫자를 적절히 더하고 빼서 타겟 넘버를 만드는 방법의 수를 return 하도록 solution 함수를 작성하세요. 제한사항숫자의 개수: 2개 이상 20개 이하각 숫자: 1 이상 50 이하 자연수타겟 넘버..

문제정수 X에 사용할 수 있는 연산은 다음과 같이 세 가지 이다.X가 3으로 나누어 떨어지면, 3으로 나눈다.X가 2로 나누어 떨어지면, 2로 나눈다.1을 뺀다.정수 N이 주어졌을 때, 위와 같은 연산 세 개를 적절히 사용해서 1을 만들려고 한다. 연산을 사용하는 횟수의 최솟값을 출력하시오. 입력첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 정수 N이 주어진다. 출력첫째 줄에 연산을 하는 횟수의 최솟값을 출력한다. 풀이 #1각 숫자 인덱스에 연산 횟수를 저장하여 조회할 수 있도록 하였다. 그러나 이 풀이는 Bottom-up 방식으로, for문을 통해 1부터 n까지 모든 값을 계산하기 때문에 실제로 n의 최소 연산 횟수를 구하는 데 불필요한 값들까지 모두 연산하게 된다. 그리고 파이썬에서 list..

문제NxN 크기의 공간에 물고기 M마리와 아기 상어 1마리가 있다. 공간은 1x1 크기의 정사각형 칸으로 나누어져 있다. 한 칸에는 물고기가 최대 1마리 존재한다.아기 상어와 물고기는 모두 크기를 가지고 있고, 이 크기는 자연수이다. 가장 처음에 아기 상어의 크기는 2이고, 아기 상어는 1초에 상하좌우로 인접한 한 칸씩 이동한다.아기 상어는 자신의 크기보다 큰 물고기가 있는 칸은 지나갈 수 없고, 나머지 칸은 모두 지나갈 수 있다. 아기 상어는 자신의 크기보다 작은 물고기만 먹을 수 있다. 따라서, 크기가 같은 물고기는 먹을 수 없지만, 그 물고기가 있는 칸은 지나갈 수 있다.아기 상어가 어디로 이동할지 결정하는 방법은 아래와 같다.더 이상 먹을 수 있는 물고기가 공간에 없다면 아기 상어는 엄마 상어에게..

문제상어 초등학교에는 교실이 하나 있고, 교실은 NxN 크기의 격자로 나타낼 수 있다.교실은 NxN 크기의 격자학생 수는 N^2명학생은 1번부터 N^2번까지 번호가 매겨져 있고, (r,c)는 r행 c열을 의미한다. 교실의 가장 왼쪽 윗 칸은 (1,1)이고 가장 오른쪽 아랫칸은 (N,N)이다선생님은 학생의 순서를 정했고, 각 학생이 좋아하는 학생 4명도 모두 조사했다.이제 다음과 같은 규칙을 이용해 정해진 순서대로 학생의 자리를 정하려고 한다.한 칸에는 학생 한 명의 자리만 있을 수 있고, |r1 - r2| + |c1 - c2| = 1 을 만족하는 두 칸이 (r1, c1)과 (r2, c2)을 인접하다고 합니다.비어있는 칸 중에서 좋아하는 학생이 인접한 칸에 가장 많은 칸으로 자리를 정한다.1을 만족하는 칸..

문제 입력출력로봇 청소기가 작동을 시작한 후 작동을 멈출 때까지 청소하는 칸의 개수를 출력한다.내 풀이로봇 청소기는 N×M 크기의 맵에서 청소를 수행한다.각 칸은 벽(1) 또는 빈 칸(0)으로 구분된다.로봇의 행동 규칙:현재 위치를 청소한다.왼쪽부터 차례대로 4방향을 탐색하며, 청소하지 않은 칸이 있으면 이동한다.4방향 모두 청소가 완료되면 후진을 시도한다.후진이 불가능하면 작동을 멈춘다.DFS(깊이 우선 탐색)를 사용하면, 재귀적으로 청소와 이동을 구현할 수 있다.n, m = map(int, input().split()) # 세로, 가로r, c, d = map(int, input().split())graph = []result = 1for _ in range(n): graph.append(lis..

01. 집합과 상호배타적 집합의 개념집합순서와 중복이 없는 원소들을 갖는 자료구조상호배타적 집합: 교집합이 없는 집합 관계ex. A = {1,2,3} 과 B = {4,5,6,7}활용 알고리즘이미지 분할이미지를 서로 다른 부분으로 나누는 데 사용ex. 사람과 배경을 겹치지 않게 분할도로 네트워크 구성도로 구축시 각 도로를 서로 교차하지 않도록 설계하는 데 사용최소 신장 트리 알고리즘 구현간선을 추가할 때마다 사이클을 형성하는지 여부를 체크할 때 사용게임 개발캐릭터의 동작 자연스럽게 구현 가능ex. 플레이어와 적군 충돌 시 두 캐릭터가 겹치지 않도록 함클러스터링 작업각 작업이 서로 겹치지 않도록 구성 가능작업 간의 의존 관계가 없으면 동시에 여러 작업 진행 가능02. 집합의 연산보통 집합은 트리로 표현대표적..

1. 스택`스택` : 먼저 입력한 데이터를 제일 나중에 꺼낼 수 있는 자료구조`LIFO (Last In First Out)` : 먼저 들어간 것이 마지막에 나오는 규칙`push` : 스택에 삽입하는 연산`pop` : 스택에서 꺼내는 연산최근에 삽입한 데이터를 대상으로 연산해야 한다면 스택을 떠올리는 것이 좋음 스택의 ADTADT란 ?Abstract Data Type의 약자추상 자료형 (인터페이스만 있고 실제로 구현은 되지 않는 자료형)일종의 자료형의 설계도정의해야 할 연산 : `push` ,`pop` , `isFull` , `isEmpty`정의해야 할 상태 : `top` , `data[maxsize]` 데이터가 없으면 top = -1 스택 세부 동작1. push(3) 호출2. isFull()을 수행하..

01. 배열인덱스와 값을 일대일 대응해 관리하는 자료구조데이터를 저장할 수 있는 모든 공간은 인덱스와 일대일 대응하므로 어떤 위치에 있는 데이터든 한 번에 접근 가능배열 선언int[] arr = { 0, 0, 0, 0, 0, 0 };int[] arr = new int[6];// 둘 실행 결과 같음배열은 인덱스가 0부터 시작배열과 유사한 기능을 가진 ArrayList와 차이배열: 처음 선언할 때 배열의 크기 결정정확한 데이터의 개수를 알고 있는 경우 (속도 더 빠름)ArrayList: 크기 동적임저장해야 할 데이터의 개수를 정확히 알 수 없는 경우배열과 차원컴퓨터 메모리의 구조는 1차원이므로 2차원, 3차원 배열도 실제로는 1차원 공간에 저장배열은 차원과는 무관하게 메모리에 연속 할당1차원 배열배열의 각 ..

문제 셀프 넘버는 1949년 인도 수학자 D.R. Kaprekar가 이름 붙였다. 양의 정수 n에 대해서 d(n)을 n과 n의 각 자리수를 더하는 함수라고 정의하자. 예를 들어, d(75) = 75+7+5 = 87이다. 양의 정수 n이 주어졌을 때, 이 수를 시작해서 n, d(n), d(d(n)), d(d(d(n))), ...과 같은 무한 수열을 만들 수 있다. 예를 들어, 33으로 시작한다면 다음 수는 33 + 3 + 3 = 39이고, 그 다음 수는 39 + 3 + 9 = 51, 다음 수는 51 + 5 + 1 = 57이다. 이런식으로 다음과 같은 수열을 만들 수 있다. 33, 39, 51, 57, 69, 84, 96, 111, 114, 120, 123, 129, 141, ... n을 d(n)의 생성자라..

문제 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)이 주어진다. 다음 줄에는 M개의 수들이 주어지는데, 이 수들이 A안에 존재하는지 알아내면 된다. 모든 정수의 범위는 -231 보다 크거나 같고 231보다 작다. 출력 M개의 줄에 답을 출력한다. 존재하면 1을, 존재하지 않으면 0을 출력한다. 내 풀이 n = int(input()) fa = set(list(map(int, input().split(" ")))) m = int(inp..

문제 인하은행에는 ATM이 1대밖에 없다. 지금 이 ATM 앞에 N명의 사람들이 줄을 서있다. 사람은 1번부터 N번까지 번호가 매겨져 있으며, i번 사람이 돈을 인출하는데 걸리는 시간은 Pi분이다. 사람들이줄을 서는 순서에 따라서, 돈을 인출하는데 필요한 시간의 합이 달라지게 된다. 예를 들어 총 5명이 있고, P1 = 3, P2 = 1, P3 = 4, P4 = 3, P5 = 2인 경우를 생각해보자. [1,2,3,4,5] 순서로 줄을 선다면, 1번 사람은 3분만에 돈을 뽑을 수 있다. 2번 사람은 1번 사람이 돈을 뽑을 때까지 기다려야 하기 때문에, 3 + 1 = 4분이 걸리게 된다. 3번 사람은 1번, 2번 사람들이 돈을 뽑을 때까지 기다려야 하기 때문에, 3 + 1 + 4 = 8분이 필요하게 된다. ..

탐색 : 많은 양의 데이터 중에서 원하는 데이터를 찾는 과정ㄴ 대표적인 탐색 알고리즘: DFS & BFS자료구조 : 데이터를 표현하고 관리하고 처리하기 위한 구조ㄴ 스택과 큐 : 자료구조의 기초 개념ㅤ> 삽입 (Push) & 삭제 (Pop)을 핵심으로 하여 구성됨ㅤ> 오버플로 (특정한 자료구조가 수요할 수 있는 데이터의 크기를 이미 가득 찬 상태에서 삽입 연산을 수행할 때 발생) & 언더플로 (특정한 자료구조에 데이터가 전혀 들어 있지 않은 상태에서 삭제 연산을 수행)도 고민해야 함 스택스택 = 박스 쌓기 = 아래에서부터 위로 쌓임 = 아래에 있는 박스를 치우기 위해서는 위에 있는 박스를 먼저 내려야 함 = 선입후출 구조 (First In Last Out) = 후입선출 구조 (Last in First O..

문제 유진수는 어떤 수를 10진수로 표현한 뒤 그 수를 두 부분으로 나눴을 때, 앞부분 자리수의 곱과 뒷부분 자리수의 곱이 같을 때를 말한다. 예를 들어, 1221은 유진수이다. 12와 21로 나눴을 때, 앞부분 자리수의 곱 1*2는 뒷부분 자리수의 곱 2*1과 같기 때문이다. 1236도 마찬가지로 유진수이다. 하지만, 1234는 아니다. 수를 나눌 때 항상 연속된 자리수를 나눠야하고, 각 부분에 적어도 한자리는 있어야 한다. 예를 들어, 12345는 총 4가지 방법으로 나눌 수 있다. 1-2345, 12-345, 123-45, 1234-5 어떤 수 N이 주어질 때, 이 수가 유진수인지 아닌지 구하는 프로그램을 작성하시오. 입력 첫째 줄에 수 N이 주어진다. 이 수는 2,147,483,647보다 작거나 ..

문제 오민식 선생님은 올해 형택초등학교 6학년 1반 담임을 맡게 되었다. 오민식 선생님은 우선 임시로 반장을 정하고 학생들이 서로 친숙해진 후에 정식으로 선거를 통해 반장을 선출하려고 한다. 그는 자기반 학생 중에서 1학년부터 5학년까지 지내오면서 한번이라도 같은 반이었던 사람이 가장 많은 학생을 임시 반장으로 정하려 한다. 그래서 오민식 선생님은 각 학생들이 1학년부터 5학년까지 몇 반에 속했었는지를 나타내는 표를 만들었다. 예를 들어 학생 수가 5명일 때의 표를 살펴보자. 위 경우에 4번 학생을 보면 3번 학생과 2학년 때 같은 반이었고, 3번 학생 및 5번 학생과 3학년 때 같은 반이었으며, 2번 학생과는 4학년 때 같은 반이었음을 알 수 있다. 그러므로 이 학급에서 4번 학생과 한번이라도 같은 반..

문제 동호는 내년에 초등학교를 입학한다. 그래서 동호 어머니는 수학 선행 학습을 위해 쉽게 푸는 문제를 동호에게 주었다. 이 문제는 다음과 같다. 1을 한 번, 2를 두 번, 3을 세 번, 이런 식으로 1 2 2 3 3 3 4 4 4 4 5 .. 이러한 수열을 만들고 어느 일정한 구간을 주면 그 구간의 합을 구하는 것이다. 하지만 동호는 현재 더 어려운 문제를 푸느라 바쁘기에 우리가 동호를 도와주자. 입력 첫째 줄에 구간의 시작과 끝을 나타내는 정수 A, B(1 ≤ A ≤ B ≤ 1,000)가 주어진다. 즉, 수열에서 A번째 숫자부터 B번째 숫자까지 합을 구하면 된다. 출력 첫 줄에 구간에 속하는 숫자의 합을 출력한다. 내 풀이 n, m = map(int, input().split(" ")) k = 1 ..