본문 바로가기

알고리즘/백준

백준 16934 게임 닉네임 https://www.acmicpc.net/problem/16934 16934번: 게임 닉네임 첫째 줄에 가입한 유저의 수 N(1 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 N개의 줄에는 유저의 닉네임이 가입한 순서대로 한 줄에 하나씩 주어진다. 닉네임은 알파벳 소문자로만 이루어져 있고, �� www.acmicpc.net 1 . 트라이 문제에 들어가기 앞서 간단히 트라이에 대해 설명하겠다. 트라이는 문자열 검색에 특화된 트리로 다음과 같은 구조를 가지고 있다. 각 노드마다 Map을 가지고 있고, 문자열을 문자단위로 쪼개고 노드에 저장한다. 문자열를 검색하고 삽입하는데 걸리는시간은 O(NlogN)이다. 2. 알고리즘 알고리즘은 다음과 같다. 1. 문자열(word)을 문자로 쪼개고 각 문자를 노드에.. 더보기
백준 - 6198 옥상정원꾸미기 https://www.acmicpc.net/problem/6198 6198번: 옥상 정원 꾸미기 문제 도시에는 N개의 빌딩이 있다. 빌딩 관리인들은 매우 성실 하기 때문에, 다른 빌딩의 옥상 정원을 벤치마킹 하고 싶어한다. i번째 빌딩의 키가 hi이고, 모든 빌딩은 일렬로 서 있고 오른쪽으�� www.acmicpc.net 스택에 아이템을 한 개씩 push하면서 스택의 top()과 비교한다. push 한 아이템의 높이가 스택의 top() 보다 작다면 스택의 모든 원소들은 그 아이템을 볼 수 있다는 뜻이다. 그러므로 답에 스택의 크기만큼 더해준다. 아이템의 크기가 스택의 값보다 크거나 같다면 스택의 top() 더이상 아이템 오른쪽에 있는 것들을 보지 못하므로 pop 시켜주고 이를 모든 아이템에 대해서 반복하.. 더보기
JAVA 8 - (1) 람다 함수 1. 람다 함수 VS 기존 JAVA 익명 함수 , 익명 클래스 기존 Java에서도 익명함수, 익명 클래스는 있었다. 다음과 같이 표현되었다. Comparator 인터페이스를 상속받는 클래스를 상속 받기 위해 위와 같은 익명클래스를 사용하고 했다. 하지만 보다시피 코드가 너무 길고, 복잡하고, 실제로 나같은경우에도 실수를 너무 많이 했던 부분이다. 람다 함수를 이용하면 같은 코드를 훨씬 더 간결하게 쓸 수 있다. 그러면 람다함수는 어떻게 작동하는 것이고 어떤 문법을 가지고 있는지 알아보자 2. Functional Interface(함수형 인터페이스) 우선 람다함수를 알기 전에 Functional Inteface에 대해서 알고 있어야한다. Functional Interface는 Interface 중에서 단 .. 더보기
백준 세부 13905 https://www.acmicpc.net/problem/13905 13905번: 세부 첫 번째 줄에는 섬에 존재하는 집의 수 N(2≤N≤100,000)와 다리의 수 M(1≤M≤300,000)이 주어진다. 두 번째 줄에는 숭이의 출발 위치(s)와 혜빈이의 위치(e)가 주어진다. (1≤s, e≤N, s≠e). 다음 M개의 줄 www.acmicpc.net 다익스트라를 변형해서 풀면된다. 기존의 다익스트라가 한 정점에서 다른 정점으로의 최단거리를 구한다고 하면 변형된 다익스트라는 한 정점에서 다른 정점으로의 경로중로 이동하는 가중치의 최소값들의 최대값을 구하는 것이다. 예시로 든 그림을 보면 1에서 5로 가는 경로는 총 4가지다. 1) 1-2-3-5 2) 1-7-3-5 3) 1 -7-5 4) 1-7-6-5 각.. 더보기
백준 15961 회전초밥 https://www.acmicpc.net/problem/15961 15961번: 회전 초밥 첫 번째 줄에는 회전 초밥 벨트에 놓인 접시의 수 N, 초밥의 가짓수 d, 연속해서 먹는 접시의 수 k, 쿠폰 번호 c가 각각 하나의 빈 칸을 사이에 두고 주어진다. 단, 2 ≤ N ≤ 3,000,000, 2 ≤ d ≤ 3,000, 2 www.acmicpc.net 연속해서 K 개의 초밥을 먹었을때 먹을수 있는 최대의 초밥 종류 갯수를 구하는 문제다. 완전탐색을 이용할 경우 초밥의 접시가 N이 최대 300만개, 연속해서 먹을수 있는 접시의 갯수 k 가 최대 3000이므로 시간복잡도가 O(N*k) = O(300만 * 3000) = O(90억)이므로 시간초과가 난다. 연속하는 경우 수를 구할때는 투포인터를 이용하여 풀.. 더보기
백준 2458 키 순서 https://www.acmicpc.net/problem/2458 2458번: 키 순서 1번부터 N번까지 번호가 붙여져 있는 학생들에 대하여 두 학생끼리 키를 비교한 결과의 일부가 주어져 있다. 단, N명의 학생들의 키는 모두 다르다고 가정한다. 예를 들어, 6명의 학생들에 대하여 www.acmicpc.net 키를 비교한 결과가 주어졌을 때 자신의 키가 몇번째인지 알수있는 학생이 몇명인지 알아내자. 키를 비교한 결과를 그래프로 나타내면 다음과 같다. 자신이 몇번쨰인지 알기 위해서는 1. 다른 점에서 자기를 방문할수 있다. 2. 자기가 다른 점을 방문 할수 있다. 가 모든 점에 대해 만족 되야한다. 위의 그림에서 4번은 2,6번을 방문 할수있고, 1 3 5는 4를 방문할수 있으므로 4번은 자신의 순서를 알.. 더보기
백준 1766 문제집 https://www.acmicpc.net/problem/1766 1766번: 문제집 첫째 줄에 문제의 수 N(1 ≤ N ≤ 32,000)과 먼저 푸는 것이 좋은 문제에 대한 정보의 개수 M(1 ≤ M ≤ 100,000)이 주어진다. 둘째 줄부터 M개의 줄에 걸쳐 두 정수의 순서쌍 A,B가 빈칸을 사이에 두고 주 www.acmicpc.net N개의 문제는 모두 풀어야 한다. 먼저 푸는 것이 좋은 문제가 있는 문제는, 먼저 푸는 것이 좋은 문제를 반드시 먼저 풀어야 한다. 가능하면 쉬운 문제부터 풀어야 한다. (1이 가장 쉽고 N이 가장 어렵다) 내가 어떤 한 문제를 풀기 위해서는 그 문제로 들어오는 노드들 또한 풀어야만 가능하다. 즉 부모노드가 0개여야 가능하다는 뜻이다. 부모노드가 0개인 노드들을 배열.. 더보기
백준 16228 GCC의 유산 https://www.acmicpc.net/problem/16228 더보기

티스토리툴바