https://www.acmicpc.net/problem/2573 2573번: 빙산 첫 줄에는 이차원 배열의 행의 개수와 열의 개수를 나타내는 두 정수 N과 M이 한 개의 빈칸을 사이에 두고 주어진다. N과 M은 3 이상 300 이하이다. 그 다음 N개의 줄에는 각 줄마다 배열의 각 행을 www.acmicpc.net 풀이 BFS알고리즘을 사용하였습니다. 코드 # 2573번 빙산 import sys from collections import deque dxys = [[1,0],[-1,0],[0,1],[0,-1]] # bfs 두번 실행 def bfs(s_x, s_y): queue = deque([]) queue.append([s_x, s_y]) visited[s_y][s_x] = True while queu..

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..

파이썬 reverse, reversed의 차이 파이썬에서 리스트의 요소를 뒤집을때 reverse, reversed를 사용한다. 이 두개의 차이에 대하여 간단하게 알아보자. reverse reverse는 list타입에서 제공하는 함수이다. l = ['a', 'b', 'c'] t = ('a', 'b', 'c') d = {'a': 1, 'b': 2, 'c': 3} s = 'abc' l.reverse() # list의 순서를 뒤집어줌 t.reverse() # AttributeError: 'tuple' object has no attribute 'reverse' d.reverse() # AttributeError: 'dict' object has no attribute 'reverse' s.reverse() # ..

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 = ..