본문 바로가기

algorithm/BOJ

(63)
백준 3055_암호만들기(C++) www.acmicpc.net/problem/1759 1759번: 암호 만들기 첫째 줄에 두 정수 L, C가 주어진다. (3 ≤ L ≤ C ≤ 15) 다음 줄에는 C개의 문자들이 공백으로 구분되어 주어진다. 주어지는 문자들은 알파벳 소문자이며, 중복되는 것은 없다. www.acmicpc.net [문제 풀이] 시뮬레이션을 통해 문제를 해결했습니다. 이 문제의 경우 정렬과 조합을 이용하면 쉽게 풀리는 문제였습니다. 암호는 알파벳 순으로 나올 수 밖에 없으므로 처음에 입력받은 문자들을 정렬해 주었습니다. 그 후 문제의 답을 찾기 위해 조합을 이용하여 완전 탐색을 해주었습니다. 조합을 구현하는 과정에서 자음과 모음 개수를 확인하여 주었습니다. [코드] #include #include #include #includ..
백준 3055_탈출(C++) www.acmicpc.net/problem/3055 3055번: 탈출 사악한 암흑의 군주 이민혁은 드디어 마법 구슬을 손에 넣었고, 그 능력을 실험해보기 위해 근처의 티떱숲에 홍수를 일으키려고 한다. 이 숲에는 고슴도치가 한 마리 살고 있다. 고슴도치는 제�� www.acmicpc.net [문제 풀이] 시뮬레이션을 통해 문제를 해결했습니다. 고슴도치와 물의 좌표를 queue에 저장해 BFS를 통해 문제를 해결했습니다. 문제에 따르면 물이 먼저 퍼지기 때문에 물을 먼저 queue의 크기만큼 퍼뜨려주고, 그 후 고슴도치 queue의 크기만큼 퍼뜨려 주는 식의 방법을 이용하였습니다. while 문의 탈출 조건은 고슴도치가 목적지의 도달했을 때, 혹은 목적지에 갈 수 없을 때입니다. [코드] #include #..
백준 1713_후보 추천하기(C++) www.acmicpc.net/problem/1713 1713번: 후보 추천하기 첫째 줄에는 사진틀의 개수 N이 주어진다. (1≤N≤20) 둘째 줄에는 전체 학생의 총 추천 횟수가 주어지고, 셋째 줄에는 추천받은 학생을 나타내는 번호가 빈 칸을 사이에 두고 추천받은 순서대로 � www.acmicpc.net [문제 풀이] 단순 구현을 통해 문제를 해결했습니다. 이 문제의 경우 스케줄러를 구현하는 것과 비슷한 형태였습니다. 문제를 해결하기 위해 사진틀을 map을 통해 구현하였습니다. N(사진틀)의 범위가 20 이하이므로 추천 횟수 하나마다 map을 순회하는 형식으로 구현하였습니다. [코드] #include #include using namespace std; map LRU; int N, M; int main(..
백준 1920_수 찾기(C++) www.acmicpc.net/problem/1920 1920번: 수 찾기 첫째 줄에 자연수 N(1≤N≤100,000)이 주어진다. 다음 줄에는 N개의 정수 A[1], A[2], …, A[N]이 주어진다. 다음 줄에는 M(1≤M≤100,000)이 주어진다. 다음 줄에는 M개의 수들이 주어지는데, 이 수들이 A안�� www.acmicpc.net [문제 풀이] 이분 탐색을 이용하여 풀었습니다. 이 문제의 경우 정렬이 되어있지 않으면 완전 탐색을 이용해야 합니다. 하지만 완전 탐색을 이용한다면 시간 초과가 날 것이라 생각하였기 때문에 정렬을 해주고 이분 탐색을 이용하여 문제를 풀어주었습니다. 아래 링크를 들어가시면 이분 탐색에 대한 자세한 내용을 정리해 두었습니다. steady-life.tistory.com/5..
백준 10942_팰린드롬?(C++) https://www.acmicpc.net/problem/10942 10942번: 팰린드롬? 총 M개의 줄에 걸쳐 홍준이의 질문에 대한 명우의 답을 입력으로 주어진 순서에 따라서 출력한다. 팰린드롬인 경우에는 1, 아닌 경우에는 0을 출력한다. www.acmicpc.net [문제 풀이] DP를 이용하여 문제를 해결했습니다. 이 문제의 경우 완전탐색으로 풀 경우 0.5초의 시간을 넘어가기 때문에 DP를 이용하였습니다. 세 가지의 경우로 나눠서 dp배열에 메모제이션 해주었습니다. 첫 번째 경우 문자열의 길이가 1인 경우 항상 팰린드롬은 성립하므로 dp[i][i] = 1로 메모제이션 해주었습니다. 두 번째 경우 문자열의 길이가 2인 경우 앞뒤 문자가 같은지 판별하여 같은 경우 dp[i][i+1] = 1로 메모..
백준 14889_랜선 자르기(C++) https://www.acmicpc.net/problem/1654 1654번: 랜선 자르기 첫째 줄에는 오영식이 이미 가지고 있는 랜선의 개수 K, 그리고 필요한 랜선의 개수 N이 입력된다. K는 1이상 10,000이하의 정수이고, N은 1이상 1,000,000이하의 정수이다. 그리고 항상 K ≦ N 이다. 그 www.acmicpc.net [문제 풀이] 이 문제를 풀기에 앞서 이분 탐색에 대한 정확한 이해를 하시고 푸는 것을 권장해 드립니다. https://steady-life.tistory.com/57 이분 탐색 이분 탐색 이분 탐색은 탐색 기법의 하나입니다. 탐색 범위를 두 부분으로 분할 하며 탐색한다 하여 이분 탐색이라고 이름 지어졌습니다. 이분 탐색의 핵심은 왼쪽 경계, 오른쪽 경계, 가운데를 s..
백준 5557_1학년(C++) https://www.acmicpc.net/problem/5557 5557번: 1학년 문제 상근이가 1학년 때, 덧셈, 뺄셈을 매우 좋아했다. 상근이는 숫자가 줄 지어있는 것을 보기만 하면, 마지막 두 숫자 사이에 '='을 넣고, 나머지 숫자 사이에는 '+' 또는 '-'를 넣어 등식을 만들�� www.acmicpc.net [문제 풀이] DP를 이용하여 문제를 풀었습니다. 1부터 N까지 받은 후에 2부터 N-1까지 돌면서 dp[i][j]에 먼저 체크해주었습니다. 상근이는 0~20까지의 숫자까지만 알기 때문에 j를 21로 크기를 선언하고 - +가 범위를 벗어나는지 보고 벗어나면 무시하고 아니면 더하는 식으로 했습니다. [코드] #include using namespace std; int N; int arr[..
백준 12865_평범한 배낭(C++) https://www.acmicpc.net/problem/12865 12865번: 평범한 배낭 첫 줄에 물품의 수 N(1 ≤ N ≤ 100)과 준서가 버틸 수 있는 무게 K(1 ≤ K ≤ 100,000)가 주어진다. 두 번째 줄부터 N개의 줄에 거쳐 각 물건의 무게 W(1 ≤ W ≤ 100,000)와 해당 물건의 가치 V(0 ≤ V ≤ 1,000) www.acmicpc.net [문제 풀이] DP를 이용하여 문제를 풀었습니다. 물건 N 개번 돌리면서 각각 돌면서 무게별로 준서가 배낭에 그 물건을 담았을 때와 담지 않았을 때를 고려해서 그러한 두값의 MAX로 풀었습니다. [코드] #include #include #include using namespace std; int N, K; vector item; i..