https://www.acmicpc.net/problem/13549 13549번: 숨바꼭질 3 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 때 www.acmicpc.net 풀이 계획 - 가중치가 다르게 주어진 그래프 이동을 하는 문제 - 한 정점에서 다른 모든 정점으로부터의 최단거리 계산 - 다익스트라 알고리즘 적용 코드 # 13549번 숨바꼭질 3 import sys import heapq input = sys.stdin.readline INF = sys.maxsize def rangeValid(v): if 0 dist: if..

https://www.acmicpc.net/problem/1236 1236번: 성 지키기 첫째 줄에 성의 세로 크기 N과 가로 크기 M이 주어진다. N과 M은 50보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에는 성의 상태가 주어진다. 성의 상태는 .은 빈칸, X는 경비원이 있는 칸이다 www.acmicpc.net 풀이 처음에는 어떻게 풀지 고민해보았는데, 문제에서 요구하는 바는 행과 열마다 경비원이 하나씩 존재해야한다는 것이다. 어느 n행과 m열이 주어졌을 때 두 직선의 교점에 경비원이 위치한다면 한 경비원으로도 문제에서 원하는 바를 만족시킬 수 있다는 것이다. 그말은 즉슨 가장 긴 직선의 길이만큼 경비원을 배치해준다면 다른 직선의 경비원 문제는 자연스럽게 해결된다는 것이다. 코드 # 1236번..

https://www.acmicpc.net/problem/1987 1987번: 알파벳 세로 R칸, 가로 C칸으로 된 표 모양의 보드가 있다. 보드의 각 칸에는 대문자 알파벳이 하나씩 적혀 있고, 좌측 상단 칸 (1행 1열) 에는 말이 놓여 있다. 말은 상하좌우로 인접한 네 칸 중의 한 칸으 www.acmicpc.net 풀이 BFS 문제 풀이를 위해서 기존에 자료구조를 deque으로 사용하였지만 이번에는 set으로 구현해주었습니다. 더군다나 지나온 경로를 일일이 set이나 list에 저장할 경우 메모리 초과가 발생하기에 문자열로 저장해주었습니다. 다음번에는 경로문제가 생길경우에 DFS를 우선시해서 풀어보겠습니다. 코드(BFS) # 1987번 알파벳 dxys = [[1,0],[-1,0],[0,1],[0,-1..

https://www.acmicpc.net/problem/11478 11478번: 서로 다른 부분 문자열의 개수 첫째 줄에 문자열 S가 주어진다. S는 알파벳 소문자로만 이루어져 있고, 길이는 1,000 이하이다. www.acmicpc.net 풀이 구현문제를 풀기 위해 인덱싱을 통해서 풀어주었습니다. 코드 # 11478번 서로 다른 부분 문자열의 개수 t = input() li = set() length = len(t) for space in range(1, length+1): for j in range(length-space+1): # 인덱스 기준 li.add(t[j:j+space]) print(len(list(li))) 출력결과

https://www.acmicpc.net/problem/7785 7785번: 회사에 있는 사람 첫째 줄에 로그에 기록된 출입 기록의 수 n이 주어진다. (2 ≤ n ≤ 106) 다음 n개의 줄에는 출입 기록이 순서대로 주어지며, 각 사람의 이름이 주어지고 "enter"나 "leave"가 주어진다. "enter"인 경우는 www.acmicpc.net 풀이 집합을 이용해서 풀어주었습니다. 코드 # 7785번 회사에 있는 사람 import sys n = int(input()) li = set() for _ in range(n): name, stat = input().rstrip().split() if stat == "enter": li.add(name) else: li.discard(name) print("..

https://www.acmicpc.net/problem/1010 1010번: 다리 놓기 입력의 첫 줄에는 테스트 케이스의 개수 T가 주어진다. 그 다음 줄부터 각각의 테스트케이스에 대해 강의 서쪽과 동쪽에 있는 사이트의 개수 정수 N, M (0 < N ≤ M < 30)이 주어진다. www.acmicpc.net 풀이 강 동쪽에 있는 점에서 강 서쪽 점의 개수만큼 뽑아주는 문제이기에 조합을 써주면 됩니다. 이를 위해 조합을 구현해주었습니다. 코드 # 1010번 다리 놓기 t = int(input()) def factorial(k): cnt = 1 for i in range(1, k+1): cnt *= i return cnt for _ in range(t): n, m = map(int, input().spl..

https://www.acmicpc.net/problem/15651 15651번: N과 M (3) 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해 www.acmicpc.net 풀이 중복조합을 구현해주는 문제입니다. 백트래킹으로 구현해주어도 되지만 파이썬의 라이브러리인 itertools의 product(데카르트 곱을 구현해주는)를 이용해서 문제를 풀어줘도 좋습니다. 코드 # 15651번 N과 M(3) import sys sys.setrecursionlimit(10000) n, m = map(int, input().split()) arr = [] def find_num(..

https://www.acmicpc.net/problem/17836 17836번: 공주님을 구해라! 용사는 마왕이 숨겨놓은 공주님을 구하기 위해 (N, M) 크기의 성 입구 (1,1)으로 들어왔다. 마왕은 용사가 공주를 찾지 못하도록 성의 여러 군데 마법 벽을 세워놓았다. 용사는 현재의 가지고 있는 www.acmicpc.net 풀이 bfs()알고리즘을 이용해서 문제를 풀어주면 됩니다. 다만 벽을 부술 수 있는 그람을 발견하면 벽과 상관없이 공주를 찾으러 갈 수 있기 때문에 그람을 찾는순간 그 위치에서 최단거리를 계산해주면 됩니다. 코드 # 17836번 공주님을 구해라! # 0은 빈공간 1은 벽 2는 그람을 의미한다. import sys from collections import deque input = ..