백준(4)
-
[백준] 집합과 맵 연습문제 (1764번, 10815번, 14425번, 7785번)
1764번: 듣보잡 김진영이 듣도 못한 사람의 명단과, 보도 못한 사람의 명단이 주어질 때, 듣도 보도 못한 사람의 명단을 구하는 프로그램을 작성하시오. 입력: 첫째 줄에 듣도 못한 사람의 수 N, 보도 못한 사람의 수 M이 주어진다. 이어서 둘째 줄부터 N개의 줄에 걸쳐 듣도 못한 사람의 이름과, N+2째 줄부터 보도 못한 사람의 이름이 순서대로 주어진다. 이름은 띄어쓰기 없이 알파벳 소문자로만 이루어지며, 그 길이는 20 이하이다. N, M은 500,000 이하의 자연수이다. 듣도 못한 사람의 명단에는 중복되는 이름이 없으며, 보도 못한 사람의 명단도 마찬가지이다. 출력: 듣보잡의 수와 그 명단을 사전순으로 출력한다. 문제를 보자마자 "교집합->set을 이용하자" 를 떠올렸다. Intersection..
2024.04.13 -
큐 vs 덱 (백준 2164) (feat. 요세푸스 문제)
백준 2164번: 카드 2 N장의 카드가 있다. 각각의 카드는 차례로 1부터 N까지의 번호가 붙어 있으며, 1번 카드가 제일 위에, N번 카드가 제일 아래인 상태로 순서대로 카드가 놓여 있다. 이제 다음과 같은 동작을 카드가 한 장 남을 때까지 반복하게 된다. 우선, 제일 위에 있는 카드를 바닥에 버린다. 그 다음, 제일 위에 있는 카드를 제일 아래에 있는 카드 밑으로 옮긴다. 예를 들어 N=4인 경우를 생각해 보자. 카드는 제일 위에서부터 1234 의 순서로 놓여있다. 1을 버리면 234가 남는다. 여기서 2를 제일 아래로 옮기면 342가 된다. 3을 버리면 42가 되고, 4를 밑으로 옮기면 24가 된다. 마지막으로 2를 버리고 나면, 남는 카드는 4가 된다. N이 주어졌을 때, 제일 마지막에 남게 되..
2024.04.13 -
탐색 알고리즘 (백준 1920번)
무작위로 N개의 수가 들어있는 리스트가 있다고 하자. 이 안에 특정 수 x가 들어있는지 찾는 최적의 알고리즘은 무엇일까? 이런 류의 문제를 탐색(searching)문제라고 한다. 탐색 문제에는 크게 세 가지 알고리즘이 있다. 선형 탐색(linear searching) 복잡도 : O(N) 선형 탐색은 N개의 수를 하나씩 차례대로 x인지 비교하는 방법이다. 이는 가장 간단한 알고리즘이지만 N이 커질 때 복잡도가 크게 늘어난다. 파이썬의 in 연산자가 선형 탐색을 이용한다. 이진 탐색(binary searching) 복잡도 : O(logN) 정렬된 리스트에서 사용 가능한 알고리즘으로, 아래의 순서로 진행된다. 리스트의 중간 인덱스를 잡고, 해당 인덱스의 값을 x와 비교하여 같으면 종료한다. 다르다면, 크기를 ..
2024.03.25 -
스택(stack)구조란? (백준 9012번, 10828번)
스택 구조란, 쌓여 있는(stack) 더미처럼 된 자료구조를 말한다. 그림처럼 쌓은 수건을 위에서부터 사용하면서, 빨래한 새 수건을 다시 위에 쌓으면 아래 있는 수건은 계속 안 써서 먼지가 쌓인다. 이 구조가 스택 구조이다. 스택 구조는 나중에 들어온 데이터가 먼저 나가는 LIFO(Last In, First Out) 구조이다. 또한, 스택에 데이터를 넣는 것을 push, 데이터를 (위에서) 빼는 것을 pop이라고 한다. 백준 9012번: 괄호 백준 9012번(괄호)는 스택 문제의 대표적인 유형이다. 괄호 문자열(Parenthesis String, PS)은 두 개의 괄호 기호인 ‘(’ 와 ‘)’ 만으로 구성되어 있는 문자열이다. 그 중에서 괄호의 모양이 바르게 구성된 문자열을 올바른 괄호 문자열(Valid..
2024.03.25