[백준 파이썬] 16937 두 스티커

16937번: 두 스티커 첫째 줄에 모눈종이의 크기 H, W, 둘째 줄에 스티커의 수 N이 주어진다. 다음 N개의 줄에는 스티커의 크기 Ri, Ci가 주어진다. www.acmicpc.net 문제 크기가 주어진 모눈종이에 2개의 스티커를 골라 붙혔을 때 넓이가 가장 큰 경우의 값을 구하는 문제이다. 풀이 1 ≤ H, W, N ≤ 100 1 ≤ Ri, Ci ≤ 100 조건이 다음과 같으므로 모든 경우의 수를 탐색해도 괜찮다 판단하여 브루트 포스를 사용하였다. 1. 브루트 포스 브루트 포스란 조합 가능한 모든 문자열을 하나씩 대입해 보는 방식으로 암호를 해독하는 방법이다. 2. 아이디어 먼저 가능한 경우의 수를 따져보았다. 2개의 스티커를 뽑고 각각의 스티커는 회전할 수 있으므로, 위의 그림과 같이 4가지의..

• format_list_bulleted 알고리즘
• · 2023. 10. 27.
• textsms

[백준 파이썬] 1953 팀배분

https://www.acmicpc.net/problem/1953 1953번: 팀배분 첫줄에는 청팀의 사람의 수를 출력하고, 그리고 둘째 줄에는 청팀에 속한 사람들을 오름차순으로 나열한다. 그리고 셋째 줄과 넷째 줄은 위와 같은 방법으로 백팀에 속한 인원의 수, 백팀에 속 www.acmicpc.net 문제 각 학생별로 싫어하는 학생의 번호가 주어지고 각 학생이 싫어하는 학생과 다른 팀이 되도록 분배하는 문제이다 풀이 해당 문제를 풀기위해 DFS를 사용하였다. 1. DFS DFS란 깊이 우선 탐색으로 루트 노드(혹은 다른 임의의 노드)에서 시작해서 다음 분기(branch)로 넘어가기 전에 해당 분기를 완벽하게 탐색하는 방법이다. 만약 1번학생이 싫어하는 학생에 3번일 경우 3번을 1번학생과 다른팀에 배정..

• format_list_bulleted 알고리즘
• · 2023. 10. 25.
• textsms

[백준 파이썬] 1713 후보 추천하기

문제 주어진 사진틀의 개수만큼 사진을 넣을 수 있고, 기존 사진이 들어오면 점수가 증가, 사진틀에 없는 사진이 들어오면 기존 사진틀의 사진 중 가장 낮은 점수를 가진 사진이 빠지고 새로운 사진이 들어오는 방식이다. 점수가 같아 빠지는 사진이 여러장일 경우 가장 오래된 사진이 빠진다. 풀이 처음엔 스택을 사용하려 했으나 저장해야할 배열이 사진틀, 점수, 투표된 인원 3가지이기 때문에 배열로 구현하였다. 먼저 크게 2가지로 구분하였는데, 넣으려는 후보의 사진이 이미 사진틀에 있는 경우와 없는 경우로 나누었다. 이미 사진이 있는경우 배열에서 해당사진의 위치를 찾아 점수를 +1 하였다. if vote[i] in pic: #사진틀에 이미 넣으려는 사진이 있을경우 for j in range(len(pic)): i..

• format_list_bulleted 알고리즘
• · 2023. 10. 23.
• textsms

[백준 파이썬] 20529 가장 가까운 세 사람의 심리적 거리

문제 3이상의 사람수에 대해 3명을 뽑아 두명끼리 비교하여 mbti가 다를때마다 +1을 더해 가장 적은 수가 나오는 경우를 구하는 문제이다! 풀이 모든 경우의 수를 분석하는 브루트 포스 알고리즘을 사용하여 풀었다. for i in range(N): for j in range(N): for k in range(N): tmp = 0 if i == j or j == k or k == i: continue for x in range(4): if mbti[i][x] != mbti[j][x]: tmp += 1 if mbti[j][x] != mbti[k][x]: tmp += 1 if mbti[k][x] != mbti[i][x]: tmp += 1 answer = min(answer, tmp) 3명을 뽑아야 하므로 3중..

• format_list_bulleted 알고리즘
• · 2023. 10. 20.
• textsms

[백준 파이썬] 14940 쉬운 최단거리

https://www.acmicpc.net/problem/14940 1. 문제 요약하자면 목표지점에서 모든 지점까지의 거리를 구하는문제이다. 2. 풀이 목표지점으로부터의 거리를 구하는 문제이므로 BFS를 사용하였다. BFS를 구현하기 위해 파이썬의 deque을 사용하였다. (1)BFS(너비 우선탐색) BFS는 시작지점을 방문한 후 인접한 모든 점을 우선적으로 방문하는 방법이다. (2)Deque(덱) queue와는 다르게 양방향으로 입/출력이 가능한 자료구조이다. 3. 코드 from collections import deque import sys input = sys.stdin.readline n, m = map(int, input().split()) graph = [list(map(int, input()..

• format_list_bulleted 알고리즘
• · 2023. 10. 17.
• textsms

[백준 파이썬] 1149 RGB거리

문제 RGB거리에는 집이 N개 있다. 거리는 선분으로 나타낼 수 있고, 1번 집부터 N번 집이 순서대로 있다. 집은 빨강, 초록, 파랑 중 하나의 색으로 칠해야 한다. 각각의 집을 빨강, 초록, 파랑으로 칠하는 비용이 주어졌을 때, 아래 규칙을 만족하면서 모든 집을 칠하는 비용의 최솟값을 구해보자. 1번 집의 색은 2번 집의 색과 같지 않아야 한다. N번 집의 색은 N-1번 집의 색과 같지 않아야 한다. i(2 ≤ i ≤ N-1)번 집의 색은 i-1번, i+1번 집의 색과 같지 않아야 한다. 입력 첫째 줄에 집의 수 N(2 ≤ N ≤ 1,000)이 주어진다. 둘째 줄부터 N개의 줄에는 각 집을 빨강, 초록, 파랑으로 칠하는 비용이 1번 집부터 한 줄에 하나씩 주어진다. 집을 칠하는 비용은 1,000보다 ..

• format_list_bulleted 알고리즘
• · 2023. 10. 15.
• textsms