본문 바로가기

Algorithm/자료구조

 (126)
(C++) - 백준(BOJ) 4158 : CD https://www.acmicpc.net/problem/4158 4158번: CD 입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스의 첫째 줄에는 상근이가 가지고 있는 CD의 수 N, 선영이가 가지고 있는 CD의 수 M이 주어진다. N과 M은 최대 백만이다. 다음 줄 www.acmicpc.net 적합한 자료구조를 찾아 자료를 저장해 해결한 문제였습니다. 📕 풀이방법 📔 입력 및 초기화 n, m, 정답을 출력할 ans, unordered_map sangeunCD를 선언한 후 매 test case별로 입력받습니다. 📔 풀이과정 set또는 map은 원소조회에 걸리는 시간복잡도가 logn이 소모됩니다. 최대 100만에 달하는 원소가 input으로 들어오게 되므로 O(100만log100만)은 ..
(C++) - 백준(BOJ) 2358 : 평행선 https://www.acmicpc.net/problem/2358 2358번: 평행선 첫째 줄에 n(1 ≤ n ≤ 100,000)이 주어진다. 다음 n개의 줄에는 각 점의 좌표가 주어진다. 만약 입력에 서로 같은 두 점이 주어지면, 그 두 점을 이용하여 직선을 만들 수 있다. 좌표는 절댓값이 231보 www.acmicpc.net 자료구조 map을 사용하는 문제였습니다. 📕 풀이방법 📔 입력 및 초기화 점 개수 n, 정답출력위한 변수 ans, map xMap, yMap을 선언한 뒤 입력받습니다. 📔 풀이과정 n이 10만이므로 이중 for문은 시간초과가 납니다. 따라서 nlogn시간복잡도를 가진 자료구조 map으로 해결해야합니다. x축에 평행한 직선과 y축에 평행한 직선을 구하는 문제이므로 같은 x좌표에 대..
(C++) - 백준(BOJ) 5397 : 키로거 https://www.acmicpc.net/problem/5397 5397번: 키로거 첫째 줄에 테스트 케이스의 개수가 주어진다. 각 테스트 케이스는 한줄로 이루어져 있고, 강산이가 입력한 순서대로 길이가 L인 문자열이 주어진다. (1 ≤ L ≤ 1,000,000) 강산이가 백스페이스를 입 www.acmicpc.net std::list를 사용해 푼 문제였습니다. 📕 풀이방법 📔 입력 및 초기화 test case t, keyLog, list li를 선언한 뒤 적절히 입력해줍니다. 매 test case마다 li는 clear()해줍니다. 📔 풀이과정 array의 삽입, 삭제 수행시간은 중앙에 값이 삽입 또는 삭제되었을 때 나머지 원소를 당겨주는 시간까지 포함해 O(n)입니다. L이 100만 제한이므로 삭제, ..
(C++) - 백준(BOJ) 10104 : Party Invitation https://www.acmicpc.net/problem/10104 10104번: Party Invitation The first line of input contains the integer K (1 ≤ K ≤ 100). The second line of input contains the integer m (1 ≤ m ≤ 10), which is the number of rounds of removal. The next m lines each contain one integer. The ith of these lines (1 ≤ i ≤ m) www.acmicpc.net 자료구조를 사용하는 문제였습니다. 📕 풀이방법 📔 입력 및 초기화 친구 수 k, list에서 지워지는 단위 m, 친구 list frie..
(C++) - 백준(BOJ) 11576 : Base Conversion https://www.acmicpc.net/problem/11576 11576번: Base Conversion 타임머신을 개발하는 정이는 오랜 노력 끝에 타임머신을 개발하는데 성공하였다. 미래가 궁금한 정이는 자신이 개발한 타임머신을 이용하여 500년 후의 세계로 여행을 떠나게 되었다. 500년 후의 www.acmicpc.net 진법변환해 답을 저장할 자료구조를 적절히 선택하는 문제였습니다. 📕 풀이방법 📔 입력 및 초기화 1. 진법 a, 진법 b, a를 구성하는 10진수로 표현된 수의 개수m, 개수를 저장할 vector nums, 정답을 출력할 stack ans를 선언 후 적절히 입력받습니다. 2. m만큼 for loop를 수행하며 nums에 수들을 입력받고 저장합니다. 📔 풀이과정 함수 convert..
(C++) - 백준(BOJ) 1417 : 국회의원 선거 https://www.acmicpc.net/problem/1417 1417번: 국회의원 선거 첫째 줄에 후보의 수 N이 주어진다. 둘째 줄부터 차례대로 기호 1번을 찍으려고 하는 사람의 수, 기호 2번을 찍으려고 하는 수, 이렇게 총 N개의 줄에 걸쳐 입력이 들어온다. N은 50보다 작거나 같 www.acmicpc.net 우선순위 큐를 이용하는 자료구조 문제였습니다. 📕 풀이방법 📔 입력 및 초기화 총 후보 수 n, 다솜을 찍은 사람 수 dasom, 정답을 출력할 변수 ans, 우선순위 큐 pq를 선언 후 적절히 입력받습니다. 📔 풀이과정 우선순위 큐의 default는 max heap입니다. 즉, top에는 항상 최댓값을 가지고 있습니다. pq에 원소가 존재하며 항상 top만 비교하며 dasom값 이상인..
(C++) - 백준(BOJ) 1380 : 귀걸이 https://www.acmicpc.net/problem/1380 1380번: 귀걸이 입력은 번호를 가진 시나리오들로 구성됩니다. 시나리오 번호는 1부터 순서대로 증가하고, 각 시나리오는 아래의 내용을 포함합니다. 한 줄에 귀걸이를 압수당한 여학생의 수, n (1 ≤ n ≤ 100)이 www.acmicpc.net 자료구조 문제였습니다. 📕 풀이방법 📔 입력 및 초기화 t를 선언 후 for loop를 수행하며 n이 0일 때까지 입력받습니다. 이후 이름 list를 저장할 vector name을 선언, 서순의 오류가 없도록 unordered_map m, string s를 선언해줍니다. 📔 풀이과정 귀걸이가 어처피 쌍으로 주어지므로 A, B여부는 중요하지 않습니다. m에 학생이름의 번호를 key, value를 ..
(C++) - 백준(BOJ) 1864 : 문어 숫자 https://www.acmicpc.net/problem/1864 1864번: 문어 숫자 해류가 매우 느리고 바닥을 기어다니는 생물이 적은 바다 밑바닥에서만 발견되는 잔물결 무늬의 정체는 오랫동안 해양학자들에게 수수께끼였다. 하지만 최근의 연구 성과는 동물 언어학 분야 www.acmicpc.net 자료구조, 문자열, 진수변환 문제였습니다. 📕 풀이방법 📔 입력 및 초기화 1. 문어의 수를 저장할 map변수 m, 문자열을 입력받을 s를 선언해줍니다. 2. 각 문어의 수를 10진수로 변환하기 위한 전처리를 해줍니다. 3. "#"이 나올 때까지 s에 입력해줍니다. 📔 풀이과정 convert()함수를 수행합니다. pow함수를 사용하면 8 ^ 2, 8 ^ 1식으로 지수가 포함된 식을 한번에 구할 수 있습니다. 📔..

티스토리툴바