개발 언어 및 알고리즘 기초 (43) 썸네일형 리스트형 [백준 12865번/C언어] 평범한 배낭, 동적계획법으로 풀이 (KnapSack Problem) 백준 12865번 문제를 Dynamic Programming (DP, 동적 계획법)을 이용하여 풀어보았습니다. 이 문제는 대표적인 냅섹 문제(KnapSack Problem)에 해당합니다. 백준 12865번: https://www.acmicpc.net/problem/2748 2748번: 피보나치 수 2 피보나치 수는 0과 1로 시작한다. 0번째 피보나치 수는 0이고, 1번째 피보나치 수는 1이다. 그 다음 2번째 부터는 바로 앞 두 피보나치 수의 합이 된다. 이를 식으로 써보면 Fn = Fn-1 + Fn-2 (n ≥ 2)가 www.acmicpc.net 문제 내용은 다음과 같습니다. 이 문제는 앞서 언급한 대로 동적계획법으로 푸는 문제입니다. 혹시 동적 계획법이 익숙하지 않은 분들이라면 더 쉬운 동적계획법 .. [백준 10699번/C언어] 오늘 날짜 풀이 백준 10699번 문제를 풀어보았습니다. 백준 10699번: https://www.acmicpc.net/problem/10699 10699번: 오늘 날짜 서울의 오늘 날짜를 출력하는 프로그램을 작성하시오. www.acmicpc.net 문제 내용은 아래와 같습니다. 이 문제는 알고리즘 문제라기보다는 헤더를 익히는 문제라고 생각하시면 됩니다. 저도 사용해 본 적이 없어서 이번 기회에 검색해 보며 공부를 해봤습니다. 제가 참고한 블로그 글은 아래와 같습니다. 잘 설명되어 있으니, 이것만 잘 안다면 어려운 부분은 딱히 없습니다. https://dev-astra.tistory.com/182 [C/C++] 현재 날짜/시간 원하는 형태로 출력하기 현재 날짜/시간 원하는 형태로 출력하기 ① 헤더 불러오기 C #incl.. [백준 1012번/C언어] 괄호 풀이 백준 1012번 문제를 풀어보았습니다. 백준 1012번: https://www.acmicpc.net/problem/1012 1012번: 유기농 배추 차세대 영농인 한나는 강원도 고랭지에서 유기농 배추를 재배하기로 하였다. 농약을 쓰지 않고 배추를 재배하려면 배추를 해충으로부터 보호하는 것이 중요하기 때문에, 한나는 해충 방지에 www.acmicpc.net 문제 내용은 아래와 같습니다. 제 블로그를 보시면 제가 비슷한 다른 문제들은 전역 변수 배열을 활용해서 해결해 왔다는 것을 알 수 있습니다. 하지만 이 문제 같은 경우에는 테스트 케이스가 한 번 실행에 하나가 아니기 때문에 전역변수를 사용하는 것의 이점이 크지 않습니다. (전역 변수를 사용하면 두 번째 테스트 케이스부터는 어차피 다시 0으로 초기화를 다.. [백준 10828번/C언어] 스택 풀이 백준 10828번 문제를 풀어보았습니다. 백준 10828번: https://www.acmicpc.net/problem/10828 10828번: 스택 첫째 줄에 주어지는 명령의 수 N (1 ≤ N ≤ 10,000)이 주어진다. 둘째 줄부터 N개의 줄에는 명령이 하나씩 주어진다. 주어지는 정수는 1보다 크거나 같고, 100,000보다 작거나 같다. 문제에 나와있지 www.acmicpc.net 문제 내용은 아래와 같습니다. 이 문제는 stack과 queue 자료구조에 대한 기본적인 이해만 있으면 어렵지 않게 풀 수 있습니다. stack은 기본적으로 queue와는 반대로 후입선출(LIFO)의 방식을 가진 자료구조로, 쌓아둔 접시를 위에서부터 꺼내는 것을 생각하면 쉽습니다. 그래서 배열을 선언하고, 배열의 끝에 .. [백준 1260번/C언어] 미로 탐색, BFS로 풀이 백준 2178번 문제를 BFS(Breadth-First Search)를 활용하여 풀어보았습니다. 백준 2178번: https://www.acmicpc.net/problem/2178 2178번: 미로 탐색 첫째 줄에 두 정수 N, M(2 ≤ N, M ≤ 100)이 주어진다. 다음 N개의 줄에는 M개의 정수로 미로가 주어진다. 각각의 수들은 붙어서 입력으로 주어진다. www.acmicpc.net 문제 내용은 아래와 같습니다. 이 문제는 처음에 다른 방식으로 접근했다가 시간초과가 떠서 다시 힌트를 조금 참고해서 BFS를 활용해서 만들었습니다. BFS 구현이나 설명은 제 블로그 글 중 아래 글에서 참고하시면 됩니다. https://programming-diary-ina.tistory.com/30 [백준 1260.. [백준 1181번/C언어] 단어 정렬, hash table과 구조체로 풀이 백준 1181번 문제를 hash table과 구조체를 이용하여 풀어보았습니다. 백준 1181번: https://www.acmicpc.net/problem/1181 1181번: 단어 정렬 첫째 줄에 단어의 개수 N이 주어진다. (1 ≤ N ≤ 20,000) 둘째 줄부터 N개의 줄에 걸쳐 알파벳 소문자로 이루어진 단어가 한 줄에 하나씩 주어진다. 주어지는 문자열의 길이는 50을 넘지 않는다. www.acmicpc.net 문제 내용은 아래와 같습니다. 이 문제 역시 정렬하는 것이지만 문자열을 정렬해야 하므로 신경 써야 할 것이 더 많습니다. 우리가 정수를 정렬할 때는 수의 크기 하나만 신경 쓰지만 여기서는 두 가지 요소 모두를 신경 써줘야 하기 때문에 더 복잡할 수 있습니다. 그래서 구현할 때 두 가지 요소 .. [백준 10989번/C언어] 수 정렬하기 3, 배열을 활용한 풀이 백준 10989번 문제를 배열을 활용하여 풀어보았습니다. 백준 10989번: https://www.acmicpc.net/problem/10989 10989번: 수 정렬하기 3 첫째 줄에 수의 개수 N(1 ≤ N ≤ 10,000,000)이 주어진다. 둘째 줄부터 N개의 줄에는 수가 주어진다. 이 수는 10,000보다 작거나 같은 자연수이다. www.acmicpc.net 문제 내용은 아래와 같습니다. 이 문제는 아주 기본에 해당하는 정렬 문제입니다. Quick Sort나 Merge Sort, Bubble Sort 등 다양한 정렬 방법이 있지만 저는 가장 간단히 해결할 수 있는 배열을 활용한 정렬 방법을 사용했습니다. 사실 공간효율은 거의 포기한 느낌의 코드라고 보시면 됩니다....ㅎㅎ 여기서는 수의 크기가 .. [백준 1260번/C언어] DFS와 BFS, Queue로 풀이 백준 1260번 문제를 큐(Queue)로 풀어보았습니다. 백준 1260번: https://www.acmicpc.net/problem/1260 1260번: DFS와 BFS 첫째 줄에 정점의 개수 N(1 ≤ N ≤ 1,000), 간선의 개수 M(1 ≤ M ≤ 10,000), 탐색을 시작할 정점의 번호 V가 주어진다. 다음 M개의 줄에는 간선이 연결하는 두 정점의 번호가 주어진다. 어떤 두 정점 사 www.acmicpc.net 문제 내용은 아래와 같습니다. DFS와 BFS에 대해서는 이전에 자료구조를 공부할 때 스택과 큐를 공부하며 코드를 구현해본 적이 있는데요, 그 때는 지금 문제와는 달리 일방향 그래프에 대해서 구현을 해서 아예 코드를 다시 작성했습니다. 이전에 일방향 그래프로 구현한 코드도 추후에 기회가.. 이전 1 2 3 4 5 6 다음
