본문 바로가기

Algorithm/자료구조

 (110)
(C++) - 백준(BOJ) 4358번 : 생태학 https://www.acmicpc.net/problem/4358 4358번: 생태학 프로그램은 여러 줄로 이루어져 있으며, 한 줄에 하나의 나무 종 이름이 주어진다. 어떤 종 이름도 30글자를 넘지 않으며, 입력에는 최대 10,000개의 종이 주어지고 최대 1,000,000그루의 나무가 주어 www.acmicpc.net 자료구조 map을 사용해보는 문제였습니다. 풀이방법 1. map의 key를 종 value를 해당 종의 나무 개수로 하여 저장합니다. 2. 정답을 출력합니다. * printf("%.소수점 몇 쨰자리f) 로 출력 형식을 고정시킬 수 있습니다. Code #include using namespace std; map m; double totalCnt; string s; int main(){ wh..
(C++) - 백준(BOJ) 7785번 : 회사에 있는 사람 https://www.acmicpc.net/problem/7785 7785번: 회사에 있는 사람 첫째 줄에 로그에 기록된 출입 기록의 수 n이 주어진다. (2 ≤ n ≤ 106) 다음 n개의 줄에는 출입 기록이 순서대로 주어지며, 각 사람의 이름이 주어지고 "enter"나 "leave"가 주어진다. "enter"인 경우는 www.acmicpc.net 정렬과 적절한 자료구조를 이용하는 문제였습니다. 풀이방법 1. n만큼 이름, 상태를 입력받습니다. 2. 상태가 "leave"라면 map에 key가 name, value는 0으로 저장합니다. "enter"라면 map에 같은 key를 가지며 value는 1로 저장합니다. 3. vector에 map의 value가 1인 것들의 이름을 저장한뒤 역순으로 정렬합니다. ..
(C++) - 백준(BOJ) 1655번 : 가운데를 말해요 https://www.acmicpc.net/problem/1655 1655번: 가운데를 말해요 첫째 줄에는 수빈이가 외치는 정수의 개수 N이 주어진다. N은 1보다 크거나 같고, 100,000보다 작거나 같은 자연수이다. 그 다음 N줄에 걸쳐서 수빈이가 외치는 정수가 차례대로 주어진다. 정수는 -1 www.acmicpc.net 우선순위 큐 문제였습니다. 풀이방법 * 입 출력이 많으므로 c와 동기화를 끊어줘야 합니다. 제 소스코드의 #define의 fastio 참고하세요. 최대 힙, 최소 힙 이렇게 두 개의 우선순위 큐를 선언해줍니다. 이 두개로 중앙값을 찾기 위해 규칙을 세웁니다. 1. 최대 힙과 최소 힙의 원소 개수가 같다면 최대힙에 push를 먼저해줍니다. 2. 최소 힙의 원소들은 최대 힙의 원소 이..
(C++) - 백준(BOJ) 3273번 : 두 수의 합 답 www.acmicpc.net/problem/3273 3273번: 두 수의 합 n개의 서로 다른 양의 정수 a1, a2, ..., an으로 이루어진 수열이 있다. ai의 값은 1보다 크거나 같고, 1000000보다 작거나 같은 자연수이다. 자연수 x가 주어졌을 때, ai + aj = x (1 ≤ i < j ≤ n)을 만족하는 www.acmicpc.net map을 이용해 푼 문제였습니다. 풀이방법 1. map에 key는 a의 원소, value는 존재여부(0은 없음,1은 있음)으로 해 저장합니다. 2. (x - map.first, map.first) 가 모두 1이라면 한 쌍이 만들어지므로 답 변수 ans++해줍니다. 3. 중복해서 더해졌으므로 ans/2를 출력합니다. Code #include #define l..
(C++) - 백준(BOJ) 11652번 : 카드 답 www.acmicpc.net/problem/11652 11652번: 카드 준규는 숫자 카드 N장을 가지고 있다. 숫자 카드에는 정수가 하나 적혀있는데, 적혀있는 수는 -262보다 크거나 같고, 262보다 작거나 같다. 준규가 가지고 있는 카드가 주어졌을 때, 가장 많이 가지 www.acmicpc.net map을 사용해 푼 문제였습니다. 풀이방법 1. key : 카드의 수, value : 해당 수가 나온 개수인 map자료구조 변수 m을 선언합니다. 2. 가장 많이 나온 수를 구하고 map을 처음부터 순회하면서 iterator의 second와 같다면 first를 출력하고 종료합니다. *int범위를 초과하므로 변수를 long long으로 선언해야합니다. Code #include #define ll long l..
(C++) - 백준(BOJ) 17298번 : 오큰수 답 www.acmicpc.net/problem/17298 17298번: 오큰수 첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000,000)이 주어진다. 둘째에 수열 A의 원소 A1, A2, ..., AN (1 ≤ Ai ≤ 1,000,000)이 주어진다. www.acmicpc.net stack으로 푼 문제였습니다. 풀이방법 1. 인덱스를 넣어줄 스택을 만들어줍니다. 입력을 받은 뒤, 스택이 비어있지 않다면 현재 값보다 작은 동안 해당 인덱스의 값을 갱신해주고 스택 pop해줍니다. 2. 그렇게 모두 수행한다면 찌꺼기가 남는데 오른쪽에 더이상큰 값이 없는 경우에 해당합니다. 그런 값들의 index를 저장하고 있는 stack에 대해 stack이 빌 때까지 top에 해당하는 인덱스의 값들을 -1하고 pop해줍니..
(C++) - 프로그래머스(월간 코드 챌린지 시즌2) : 괄호 회전하기 programmers.co.kr/learn/courses/30/lessons/76502 코딩테스트 연습 - 괄호 회전하기 programmers.co.kr 간단한 스택, 구현 문제였습니다. 풀이방법 1. 왼쪽으로 회전시킨다는 의미는 가장 끝에있는 문자열을 처음으로 위치시키고 0번쨰 ~ size-1까지를 그 다음에 위치시키는 것입니다. 회전한 문자열을 반환하는 함수를 만들어줍니다. 2. 올바른 문자열인지 check해주는 함수를 만들어 줍니다. 여는 괄호라면 stack에 해당 문자열을 push해줍니다. 닫는 괄호라면 다음을 수행합니다. 먼저 여는 괄호가 없는데 닫는 괄호가 나왔다면 0을 반환합니다. stack이 비어있을 때 stack.top()을 해서 접근하면 segmentation fault이므로 !empt..
(C++) - 백준(BOJ) 1918번 : 후위 표기식 www.acmicpc.net/problem/1918 1918번: 후위 표기식 첫째 줄에 중위 표기식이 주어진다. 단 이 수식의 피연산자는 A~Z의 문자로 이루어지며 수식에서 한 번씩만 등장한다. 그리고 -A+B와 같이 -가 가장 앞에 오거나 AB와 같이 *가 생략되는 등의 수식 www.acmicpc.net stack으로 해결한 문제였습니다. 풀이방법 1. 정답을 출력할 string 변수 ans, 연산자를 넣어줄 stack op 변수를 선언합니다. 2. 입력받은 string 변수 str의 size만큼 loop를 돌며 다음을 수행합니다. 2-1. str[i] == '('면 무조건 op에 push 2-2. str[i] == ')'면 '('를 포함한 한블럭의 op를 pop() 2-3. str[i] == '*' ..

티스토리툴바