목록분류 전체보기 (104)
개발자 김수진
[ 유니온 파인드란 ? ] 합집합을 찾는 대표적인 알고리즘 Disjoint-Set이라고도 부른다. - Union : 노드 X가 포함된 집합과 노드 Y가 포함된 집합을 하나로 합친다. - Find : 노드 X가 포함된 집합을 찾아준다. [ 구현 ] - i는 노드번호, parent[i]는 i 노드의 부모 노드를 저장 [그림 1]과 같이 처음에는 parent[i] 를 자기 자신인 i로 초기화한다. Union(1,2) Union(3,4)을 통해 그림 2와 같이 변한다. 노드 2의 부모 노드는 1이 되고 , 노드 4의 부모 노드는 3이 된다. Union(1,3)을 통해 노드 3의 부모 노드는 1이 된다. 따라서 1,2,3,4가 하나의 집합에 포함되는 것을 확인할 수 있다. [ Find 함수 ] 위에서 설명한 것과..
[문제] https://www.acmicpc.net/problem/4195 4195번: 친구 네트워크 첫째 줄에 테스트 케이스의 개수가 주어진다. 각 테스트 케이스의 첫째 줄에는 친구 관계의 수 F가 주어지며, 이 값은 100,000을 넘지 않는다. 다음 F개의 줄에는 친구 관계가 생긴 순서대로 주어진 www.acmicpc.net [풀이] Union-Find (혹은 Disjoint-Set)을 사용해서 풀었다. 입력 값이 문자로 주어지기 때문에 map을 사용했다. parent 배열에는 해당 index의 부모 노드 index를 저장했고 number 배열에는 부모 index를 기준으로 해당 set에 속한 노드의 개수를 저장했다. map의 count 함수를 사용해 이미 존재하는 친구인지 아닌지를 확인한다. 존재..
[문제] https://www.acmicpc.net/problem/16236 16236번: 아기 상어 N×N 크기의 공간에 물고기 M마리와 아기 상어 1마리가 있다. 공간은 1×1 크기의 정사각형 칸으로 나누어져 있다. 한 칸에는 물고기가 최대 1마리 존재한다. 아기 상어와 물고기는 모두 크기를 가�� www.acmicpc.net [풀이] 아기 상어와 물고기가 존재. 아기 상어는 자신보다 작은 물고기들을 잡아먹을 수 있다. 아기 상어는 자신보다 큰 물고기가 존재하는 칸은 지나가지 못한다. 아기 상어는 1칸 움직이는데 1초 걸린다. 아기 상어가 자신의 크기만큼 물고기를 먹는다면 크기가 1 증가한다. ( 크기가 3인 상어가 물고기 3마리를 먹으면 크기가 4가 된다.) 입력으로는 공간의 크기와 상태가 주어진다..
[문제] https://www.acmicpc.net/problem/16235 16235번: 나무 재테크 부동산 투자로 억대의 돈을 번 상도는 최근 N×N 크기의 땅을 구매했다. 상도는 손쉬운 땅 관리를 위해 땅을 1×1 크기의 칸으로 나누어 놓았다. 각각의 칸은 (r, c)로 나타내며, r은 가장 위에서부터 www.acmicpc.net [풀이] N,M,K가 주어지고 K년 후에 남아있는 나무의 수를 출력하면 된다. 따라서 for 문을 K년 동안 돌리고 for문에서 봄, 여름, 가을, 겨울에 대한 함수를 호출했다. 봄 - 에는 나무가 영양분을 먹는다. 단, 한 좌표에 나무가 2개 이상이면 나이가 어린 순서부터 영양분을 먹는다. 영양분이 부족하다면 먹지 못하고 나무는 죽는다. 여름 - 봄에 죽은 나무가 양분으..
[ 캐시란 ] Main memory와 CPU 사이에 존재하여 자주 쓰는 데이터를 저장한다. 따라서 데이터를 읽기 위해 Main memory에 접근하지 않아도 된다. => 시간 단축 [ 캐시 작동 원리 ] 시간 지역성 ( Temporal Reference) 한번 참조된 데이터는 다시 참조될 확률이 높다. 공간 지역성 ( Spatial Reference) 참조된 데이터 주변에 있는 데이터가 다음에 참조될 확률이 높다. 위의 두가지를 반복문을 예로 설명하면 i라는 변수는 다시 참조된다. => 시간 지역성 arr 주변 데이터가 참조된다. (arr[0], arr[1], ...) => 공간 지역성 for(int i=0;i
[문제] https://www.acmicpc.net/problem/16234 16234번: 인구 이동 N×N크기의 땅이 있고, 땅은 1×1개의 칸으로 나누어져 있다. 각각의 땅에는 나라가 하나씩 존재하며, r행 c열에 있는 나라에는 A[r][c]명이 살고 있다. 인접한 나라 사이에는 국경선이 존재한다. 모�� www.acmicpc.net [풀이] 인구 차가 L 이상, R 이하라면 queue와 vector에 넣어서 인구 이동 할 수 있는 좌표 모두 구하고 마지막에 인구 평균 구하고 map을 평균 값으로 update 해준다. queue는 BFS로 풀기 위해서 사용 vector는 나중에 인구 이동 하고 인구 수 update 하기 위한 좌표들 저장 solve 함수에서 평균 인구 수 구하고 vector에 저장된 ..
[문제] https://programmers.co.kr/learn/courses/30/lessons/59410 코딩테스트 연습 - NULL 처리하기 ANIMAL_INS 테이블은 동물 보호소에 들어온 동물의 정보를 담은 테이블입니다. ANIMAL_INS 테이블 구조는 다음과 같으며, ANIMAL_ID, ANIMAL_TYPE, DATETIME, INTAKE_CONDITION, NAME, SEX_UPON_INTAKE는 각각 동물의 아이디 programmers.co.kr [풀이] sql 문제로 IFNULL을 사용해 이름이 NULL이면 "No name"으로 채워줬다. 또한 ANIMAL_ID를 기준으로 오름차순으로 정렬 IFNULL(필드명, "대체할 값") : 필드가 Null이면 대체할 값으로 채운다. [코드] S..
[문제] https://programmers.co.kr/learn/courses/30/lessons/42884 코딩테스트 연습 - 단속카메라 [[-20,15], [-14,-5], [-18,-13], [-5,-3]] 2 programmers.co.kr [풀이] 차량 이동경로를 sort 함수를 사용해 오름차순으로 정렬한다. 첫번째 이동경로의 진출 지점을 CCTV의 위치로 초기화 두번째 이동경로부터 마지막 이동경로까지 현재 이동경로의 진출 지점이 CCTV의 위치보다 앞에 있는 경우 => CCTV의 위치만 update 현재 이동경로의 진입 지점이 CCTV의 위치보다 뒤에 있는 경우 => CCTV의 위치 update, CCTV 설치 갯수 1 증가. [코드] #include #include #include usin..