자료구조

문제 : https://www.acmicpc.net/problem/5052 5052번: 전화번호 목록 첫째 줄에 테스트 케이스의 개수 t가 주어진다. (1 ≤ t ≤ 50) 각 테스트 케이스의 첫째 줄에는 전화번호의 수 n이 주어진다. (1 ≤ n ≤ 10000) 다음 n개의 줄에는 목록에 포함되어 있는 전화번호가 www.acmicpc.net 어떤 문제인가? 전화번호 목록에 여러 개의 전화번호가 존재한다. 문제의 예시처럼 선영이에게 전화를 걸기 위해선 911을 눌러야 하지만 911이란 번호가 긴급전화라 전화 버튼을 누르지 않아도 바로 전화가 걸린다. 따라서 선영이에게 전화를 거는 것은 불가능하다. 이러한 전화번호 목록을 일관성이 없다고 문제에서 표현했다. 문제는 어떠한 전화번호 목록이 일관성이 있는지 없..

문제 : https://www.acmicpc.net/problem/19638 19638번: 센티와 마법의 뿅망치 마법의 뿅망치를 센티의 전략대로 이용하여 거인의 나라의 모든 거인이 센티보다 키가 작도록 할 수 있는 경우, 첫 번째 줄에 YES를 출력하고, 두 번째 줄에 마법의 뿅망치를 최소로 사용한 횟수 www.acmicpc.net 어떤 문제인가? 때리면 키가 키/2가 되는 뿅망치를 n번 때려 거인들의 키가 센티보다 작게 할 수 있는지 여부 할 수 있다 -> 뿅망치 사용 횟수 출력 할 수 없다 -> 가장 큰 거인의 키 출력 간단하게 정리해보면 위와 같다. 접근 방법 문제에서 키가 가장 큰 거인부터 때리라고 알려줬다. 그러면 일단 거인들을 키가 큰 순서대로 정렬해야 했다. 키를 다 입력하고 정렬을 한다면 ..

문제 : https://www.acmicpc.net/problem/14713 14713번: 앵무새 자가용 비행기를 타고 세계 일주를 하던 pps789와 cseteram은 어느 날 엔진 고장으로 인해 이름 모를 섬에 불시착하게 된다. 그들은 이 섬을 탐험하는 도중 아주 신기한 사실을 알게 되었는데, 바로 www.acmicpc.net 어떤 문제인가? n가지의 문장과 기준이 되는 문장을 입력받는다. n가지 문장의 단어들은 뒤죽박죽 섞여있다. 이때, n가지 문장들의 단어들의 순서를 잘 조합해서 기준 문장을 만들 수 있는지의 여부를 묻는 문제이다. 접근 방법 기준 문장의 첫 단어와 n가지 문장들의 첫 단어가 일치하는지를 확인해가며 만약 일치한다면 pop 시켜주는 방법을 떠올렸다. vector와 queue를 사용해..

문제 : https://www.acmicpc.net/problem/25192 25192번: 인사성 밝은 곰곰이 첫번째 새로운 사람이 들어온 뒤 pjshwa, chansol, chogahui05은 모두 곰곰티콘으로 인사했다. 두번째 새로운 사람이 들어온 뒤 pjshwa와 chansol은 다시 곰곰티콘으로 인사했다. www.acmicpc.net 어떤 문제인가? 채팅방에 새로운 사람이 들어왔을 때 유저의 닉네임의 첫 번째 등장만이 신입에게 인사를 한 채팅이다. 그 외의 나머지는 잡답이다. 따라서 ENTER가 입력된 후에 처음 등장한 닉네임의 숫자만 세주면 된다. 접근 방법 문제를 읽자마자 map을 써야겠다고 생각했다. map user; 유저의 이름을 key로 인사 여부를 value로 저장하는 map을 선언했다..

문제 : https://www.acmicpc.net/problem/17952 17952번: 과제는 끝나지 않아! 성애는 이번 학기에 전공을 정말 많이 듣는다. 이로 인해 거의 매일을 과제를 하면서 보내고 있다. 그런데도 과제가 줄어들 기미가 보이지 않는데, 바로 분단위로 과제가 추가되고 있기 때문이 www.acmicpc.net 어떤 문제인가? 참 공감되는 문제다ㅎㅎ 입력받은 N분동 안 해결한 과제의 총점을 출력하는 문제이다. 기존 과제를 끝내지 않고 새로 받은 과제부터 끝내는 로직이 존재한다. 실제로 저렇게 하면 효율이 많이 떨어질 텐데ㅎㅎ.. 하지만 문제니까^^ 접근 방법 1이 입력됐을 때는 가장 최근의 과제를 해야 한다. 처음엔 stack을 사용해보려고 했는데 stack에 과제 해결 점수와 남은 시간..

문제 : https://www.acmicpc.net/problem/12789 12789번: 도키도키 간식드리미 인하대학교 학생회에서는 중간, 기말고사 때마다 시험 공부에 지친 학우들을 위해 간식을 나눠주는 간식 드리미 행사를 실시한다. 승환이는 시험 기간이 될 때마다 간식을 받을 생각에 두근두 www.acmicpc.net 어떤 문제인가? 일단 우리 학교 대회 문제다ㅋㅋ 괜히 반갑게 느껴진다. 문제는 1번부터 N번까지 번호표가 존재하고 번호표 순서대로 간식을 받을 수 있는지 없는지 여부를 출력하면 된다. 접근 방법 문제를 읽자마자 스택과 큐를 사용해야겠다고 떠올렸다. stack waiting; queue student; vector after; 현재 줄이 서있는 곳인 큐로, 대기 공간은 스택으로, 간식 받..

문제 : https://www.acmicpc.net/problem/5430 5430번: AC 각 테스트 케이스에 대해서, 입력으로 주어진 정수 배열에 함수를 수행한 결과를 출력한다. 만약, 에러가 발생한 경우에는 error를 출력한다. www.acmicpc.net 어떤 문제인가? 명령어와 수열을 입력받고 명령어에 맞게 연산을 실행한 후 결과를 출력하면 된다. 접근 방법 처음에는 벡터에 문자를 저장했다. 그리고 R이 입력될 때마다 reverse함수로 정말 벡터를 역순으로 만들어줬다. 당연히 결과는 시간 초과...... 그래서 다른 방법을 생각하다가 할 수 있는 연산이 2개밖에 없으니 정말 뒤집지 말고 뒤집어졌다고 생각하고 연산을 하기로 했다. 만약 현재 상태가 뒤집어져있는 상태가 아닐 때 D가 입력되면 맨..

문제 : https://www.acmicpc.net/problem/13335 13335번: 트럭 입력 데이터는 표준입력을 사용한다. 입력은 두 줄로 이루어진다. 입력의 첫 번째 줄에는 세 개의 정수 n (1 ≤ n ≤ 1,000) , w (1 ≤ w ≤ 100) and L (10 ≤ L ≤ 1,000)이 주어지는데, n은 다리를 건너는 트 www.acmicpc.net 어떤 문제인가? 문제가 길다. 간단히 말하면 n대의 트럭이 길이가 w인 다리를 건널 때 다리의 최대하중인 L을 지켜가며 건너야 한다. 이때 모든 트럭이 다리를 건너는 최소 시간을 출력하면 된다. 접근 방법 queue truck; deque bridge; 아직 다리에 올라가지 않은 트럭들은 queue를 사용해 저장한다. 다리에 올라간 트럭은 ..

문제 : https://www.acmicpc.net/problem/1158 1158번: 요세푸스 문제 첫째 줄에 N과 K가 빈 칸을 사이에 두고 순서대로 주어진다. (1 ≤ K ≤ N ≤ 5,000) www.acmicpc.net 어떤 문제인가? 1번부터 N번까지 사람이 있고 K번째 사람을 제거해가며 제거된 사람들을 순서대로 출력하는 문제이다. 접근 방법 문제에서 사람들이 원을 그리고 앉아있다는 것을 보고 원형 큐를 사용해야겠다고 생각했다. k번째 사람이 큐의 맨 앞에 오도록 해 준 다음 front를 출력하고 사람이 제거되어야 하니 pop을 해줘야겠다고 생각했다. int n, k; queue q; cin >> n >> k; for (int i = 1; i

문제 : https://www.acmicpc.net/problem/1406 1406번: 에디터 첫째 줄에는 초기에 편집기에 입력되어 있는 문자열이 주어진다. 이 문자열은 길이가 N이고, 영어 소문자로만 이루어져 있으며, 길이는 100,000을 넘지 않는다. 둘째 줄에는 입력할 명령어의 개수 www.acmicpc.net 어떤 문제인가? 문자열을 입력받고 가상의 커서가 존재해서 문자와 문자 사이를 왔다 갔다 하며 삭제하거나 추가하는 기능을 구현하면 된다. 사실 우리가 키보드로 타이핑할 때와 똑같은 경우이다. 그리고 모든 연산이 끝난 후의 문자열을 출력하면 된다. 접근 방법 vector text; string input, order; int M; cin >> input >> M; int cursor = inp..