문제 https://programmers.co.kr/learn/courses/30/lessons/42888 코딩테스트 연습 - 오픈채팅방 오픈채팅방 카카오톡 오픈채팅방에서는 친구가 아닌 사람들과 대화를 할 수 있는데, 본래 닉네임이 아닌 가상의 닉네임을 사용하여 채팅방에 들어갈 수 있다. 신입사원인 김크루는 카카오톡 오 programmers.co.kr 풀이 간단한 구현 문제였다. 파이썬에선 defaultdict, 자바에선 HashMap 자료구조를 이용해서 풀 수 있었다. 다만, "Leave"의 경우엔 "Enter"나 "Change"와 달리 split한 배열의 길이가 2가 되므로 이에 주의해야 한다. 코드 파이썬 from collections import defaultdict def solution(rec..
문제 https://programmers.co.kr/learn/courses/30/lessons/77484 코딩테스트 연습 - 로또의 최고 순위와 최저 순위 로또 6/45(이하 '로또'로 표기)는 1부터 45까지의 숫자 중 6개를 찍어서 맞히는 대표적인 복권입니다. 아래는 로또의 순위를 정하는 방식입니다. 1 순위 당첨 내용 1 6개 번호가 모두 일치 2 5개 번호 programmers.co.kr 풀이 기본 아이디어는 순회를 하면서 주어진 두 배열의 원소를 비교하는 간단한 문제였다. 문제의 제한사항 중 '중복된 원소가 없다'라는 조건이 있었는데, 이를 이용하면 간단하게 문제를 풀 수 있다. 코드 파이썬 def solution(lottos, win_nums): answer = [] zero_cnt = 0 ..
1. 인덱스란? (http://www.btechsmartclass.com/data_structures/b-trees.html) 인덱스(Index)란 색인을 의미한다. 색인이란 책에서 중요한 단어나 항목, 고유명사 등을 쉽게 찾을 수 있도록 그것들을 일정 순서에 따라 배열한 목록이다. 데이터베이스 분야에서 말하는 인덱스는 테이블에 대한 동작의 속도를 높여주는 자료 구조를 일컫는다. 만약 색인이 없다면 원하는 내용을 찾을 때 일일이 책장을 넘기며 찾아야 하는 것처럼 데이터베이스에서도 인덱스가 없다면 Full Table Scan을 해야 한다. (http://www.btechsmartclass.com/data_structures/b-trees.html) 인덱스는 기본적으로 의 쌍으로 구성된다. 데이터 레코드에 ..
문제 https://www.acmicpc.net/problem/1939 1939번: 중량제한 첫째 줄에 N, M(1 ≤ M ≤ 100,000)이 주어진다. 다음 M개의 줄에는 다리에 대한 정보를 나타내는 세 정수 A, B(1 ≤ A, B ≤ N), C(1 ≤ C ≤ 1,000,000,000)가 주어진다. 이는 A번 섬과 B번 섬 사이에 중량제한이 www.acmicpc.net 풀이 그래프 탐색과 이분 탐색을 함께 사용하여 해결했다. 그래프 탐색이 조금 까다로웠는데, 결정 문제를 접합하면 좀 더 간단하게 해결이 가능했다. C의 범위가 굉장히 크기에 이분 탐색을 적용해야 한다. 그래프 탐색 시 인접한 노드와 연결된 다리의 중량제한이 판별하고자 하는 값(target, == mid)과 같거나 큰 경우에만 탐색할 ..
문제 https://www.acmicpc.net/problem/3020 3020번: 개똥벌레 개똥벌레 한 마리가 장애물(석순과 종유석)로 가득찬 동굴에 들어갔다. 동굴의 길이는 N미터이고, 높이는 H미터이다. (N은 짝수) 첫 번째 장애물은 항상 석순이고, 그 다음에는 종유석과 석순이 www.acmicpc.net 풀이 석순과 종유석을 별도의 리스트에 담아 정렬한 후, 이진 탐색을 진행하면 얼마나 많은 장애물을 파괴해야 하는지 구할 수 있다. 이때, bisect 모듈을 사용하면 좀 더 간결하게 코드를 짤 수 있다. 해당 함수들은 리스트에서 특정 값이 삽입될 인덱스를 반환한다. bisect_left(arr, value) bisect_right(arr, value) bisect — 배열 이진 분할 알고리즘 —..
