→

문제link: https://www.acmicpc.net/problem/1655n개의 정수가 차례로 주어진다. 수가 입력될 때마다 지금까지 입력된 수들의 중앙값을 출력해야 한다.접근최대 힙 하나, 최소 힙 하나를 만들어 숫자를 관리한다. 크기 순으로 정렬했을 때 앞에서 n/2개는 최대 힙에, 뒤에서 n/2개는 최소 힙에 저장하도록 관리하면 된다. 아래 코드에서는 python의 heapq를 활용했고, 최대 힙을 만드는 대신 마이너스 부호를 붙여 최소 힙을 최대 힙처럼 활용했다. 코드import sysinput = sys.stdin.readlineimport heapqn = int(input())h1 = [-int(input())]print(-h1[0])h2 = []for i in range(2, n+1):..

문제link: https://www.acmicpc.net/problem/3584루트가 있는 트리에 대해, 주어진 두 정점의 가장 가까운 공통 조상을 찾는 문제이다. 접근트리의 노드 개수 n과 n-1개의 간선 정보를 입력받아 트리를 구성한다. a의 조상을 집합에 저장한 후, b에서부터 root로 거슬러 올라가며 부모 노드가 집합에 포함되는지를 확인한다. root가 있는 트리이므로 무조건 답이 존재한다.초반에는 tree[노드] = [자식 노드 리스트] 형태로 코드를 짜고 있었는데 tree[노드] = 부모 노드 형태가 문제를 풀기에 더 적절할 것 같다는 생각이 들어 중간에 코드를 많이 고쳤다. 그러다 보니 정답 코드를 제출하긴 했지만 다시 확인했을 때 변수 이름 등이 매끄럽지 못했고 내가 봐도 왜 이렇게 짰나..

문제link: https://www.acmicpc.net/problem/16934 접근중복 닉네임인 경우는 딕셔너리로 확인해 결과를 빠르게 출력하도록 했다. 코드import sysinput = sys.stdin.readlinefrom collections import deque n = int(input())d = dict()tree = [[] for _ in range(26)]for _ in range(n): nickname = input().rstrip() if nickname in d: d[nickname] += 1 print(f'{nickname}{d[nickname]}') continue else: d[nickname] = 1 ..

문제link: https://www.acmicpc.net/problem/18224 접근시간 초과가 발생해 pypy3으로 제출했다.벽을 뛰어넘었을 때 최종적으로 도달할 좌표를 방향에 따라 저장하면 실행 시간이 줄어들 것 같다.(아래 코드에서는 따로 적용하지 않았다.) 코드import sysinput = sys.stdin.readlinefrom collections import deque d = ((-1, 0), (1, 0), (0, -1), (0, 1))n, m = map(int, input().split())maze = [list(map(int, input().split())) for _ in range(n)]visited = [[[0]*(m*2) for _ in range(n)] for _ in ran..

문제link: https://www.acmicpc.net/problem/14503 접근문제에서 제시하는 대로 로봇 청소기를 동작하게 하면 되는 평이한 문제이다. 알고리즘 문제를 풀 때마다 좋은 변수명이 무엇인지 생각하게 되는 요즘이다ㅎㅎ...튜플을 저장할 변수 이름 하나를 dir로 지었는데(direction에서 따 왔다) 파이썬 내장 함수와 이름이 겹치는 걸 간과하고 있었다ㅎㅎㅠㅠ 다음엔 다르게 지어야지 코드import sysinput = sys.stdin.readline#방의 크기n, m = map(int, input().split())#로봇 청소기 초기 위치와 바라보는 방향r, c, d = map(int, input().split())room = [list(map(int, input().split()..

문제link: https://www.acmicpc.net/problem/27903자신의 아이디에 포함된 문자를 사용하지 않으면서 아이디를 출력하는 문제이다. 접근사람마다 아이디가 다르기 때문에 아래 코드가 모든 사람에게 해법이 되지는 않겠지만 재미있는 문제라고 생각해 포스팅한다.나의 경우 아이디가 starpotato라서 a, o, p, r, s, t를 사용할 수 없다.아이디에 p, r, t가 있으므로 printf(), print()를 사용할 수 없었다. 그래서 파이썬의 exec()를 활용해 실행할 코드를 string으로 만들어 문제를 해결하려고 했다.처음에는 아스키코드를 활용해 아이디를 출력하려고 했는데, chr()에도 'r'이 들어가 있었다.최종적으로는 유니코드로 코드를 작성한 후 exec()로 실행하..

문제link: https://www.acmicpc.net/problem/7771 접근발포할 순서가 정해져 있으므로 쉽게 풀 수 있다. 모든 전함이 침몰해야 게임이 끝나기 때문에, 가장 마지막 라운드에서 발포하는 칸(100번 칸)에 전함이 위치하도록 전함을 배치하면 된다. 이외 전함은 규칙에 맞게만 배치하면 상관없다. 코드import sysinput = sys.stdin.readlineboard = [['.']*10 for _ in range(10)]x = 0for i in range(10): tmp = list(map(int, input().split())) for j in range(10): if tmp[j] == 100: x = i boa..

문제link: https://www.acmicpc.net/problem/23823 접근집합을 쓰면 될 걸 리스트를 써서 시간 초과가 났다ㅎㅎ; 처음에 집합을 사용하다가 인덱스로 원소에 접근하고 싶어서 아무 생각 없이 바꿨는데 내 코드 안에서 in 연산을 사용한다는 걸 잠시 잊고 있었다. 유지보수가 쉽도록 알아보기 좋게 코드를 쓰고 싶고 변수 네이밍도 좀 더 직관적으로 하고 싶은데 현업에선 어떤 식으로 하는지 모르겠고 클린코드를 읽어 봐야 하나 하는 요즘이다,, 코드import sysinput = sys.stdin.readlinen, q = map(int, input().split())li = [0, [0]*(n+1), [0]*(n+1)]se = [0, set(), set()]length = [0, [n..

문제link: https://www.acmicpc.net/problem/13334 접근집과 사무실의 위치 정수쌍이 정렬되지 않은 상태로 주어짐에 유의해야 한다. 집의 위치 정수값이 사무실 위치보다 클 수 있으므로 꼭 비교하여 사용해야 한다.집과 사무실 중 더 큰 값을 기준으로 정수쌍을 정렬한 후, 파이썬의 heapq 모듈을 활용해 최댓값을 저장했다. 힙에 들어 있는 것 중 제일 앞선 건물(집 또는 사무실)와 제일 뒤에 놓인 건물의 위치 차가 정수 d 이하이도록 관리해주었다. 코드import sysinput = sys.stdin.readlineimport heapqn = int(input())ho = []for _ in range(n): a, b = map(int, input().split()) ..

문제link: https://www.acmicpc.net/problem/9898정수 n이 주어졌을 때, 2*1 크기의 도미노로 4*n 사각형을 채우는 경우의 수를 구해 출력하는 문제이다. 접근처음에는 2*n 도미노 타일링 문제처럼 접근해보려고 했는데 채워야 하는 공간의 크기가 4*n이다 보니 그때와 완전히 같은 방법으로 해결할 수는 없었다.DP로 접근해야 한다는 것까지는 알았지만 점화식 도출이 어려워 인터넷상의 자료 다수를 참고하여 문제를 해결했다.(참고한 글 링크는 하단에 기재)해당 글에서 사용한 해결법은 다소 수학적으로, 아마 이보다 더 쉬운 접근법이 있을 것으로 생각된다.4*n 정사각형을 2*1 크기 도미노로 채울 때, (좌측에서 출발해) 한 열(4칸)을 채우는 방법은 위와 같이 여섯 가지이다.한 ..