본문 바로가기

알고리즘

 (305)
[백준] 21610번 : 마법사 상어와 비바라기 21610번: 마법사 상어와 비바라기 21610번: 마법사 상어와 비바라기 마법사 상어는 파이어볼, 토네이도, 파이어스톰, 물복사버그 마법을 할 수 있다. 오늘 새로 배운 마법은 비바라기이다. 비바라기를 시전하면 하늘에 비구름을 만들 수 있다. 오늘은 비바라기 www.acmicpc.net 🤔 문제분석 아래의 3가지의 함수를 통하여 M번 반복하여 문제를 해결하였습니다. 그룸을 이동시키는 함수 그룸을 통하여 바구니에 저장된 물이 증가하는 함수 새로운 그룸을 생성하는 함수 그룸을 이동시키는 함수에서 중요한점은 N이 넘어가는 순간 0으로 바꾸어주고, -1로 넘어가는순간 N-1로 바꾸어주는 로직이 필요하다. 이부분은 문제에서 N번째 열과 0번째 열이 연결되어있고, N번째 행과 0번째 행이 연결되어있는 조건을 해결..
[백준] 19237번 : 어른 상어 19237번: 어른 상어 19237번: 어른 상어 첫 줄에는 N, M, k가 주어진다. (2 ≤ N ≤ 20, 2 ≤ M ≤ N2, 1 ≤ k ≤ 1,000) 그 다음 줄부터 N개의 줄에 걸쳐 격자의 모습이 주어진다. 0은 빈칸이고, 0이 아닌 수 x는 x번 상어가 들어있는 칸을 의미 www.acmicpc.net 🤔 문제분석 함수를 3가지로로 나누어서 문제를 해결하였습니다. 상어가 움직인다 : 상어가 움직이는것은 첫번째로 우선순위에 따라서 빈칸을 체크하고, 그 다음순으로 자기자신의 냄새를 찾는다. ( 여기서 중요한점은 항상 빈칸이거나 자기자신의 냄새를 찾을 수 있다.) 냄새를 풍긴다 : 움직이는 우선순이때문에 다른 상어와 겹칠 일은 없다. 냄새가 사라진다 : 냄새가 사라지면서 만약 냄새가 0이되면 상어 ..
[백준] 17837번 : 새로운게임 17837번: 새로운 게임 2 17837번: 새로운 게임 2 재현이는 주변을 살펴보던 중 체스판과 말을 이용해서 새로운 게임을 만들기로 했다. 새로운 게임은 크기가 N×N인 체스판에서 진행되고, 사용하는 말의 개수는 K개이다. 말은 원판모양이고, 하 www.acmicpc.net 🤔 문제분석 시뮬레이션 문제로 주어진 조건을 잘 분석하여 분기처리하여 문제를 풀면 풀 수 있다. 3가지 로직을 구현하여 조합하면 된다. 파란색과 범위를 벗어나는 조건 자기자신위에 있는 배열을 구하는 방법 자기자신위에 배열을 구하는방법은 현재 채스판의 위치에서 자기자신의 인덱스를 찾아서 그 인덱스를 기준으로 모든 값을 복사한다. 그리고 그 인덱스를 기준으로 모든값을 제거시킨다. 빨간색일때 배열을 뒤집는방법 파이썬의 리스트 컴프리핸션..
[백준] 17825번 : 주사위 17825번: 주사위 윷놀이 17825번: 주사위 윷놀이 주사위 윷놀이는 다음과 같은 게임판에서 하는 게임이다. 처음에는 시작 칸에 말 4개가 있다. 말은 게임판에 그려진 화살표의 방향대로만 이동할 수 있다. 말이 파란색 칸에서 이동을 시작하면 www.acmicpc.net 🤔 문제분석 그래프와 점수의 판을 하드코딩으로 그려놓고 파란색 판을 이동하는 조건을 걸어 문제를 해결 할 수 있습니다. 파란색칸은 배열의 길이가 2인경우이고 해당 배열로 이동할경우 그래프에 그려놓은 위치로 이동시킵니다. 이제 위의 조건으로 백트래킹을 이용하여 문제를 해결하면 끝입니다. 💻 코드 import sys input = sys.stdin.readline graph = [[1], [2], [3], [4], [5], [6, 21],..
[백준] 4803번 : 트리 4803번: 트리 4803번: 트리 입력으로 주어진 그래프에 트리가 없다면 "No trees."를, 한 개라면 "There is one tree."를, T개(T > 1)라면 "A forest of T trees."를 테스트 케이스 번호와 함께 출력한다. www.acmicpc.net 🤔 문제분석 특정 노드로 부터 시작하여 사이클이 존재하는지 확인하면 된다. 방문 체크 배열을 두어 사이클이 발생했었던 노드는 다시 방문하지 않는다. 사이클이 발생하는 유무는 너비우선탐색으로 찾아내었는데, 입력받은 간선을 계속 따라가 가면서 방문했던 노드를 또다시 방문했다면 사이클이 발생한 것이다. 💻 코드 import sys from collections import deque input = sys.stdin.readline ..
[백준] 16120번 : PPAP 16120번: PPAP 16120번: PPAP 첫 번째 줄에 문자열이 주어진다. 문자열은 대문자 알파벳 P와 A로만 이루어져 있으며, 문자열의 길이는 1 이상 1,000,000 이하이다. www.acmicpc.net 🤔 문제분석 스택자료구조와 P의 개수와 C의 개수를 카운팅하여 조건부 연산을 통하여 PPAP를 만들 수 있는지 확인합니다. P를 만나면 p_count를 증가시키고 C를 만나면 c_count를 증가시킵니다. 이전에 값이 C이고 그다음이 P가 나올경우 p_count의 PPAP를 만들 수 있는지 카운팅을 하고 p_count값을 -2 감소 c_count값을 -1을 감소시킵니다. 이렇게 해서 최종 p_count값이 1이 나온경우만 정답이 됩니다. 마지막에 PPAP → P로 변하기 때문이다. 💻 코드 ..
[백준] 13975번 : 파일 합치기 3 13975번: 파일 합치기 3 13975번: 파일 합치기 3 프로그램은 표준 입력에서 입력 데이터를 받는다. 프로그램의 입력은 T개의 테스트 데이터로 이루어져 있는데, T는 입력의 맨 첫 줄에 주어진다.각 테스트 데이터는 두 개의 행으로 주어지는데, www.acmicpc.net 🤔 문제분석 우선순위큐를 활용하여 가장 작은 파일부터 합쳐나아가는 문제입니다. 가장 작은 파일끼리 합쳐야 합의 가중치가 낮기때문입니다. 💻 코드 import sys import heapq input = sys.stdin.readline T = int(input()) for _ in range(T): K = int(input()) queue = [] for file in list(map(int, input().split())): h..
[백준] 16724번 : 피리부는사나이 16724번: 피리 부는 사나이 16724번: 피리 부는 사나이 첫 번째 줄에 지도의 행의 수를 나타내는 N(1 ≤ N ≤ 1,000)과 지도의 열의 수를 나타내는 M(1 ≤ M ≤ 1,000)이 주어진다. 두 번째 줄부터 N개의 줄에 지도의 정보를 나타내는 길이가 M인 문자열이 주 www.acmicpc.net 🤔 문제분석 서로소 집합을 활용하여 문제를 해결하였습니다. 사이클이 생기는 집합을 만들고, 그 집합의 총 개수를 구하면 됩니다. 사이클이 생기는 그룹의 집합안에서 어느한곳이 막힌다면 움직이지 못하기 때문입니다. 유니온-파인드로 사이클을 모두 하나의 집합으로 만들어주고 그 집합의 개수를 새면 됩니다. 💻 코드 import sys input = sys.stdin.readline N, M = map(i..

티스토리툴바