조용하지않는개발Blog

https://www.acmicpc.net/problem/16234 16234번: 인구 이동 N×N크기의 땅이 있고, 땅은 1×1개의 칸으로 나누어져 있다. 각각의 땅에는 나라가 하나씩 존재하며, r행 c열에 있는 나라에는 A[r][c]명이 살고 있다. 인접한 나라 사이에는 국경선이 존재한다. 모 www.acmicpc.net 풀이 문제를 보았을 때 알 수 있는 힌트 문제에서 이야기하는 조건과 bfs만 알고 있으면 풀 수 있는 문제이다. 다만 시간을 줄이기 위해서는 여러가지 공부가 필요할듯하다. 문제 내용을 잘 보면 옆의 나라의 인구 차이가 L과 R 사이에 있다면 같이 공유한다고 한다. 이를 생각하여 연결된 모든 국경 인원을 저장하고 나라 수 만큼의 평균을 만들고 기존의 그래프에 저장 시키면 된다. 이를 ..

https://www.acmicpc.net/problem/13549 13549번: 숨바꼭질 3 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 www.acmicpc.net 풀이 문제를 보았을때 알수있는 힌트 이전에 풀었던 숨바꼭질 1,2 문제들 과 유사하게 풀면 되는데 그중에 2*x의 경우에는 시간을 증가하지 않게 하면 쉽게 풀리는 문제이다. from collections import deque def bfs(v): count = 0 q = deque([[v, count]]) while q: v = q.popleft() e = v[..

https://www.acmicpc.net/problem/2660 2660번: 회장뽑기 입력의 첫째 줄에는 회원의 수가 있다. 단, 회원의 수는 50명을 넘지 않는다. 둘째 줄 이후로는 한 줄에 두 개의 회원번호가 있는데, 이것은 두 회원이 서로 친구임을 나타낸다. 회원번호는 1부터 www.acmicpc.net 풀이 문제를 보았을때 알수있는 힌트 친구와 친구 등으로 연결되어있는 것으로 보아 그래프 문제라고 생각들며 이미 들린 곳은 다시 들리지 않게 하면 될듯하다. 또한 BFS를 통해서 총 몇번을 안으로 들어가는지 확인하면 쉽게 풀릴 수 있는 문제이다. import sys from collections import deque input = sys.stdin.readline n = int(input()) g..

https://www.acmicpc.net/problem/3190 3190번: 뱀 'Dummy' 라는 도스게임이 있다. 이 게임에는 뱀이 나와서 기어다니는데, 사과를 먹으면 뱀 길이가 늘어난다. 뱀이 이리저리 기어다니다가 벽 또는 자기자신의 몸과 부딪히면 게임이 끝난다. 게임 www.acmicpc.net 풀이 문제를 보았을때 알수있는 힌트 bfs 형식으로 문제를 풀어가면 되며 X초 마다 상하좌우 방향 전환하는 것과 사과 존재에 따라 꼬리 변화 그리고 벽이나 자기자신을 부딪히는 조건을 찾아서 멈추기만 하면 끝나는문제 저 두가지 조건만 빠르게 구현하면 쉽게 풀수있다. import sys from collections import deque input= sys.stdin.readline count=1 n = ..

https://softeer.ai/practice/info.do?eventIdx=1&psProblemId=411 Softeer 연습문제를 담을 Set을 선택해주세요. 취소 확인 softeer.ai 풀이 문제를 보았을때 알수있는 힌트 단순 BFS,DFS 문제에 한가지 조건을 더해서 좀더 어렵게 만들었다. 하지만 문제에 힌트가 있다. 격자 화면의 맨 가장자리에는 얼음이 놓이지 않는 다고한다. 그렇다면 바깥 부분에서 1에 닿는 부분을 체크하며 지워나가면 답을 찾을수있는 문제이다. import sys from collections import deque input= sys.stdin.readline nx=[0,0,1,-1] ny=[1,-1,0,0] n,m = map(int,input().split()) grap..

https://softeer.ai/practice/info.do?eventIdx=1&psProblemId=409 Softeer 연습문제를 담을 Set을 선택해주세요. 취소 확인 softeer.ai 문제 자율주행팀 SW 엔지니어인 당신에게 장애물과 도로를 인식할 수 있는 프로그램을 만들라는 업무가 주어졌다. 우선 [그림 1]과 같이 정사각형 모양의 지도가 있다. 1은 장애물이 있는 곳을, 0은 도로가 있는 곳을 나타낸다. 당신은 이 지도를 가지고 연결된 장애물들의 모임인 블록을 정의하고, 불록에 번호를 붙이려 한다. 여기서 연결되었다는 것은 어떤 장애물이 좌우, 혹은 아래위로 붙어 있는 경우를 말한다. 대각선 상에 장애물이 있는 경우는 연결된 것이 아니다. [그림 2]는 [그림 1]을 블록 별로 번호를 붙..

https://www.acmicpc.net/problem/9019 9019번: DSLR 네 개의 명령어 D, S, L, R 을 이용하는 간단한 계산기가 있다. 이 계산기에는 레지스터가 하나 있는데, 이 레지스터에는 0 이상 10,000 미만의 십진수를 저장할 수 있다. 각 명령어는 이 레지스터에 www.acmicpc.net 풀이 문제를 보았을때 알수있는 힌트 먼저 pypy3로 푸는 것이 좋다. 실제 확인해보니 python으로 푼사람이 8명도 안된다..;; 문제를 보고 반복 시키기에는 너무 많은 양을 반복해야할듯해서 BFS를 통해 풀면 될듯하다는생각을 가졌다. dfs는 방문을 했는지만 체크하면 확실히 시간을 줄일 수 있다. 이를 유의하여 문제를 풀면 된다. import sys from collections..

https://www.acmicpc.net/problem/5014 5014번: 스타트링크 첫째 줄에 F, S, G, U, D가 주어진다. (1 ≤ S, G ≤ F ≤ 1000000, 0 ≤ U, D ≤ 1000000) 건물은 1층부터 시작하고, 가장 높은 층은 F층이다. www.acmicpc.net 풀이 문제를 보았을때 알수있는 힌트 한 위치가 잡혔을때 위, 아래로 움직일수있고 이를 통해서 최소로 갈 수 있는 문제이다. 또한 가지 못하는 경우까지 고려하며 문제를 풀어야한다. 한 곳에서 2군데로 이동가능하다 또 이미 지난 곳은 들려봤다 최소가 아니기때문에 BFS문제구나 라는 것을 알수있다. 또한 처음에 들어있는 수를 -1로 두어 도착을 못했는지를 확인할 수 있다. import sys from collect..

https://www.acmicpc.net/problem/1926 1926번: 그림 어떤 큰 도화지에 그림이 그려져 있을 때, 그 그림의 개수와, 그 그림 중 넓이가 가장 넓은 것의 넓이를 출력하여라. 단, 그림이라는 것은 1로 연결된 것을 한 그림이라고 정의하자. 가로나 세로 www.acmicpc.net 풀이 문제를 보았을때 알수있는 힌트 0,0부터 n,m 좌표까지 한개씩 반복하여 확인하면 되며 상하좌우를 움직이며 연결되어 있으면 넚이의 수를 늘리고 새로운 넓이가 나오면 그림의 개수를 늘리는 형식으로 문제를 풀면 된다. DFS,BFS로 풀수있는데 DFS는 메모리 초과로 풀리지 않는다.(이부분은 나중에 어려 시도를 해봐야겠다. 이미 많은 시도를 했지만 메모리초과를 해결하지 못했다.) 예상으로는 500X5..

https://www.acmicpc.net/problem/9205 9205번: 맥주 마시면서 걸어가기 송도에 사는 상근이와 친구들은 송도에서 열리는 펜타포트 락 페스티벌에 가려고 한다. 올해는 맥주를 마시면서 걸어가기로 했다. 출발은 상근이네 집에서 하고, 맥주 한 박스를 들고 출발한다. www.acmicpc.net 풀이 문제를 보았을때 알수있는 힌트 문제를 보고 시작점과 도착점이 있어서 bfs관련해서 풀어야겠다는 생각이 들었다. 중간에 들렸다가 가야하는 것이 다른 조건을 가지고 있다. bfs 돌면서 중간에 들리는 곳을 확인하여 갈수있는지 갈수있다면 방문하게끔 코드를 짜면 된다. import sys from collections import deque input = sys.stdin.readline t=..