목록분류 전체보기 (237)
Machineboy空
https://www.acmicpc.net/problem/4659 4659번: 비밀번호 발음하기 좋은 패스워드를 만드는것은 어려운 일이다. 대부분의 사용자들은 buddy처럼 발음하기 좋고 기억하기 쉬운 패스워드를 원하나, 이런 패스워드들은 보안의 문제가 발생한다. 어떤 사이트들은 xvtp www.acmicpc.net 문제요약 비밀번호가 조건에 맞는지 판단하기 난이도 Silver 5 풀이 포인트 플래그 적절히 사용 REVIEW 우선 이런 문제는 체력으로 풀 수 있기에 맞췄다. 하지만 모범 답안과 달리 조건 마다 플래그를 달아 반복문을 탈출하는 형식으로 짰다. 그리고 자음, 모음이 3번 연속되는지를 판단하는 코드도 앞선 두개를 비교하는 식으로 3덩어리씩 비교했다. 이제 모범 답안에서 배울 것. good인지 ..
이진탐색트리를 만드는 방법은 N!가지이며, worst case의 경우 find, insert, remove의 시간복잡도가 배열이나 연결리스트보다 좋지 못함. 따라서 균형잡힌 이진탐색 트리를 만드는 것이 중요한데, 여기서 사용되는 개념이 균형 계수 등이 있고, 다음 시간에 b tree나, avl tree 등을 만드는 방법을 알아볼 것임. 2.5 BST Analysis Binary Search Trees(BSTs) can take on many forms and structures even containing the same data: So we want to think about how can we build trees that are both efficient, and what happens when w..
이진 탐색트리는 정렬된 이진트리. find 시, 정렬되어 있으므로 해당 노드보다 큰지 작은지 판단 후 좌우 이동. insert 시, find와 같음. find가 반환하는 포인터를 바탕으로 삽입 위치 찾음. remove, 보통은 연결 리스트의 제거 원리가 적용되지만, 자식이 2개일 경우 IOP 순회흐름에서 우선하는 것, 즉 왼쪽 트리의 가장 아래노드와 swap후 제거한다. 이런 원리를 바탕으로 이메일(key)로 개인정보(data)에 접근하는 딕셔너리 등을 만들 때 활용되기도 한다. 2.4 Binary Search Trees(이진탐색트리) A binary search tree(BST) is an ordered binary tree capable of being used as a search structure..
https://www.acmicpc.net/problem/2910 2910번: 빈도 정렬 첫째 줄에 메시지의 길이 N과 C가 주어진다. (1 ≤ N ≤ 1,000, 1 ≤ C ≤ 1,000,000,000) 둘째 줄에 메시지 수열이 주어진다. www.acmicpc.net 문제요약 두 가지 조건에 맞게 정렬하여 출력 난이도 Silver 3 풀이 포인트 조건 파악 1순위 : 빈도가 높을 수록 먼저 2순위: 먼저 입력받은 값일 수록 먼저 적절한 자료구조 활용 map pair; sort(v.begin(), v.end(), 비교함수); bool compare(int a, int b) { return a > b; // 내림차순 정렬 } vector vec = {3, 1, 4, 1, 5, 9, 2, 6}; sort(v..
https://www.acmicpc.net/problem/1992 1992번: 쿼드트리 첫째 줄에는 영상의 크기를 나타내는 숫자 N 이 주어진다. N 은 언제나 2의 제곱수로 주어지며, 1 ≤ N ≤ 64의 범위를 가진다. 두 번째 줄부터는 길이 N의 문자열이 N개 들어온다. 각 문자열은 0 또 www.acmicpc.net 문제요약 4분면을 나누어 탐색 후 압축하여 출력 난이도 Silver 1 풀이 포인트 입력값 받기 string 한줄로 받아 인덱스로 접근 string 111000을 int형으로 변환하여 받기 1 - '0' 이런 식 재귀 함수 짜기 재귀를 짤때는 어떤 로직이 반복되는지 정확히 체크후 반복 돌리기 로봇 청소기 똑같은 로직인데 매개변수만 바뀌는 것 분할 정복 ( Divide and Conqu..
지금까지 배운 것(array, linked list, stack, queue)는 linear or flat data structures. 오늘 배울 Tree는 data structures that provide complicated data and relationships such as a parent, child, and sibling relationships. 2.1 Tree Terminology *terminology 학술적 용어, 전문용어 (=term) A tree is a linked structure with a sense of ancestry (parents,children, siblings, and more)! Terminology Each element in our tree is a no..
https://www.acmicpc.net/problem/2828 2828번: 사과 담기 게임 상근이는 오락실에서 바구니를 옮기는 오래된 게임을 한다. 스크린은 N칸으로 나누어져 있다. 스크린의 아래쪽에는 M칸을 차지하는 바구니가 있다. (M> n >> m >> j; l = 1; for (int i = 0; i > temp; if (temp >= l && temp
https://www.acmicpc.net/problem/2583 2583번: 영역 구하기 첫째 줄에 M과 N, 그리고 K가 빈칸을 사이에 두고 차례로 주어진다. M, N, K는 모두 100 이하의 자연수이다. 둘째 줄부터 K개의 줄에는 한 줄에 하나씩 직사각형의 왼쪽 아래 꼭짓점의 x, y좌표값과 오 www.acmicpc.net 문제요약 connected component 개수와 넓이 구하기 난이도 Silver 1 풀이 포인트 DFS 일반적 x,y좌표와 2차원 배열 인덱스 간의 매핑 REVIEW dfs 문제 드디어 한 번에 정답.. 감격적 이 문제는 배열 표기와 좌표 표기가 헷갈려 for문 범위 지정이 어려웠다. 일반 좌표를 x축 회전, 그리고 y좌표와 x좌표를 바꾼 것이 2차원 배열의 인덱스와 매핑된..