목록전체 글 (10)
세상의 모든 알고리즘
https://programmers.co.kr/learn/courses/30/lessons/12934 코딩테스트 연습 - 정수 제곱근 판별 임의의 양의 정수 n에 대해, n이 어떤 양의 정수 x의 제곱인지 아닌지 판단하려 합니다. n이 양의 정수 x의 제곱이라면 x+1의 제곱을 리턴하고, n이 양의 정수 x의 제곱이 아니라면 -1을 리턴하는 함 programmers.co.kr math의 sqrt라는 제곱근을 구하는 함수를 사용했습니다. 이 문제의 핵심은 제곱근을 구했을때 정확히 딱 떨어졌는지를 확인하는 것을 조건문으로 사용하는 것입니다. 초기에는 type함수를 사용해 정수값이면 출력해주려 했으나 sqrt함수를 사용하면 float 형식으로 바뀌어 불가능 합니다. 두번째 시도에는 아래처럼 int를 사용해 소..
https://www.acmicpc.net/problem/2606 2606번: 바이러스 첫째 줄에는 컴퓨터의 수가 주어진다. 컴퓨터의 수는 100 이하이고 각 컴퓨터에는 1번 부터 차례대로 번호가 매겨진다. 둘째 줄에는 네트워크 상에서 직접 연결되어 있는 컴퓨터 쌍의 수가 주어 www.acmicpc.net 리스트 BFS문제를 풀다 그래프 탐색문제를 풀었습니다. 핵심은 양방향 그래프 아래 부분이라고 생각합니다. graph[a].append(b) graph[b].append(a) 알고있다면 굉장히 쉬운데 모르면 이해하기 힘든.. 몇번 활용해보고 이해하시길 바라겠습니다 import sys from collections import deque input = sys.stdin.readline n = int(inp..
https://www.acmicpc.net/problem/2667 2667번: 단지번호붙이기 과 같이 정사각형 모양의 지도가 있다. 1은 집이 있는 곳을, 0은 집이 없는 곳을 나타낸다. 철수는 이 지도를 가지고 연결된 집의 모임인 단지를 정의하고, 단지에 번호를 붙이려 한다. 여 www.acmicpc.net 전형적인 탐색문제로 DFS와 BFS 중 BFS로 문제를 풀어 보았습니다. ''' 7 0110100 0110101 1110101 0000111 0100000 0111110 0111000 ''' import sys from collections import deque input = sys.stdin.readline numbering = [] result = [] n = int(input()) for _..
https://www.acmicpc.net/problem/18352 18352번: 특정 거리의 도시 찾기 첫째 줄에 도시의 개수 N, 도로의 개수 M, 거리 정보 K, 출발 도시의 번호 X가 주어진다. (2 ≤ N ≤ 300,000, 1 ≤ M ≤ 1,000,000, 1 ≤ K ≤ 300,000, 1 ≤ X ≤ N) 둘째 줄부터 M개의 줄에 걸쳐서 두 개 www.acmicpc.net from collections import deque import sys input = sys.stdin.readline n,m,k,x = map(int,input().split()) graph = [[] for _ in range(n+1)] visited = [-1] * (n+1) visited[x] = 0 for _ in..
https://www.acmicpc.net/problem/2178 2178번: 미로 탐색 첫째 줄에 두 정수 N, M(2 ≤ N, M ≤ 100)이 주어진다. 다음 N개의 줄에는 M개의 정수로 미로가 주어진다. 각각의 수들은 붙어서 입력으로 주어진다. www.acmicpc.net 이전 이코테 책에 수록된 문제가 백준에 있어 다시한번 풀어보는 시간을 갖게 되었습니다. 책을 통해 문제를 풀때는 시간제한이 없어 쉽게 느껴졌지만, 이번 문제 같은경우 1초의 시간제한이 있어 input() 함수를 -> 좀더 시간이 효율적인 sys.stdin.readline() 함수로 교체해서 사용했습니다. import sys input = sys.stdin.readline from collections import deque n,..
https://www.acmicpc.net/problem/7576 7576번: 토마토 첫 줄에는 상자의 크기를 나타내는 두 정수 M,N이 주어진다. M은 상자의 가로 칸의 수, N은 상자의 세로 칸의 수를 나타낸다. 단, 2 ≤ M,N ≤ 1,000 이다. 둘째 줄부터는 하나의 상자에 저장된 토마토 www.acmicpc.net 지금까지 BFS 문제를 풀때 하나의 시작점에서 출발해 문제를 푸는 방식이였다면 이번 문제는 두군데 시작부터 그 이상의 시작점을 통해 탐색을 진행하는 문제였습니다. 처음에는 이중포문을 통해 1인 시작점을 구하고 그 좌표를 함수로 전달해서 탐색하는 방법으로 구현하려 했으나 하나의 시작점이 전달되었을때 바로 모든 값이 변경돼 다른 시작점이 투입되도 결과가 변경되지 않는 문제가 발생했습니..
page 152 미로 탈출 BFS 문제 리스트를 입력받아 0인 괴물을 피해 n,m 좌표로 이동하는데 최소비용을 출력하기 길찾기문제는 BFS로 푸는것이 효율적이기에 BFS풀게되었고 1일때 지나갈수있는벽 0일때 못지나가는 괴물 이 두가지 조건을 조건문으로 잘 걸러내면 쉽게 풀 수 있는 문제 였습니다. from collections import deque n,m = map(int, input().split()) maze = [] for _ in range(n): maze.append(list(map(int,input()))) dx = [0,0,1,-1] dy = [1,-1,0,0] def bfs(x,y): q = deque() q.append((x,y)) while q: a,b = q.popleft() for..
https://www.acmicpc.net/problem/1260 1260번: DFS와 BFS 첫째 줄에 정점의 개수 N(1 ≤ N ≤ 1,000), 간선의 개수 M(1 ≤ M ≤ 10,000), 탐색을 시작할 정점의 번호 V가 주어진다. 다음 M개의 줄에는 간선이 연결하는 두 정점의 번호가 주어진다. 어떤 두 정점 사 www.acmicpc.net from collections import deque n,m,v = map(int, input().split()) graph = [[] for _ in range(n+1)] visited_dfs = [0] * (n+1) visited_bfs = [0] * (n+1) for _ in range(m): a,b = map(int, input().split()) gr..