코후닝

알고리즘 분류: 그리디 알고리즘 문제 링크: https://www.acmicpc.net/problem/11047 11047번: 동전 0 첫째 줄에 N과 K가 주어진다. (1 ≤ N ≤ 10, 1 ≤ K ≤ 100,000,000) 둘째 줄부터 N개의 줄에 동전의 가치 Ai가 오름차순으로 주어진다. (1 ≤ Ai ≤ 1,000,000, A1 = 1, i ≥ 2인 경우에 Ai는 Ai-1의 배수) www.acmicpc.net 【 풀이 】 그리디 알고리즘을 활용하는 그리디 기초 문제이다. 동전 거스름돈은 항상 가장 큰 금액의 동전부터 거슬러 주는 것이 최적해이기 때문에 n개의 동전들을 배열에 저장해 주고 배열의 맨 뒤에서부터 계산해 주면 된다. 【 코드 】 #include using namespace std; i..

알고리즘 분류: 자료 구조, 문자열, 정렬, 해시를 사용한 집합과 맵 문제 링크: https://www.acmicpc.net/problem/1764 1764번: 듣보잡 첫째 줄에 듣도 못한 사람의 수 N, 보도 못한 사람의 수 M이 주어진다. 이어서 둘째 줄부터 N개의 줄에 걸쳐 듣도 못한 사람의 이름과, N+2째 줄부터 보도 못한 사람의 이름이 순서대로 주어진다. www.acmicpc.net 【 풀이 】 반복자를 생성하고 map의 멤버 함수 중 하나인 find로 key 값을 저장한다. map.find(key)는 찾고자 하는 값이 없으면 map.end()를 반환하기 때문에, 이를 이용해 개수와 key의 value를 1씩 증가시킨다. 그 후 map을 순회하면서, value값이 1인 key를 출력해 주면 된..

알고리즘 분류: 자료 구조, 큐 문제 링크: https://www.acmicpc.net/problem/18258 18258번: 큐 2 첫째 줄에 주어지는 명령의 수 N (1 ≤ N ≤ 2,000,000)이 주어진다. 둘째 줄부터 N개의 줄에는 명령이 하나씩 주어진다. 주어지는 정수는 1보다 크거나 같고, 100,000보다 작거나 같다. 문제에 나와있지 www.acmicpc.net 【 풀이 】 2023.04.09 - [백준 [BAEKJOON]] - [백준] 10845번: 큐 [C++] [백준] 10845번: 큐 [C++] 알고리즘 분류: 자료 구조, 큐 문제 링크: https://www.acmicpc.net/problem/10845 10845번: 큐 첫째 줄에 주어지는 명령의 수 N (1 ≤ N ≤ 10,..

알고리즘 분류: 자료 구조, 해시를 사용한 집합과 맵 문제 링크: https://www.acmicpc.net/problem/1620 1620번: 나는야 포켓몬 마스터 이다솜 첫째 줄에는 도감에 수록되어 있는 포켓몬의 개수 N이랑 내가 맞춰야 하는 문제의 개수 M이 주어져. N과 M은 1보다 크거나 같고, 100,000보다 작거나 같은 자연수인데, 자연수가 뭔지는 알지? 모르면 www.acmicpc.net 【 풀이 】 17219번: 비밀번호 찾기와 같이 map을 이용하여 풀 수 있는 문제이다. 2023.05.11 - [백준 [BAEKJOON]] - [백준] 17219번: 비밀번호 찾기 [C++] [백준] 17219번: 비밀번호 찾기 [C++] 알고리즘 분류: 자료 구조, 해시를 사용한 집합과 맵 문제 링크..

알고리즘 분류: 구현, 비트마스킹 문제 링크: https://www.acmicpc.net/problem/11723 11723번: 집합 첫째 줄에 수행해야 하는 연산의 수 M (1 ≤ M ≤ 3,000,000)이 주어진다. 둘째 줄부터 M개의 줄에 수행해야 하는 연산이 한 줄에 하나씩 주어진다. www.acmicpc.net 【 풀이 】 비트마스크 알고리즘을 활용하여 푸는 문제이다. 비트마스크란 이진수를 사용하는 컴퓨터 연산 방식을 이용해, 정수의 이진수 표현을 구현하는 데 사용되는 알고리즘이다. 비트연산을 이용하면, 원하는 숫자에 해당하는 인덱스의 비트를 0 또는 1로 표현하면서 집합을 구현해낼 수 있다. & 비트단위로 AND 연산 | 비트단위로 OR 연산 ^ 비트단위로 XOR 연산 ~ 단항연산자. 피연산..

알고리즘 분류: 자료 구조, 해시를 사용한 집합과 맵 문제 링크: https://www.acmicpc.net/problem/17219 17219번: 비밀번호 찾기 첫째 줄에 저장된 사이트 주소의 수 N(1 ≤ N ≤ 100,000)과 비밀번호를 찾으려는 사이트 주소의 수 M(1 ≤ M ≤ 100,000)이 주어진다. 두번째 줄부터 N개의 줄에 걸쳐 각 줄에 사이트 주소와 비밀번 www.acmicpc.net 【 풀이 】 C++ STL인 map 자료구조를 이용하면 쉽게 해결할 수 있다. mapm 위와 같이, key와 value를 pair 형식으로 저장하는 자료구조이다. 파이썬을 공부했다면 딕셔너리를 생각하면 되는데, 딕셔너리처럼 키를 통해 키에 해당하는 값에 접근할 수 있다. 즉 찾고자 하는 사이트 주소를 ..