본문 바로가기

코딩16

[Python-백준 2667] DFS - 단지번호 붙이기 알고리즘 문제 풀이 (DFS) - 단지번호 붙이기 https://www.acmicpc.net/problem/2667 2667번: 단지번호붙이기 과 같이 정사각형 모양의 지도가 있다. 1은 집이 있는 곳을, 0은 집이 없는 곳을 나타낸다. 철수는 이 지도를 가지고 연결된 집의 모임인 단지를 정의하고, 단지에 번호를 붙이려 한다. 여 www.acmicpc.net 이상하게 잘 안풀렸던 DFS문제.. 문제 읽고서는 굉장히 쉽다고 느꼈는데 어디선가 머리가 꼬인것인지 계속 빙빙 돌았던 문제였습니다. 기존 DFS 문제인 유기농 배추 + 섬의개수를 섞어놓은 문제였습니다. 문제 과 같이 정사각형 모양의 지도가 있다. 1은 집이 있는 곳을, 0은 집이 없는 곳을 나타낸다. 철수는 이 지도를 가지고 연결된 집의 모임인 단지.. 2022. 11. 17.
[Python-백준 2606] DFS - 바이러스 알고리즘 문제 풀이 (DFS) - 바이러스 https://www.acmicpc.net/problem/2606 2606번: 바이러스 첫째 줄에는 컴퓨터의 수가 주어진다. 컴퓨터의 수는 100 이하이고 각 컴퓨터에는 1번 부터 차례대로 번호가 매겨진다. 둘째 줄에는 네트워크 상에서 직접 연결되어 있는 컴퓨터 쌍의 수가 주어 www.acmicpc.net 기본적인 DFS 알고리즘에 대한 지식을 검증해볼 수 있는 문제입니다. 매우 간단하게 구현이 가능하며, 그래프에 대한 개념을 적용하여 풀어보도록 하겠습니다. 문제 신종 바이러스인 웜 바이러스는 네트워크를 통해 전파된다. 한 컴퓨터가 웜 바이러스에 걸리면 그 컴퓨터와 네트워크 상에서 연결되어 있는 모든 컴퓨터는 웜 바이러스에 걸리게 된다. 예를 들어 7대의 컴퓨터.. 2022. 11. 17.
[Python-백준] 문자열 - 그룹 단어 체커 알고리즘 문제 풀이 (문자열) - 그룹 단어 체커 https://www.acmicpc.net/problem/1316 1316번: 그룹 단어 체커 그룹 단어란 단어에 존재하는 모든 문자에 대해서, 각 문자가 연속해서 나타나는 경우만을 말한다. 예를 들면, ccazzzzbb는 c, a, z, b가 모두 연속해서 나타나고, kin도 k, i, n이 연속해서 나타나기 때 www.acmicpc.net 기본적인 파이썬 문자열에 대한 지식을 검증해볼 수 있는 문제입니다. 문제 그룹 단어란 단어에 존재하는 모든 문자에 대해서, 각 문자가 연속해서 나타나는 경우만을 말한다. 예를 들면, ccazzzzbb는 c, a, z, b가 모두 연속해서 나타나고, kin도 k, i, n이 연속해서 나타나기 때문에 그룹 단어이지만, .. 2022. 11. 16.
[Python-백준 1012] DFS - 유기농 배추 알고리즘 문제 풀이 (DFS) - 유기농 배추 https://www.acmicpc.net/problem/1012 1012번: 유기농 배추 차세대 영농인 한나는 강원도 고랭지에서 유기농 배추를 재배하기로 하였다. 농약을 쓰지 않고 배추를 재배하려면 배추를 해충으로부터 보호하는 것이 중요하기 때문에, 한나는 해충 방지에 www.acmicpc.net 문제 차세대 영농인 한나는 강원도 고랭지에서 유기농 배추를 재배하기로 하였다. 농약을 쓰지 않고 배추를 재배하려면 배추를 해충으로부터 보호하는 것이 중요하기 때문에, 한나는 해충 방지에 효과적인 배추흰지렁이를 구입하기로 결심한다. 이 지렁이는 배추근처에 서식하며 해충을 잡아 먹음으로써 배추를 보호한다. 특히, 어떤 배추에 배추흰지렁이가 한 마리라도 살고 있으면 이.. 2022. 11. 16.
[Python-백준 24479] DFS - 알고리즘 수업 - 깊이 우선 탐색 1 알고리즘 수업 - 깊이 우선 탐색 1 DFS 알고리즘 문제 풀이 시간 초과 건으로 인해서 계속 오류가 나는데 이유를 모르겠어서 헤매다가 해결했습니다. 문제 자체는 DFS 기본적인 내용인데 오류가 나니까 원인을 계속 찾았는데, 알고보니 입출력 간 발생 하는 문제였습니다. Python3 같은 경우, 입출력 간 시간이 많이 소요되기 때문에 input = sys.stdin.readline 코드를 통해서 입력 시간을 줄여주는 작업이 필요합니다. 입출력 관련한 문제는 백준 새싹 문제에 있으니 한번 풀어보도록 하여 익히도록 합니다. https://www.acmicpc.net/problem/15552 15552번: 빠른 A+B 첫 줄에 테스트케이스의 개수 T가 주어진다. T는 최대 1,000,000이다. 다음 T줄에는.. 2022. 11. 16.
[Python-백준 10026] DFS - 적록색약 알고리즘 문제 풀이 (DFS) - 적록색약 문제 적록색약은 빨간색과 초록색의 차이를 거의 느끼지 못한다. 따라서, 적록색약인 사람이 보는 그림은 아닌 사람이 보는 그림과는 좀 다를 수 있다. 크기가 N×N인 그리드의 각 칸에 R(빨강), G(초록), B(파랑) 중 하나를 색칠한 그림이 있다. 그림은 몇 개의 구역으로 나뉘어져 있는데, 구역은 같은 색으로 이루어져 있다. 또, 같은 색상이 상하좌우로 인접해 있는 경우에 두 글자는 같은 구역에 속한다. (색상의 차이를 거의 느끼지 못하는 경우도 같은 색상이라 한다) 예를 들어, 그림이 아래와 같은 경우에 RRRBB GGBBB BBBRR BBRRR RRRRR 적록색약이 아닌 사람이 봤을 때 구역의 수는 총 4개이다. (빨강 2, 파랑 1, 초록 1) 하지만, .. 2022. 11. 15.

티스토리툴바