1. 좌표압축이란 정점 번호가 1에서 $10^{9}$사이의 값으로 이루어져 있는 그래프가 하나 주어질때, 1번 정점에서 시작하여, 방문 가능한 서로 다른 노드의 수를 구하는 프로그램을 작성하세요. 일반적인 DFS 탐색으로는 1번 정점에서 N번 정점까지 번호가 매겨져 있어서, 큰 문제 없이 크기가 N인 visited 배열과 간선 정보를 나타내는 인접 리스트를 만들어 해결할 수 있습니다. 하지만 위와 같이 정점 번호가 1번에서 $10^{9}$사이로 주어진다면, visited 배열을 만드는 순간 메모리 초과로 일반적인 방법으로는 해결하기 어렵다. 그런데 조금만 생각해보면... 주어진 정점 번호를 오름차순으로 나열할때, 1,4,6,7,30,2000,$10^{9}$밖에 없으며.. 이 정점들의 번호를 1번부터 순서..
1. HashMap 해싱을 기반으로 데이터들을 관리해주는 자료구조 파이썬에서 dict와 대응된다 HashMap은 (key,value) 쌍 형태로 들어가 있어서, key와 그 key에 따른 value값을 동시에 저장하는 형태 따라서 HashMap의 삽입, 삭제, 탐색 등 모든 함수의 시간복잡도는 O(1)이다. HashMap은 TreeMap보다 속도가 빠르며, 값 자체에만 관심이 있지, 그 순서에는 관심이 없는 자료구조 HashMap 사용을 위해서 import java.util.HashMap; HashMap (name) = new HashMap(); 형태의 선언이 필요하다. K,V는 key와 value에 해당하는 타입이다. import java.util.HashMap; public class Main { p..
1. set 중복되는 요소가 없이, 순서에 상관없는 데이터들의 묶음 중복을 허용하지 않으므로 중복되는 원소가 있다면 하나만 저장함 순서가 없으므로 인덱스를 이용한 접근이 불가능하다 수학에서 집합을 표현한 자료형 >> 집합연산이 가능한데, 여집합을 나타내는 연산자는 별도로 존재하지 않아 >> 중복된 값이 존재하지 않아 담고 있는 요소를 삽입, 변경, 삭제가 가능함 >> 가변 자료형(mutable) 2. set의 메소드 리스트에서 append()를 쓰는것과는 다르게 set은 add로 추가한다는 점에서 add가 제일 중요하고.. 나머지도 알아보자고 set은 순서가 없는 자료형이기 때문에 s.pop()을 하면 랜덤하게 항목을 제거해서 반환한다고함 비슷하게 add()도 랜덤한 위치에 넣는다고 하는데 3. s.ad..
1. 문제 https://programmers.co.kr/learn/courses/30/lessons/43162 코딩테스트 연습 - 네트워크 네트워크란 컴퓨터 상호 간에 정보를 교환할 수 있도록 연결된 형태를 의미합니다. 예를 들어, 컴퓨터 A와 컴퓨터 B가 직접적으로 연결되어있고, 컴퓨터 B와 컴퓨터 C가 직접적으로 연결되어 있 programmers.co.kr 네트워크란 컴퓨터 상호 간에 정보를 교환할 수 있도록 연결된 형태를 의미합니다. 예를 들어, 컴퓨터 A와 컴퓨터 B가 직접적으로 연결되어있고, 컴퓨터 B와 컴퓨터 C가 직접적으로 연결되어 있을 때 컴퓨터 A와 컴퓨터 C도 간접적으로 연결되어 정보를 교환할 수 있습니다. 따라서 컴퓨터 A,B,C는 모두 같은 네트워크 상에 있다고 할 수 있습니다. ..
1. 문제 https://programmers.co.kr/learn/courses/30/lessons/92334 코딩테스트 연습 - 신고 결과 받기 문제 설명 신입사원 무지는 게시판 불량 이용자를 신고하고 처리 결과를 메일로 발송하는 시스템을 개발하려 합니다. 무지가 개발하려는 시스템은 다음과 같습니다. 각 유저는 한 번에 한 명의 programmers.co.kr 신입사원 무지는 게시판 불량 이용자를 신고하고 처리 결과를 메일로 발송하는 시스템을 개발하려 합니다. 무지가 개발하려는 시스템은 다음과 같습니다. 각 유저는 한 번에 한 명의 유저를 신고할 수 있습니다. 신고 횟수에 제한은 없습니다. 서로 다른 유저를 계속해서 신고할 수 있습니다. 한 유저를 여러 번 신고할 수도 있지만, 동일한 유저에 대한 신..
1. 튜플(tuple) 리스트랑 비슷하지만 [1,2,3] 대신 (1,2,3)같이 ()을 사용 리스트가 사용하는 대부분 연산이 가능하나 원소의 변경이 불가능하다 이러한 특징때문에 프로그램 동작하면서 절대 변경되어서는 안되는 데이터(예:학번, 우편번호 등)를 저장할 때 사용한다 사용자 실수에 의한 데이터 변경 에러를 미리 방지 2. 하나의 원소를 가지는 튜플 (1)은 정수로 인식하고 (1,)을 튜플로 인식 a=(1) a 1 type(a) int b=(1,) b (1,) type(b) tuple 3. 집합(set) 데이터를 순서 없이 저장하는데 중복을 허용하고 싶지 않을때 리스트보다 유용하다 s = set([1,2,3,1,2,3]) s {1,2,3} type(s) set ##리스트의 중복을 제거하는 기술 li..
딥러닝/머신러닝, 통계학, IT프로그래밍, 알고리즘을 좋아하는 사람 https://github.com/yundaehyuck
