생각 생각

https://acmicpc.net/problem/1987 1987번: 알파벳 세로 R칸, 가로 C칸으로 된 표 모양의 보드가 있다. 보드의 각 칸에는 대문자 알파벳이 하나씩 적혀 있고, 좌측 상단 칸 (1행 1열) 에는 말이 놓여 있다. 말은 상하좌우로 인접한 네 칸 중의 한 칸으 www.acmicpc.net 깨달음이 있었던 문제. bfs 자리에 set을 넣을 수 있다는 생각 자체를 해보지 않았는데, 알게 되었다. 즉 특정 좌표에서 특정 visited 상태로 다시 진입하지 않을 수 있도록 q를 set으로 두는 것이다. 알파벳의 종류를 ord()를 이용하여 int 로 전달해보기도 하고, 비트 연산으로 전달해보기도 하였으나 전부 시간초과였다. import sys input = sys.stdin.readli..

https://acmicpc.net/problem/1725 1725번: 히스토그램 첫 행에는 N (1 ≤ N ≤ 100,000) 이 주어진다. N은 히스토그램의 가로 칸의 수이다. 다음 N 행에 걸쳐 각 칸의 높이가 왼쪽에서부터 차례대로 주어진다. 각 칸의 높이는 1,000,000,000보다 작거나 같은 www.acmicpc.net 히스토그램에서 가장 큰 직사각형과 출력 형식만 다른 문제. from collections import deque import sys input=sys.stdin.readline lis=[] n=int(input()) for _ in range(n): lis.append(int(input())) ans=0 stack = deque() for i in range(n): while..

https://acmicpc.net/problem/6549 6549번: 히스토그램에서 가장 큰 직사각형 입력은 테스트 케이스 여러 개로 이루어져 있다. 각 테스트 케이스는 한 줄로 이루어져 있고, 직사각형의 수 n이 가장 처음으로 주어진다. (1 ≤ n ≤ 100,000) 그 다음 n개의 정수 h1, ..., hn (0 ≤ hi ≤ www.acmicpc.net 행렬 찾기 문제와 동일한 메커니즘으로 스택을 이용하여 풀면 되었던 문제. 행렬 찾기와 동일하여 굳이 설명을 적진 않는다. from collections import deque import sys input=sys.stdin.readline while True: lis=list(map(int,input().split())) n=lis.pop(0) i..

https://acmicpc.net/problem/1687 1687번: 행렬 찾기 첫째 줄에 행렬의 크기를 나타내는 두 정수 N, M(1≤N, M≤333)이 주어진다. 다음 N개의 줄에는 M개의 정수(0또는 1)가 공백없이 주어진다. 이 숫자는 행렬을 구성하는 원소이다. www.acmicpc.net 어려웠다. 어렴풋이 방법은 생각 나긴 했지만 그럼에도 여전히 구현하기엔 부족하다고 느꼈다. 풀이도 많지 않아 찾기에 애를 먹었으나, 결과적으로 백준 6549 와 비슷한 문제임을 알게 됐다. 위의 문제에도 여러 가지 방법이 있는데, 그 중 스택을 이용한 방법을 차용했다. from collections import deque import sys input=sys.stdin.readline n,m=map(int,i..

https://acmicpc.net/problem/16209 16209번: 수열 섞기 인접한 원소의 곱들을 최대화한 본 수열의 재배열을 하나 출력하자. 만약 최대화할 수 있는 재배열이 여러 가지 있다면 아무거나 하나 출력하면 된다. www.acmicpc.net 크리스마스 시즌에 이벤트로 나온 문제였다. 자꾸 50점이 나와서 좀 헤멨다. 그리디하게 풀 수 있는 문제였다. 처음엔 naive하게 큰 수는 큰 수끼리, 작은 수는 작은 수끼리 붙이면 되겠다 생각해서 이런 풀이를 생각했다. from collections import deque n=int(input()) lis=list(map(int,input().split())) lis.sort() #list 내의 숫자들을 정렬한다. q=deque() odd=Tr..

https://acmicpc.net/problem/1766 1766번: 문제집 첫째 줄에 문제의 수 N(1 ≤ N ≤ 32,000)과 먼저 푸는 것이 좋은 문제에 대한 정보의 개수 M(1 ≤ M ≤ 100,000)이 주어진다. 둘째 줄부터 M개의 줄에 걸쳐 두 정수의 순서쌍 A,B가 빈칸을 사이에 두고 주 www.acmicpc.net 위상 정렬의 개념을 모르고 풀어서 한참을 고생한 문제였다. 처음 풀이는 이랬다. import sys, heapq from collections import deque input=sys.stdin.readline n,m=map(int,input().split()) ps=[] visited=[False]*(n+1) for _ in range(m): heapq.heappush(p..

https://acmicpc.net/problem/7579 7579번: 앱 입력은 3줄로 이루어져 있다. 첫 줄에는 정수 N과 M이 공백문자로 구분되어 주어지며, 둘째 줄과 셋째 줄에는 각각 N개의 정수가 공백문자로 구분되어 주어진다. 둘째 줄의 N개의 정수는 현재 활 www.acmicpc.net 다른 문제보다 빠르게 원트에 풀 수 있었던 문제였다. 보고 바로 냅색 문제임은 생각할 수 있었다. 다만 비용을 기준으로 정렬할지 메모리를 기준으로 정렬할지를 잠시 고민했다. 비용의 범위가 더 좁아 비용을 이용해 냅색을 진행했다. cost를 다 합한 것을 dp의 길이로 설정했다. n,m=map(int,input().split()) m_lis=list(map(int,input().split())) #메모리 리스트 ..

https://acmicpc.net/problem/12100 12100번: 2048 (Easy) 첫째 줄에 보드의 크기 N (1 ≤ N ≤ 20)이 주어진다. 둘째 줄부터 N개의 줄에는 게임판의 초기 상태가 주어진다. 0은 빈 칸을 나타내며, 이외의 값은 모두 블록을 나타낸다. 블록에 쓰여 있는 수는 2 www.acmicpc.net 풀긴 풀었는데, 백트래킹이 아닌 브루트포스로 풀었다고 보는 게 맞을 것 같아서 풀이를 한참 고치다 실패한 문제. 이거 생각한다고 블로그 글을 계속 정리하지 않고 있었다. 풀이는 다음과 같았다. n=int(input()) graph=[] max_num=-1 for _ in range(n): graph.append(list(map(int, input().split()))) #mo..