본문 바로가기

⭐ Problem_Solving44

[백준] 14621 나만 안되는 연애 (Python/파이썬) https://www.acmicpc.net/problem/14621 14621번: 나만 안되는 연애 입력의 첫째 줄에 학교의 수 N와 학교를 연결하는 도로의 개수 M이 주어진다. (2 ≤ N ≤ 1,000) (1 ≤ M ≤ 10,000) 둘째 줄에 각 학교가 남초 대학교라면 M, 여초 대학교라면 W이 주어진다. 다음 M개의 www.acmicpc.net 1. 기본적인 MST 문제이다. 2. 대학교 남초/여초 여부를 딕셔너리 형태로 저장해서 크루스칼 알고리즘에서 다음 간선 선택 시 다른 종류의 대학교일 경우만 선택하도록 했다. 3. 그 외에는 조건을 만족하는 mst가 없을 경우 -1을 출력하도록 해야된다. import sys, os, io, atexit input = lambda: sys.stdin.read.. 2022. 10. 2.

[백준] 16724 피리 부는 사나이 (Python/파이썬) https://www.acmicpc.net/problem/16724 16724번: 피리 부는 사나이 첫 번째 줄에 지도의 행의 수를 나타내는 N(1 ≤ N ≤ 1,000)과 지도의 열의 수를 나타내는 M(1 ≤ M ≤ 1,000)이 주어진다. 두 번째 줄부터 N개의 줄에 지도의 정보를 나타내는 길이가 M인 문자열이 주 www.acmicpc.net 0. DFS / BFS (+ 유니온파인드) 문제이다. 유니온 파인드에 괄호를 친 이유는 아래 설명하겠지만 유니온 파인드를 안 쓰고 bfs만으로 풀이 하는 방법도 있기 때문이다. (아래 설명) 1. 유니온 파인드 풀이 주어진 그래프에서 dfs를 통해서 사이클을 확인하고 해당 사이클을 하나의 safezone 그룹으로 묶는 과정을 반복해야하는데 이 과정에서 유니온 파.. 2022. 10. 2.

[백준] 2146 다리 만들기 (Python/파이썬) https://www.acmicpc.net/problem/2146 2146번: 다리 만들기 여러 섬으로 이루어진 나라가 있다. 이 나라의 대통령은 섬을 잇는 다리를 만들겠다는 공약으로 인기몰이를 해 당선될 수 있었다. 하지만 막상 대통령에 취임하자, 다리를 놓는다는 것이 아깝다 www.acmicpc.net 1. 기본 접근은 각각의 섬에 다른 번호를 부여하고 각각의 섬에 대해서 bfs를 통해서 다리의 최소 길이를 구하는 것이다. 2. 다만 메모리초과가 나기 쉬워서 visited배열을 잘 활용해야 한다. 나 같은 경우는 다리 건설하는 bfs 함수 안에 visited배열을 하나 만들고, 섬의 번호에 대한 visited배열을 하나 더 만들어서 한 번 탐색한 섬에 대해서 다시 탐색하지 않도록 했다. 3. 다리를 .. 2022. 10. 1.

[백준] 20055 컨베이어 벨트 위의 로봇 (Python/파이썬) https://www.acmicpc.net/problem/20055 20055번: 컨베이어 벨트 위의 로봇 길이가 N인 컨베이어 벨트가 있고, 길이가 2N인 벨트가 이 컨베이어 벨트를 위아래로 감싸며 돌고 있다. 벨트는 길이 1 간격으로 2N개의 칸으로 나뉘어져 있으며, 각 칸에는 아래 그림과 같이 1부 www.acmicpc.net 1. 주어진 조건대로 구현하면 되는 구현 문제이다. 2. 크게 복잡한 알고리즘이나 구현은 필요 없고 문제 읽고 단계별로 각 동작을 꼼꼼히 구현하면 무난하게 통과 된다. 3. 벨트 회전은 deque의 rotate() 메서드를 이용하면 편하고 로봇의 배열 같은 경우는 데크보다 그냥 리스트가 편하고 빠르다. from collections import deque import sys,.. 2022. 9. 30.

[백준] 2212 센서 (Python/파이썬) https://www.acmicpc.net/problem/2212 2212번: 센서 첫째 줄에 센서의 개수 N(1 ≤ N ≤ 10,000), 둘째 줄에 집중국의 개수 K(1 ≤ K ≤ 1000)가 주어진다. 셋째 줄에는 N개의 센서의 좌표가 한 개의 정수로 N개 주어진다. 각 좌표 사이에는 빈 칸이 하나 있 www.acmicpc.net 그리디 알고리즘으로 분류되는 문제인데 대부분의 그리디 문제가 그렇듯이 그리디인 걸 알고 나면 쉽다. 그리디인 걸 알고 확신하기까지가 어려워서 그렇지... 센서와 집중국 간의 거리를 최소화 해야되기 때문에 센서 간 거리가 가장 큰 지역이 집중국 수신 영역 내에 포함되지 않도록 해야된다. 따라서 센서 간 거리를 구해서 가장 거리가 큰 지역 K - 1개를 총 지역에서 빼주면 된.. 2022. 9. 29.

[백준] 3190 뱀 (Python/파이썬) https://www.acmicpc.net/problem/3190 3190번: 뱀 'Dummy' 라는 도스게임이 있다. 이 게임에는 뱀이 나와서 기어다니는데, 사과를 먹으면 뱀 길이가 늘어난다. 뱀이 이리저리 기어다니다가 벽 또는 자기자신의 몸과 부딪히면 게임이 끝난다. 게임 www.acmicpc.net 큐의 선입선출 구조를 활용한 구현 문제이다. 구현해야할 사항들은 간략하게 나눠보면 다음과 같다. 뱀의 이동 게임 종료 조건 벽에 부딪혔을 때(= 범위를 벗어났을 때) 뱀의 몸통에 부딪혔을 때 사과가 있을 때 뱀의 크기를 사과가 있는 영역 한 칸만큼 늘려준다. 사과가 없을 때 뱀의 크기를 유지한 채 사과가 있는 영역으로 한 칸 이동 시켜준다.(꼬리 -1) 뱀의 몸통은 뱀이 이동하는 경로를 표시해주는 방식으.. 2022. 9. 28.

이전 1 ··· 4 5 6 7 8 다음

티스토리툴바