본문 바로가기

알고리즘/백준

 (263)
[백준] 1107번 : 리모컨 https://www.acmicpc.net/problem/1107 1107번: 리모컨 첫째 줄에 수빈이가 이동하려고 하는 채널 N (0 ≤ N ≤ 500,000)이 주어진다. 둘째 줄에는 고장난 버튼의 개수 M (0 ≤ M ≤ 10)이 주어진다. 고장난 버튼이 있는 경우에는 셋째 줄에는 고장난 버튼 www.acmicpc.net 리모컨의 버튼을 눌러야하는 횟수를 계산해야하는 문제이다. 고장난 버튼이 있는데 고장난 버튼을 누르지 못한다. 고장난 버튼을 누르지않고 100번에서 N번까지 리모컨을 눌러야하는 최소 횟수를 구하는 문제이다. 처음에는 그리디 방식으로 접근을 하였습니다. N과 최대한 가까운수를 구하는 방법을 찾기 시작하였고 다음 테스트 케이스 반례로 그리디 문제로 해결 할 수 없다는것을 알게 되었습니다..
[백준] 1707번 : 이분 그래프 https://www.acmicpc.net/problem/1707 1707번: 이분 그래프 입력은 여러 개의 테스트 케이스로 구성되어 있는데, 첫째 줄에 테스트 케이스의 개수 K가 주어진다. 각 테스트 케이스의 첫째 줄에는 그래프의 정점의 개수 V와 간선의 개수 E가 빈 칸을 사이에 www.acmicpc.net 해당 문제는 이분 그래프의 성질을 알야아 풀 수 있는 문제입니다. 이분 그래프는 그래프 형태의 자료구조인데 정점을 2 그룹으로 나누었을때 같은 그룹의 정점끼리 간선이 없을 경우를 이분 그래프 라고 합니다. 아래의 그림과 같이 표현 할 수 있습니다. 빨간색 정점들과 파란색 정점들이 연결되어있는 상태로 파란색 정점들끼리 연결이 되어있지 않는상태, 빨간색 정점들끼리 연결되어있지 않는 상태 입니다. 간선..
[백준] 12100번 : 2048 (Easy) https://www.acmicpc.net/problem/12100 12100번: 2048 (Easy) 첫째 줄에 보드의 크기 N (1 ≤ N ≤ 20)이 주어진다. 둘째 줄부터 N개의 줄에는 게임판의 초기 상태가 주어진다. 0은 빈 칸을 나타내며, 이외의 값은 모두 블록을 나타낸다. 블록에 쓰여 있는 수는 2 www.acmicpc.net 해당 문제는 5번의 이동으로 테이블에 있는 값중 최대값을 찾아서 리턴해야하는 문제이다. 순열 조합으로 해당 문제를 해결해야한다. R->R->R->L->R 의 결과와 R->L->R->R->R 의 결과가 다르기 때문이다. 순열의 조건으로 탐색을 시작하고 5번의 탐색의 깊이를 백트래킹 조건으로 놓는다. 즉 모든 경우의 수를 탐색하여 최대값을 리턴 하면 된다. 움직이는 조건은..
[백준] 15649번 : N과 M(1) https://www.acmicpc.net/problem/15649 15649번: N과 M (1) 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해 www.acmicpc.net 다음 문제는 문자열 처리와 백트래킹을 사용하여 문제를 해결 하였습니다. 자기 자신을 포함하고 있거나 문자열의 길이가 만족할 경우 탐색을 멈춘다. 수열을 사전 순서대로 출력해야함으로 깊이우선탐색으로 순차적으로 탐색한다. N , M = map(int, input().split()) def dfs(i, char): char += str(i) if len(char) == M: for i in range..
[백준] 9663번 : N-Queen https://www.acmicpc.net/problem/9663 9663번: N-Queen N-Queen 문제는 크기가 N × N인 체스판 위에 퀸 N개를 서로 공격할 수 없게 놓는 문제이다. N이 주어졌을 때, 퀸을 놓는 방법의 수를 구하는 프로그램을 작성하시오. www.acmicpc.net 해당 문제는 브루트포스와 백트래킹으로 문제를 해결 하였습니다. 깊이우선탐색으로 탐색 합니다. 다음열에 Queen을 놓을 수 없을때 BackTracking을 합니다. N = int(input()) count = 0 def isvalied(queens,i,j): if N > i >=0 and N > j >= 0: for queen in queens: k, n = queen if i == k or j == n or a..
[백준] 2805번 : 나무자르기 https://www.acmicpc.net/problem/2805 2805번: 나무 자르기 첫째 줄에 나무의 수 N과 상근이가 집으로 가져가려고 하는 나무의 길이 M이 주어진다. (1 ≤ N ≤ 1,000,000, 1 ≤ M ≤ 2,000,000,000) 둘째 줄에는 나무의 높이가 주어진다. 나무의 높이의 합은 항상 M보 www.acmicpc.net 해당 문제는 아래의 문제에서 최소값을 구하는과정을 추가된 경우이다. https://bigkwangs.tistory.com/38 [백준] 2110번 : 공유기 설치 https://www.acmicpc.net/problem/2110 2110번: 공유기 설치 첫째 줄에 집의 개수 N (2 ≤ N ≤ 200,000)과 공유기의 개수 C (2 ≤ C ≤ N)이 하나 ..
[백준] 2110번 : 공유기 설치 [백준] 2110번 : 공유기 설치 2110번: 공유기 설치 2110번: 공유기 설치 첫째 줄에 집의 개수 N (2 ≤ N ≤ 200,000)과 공유기의 개수 C (2 ≤ C ≤ N)이 하나 이상의 빈 칸을 사이에 두고 주어진다. 둘째 줄부터 N개의 줄에는 집의 좌표를 나타내는 xi (0 ≤ xi ≤ 1,000,000,000)가 www.acmicpc.net 📄 문제개요 해당문제는 N개의 집이 수직선위에 있을때, 공유기 C개를 각 집에 설치하여, 최대한 많은곳에서 와이파이를 사용하고자 한다. C개의 공유기를 N개의 집에 적당히 설치해서, 가장 인접한 두 공유기 사이의 거리를 최대로 하는 프로그램을 작성하시오. 🤔 문제분석 집의 개수가 N (2 ≤ N ≤ 200,000) 이고 좌표는 Xi(0≤ Xi ≤ 1,..
[백준] 5639번 : 이진 검색 트리 https://www.acmicpc.net/problem/5639 5639번: 이진 검색 트리 트리를 전위 순회한 결과가 주어진다. 노드에 들어있는 키의 값은 106보다 작은 양의 정수이다. 모든 값은 한 줄에 하나씩 주어지며, 노드의 수는 10,000개 이하이다. 같은 키를 가지는 노드는 없다 www.acmicpc.net Node의 자료구조를 만들어 문제를 해결 하였습니다. InsertNode함수는 현재 루트 노드로부터 해당 노드를 인서트 합니다. 재귀 함수를 사용하여 preOrder 함수는 전위순회로 출력하고 postOrder 함수는 후위순회로 출력합니다. import sys sys.setrecursionlimit(10**6) class Node(object): def __init__(self,dat..

티스토리툴바