본문 바로가기

개발일지/Problem Solving

백준 10828번 - 스택 (Stack) * 문제 링크 https://www.acmicpc.net/problem/10828 10828번: 스택 첫째 줄에 주어지는 명령의 수 N (1 ≤ N ≤ 10,000)이 주어진다. 둘째 줄부터 N개의 줄에는 명령이 하나씩 주어진다. 주어지는 정수는 1보다 크거나 같고, 100,000보다 작거나 같다. 문제에 나와있지 www.acmicpc.net 문제 내용 요약 문제에서 요구하는 명령어를 구현하는 것으로 스택이란 것을 구현해보자. 접근법 (스택이란 무엇인가?) 매우매우 중요한 자료구조 중 하나인 "스택"을 구현하는 문제다. 이 밑은 "스택"에 대한 설명으로 시작하고, Linked List는 귀찮기 때문에 간단하게 배열을 이용해서 스택을 구현하는 느낌으로 설명을 할 것이지만, 그 밑에 코드는 C++ 의 "st.. 더보기
백준 11047번 - 동전 0 * 문제 링크 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 종류 있는데, 얘네들 중에 아무 2개를 선택해도 한 동전의 값이 다른 동전의 값의 배수다. 이거로 K원을 만드는데 필요한 동전 개수의 최솟값을 구해라. ( 1 ≤ N ≤ 10, 1 ≤ K ≤ 100,000,000 ) 접근법 (그리디 알고리즘이 무엇인가) 단계별로 풀어보기 '그리디 알고리즘'의 .. 더보기
백준 11659번 - 구간 합 구하기 4 * 문제 링크 https://www.acmicpc.net/problem/11659 11659번: 구간 합 구하기 4 첫째 줄에 수의 개수 N과 합을 구해야 하는 횟수 M이 주어진다. 둘째 줄에는 N개의 수가 주어진다. 수는 1,000보다 작거나 같은 자연수이다. 셋째 줄부터 M개의 줄에는 합을 구해야 하는 구간 i와 j www.acmicpc.net 문제 내용 요약 N 개의 수가 주어지고, i 번째부터 j 번째 수까지의 합을 출력할건데, ( 1 ≤ N ≤ 100,000 , 각 수는 1,000이하 ) 이 i 와 j 입력이 M개 주어진다 .( 1 ≤ M ≤ 100,000 ) 접근법 (일단 무작정 더해보기) 누적 합 (Prefix Sum) 의 필요성을 알아보기 위해 무작정 더해보자. 시간을 생각하기 위해서는 가.. 더보기
백준 9663번 - N-Queen * 문제 링크 https://www.acmicpc.net/problem/9663 9663번: N-Queen N-Queen 문제는 크기가 N × N인 체스판 위에 퀸 N개를 서로 공격할 수 없게 놓는 문제이다. N이 주어졌을 때, 퀸을 놓는 방법의 수를 구하는 프로그램을 작성하시오. www.acmicpc.net 문제 내용 요약 N * N 체스판 위에 서로의 공격 범위에 닿지 않게 퀸 N 개를 놓는 방법의 갯수를 출력해라 ( 1 ≤ N ≤ 14 ) 접근법 일단 체스를 모르는 사람이 있을 수도 있으니 체스와 퀸에 대해 먼저 알아보자 체스를 좋아하긴 하다만 M e g a c h e s s a t r o n 그놈의 캐슬링 앙파상 뭐시기 오픈 뭐시기 뭐시기 너무 많다. (그리고 잘 알지도 못함) 정말로 체스에서의 .. 더보기
백준 9251번 - LCS (Longest Common Subsequence) * 문제 링크 https://www.acmicpc.net/problem/9251 9251번: LCS LCS(Longest Common Subsequence, 최장 공통 부분 수열)문제는 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다. 예를 들어, ACAYKP와 CAPCAK의 LCS는 ACAK가 된다. www.acmicpc.net 문제 내용 요약 문자열이 2개 주어지면 (최대 길이 1000자), 공통된 부분 수열 중 가장 긴 거 길이를 출력해라. (Longest Common Subsequence = 최장 공통 부분 수열) 접근법 매우 유명한 다이나믹 프로그래밍 문제 2 정도로 보면 된다. 항상 그렇듯이, 무엇을 어떻게 메모할지를 정하는 것이 중요하다. 첫번째 힌트로.. 더보기
백준 10254번 - 고속도로 * 문제 링크 https://www.acmicpc.net/problem/10254 10254번: 고속도로 n개의 도시를 가진 나라가 있다. 이 나라에서는 도시들 중 가장 먼 두 도시 사이에 직행 고속도로를 놓으려 한다. 고속도로는 시작점과 끝점이 아닌 다른 나라를 통과해도 된다. 즉, n개의 도시 www.acmicpc.net 문제 내용 요약 나라에 도시 N개 (2 ≤ N ≤ 200,000) 가 있는데 거기에서 가장 먼 두 도시를 찾아내라. 접근법 이 문제는 회전하는 캘리퍼스 (Rotating Calipers) 를 사용하기 때문에, 컨벡스 헐을 기본으로 깔고 가야한다. 컨벡스 헐에 대한 설명 및 내용은 아래 글 참조 https://syerco0.com/10 백준 1708번 - 볼록 껍질 * 문제 링크 ht.. 더보기
백준 2565번 - 전깃줄 * 문제 링크 https://www.acmicpc.net/problem/2565 2565번: 전깃줄 첫째 줄에는 두 전봇대 사이의 전깃줄의 개수가 주어진다. 전깃줄의 개수는 100 이하의 자연수이다. 둘째 줄부터 한 줄에 하나씩 전깃줄이 A전봇대와 연결되는 위치의 번호와 B전봇대와 연결되는 www.acmicpc.net 문제 내용 요약 전봇대에 높이에 따라 1번부터 500번까지 있는데, 전깃줄은 두 전봇대 각각의 번호 한 쌍을 연결한다. 근데 이게 교차되면 합선되니까 교차가 안되게 제거할 전깃줄의 최소 개수를 구해라 접근법 단계별로 풀어보기에도 나와있지만, 이 문제 또한 LIS의 응용 문제다. LIS에 관한 설명은 아래의 링크를 참고하자. https://syerco0.com/22 백준 11053번 - 가장.. 더보기
백준 11054번 - 가장 긴 바이토닉 부분 수열 * 문제 링크 https://www.acmicpc.net/problem/11054 11054번: 가장 긴 바이토닉 부분 수열 첫째 줄에 수열 A의 크기 N이 주어지고, 둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ N ≤ 1,000, 1 ≤ Ai ≤ 1,000) www.acmicpc.net 문제 내용 요약 어떤 수 S_k 를 기준으로 S_1 부터 S_k 까지 증가, S_k 부터 S_n 까지 감소하는 형태면 바이토닉 부분 수열이라고 부른다. 수열이 주어지면 가장 긴 바이토닉 부분 수열의 길이를 구하여라. 접근법 일단은 이 문제를 풀기 전에 LIS 문제부터 풀고 오는 것을 추천한다. https://syerco0.com/22 백준 11053번 - 가장 긴 증가하는 부분 수열 (LIS) * 문제.. 더보기
728x90
반응형

티스토리툴바