본문 바로가기

개발 언어 및 알고리즘 기초/C언어로 푸는 백준

 (32)
[백준 1654번/C언어] 랜선 자르기, 이진탐색으로 풀이 백준 1654번 문제를 이진탐색(Binary Search)으로 풀어보았습니다. 백준 1654번: https://www.acmicpc.net/problem/1654 1654번: 랜선 자르기 첫째 줄에는 오영식이 이미 가지고 있는 랜선의 개수 K, 그리고 필요한 랜선의 개수 N이 입력된다. K는 1이상 10,000이하의 정수이고, N은 1이상 1,000,000이하의 정수이다. 그리고 항상 K ≦ N 이다. 그 www.acmicpc.net 문제 내용은 아래와 같습니다. 이 문제는 작동하게만 하려는 목표라면 굳이 이진탐색을 사용하지 않아도 되지만, 이진탐색을 사용하지 않으면 시간초과가 발생하기 때문에 효율을 위해서 이진탐색을 써야 하는 문제입니다. 사실 이진탐색만 알면 나머지 구조 자체는 크게 어려울 것이 없는..
[백준 9012번/C언어] 괄호 풀이 백준 9012번 문제를 풀어보았습니다. 백준 9012번: https://www.acmicpc.net/problem/9012 9012번: 괄호 괄호 문자열(Parenthesis String, PS)은 두 개의 괄호 기호인 ‘(’ 와 ‘)’ 만으로 구성되어 있는 문자열이다. 그 중에서 괄호의 모양이 바르게 구성된 문자열을 올바른 괄호 문자열(Valid PS, VPS)이라고 www.acmicpc.net 문제 내용은 아래와 같습니다. 예전에 유사한 문제를 아주 어렵게 풀었던 기억이 있는데, 이번에는 보다 쉽게 푼 것 같아서 뿌듯했습니다. 문제 자체가 복잡한 알고리즘을 사용해야 하는 게 아닌데 지난번엔 왜 그렇게 어렵게 풀었나 싶지만 발전했다는 것에 만족하기로 했습니다. 아마 지난번에는 stack과 queue 개..
[백준 1920번/C언어] 수 찾기, 이진탐색으로 풀이 백준 1920번 문제를 이진탐색(Binary Search)으로 풀어보았습니다. 백준 1920번: https://www.acmicpc.net/problem/1920 1920번: 수 찾기 첫째 줄에 자연수 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 줄에는 N개의 정수 A[1], A[2], …, A[N]이 주어진다. 다음 줄에는 M(1 ≤ M ≤ 100,000)이 주어진다. 다음 줄에는 M개의 수들이 주어지는데, 이 수들 www.acmicpc.net 문제 내용은 아래와 같습니다. 해당 문제를 풀이하면서, 이진탐색트리와 hash table도 사용해 보았으나, 모두 시간 초과로 실패하여 결국 Merge Sort(합병정렬)로 입력받은 배열을 정렬한 후에 Binary Search(이진탐색)를 통해 수를 찾는..
[백준 1912번/C언어] 연속합, 동적계획법으로 풀기 백준 1912번 문제를 Dynamic Programming(DP, 동적계획법)으로 풀어보았습니다. 백준 1912번: https://www.acmicpc.net/problem/1912 1912번: 연속합 첫째 줄에 정수 n(1 ≤ n ≤ 100,000)이 주어지고 둘째 줄에는 n개의 정수로 이루어진 수열이 주어진다. 수는 -1,000보다 크거나 같고, 1,000보다 작거나 같은 정수이다. www.acmicpc.net 문제 내용은 아래와 같습니다. 목표했던 문제가 있어 동적계획법 공부를 시작하였는데, 목표했던 문제는 이미 해결했으나, 한 번 공부를 시작한 만큼 다른 문제들도 풀어보고 싶어서 이 문제를 골랐습니다. 동적계획법을 공부하고 싶으신 분들은 제 블로그에 관련된 문제를 푼 게시글이 있으니 참고해 주시기..
[백준 2565번/C언어] 전깃줄, 동적계획법으로 풀이 백준 2565번 문제를 Dynamic Programming(DP, 동적계획법)으로 풀어보았습니다. 백준 2565번: https://www.acmicpc.net/problem/2565 2565번: 전깃줄 첫째 줄에는 두 전봇대 사이의 전깃줄의 개수가 주어진다. 전깃줄의 개수는 100 이하의 자연수이다. 둘째 줄부터 한 줄에 하나씩 전깃줄이 A전봇대와 연결되는 위치의 번호와 B전봇대와 연결되는 www.acmicpc.net 문제 내용은 아래와 같습니다. 목표했던 문제가 있어 동적계획법 공부를 시작하였는데, 목표했던 문제는 이미 해결했으나, 한 번 공부를 시작한 만큼 다른 문제들도 풀어보고 싶어서 이 문제를 골랐습니다. 동적계획법을 공부하고 싶으신 분들은 제 블로그에 관련된 문제를 푼 게시글이 있으니 참고해 주..
[백준 11054번/C 언어] 가장 긴 바이토닉 부분 수열, 동적계획법으로 풀이 백준 11054번 문제를 Dynamic Programming (DP, 동적 계획법)으로 풀어보았습니다. 백준 11054번: https://www.acmicpc.net/problem/11054 11054번: 가장 긴 바이토닉 부분 수열 첫째 줄에 수열 A의 크기 N이 주어지고, 둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ N ≤ 1,000, 1 ≤ Ai ≤ 1,000) www.acmicpc.net 문제 내용은 아래와 같습니다. 목표했던 문제가 있어 동적계획법 공부를 시작하였는데, 목표했던 문제는 이미 해결했으나, 한 번 공부를 시작한 만큼 다른 문제들도 풀어보고 싶어서 이 문제를 골랐습니다. 동적계획법을 공부하고 싶으신 분들은 제 블로그에 관련된 문제를 푼 게시글이 있으니 참고해 주시기 ..
[백준 11053번/C언어] 가장 긴 증가하는 부분 수열, 동적계획법으로 풀이 백준 11053번 문제를 Dynamic Programming (DP, 동적 계획법)으로 풀어보았습니다. 백준 11053번: https://www.acmicpc.net/problem/11053 11053번: 가장 긴 증가하는 부분 수열 수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이 www.acmicpc.net 문제 내용은 아래와 같습니다. 목표했던 문제가 있어 동적계획법 공부를 시작하였는데, 목표했던 문제는 이미 해결했으나, 한 번 공부를 시작한 만큼 다른 문제들도 풀어보고 싶어서 이 문제를 골랐습니다...
[백준 2156번/C언어] 포도주 시식, 동적계획법으로 풀이 백준 2156번 문제를 Dynamic Programming (DP, 동적 계획법)으로 풀어보았습니다. 백준 2156번: https://www.acmicpc.net/problem/2156 2156번: 포도주 시식 효주는 포도주 시식회에 갔다. 그 곳에 갔더니, 테이블 위에 다양한 포도주가 들어있는 포도주 잔이 일렬로 놓여 있었다. 효주는 포도주 시식을 하려고 하는데, 여기에는 다음과 같은 두 가지 규 www.acmicpc.net 문제 내용은 아래와 같습니다. 목표했던 문제가 있어 동적계획법 공부를 시작하였는데, 목표했던 문제는 이미 해결했으나, 한 번 공부를 시작한 만큼 다른 문제들도 풀어보고 싶어서 이 문제를 골랐습니다. 동적계획법을 공부하고 싶으신 분들은 제 블로그에 관련된 문제를 푼 게시글이 있으니 ..
728x90

티스토리툴바