본문 바로가기

전체 글

 (172)
[알고리즘] 백준 5052 전화번호 목록 / 파이썬 www.acmicpc.net/problem/5052 5052번: 전화번호 목록 첫째 줄에 테스트 케이스의 개수 t가 주어진다. (1 ≤ t ≤ 50) 각 테스트 케이스의 첫째 줄에는 전화번호의 수 n이 주어진다. (1 ≤ n ≤ 10000) 다음 n개의 줄에는 목록에 포함되어 있는 전화번호가 �� www.acmicpc.net 왜 딕셔너리를 생각한거지,,? 딕셔너리 한번 써보고 싶었나보다 def sol(): dic = {} N = int(input()) for _ in range(N): num = input() dic[len(num)] = dic.get(len(num), []) + [num] for k1, v1 in dic.items(): for k2, v2 in dic.items(): if k1 >= k..
[알고리즘] 백준 15988 1, 2, 3 더하기 2 / 파이썬 www.acmicpc.net/problem/15988 15988번: 1, 2, 3 더하기 3 각 테스트 케이스마다, n을 1, 2, 3의 합으로 나타내는 방법의 수를 1,000,000,009로 나눈 나머지를 출력한다. www.acmicpc.net #처음에 % 1000000009를 print에서 해줬는데 메모리초과 테스트케이스가 커지면 초과되는듯..? lst = [0] * 1000001 lst[1], lst[2], lst[3] = 1, 2, 4 for i in range(4, 1000001): lst[i] = (lst[i-1] + lst[i-2] + lst[i-3]) % 1000000009 for _ in range(int(input())): num = int(input()) print(lst[num])
[알고리즘] 백준 3495 아스키 도형 / 파이썬 www.acmicpc.net/problem/3495 3495번: 아스키 도형 창영이는 메모장에 '.', '\', '/'을 이용해서 도형을 그렸다. 각 문자는 그림에서 1*1크기의 단위 정사각형을 나타낸다. '.'은 빈 칸을 나타내며, '/'는 정사각형의 왼쪽 아래 꼭짓점과 오른쪽 위 꼭짓 www.acmicpc.net H, W = map(int, input().split()) M = [list(input()) for _ in range(H)] result = 0 for i in range(H): line = 0 for j in M[i]: if j == '/' or j == '\\': line += 1 #line이 홀수개일때 .이 도형안에, 짝수개일때 도형밖에(도형이 닫힌거니까) 있다고 생각 if line ..
[알고리즘] 백준 2206 벽 부수고 이동하기 / 파이썬 www.acmicpc.net/problem/2206 2206번: 벽 부수고 이동하기 N×M의 행렬로 표현되는 맵이 있다. 맵에서 0은 이동할 수 있는 곳을 나타내고, 1은 이동할 수 없는 벽이 있는 곳을 나타낸다. 당신은 (1, 1)에서 (N, M)의 위치까지 이동하려 하는데, 이때 최단 경로�� www.acmicpc.net 방문을 체크하는 ck배열을 삼중배열로 만들어서 벽을 안부술경우 / 부술경우를 구별한다 벽을 안부쉈다면 ck[x][y][0]에 거리를 저장하고, 부쉈다면 ck[x][y][1]에 거리를 저장한다 그리고 n, m까지 갔다면 저장했던 거리를 리턴, 아니라면 -1을 리턴해 출력해준다 from collections import deque dx, dy = [0, -1, 0, 1], [-1, 0,..
[알고리즘] 백준 11779 최소비용 / 파이썬 www.acmicpc.net/problem/11779 11779번: 최소비용 구하기 2 첫째 줄에 도시의 개수 n(1≤n≤1,000)이 주어지고 둘째 줄에는 버스의 개수 m(1≤m≤100,000)이 주어진다. 그리고 셋째 줄부터 m+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 버스� www.acmicpc.net 다익스트라 알고리즘을 활용하는 문제, 다익스트라 알고리즘을 까먹어서 백준1753번으로 공부하고 풀었다 최소비용을 구하는데에 더하여, 경로배열에 몇번 정점에서 왔는지 표시한다 0 -> 3 -> 4라면 경로배열[3] = 0, 경로배열[4] = 3 스타트 정점엔 -1을 저장해서 경로를 찾는 과정에 써먹는다 from heapq import heappop, heappush INF = 1..
[알고리즘] 백준 15685 드래곤 커브 / 파이썬 www.acmicpc.net/problem/15685 15685번: 드래곤 커브 첫째 줄에 드래곤 커브의 개수 N(1 ≤ N ≤ 20)이 주어진다. 둘째 줄부터 N개의 줄에는 드래곤 커브의 정보가 주어진다. 드래곤 커브의 정보는 네 정수 x, y, d, g로 이루어져 있다. x와 y는 드래곤 커� www.acmicpc.net from copy import deepcopy #방향에 따른 좌표값 계산하는 함수 def loc(xx, yy, dir): if dir == 0: return xx, yy+1 elif dir == 1: return xx-1, yy elif dir == 2: return xx, yy-1 elif dir == 3: return xx+1, yy #중복을 없애는 set에 뱡향값들을 좌표로 바..
[알고리즘] 백준 16197 두 동전 / 파이썬 www.acmicpc.net/problem/16197 16197번: 두 동전 N×M 크기의 보드와 4개의 버튼으로 이루어진 게임이 있다. 보드는 1×1크기의 정사각형 칸으로 나누어져 있고, 각각의 칸은 비어있거나, 벽이다. 두 개의 빈 칸에는 동전이 하나씩 놓여져 있고, �� www.acmicpc.net #보드 가장자리에 0을 추가해서 좌표의 보드값이 0일 때 떨어진것으로 간주 from collections import deque dx, dy = [0, -1, 0, 1], [-1, 0, 1, 0] def sol(): while q: x1, y1, x2, y2 = q.popleft() if ck[x1][y1][x2][y2] > 10: break for i in range(4): xx1, yy1 = x1+d..
[알고리즘] 백준 15653 구슬 탈출 4 / 파이썬 www.acmicpc.net/problem/15653 15653번: 구슬 탈출 4 첫 번째 줄에는 보드의 세로, 가로 크기를 의미하는 두 정수 N, M (3 ≤ N, M ≤ 10)이 주어진다. 다음 N개의 줄에 보드의 모양을 나타내는 길이 M의 문자열이 주어진다. 이 문자열은 '.', '#', 'O', 'R', 'B' www.acmicpc.net from collections import deque def move(x, y, dx, dy): m = 0 while True: if B[x][y] == 'O': break if B[x][y] == '#': x -= dx y -= dy break x += dx y += dy m += 1 return x, y, m dx, dy = [-1, 0, 1, 0], [0,..
[알고리즘] 백준 16918 봄버맨 / 파이썬 www.acmicpc.net/problem/16918 16918번: 봄버맨 첫째 줄에 R, C, N (1 ≤ R, C, N ≤ 200)이 주어진다. 둘째 줄부터 R개의 줄에 격자판의 초기 상태가 주어진다. 빈 칸은 '.'로, 폭탄은 'O'로 주어진다. www.acmicpc.net 풀이 방법 폭탄을 설치할 때, 현재 몇 초인지도 같이 저장한다 그리고 폭탄을 터트릴 때 같이 저장했던 시간이 3초 뒤라면 터트린다 # pypy 제출 def fill(num): for i in range(R): for j in range(C): if Map[i][j][0] == '.': Map[i][j][0], Map[i][j][1] = 'O', num dx, dy = [0, -1, 0, 1, 0], [0, 0, -1, 0, 1]..
[알고리즘] 백준 17070 파이프 옮기기 1 / 파이썬 www.acmicpc.net/problem/17070 17070번: 파이프 옮기기 1 유현이가 새 집으로 이사했다. 새 집의 크기는 N×N의 격자판으로 나타낼 수 있고, 1×1크기의 정사각형 칸으로 나누어져 있다. 각각의 칸은 (r, c)로 나타낼 수 있다. 여기서 r은 행의 번호, c는 열의 www.acmicpc.net pypy 제출 def dfs(p, x, y): global result if x == N-1 and y == N-1: result += 1 return else: if p == 1: if x

티스토리툴바