문제 https://school.programmers.co.kr/learn/courses/30/lessons/42862?language=java 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 더보기 문제 설명 점심시간에 도둑이 들어, 일부 학생이 체육복을 도난당했습니다. 다행히 여벌 체육복이 있는 학생이 이들에게 체육복을 빌려주려 합니다. 학생들의 번호는 체격 순으로 매겨져 있어, 바로 앞번호의 학생이나 바로 뒷번호의 학생에게만 체육복을 빌려줄 수 있습니다. 예를 들어, 4번 학생은 3번 학생이나 5번 학생에게만 체육복을 빌려줄 수 있습니다. 체육복이 없..
문제 https://www.acmicpc.net/problem/12789 12789번: 도키도키 간식드리미 인하대학교 학생회에서는 중간, 기말고사 때마다 시험 공부에 지친 학우들을 위해 간식을 나눠주는 간식 드리미 행사를 실시한다. 승환이는 시험 기간이 될 때마다 간식을 받을 생각에 두근두 www.acmicpc.net 👇 문제보기 👇 더보기 문제 인하대학교 학생회에서는 중간, 기말고사 때마다 시험 공부에 지친 학우들을 위해 간식을 나눠주는 간식 드리미 행사를 실시한다. 승환이는 시험 기간이 될 때마다 간식을 받을 생각에 두근두근 설레서 시험 공부에 집중을 못 한다. 이번 중간고사에서도 역시 승환이는 설레는 가슴을 안고 간식을 받기 위해 미리 공지된 장소에 시간 맞춰 도착했다. 그런데 이게 무슨 날벼락인가..
DFS & BFS? 자료의 검색, 트리나 그래프를 탐색하는 방법. 한 노드를 시작으로 인접한 다른 노드를 재귀적으로 탐색해가고 끝까지 탐색하면 다시 위로 와서 다음을 탐색하여 검색한다. 한 노드를 시작으로 인접한 모든 정점들을 우선 방문하는 방법. 더 이상 방문하지 않은 정점이 없을 때까지 방문하지 않은 모든 정점들에 대해서도 넓이 우선 검색을 적용한다. 왜 DFS & BFS 를 배울까요? 정렬된 데이터를 이분 탐색하는 것처럼 아주 효율적인 방법이 있는 반면에, 모든 경우의 수를 전부 탐색해야 하는 경우도 있습니다. DFS 와 BFS 는 그 탐색하는 순서에서 차이가 있습니다. DFS 는 끝까지 파고드는 것이고, BFS 는 갈라진 모든 경우의 수를 탐색해보고 오는 것이 차이점입니다. DFS 끝까지 파고드는..
그래프란? 큐 (Queue), 스택 (Stack) -> 선형 구조 : 데이터들을 순차적으로 나열 자료를 저장하고 꺼내는 것에 초점 트리 (Tree) -> 비선형 구조 : 데이터가 계층, 망으로 구성 표현에 초점 그래프 : 연결 관계에 초점 노드(Node): 연결 관계를 가진 각 데이터, 정점(Vertex) 간선(Edge): 노드 간의 관계를 표시한 선 인접 노드(Adjacent Node): 간선으로 직접 연결된 노드(또는 정점) 유방향 그래프 (Directed Graph) 방향이 있는 간선 간선은 단방향 관계를 나타내며, 각 간선은 한 방향으로만 진행 가능 무방향 그래프 (Undirected Graph) 방향이 없는 간선 그래프의 표현 방법 인접 행렬(Adjacency Matrix): 2차원 배열로 그래..
최대 힙 - 삽입 힙이란? 힙? 힙은 데이터에서 최대값과 최소값을 빠르게 찾기 위해 고안된 완전 이진 트리 (Tree)(Complete Binary Tree) 최대/최소의 값들이 필요한 연산에 사용 Max 힙 : 최댓값이 맨 위 Min 힙 : 최솟값이 맨 위 8 Level 0 6 3 Level 1 2 1 Level 2 # -> 이진 트리 O 완전 이진 트리 X 이므로 힙이 아님 8 Level 0 6 3 Level 1 # -> 이진 트리 O 완전 이진 트리 O 4 2 1 Level 2 # 모든 부모 노드의 값이 자식 노드보다 크므로 힙O 8 Level 0 6 3 Level 1 # -> 이진 트리 O 완전 이진 트리 O 4 2 5 Level 2 # 모든 부모 노드의 값이자식 노드보다 크지 않으므로 힙이 아님..
트리란? 큐 (Queue), 스택 (Stack) -> 선형 구조 : 데이터들을 순차적으로 나열 / 자료를 저장하고 꺼내는 것에 초점 트리 (Tree) -> 비선형 구조 : 데이터가 계층, 망으로 구성 / 표현에 초점 트리 용어 Node: 트리에서 데이터를 저장하는 기본 요소 Root Node: 트리 맨 위에 있는 노드 Level: 최상위 노드를 Level 0으로 하였을 때, 하위 Branch로 연결된 노드의 깊이를 나타냄 Parent Node: 어떤 노드의 상위 레벨에 연결된 노드 Child Node: 어떤 노드의 하위 레벨에 연결된 노드 Leaf Node(Terminal Node): Child Node가 하나도 없는 노드 (제일 끝) Sibling: 동일한 Parent Node를 가진 노드 Depth:..
해시테이블이란? 해시테이블이란 해시함수를 이용해 키를 값에 매핑하는 자료구조 구현 충돌 아무리 좋은 해시 함수라도 충돌을 피하기는 어렵다. 예측 가능한 범위 내에서 해시값이 나오고, 데이터와 짝지어지는 것이기 때문에 해시값이 중복될 수 있다. 👉 입력값이 달라도 똑같은 결과가 나오면 충돌 이를 다루는 방식은 체이닝(Chaining), 오픈 어드레싱(Open Addressing) 이 있다. 오픈 어드레싱은 탐사를 통해 ‘빈 공간을 찾아나서는’ 방식 체이닝은 충돌 발생 시 ‘연결’해가는 것 오픈 어드레싱 O(1) 체이닝 O(n) 오픈 어드레싱은 값이 뭉치는 클러스터링 이 발생할 수 있고, 체이닝은 메모리 오버헤드와 길어질 경우 탐색이 느려진다는 단점 C++, Java, Go는 체이닝을 택하고 Python, ..
스택(Stack)스택(Stack)이란?후입선출의 원칙을 따르는 자료구조로 차곡차곡 쌓아올리는(Stack) 것삽입과 삭제시에 O(1), 탐색에는 O(n)의 시간 복잡도사용 예브라우저의 뒤로가기실행 취소 (Ctrl + z)재귀 함수역순 문자열 (문자열 거꾸로 뒤집기)구현# structures.py'''연결리스트를 응용해서, 대신 제일 앞이 아니라 제일 위여야 하므로 가장 처음 걸 top으로 한다.O↓O↓O↓O↓O형태가 된다.'''class Node: def __init__(self, val = 0, next = None): self.val = val #상자 self.next = nextclass Stack: def __init__(self): self.top ..
배열(Array) 배열이란? 동일한 데이터 타입의 요소들을 연속된 메모리 공간에 순서대로 저장하는 자료구조 데이터 조회에서 O(1)의 [[시간 복잡도]]를 가진다. 장점 연속된 메모리 공간을 사용하므로 처음 데이터의 주소를 알면 나머지도 쉽게 찾을 수 있다. 단점 크기가 고정되어 추가/삭제에 제약이 있다. 연결리스트 (Linked List) 연결리스트란? 각각의 데이터가 메모리 공간 상에 고유한 노드로 존재하며, 해당 노드에 앞과 뒤의 메모리 주소를 기억하고 있는 형태 즉, 노드들이 서로 연결되어 있는 구조 데이터 조회 시 순차적으로 탐색하기 때문에 O(N)의 시간 복잡도 데이터 추가와 삭제에는 O(1)의 시간 복잡도 Array vs Linked List 배열 (Array): 파이썬의 리스트. 접근 쉬움..
이게 사실 그냥 편집기 사용법 익히려고 하는 거지... 굉장히 비효율적이고 귀찮고 의미없다는 걸 미리 말합니다... 당연히 나는 이런 방법 귀찮아서 그냥 터미널 쓴다. 빠르고 편하고 잘 되니까...... 하지만 IntelliJ를 처음 사용해보기도 하니까 이런 저런 사용법, 어디에 뭐가 있는지 알아둬서 나쁠 건 없어서 정리해보기로 했다. GitHub Repository 생성 우선 새 레포지토리를 만들고 HTTPS 주소를 복사해둔다. IntelliJ에서 GitHub계정 연결하기 나는 한국어 패키지를 다운받아 적용시켜놓아서 한국어로 뜨는데, 원래는 File > Settings Vesion Control > Git 이 때, Git이 설치되어 있어야 한다. Test를 누르면 버전 또는 설치되지 않았다는 문구가 뜨..
문제https://school.programmers.co.kr/learn/courses/30/lessons/42747 프로그래머스코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.programmers.co.kr문제설명H-Index는 과학자의 생산성과 영향력을 나타내는 지표입니다. 어느 과학자의 H-Index를 나타내는 값인 h를 구하려고 합니다. 위키백과1에 따르면, H-Index는 다음과 같이 구합니다.어떤 과학자가 발표한 논문 n편 중, h번 이상 인용된 논문이 h편 이상이고 나머지 논문이 h번 이하 인용되었다면 h의 최댓값이 이 과학자의 H-Index입니다.어떤 과학자가 발표한 논문의 인용 횟수를 ..
문제https://school.programmers.co.kr/learn/courses/30/lessons/42746 프로그래머스코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.programmers.co.kr문제설명0 또는 양의 정수가 주어졌을 때, 정수를 이어 붙여 만들 수 있는 가장 큰 수를 알아내 주세요.예를 들어, 주어진 정수가 [6, 10, 2]라면 [6102, 6210, 1062, 1026, 2610, 2106]를 만들 수 있고, 이중 가장 큰 수는 6210입니다.0 또는 양의 정수가 담긴 배열 numbers가 매개변수로 주어질 때, 순서를 재배치하여 만들 수 있는 가장 큰 수를 문자열로 바..
문제https://school.programmers.co.kr/learn/courses/30/lessons/42627 프로그래머스코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.programmers.co.kr 문제설명하드디스크는 한 번에 하나의 작업만 수행할 수 있습니다. 디스크 컨트롤러를 구현하는 방법은 여러 가지가 있습니다. 가장 일반적인 방법은 요청이 들어온 순서대로 처리하는 것입니다.예를들어- 0ms 시점에 3ms가 소요되는 A작업 요청- 1ms 시점에 9ms가 소요되는 B작업 요청- 2ms 시점에 6ms가 소요되는 C작업 요청 와 같은 요청이 들어왔습니다. 이를 그림으로 표현하면 아래와 같습니..
문제https://school.programmers.co.kr/learn/courses/30/lessons/42626 프로그래머스코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.programmers.co.kr 문제설명매운 것을 좋아하는 Leo는 모든 음식의 스코빌 지수를 K 이상으로 만들고 싶습니다. 모든 음식의 스코빌 지수를 K 이상으로 만들기 위해 Leo는 스코빌 지수가 가장 낮은 두 개의 음식을 아래와 같이 특별한 방법으로 섞어 새로운 음식을 만듭니다.섞은 음식의 스코빌 지수 = 가장 맵지 않은 음식의 스코빌 지수 + (두 번째로 맵지 않은 음식의 스코빌 지수 * 2)Leo는 모든 음식의 스코빌 ..
문제https://school.programmers.co.kr/learn/courses/30/lessons/42583 프로그래머스코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.programmers.co.kr 문제설명트럭 여러 대가 강을 가로지르는 일차선 다리를 정해진 순으로 건너려 합니다. 모든 트럭이 다리를 건너려면 최소 몇 초가 걸리는지 알아내야 합니다. 다리에는 트럭이 최대 bridge_length대 올라갈 수 있으며, 다리는 weight 이하까지의 무게를 견딜 수 있습니다. 단, 다리에 완전히 오르지 않은 트럭의 무게는 무시합니다. 예를 들어, 트럭 2대가 올라갈 수 있고 무게를 10kg까지 ..
