본문 바로가기

Programming/백준 문제풀이

 (21)
C# 문자열 백준 문제풀이 (1157, 1316, 2675, 2908, 2941, 5622) 최근 C#을 공부하면서 차근차근 기본문제들을 C#을 이용해서 풀기로 했다. 이번에 푼 챕터는 문자열 관련 챕터이며 새롭게 알게 된 개념부터 몇 개만 소개하고 정답 공유 후 포스팅을 마치겠다. c# 인풋 받기 (input read) string input = ReadLine(); // string 경우 string[] input = ReadLine().Split(); // string split해서 입력받을 경우 int input = int.Parse(ReadLine()); // int 경우 c# 배열 초기화 (array initialization) using System.Linq; int[] freq = Enumerable.Repeat(0, 32).ToArray(); // 32개의 0값을 가지는 배열 생..
백준 2805번 나무자르기 _ 이분탐색 (python) 문제: https://www.acmicpc.net/problem/2805 2805번: 나무 자르기 문제 상근이는 나무 M미터가 필요하다. 근처에 나무를 구입할 곳이 모두 망해버렸기 때문에, 정부에 벌목 허가를 요청했다. 정부는 상근이네 집 근처의 나무 한 줄에 대한 벌목 허가를 내주었고, 상근이는 새로 구입한 목재절단기를 이용해서 나무를 구할것이다. 목재절단기는 다음과 같이 동작한다. 먼저, 상근이는 절단기에 높이 H를 지정해야 한다. 높이를 지정하면 톱날이 땅으로부터 H미터 위로 올라간다. 그 다음, 한 줄에 연속해있는 나무를 모두 절단해버린다. 따 www.acmicpc.net 이번 포스팅에서 다루게 된 2805번 나무자르기 문제는 이분탐색을 이용해야하는 전형적인 문제입니다. N은 100만 M은 20억..
백준 1629번 곱셈 _ 분할정복 (python) 문제: https://www.acmicpc.net/problem/1629 1629번: 곱셈 첫째 줄에 A, B, C가 빈 칸을 사이에 두고 순서대로 주어진다. A, B, C는 모두 2,147,483,647 이하의 자연수이다. www.acmicpc.net 이번 1629번 문제를 통해서 알아볼 개념은 분할정복입니다. 이는 딱 명확한 알고리즘이 존재하는 것이 아닌, 구하려는 값이나 그 과정이 너무 계산하기 복잡할 때 이를 간단한 문제들로 쪼개서 푼 뒤, 이를 합친다라고 생각하면 되는데요. 당장에 웹개발을 한참 공부하고 있는 저는 main.js 파일에 너무 많은 코드를 쓰다보면 나중에 오류가 발생했을 때 수정하기 어려울 뿐더러 스스로도 알아보기 힘들어 main.js에는 여러 js파일들을 import만 하고 다른..
백준 1931번 회의실배정 _ 탐욕알고리즘 (Greedy Algorithm) (python) 문제: https://www.acmicpc.net/problem/1931 1931번: 회의실배정 (1,4), (5,7), (8,11), (12,14) 를 이용할 수 있다. www.acmicpc.net 이번 1931번 문제는 정답률은 낮지만 탐욕알고리즘을 이미 알고 있었던 사람이라면, 정말 쉽게 접근이 가능했을 문제입니다. 탐욕 알고리즘이란? 모든 경우의 수를 생각하여 최선을 찾아내는 브루트포스나 동적계획법과는 달리 매 순간 순간의 선택에서 최선을 선택하는 알고리즘이라고 생각하면 되는데요. 이 문제의 경우 모든 회의 가능한 경우의 수 중 가장 많이 회의할 수 있는 경우를 찾는 형태가 브루트포스나 동적계획법의 형태라면, 그 때 그 때, 빨리 끝낼 수 있는 회의부터 끝내는 게 탐욕알고리즘이라고 할 수 있겠죠...
백준 2178번 미로 탐색 _ BFS (python) 문제: https://www.acmicpc.net/problem/2178 2178번: 미로 탐색 첫째 줄에 두 정수 N, M(2 ≤ N, M ≤ 100)이 주어진다. 다음 N개의 줄에는 M개의 정수로 미로가 주어진다. 각각의 수들은 붙어서 입력으로 주어진다. www.acmicpc.net 이번에 풀어볼 문제는 BFS(Breadth First Search) 너비우선탐색에 관한 심화 문제랍니다. 이전 2667번에서 DFS를 활용하여 문제를 풀었었던 것 처럼 1260번에서 기본적으로 구현했었던 DFS와 BFS의 구현을 활용하면 쉽게 풀 수 있는데요, 혹시 BFS의 구현이 기본적으로 어려우신 분들은 제 이전 1260번 풀이 포스팅을 참고해주세요 :) 2020/03/15 - [Programming/백준 문제풀이] ..
백준 2667번 단지번호붙이기 _ DFS (python) 문제: https://www.acmicpc.net/problem/2667 2667번: 단지번호붙이기 과 같이 정사각형 모양의 지도가 있다. 1은 집이 있는 곳을, 0은 집이 없는 곳을 나타낸다. 철수는 이 지도를 가지고 연결된 집들의 모임인 단지를 정의하고, 단지에 번호를 붙이려 한다. 여기서 연결되었다는 것은 어떤 집이 좌우, 혹은 아래위로 다른 집이 있는 경우를 말한다. 대각선상에 집이 있는 경우는 연결된 것이 아니다. 는 을 단지별로 번호를 붙인 것이다. 지도를 입력하여 단지수를 출력하고, 각 단지에 속하는 집의 수 www.acmicpc.net 이번에 풀어볼 문제는 바로 이전 포스팅에서 구현했던 DFS와 BFS문제를 활용하는 문제입니다. 그 중 DFS를 활용하는 대표적인 문제인데요. 혹시 DFS나 ..
백준 1260번 DFS와 BFS (python 구현) 문제: https://www.acmicpc.net/problem/1260 1260번: DFS와 BFS 첫째 줄에 정점의 개수 N(1 ≤ N ≤ 1,000), 간선의 개수 M(1 ≤ M ≤ 10,000), 탐색을 시작할 정점의 번호 V가 주어진다. 다음 M개의 줄에는 간선이 연결하는 두 정점의 번호가 주어진다. 어떤 두 정점 사이에 여러 개의 간선이 있을 수 있다. 입력으로 주어지는 간선은 양방향이다. www.acmicpc.net 이번 1260번 문제는 낮은 정답률과는 달리 기본적인 트리 탐색방법인 DFS(Deapth-First-Search, 깊이우선탐색)과 BFS(Breadth-First-Search, 너비우선탐색)을 구현할 수 있는 가에 대한 문제였어요. 하지만 DFS나 BFS의 기본적인 개념을 모르셨..
백준 5430번 AC _ 덱(DEQUE) (c++) 문제: https://www.acmicpc.net/problem/5430 5430번: AC 문제 선영이는 주말에 할 일이 없어서 새로운 언어 AC를 만들었다. AC는 정수 배열에 연산을 하기 위해 만든 언어이다. 이 언어에는 두 가지 함수 R(뒤집기)과 D(버리기)가 있다. 함수 R은 배열에 있는 숫자의 순서를 뒤집는 함수이고, D는 첫 번째 숫자를 버리는 함수이다. 배열이 비어있는데 D를 사용한 경우에는 에러가 발생한다. 함수는 조합해서 한 번에 사용할 수 있다. 예를 들어, "AB"는 A를 수행한 다음에 바로 이어서 B를 수행하는 함수이다. www.acmicpc.net 이 문제는 난이도 무려 19%에 달하는 나름 백준에 고난이도로 분류되는 문제이지만, 실제 구현 난이도는 그리 높지 않다. 우선 이 문..

티스토리툴바