본문 바로가기

Algorithm/자료구조

 (126)
(C++) - 백준(BOJ) 5766번 : 할아버지는 유명해! https://www.acmicpc.net/problem/5766 5766번: 할아버지는 유명해! 각 테스트 케이스마다, 당신의 프로그램은 한 행에 2등인 선수(들)의 번호를 출력해야 합니다. 2등인 선수가 두 명 이상인 경우(동점자 발생), 각 선수 번호를 공백으로 구분하여 오름차순으로 www.acmicpc.net 자료구조 (map, vector)를 사용해보는 문제였습니다. 📕 풀이방법 📔 입력 및 초기화 n주의 m명의 상위 랭커들을 입력받기위해 n, m을 선언한 뒤 n * m만큼 입력받습니다. 입력하면서 playerScoreMap에 정보를 저장해줍니다. key는 플레이어 번호, value는 점수입니다. 📔 풀이과정 1. 저장된 playerScoreMap을 순회하며 1등의 점수를 first에 저장합니다..
(C++) - 백준(BOJ) 2075번 : N번째 큰 수 https://www.acmicpc.net/problem/2075 2075번: N번째 큰 수 첫째 줄에 N(1 ≤ N ≤ 1,500)이 주어진다. 다음 N개의 줄에는 각 줄마다 N개의 수가 주어진다. 표에 적힌 수는 -10억보다 크거나 같고, 10억보다 작거나 같은 정수이다. www.acmicpc.net 자료구조 (priority_queue)를 사용한 문제였습니다. 📕 풀이방법 📔 입력 및 초기화 배열의 모양은 상관없습니다. 단순하게 n번째 큰 수이기 때문에 heap구조(min heap) 를 사용해 풀었습니다. n, pq를 선언해줍니다. 📔 풀이과정 1. n을 입력받습니다. 2. n*n만큼 수를 입력받습니다. 3. 수를 입력받고 pq에 우선 push합니다. 4. 만약 pq의 크기가 n을 넘어간다면 pq에..
(C++) - 프로그래머스(위클리 챌린지) : 4주차 https://programmers.co.kr/learn/courses/30/lessons/84325 코딩테스트 연습 - 4주차 개발자가 사용하는 언어와 언어 선호도를 입력하면 그에 맞는 직업군을 추천해주는 알고리즘을 개발하려고 합니다. 아래 표는 5개 직업군 별로 많이 사용하는 5개 언어에 직업군 언어 점수를 부 programmers.co.kr 자료구조를 사용해보는 문제였습니다. 📕 풀이방법 📔 입력 및 초기화 각 직군별 언어와 점수가 저장된 table, 질의를 하는 언어가 담긴 languages, 해당 언어의 선호도가 저장된 preference를 solution함수의 parameter로 받습니다. 📔 풀이과정 1. table의 직군별 언어들과 그 언어의 점수를 map변수 tableMap에 저장합니다...
(C++) - 백준(BOJ) 2204번 : 도비의 난독증 테스트 https://www.acmicpc.net/problem/2204 2204번: 도비의 난독증 테스트 꿍은 도비에게 영어단어들을 제시한 후 어떤 단어가 대소문자를 구분하지 않고 사전순으로 가장 앞서는지 맞추면 양말을 주어 자유를 얻게해준다고 하였다. 하지만 인성이 좋지 않은 꿍은 사실 www.acmicpc.net 자료구조 map을 이용해 해결했습니다. 📕 풀이방법 📔 입력 및 초기화 원본 문자열을 저장할 vector 변수 v, map변수 m에는 모두 소문자로만든 문자열이 key, 그 문자열의 원본문자열이 저장되어있는 v의 index를 저장했습니다. 📔 풀이과정 1. v를 저장할 때마다 해당 문자열을 모두 소문자로 바꾸고 그 인덱스를 m에 저장해줍니다. 2. map에 삽입시 자동 사전순으로 key가 저장되므..
(C++) - 백준(BOJ) 10546번 : 배부른 마라토너 https://www.acmicpc.net/problem/10546 10546번: 배부른 마라토너 마라토너라면 국적과 나이를 불문하고 누구나 참가하고 싶어하는 백준 마라톤 대회가 열린다. 42.195km를 달리는 이 마라톤은 모두가 참가하고 싶어했던 만큼 매년 모두가 완주해왔다. 단, 한 명 www.acmicpc.net map을 이용하는 문제였습니다. 📕 풀이방법 📔 입력 및 초기화 이름을 key, 이름이 나온 빈도 수를 value로 한 map변수 m을 선언한 뒤 n만큼 이름을 입력받을 때마다 해당하는 key의 value값을 1씩 증가시켜줍니다. 📔 풀이과정 1. n-1만큼 입력받으면서 해당 이름의 빈도수를 1씩 감소시켜줍니다. 2. 모두 입력 받은 뒤 m의 size만큼 loop를 돌면서 빈도수가 0이아..
(C++) - 백준(BOJ) 1811번 : 카드 놓기 https://www.acmicpc.net/problem/18115 18115번: 카드 놓기 수현이는 카드 기술을 연습하고 있다. 수현이의 손에 들린 카드를 하나씩 내려놓아 바닥에 쌓으려고 한다. 수현이가 쓸 수 있는 기술은 다음 3가지다. 제일 위의 카드 1장을 바닥에 내려놓는다. www.acmicpc.net 자료구조 (deque)를 사용한 문제였습니다. 📕 풀이방법 연산을 되감기 한다고 생각해 봅시다. 예제 입력2가 5 2 3 3 2 1 일 때 1 2 3 4 5라는 배열이 완성되어야 합니다. 여기서 답을 구하려면 2 3 3 2 1을 역순으로 배치해야합니다. 1 2 3 3 2를 한다면 원래 배열을 찾을 수 있습니다. 행동을 반대로 한다면 되감기 처럼 원래 상태가 된다고 이해하면 생각하기 수월할 것 같습..
(C++) - 백준(BOJ) 16499번 : 동일한 단어 그룹화하기 https://www.acmicpc.net/problem/16499 16499번: 동일한 단어 그룹화하기 첫째 줄에 단어의 개수 N이 주어진다. (2 ≤ N ≤ 100) 둘째 줄부터 N개의 줄에 단어가 한 줄에 하나씩 주어진다. 단어는 알파벳 소문자로만 이루어져 있고, 길이는 10을 넘지 않는다. www.acmicpc.net 자료구조를 이용한 정렬문제였습니다. 풀이방법 1. 단어의 서순은 중요하지 않으므로 매 단어마다 사전순으로 정렬하여 그 결과를 key로 결정합니다. 이를 map에다 저장해줍니다. 2. 답 출력 : map의 size를 출력해줍니다. Code #include using namespace std; int n; map m; int main(){ cin >> n; for(int i = 0; i..
(C++) - 프로그래머스(2021 카카오 채용연계형 인턴십) : 표 편집 https://programmers.co.kr/learn/courses/30/lessons/81303 코딩테스트 연습 - 표 편집 8 2 ["D 2","C","U 3","C","D 4","C","U 2","Z","Z"] "OOOOXOOO" 8 2 ["D 2","C","U 3","C","D 4","C","U 2","Z","Z","U 1","C"] "OOXOXOOO" programmers.co.kr 자료구조 활용해 푸는 구현문제였습니다. 풀이방법 삽입 삭제가 빈번해질 경우 해당 연산이 이뤄질 때마다 정렬을 하는 map같은 자료구조는 시간초과가 납니다. hash map또는 double linkedList로 구현해야합니다. Code 양방향 Linked-List #include using namespace std..

티스토리툴바