본문 바로가기

Python50

[BOJ] 1158번 요세푸스 문제 [BOJ] 1158번 요세푸스 문제 문제 자료구조 문제 중에서 굉장히 훌륭한 문제로 평가받는 문제다. 이 문제를 단순히 자료구조의 입장에서 풀지 않고, 쉬운 방법부터 시작해서 이를 자료구조로 이어지게 하는 풀이로 풀어보고자 한다. 이 문제는 원을 따라서 계속 사람을 뽑아내는 문제다. 남은 사람들에 한하여 $ K \: $번째 사람이 뽑히고, 한번 뽑힌 사람이라면 그 사람은 제외되는 시스템을 가지고 있다. 만약 이 문제를 처음으로 맞닥뜨렸다면 우선 아래의 구현 문제점을 생각해 볼 수 있다. 편의상 문제의 예시와 같이 $ N = 7, \; K = 3 \: $이라고 하자. 어떻게 첫 $ K \: $번째 사람을 찾을 것인가 뽑힌 것을 어떻게 처리할 것인가 여러 번 뽑힌 이후로는 어떻게 $ K \: $번째 사람을 .. 2023. 4. 2.
[BOJ] 11536번 줄 세우기 [BOJ] 11536번 줄 세우기 문제 간단한 문자열 정렬 문제다. 내장함수 sort를 잘 이용할 수 있는지를 확인해 보는 문제로 손색없다. 주어진 이름이 역순으로 정렬되어 있으면 DECREASING, 순서대로 정렬되어 있으면 INCREASING, 둘 다 아니면 NEITHER를 출력하면 된다. $ N \: $이 기껏해야 12자 20개뿐이고, 시간이 1초이므로 시간 초과 날 일이 절대 없다. import sys if __name__ == '__main__': ori = list() for N in range(int(sys.stdin.readline().rstrip())): ori.append(sys.stdin.readline().rstrip()) if ori == list(sorted(ori)): prin.. 2023. 3. 17.
[BOJ] 27648번 증가 배열 만들기 [BOJ] 27648번 증가 배열 만들기 문제 굉장히 흥미로운 문제였고, 그랬기에 이 문제는 꼭 기록해 보고자 마음먹었던 기억이 난다. $ N \times M \: $ 크기의 2차원 배열이 있고, $ (1, \: 1) $부터 $ (N, \: M) $까지 (즉, 예시 출력의 배열로 따지면 제일 왼쪽 위부터 제일 오른쪽 아래까지) 아래쪽 / 오른쪽으로만 이동해 얻은 경로가 증가 배열이어야 한다. 대신 $ K $까지의 정수로만 채운다는 제한이 걸려있다. 문제에서 출력을 하나만 출력하라는 뜻에서 보이듯, 이 문제는 구성적 / 애드 혹 문제이다. 굉장히 쉽게 들어가야 답이 보일 것이다. 아래쪽 / 오른쪽으로 갈 때마다 수가 증가해야 하기 때문에 이 문제는 왼쪽 아래의 사선 방향으로 수가 하나씩 증가하는 배열을 만.. 2023. 3. 9.
[BOJ] 2468번 안전영역 [BOJ] 2468번 안전영역 문제 매우 정석적인 그래프 탐색 문제이다. 문제에서 요구하는 것은 물에 잠기는 단계에 따라 최대 안전 영역의 개수를 구하는 것이다. 즉, 모든 지역에서 가장 높은 지역의 숫자까지 높이를 조절해 가며 영역의 개수를 구해야 한다. 이를 위해서는 기존 영역을 구하는 그래프 탐색 스킬에 높이에 따른 영역 개수를 구하는 브루트포스 알고리즘까지 넣으면 된다. 18111번 마인크래프트 문제를 풀 때 사용되는 스킬과 비슷하다고 봐도 무방하다. import sys from collections import deque def bfs(x, y, nh): global N travel = deque([[x, y]]) dx, dy = [-1, 1, 0, 0], [0, 0, -1, 1] while t.. 2023. 1. 29.
[BOJ] 27162번 Yatch Dice [BOJ] 27162번 Yatch Dice 문제 보드게임컵에 나왔던 문제 중 하나다. 딱 봐도 이건 많은 조건 분기라는 것을 알 수 있으며, 그 조건이 무려 12가지기 때문에 구현할 때 오류 없이 잘 짜는 것이 매우 중요하다. 실수할 가능성이 매우 높기 때문에 주석(comment)으로 이 부분은 어떤 과정인지를 작성하는 것이 하나의 큰 팁이라고 본다. 실제로 이 문제를 대회에서 풀 때 주석으로 처리하면서 풀어갔음에도 3번이나 틀렸다... 결국엔 구현이 귀찮아서 그렇지, 막상 파고들면 그렇게 어려운 문제는 아니다. 먼저 이 문제는 첫 세 개의 주사위는 고정되어 있고, 나머지 두 개의 주사위 수를 무작위로 고를 수 있다. 그와 동시에 위의 12가지 족보 중 가능한 족보만으로 점수 중 최고점을 출력하면 된다... 2023. 1. 23.
[BOJ] 1331번 나이트 투어 [BOJ] 1331번 나이트 투어 문제 간단한 구현 문제다. 먼저 나이트는 날 일日자(가로 2칸과 세로 1칸 또는 가로 1칸과 세로 2칸)로 움직이는 것을 알아야 풀 수 있다. 문제의 핵심은 글에 있는 세 가지 조건을 체크하는 것이다. 조건은 아래와 같다. 시작한 칸과 끝난 칸을 나이트가 이동할 수 있어야 한다. 칸에서 칸으로 이동할 때 나이트가 갈 수 있어야 한다. 움직인 칸이 중복되지 않아야 한다. 이를 코드로 풀어서 쓰면 된다! 조건이 그렇게 어렵지 않기 때문에 코드 짜는 것이 굉장히 간단하다. import sys if __name__ == '__main__': route = list() for _ in range(36): route.append(sys.stdin.readline().rstrip().. 2023. 1. 14.
[BOJ] 26517번 연속인가? ? [BOJ] 26517번 연속인가? ? 문제 무난한 구현 문제다. $ k \: $에서 연속인지 아닌지를 확인해주면 되는데, $ ak + b \: $와 $ ck + d \: $가 같으면 연속임을 명시해 줬고, 이것을 가지고 조건문으로 검증하면 끝난다. import sys if __name__ == '__main__': k = int(sys.stdin.readline().rstrip()) a, b, c, d = map(int, sys.stdin.readline().rstrip().split()) if a*k+b == c*k+d: print('Yes', a*k+b) else: print('No') 이 문제가 실버인 이유는 연속이라는 개념이 가지는 난이도의 어려움 때문이니 무서워하지 말자. 여기서 연속이 왜 어려.. 2023. 1. 7.
[BOJ] 26069번 붙임성 좋은 총총이 [BOJ] 26069번 붙임성 좋은 총총이 문제 무난한 해시 문제다. "무지개 댄스"에 꽃히기 쉽지만 최대한 문제를 자세히 읽어보자. 핵심은 매우 간단하다. 주어지는 문자열 중에서 ChongChong이 나온 그 순간부터 모든 문자열을 해시 안에 집어넣으면 된다. 또한 ChongChong은 반드시 세어줘야한다는 것을 잊지 말자. 문제에 ChongChong은 편의상 사람으로 분류한다고 엄연히 명시되어있다. import sys if __name__ == '__main__': rainbow = set() for N in range(int(sys.stdin.readline().rstrip())): A, B = sys.stdin.readline().rstrip().split() if A == 'ChongChong'.. 2022. 12. 31.
[BOJ] 9549번 암호화된 비밀번호 [BOJ] 9549번 암호화된 비밀번호 문제 굉장히 재밌었던 문제다. 난이도도 꽤 충분했고, 공부도 꽤 됐다. 이 문제의 핵심은 슬라이딩 윈도우(sliding window)다. 기본적인 문자열 정렬 후 비교를 할 경우 시간 초과가 나버리기 때문에, 조금 더 선형적인 시간 복잡도를 가진 알고리즘인 슬라이딩 윈도우를 사용해야 한다. 슬라이딩 윈도우는 윈도우라는 일정 칸을 잡고 미는(슬라이딩하는) 방법이다. 여기서 슬라이딩을 하는 법은 반복문을 통해 제일 뒤의 요소를 빼고 그 다음 요소를 넣으면 된다. 이렇게만 보면 은근히 투 포인터(two pointers)와 유사한 부분이 있다. 하지만 이 둘은 엄연히 다른데, 슬라이딩 윈도우는 일정한 칸을 가진 윈도우를 쭉 미는 것이라면, 투 포인터는 두 개의 포인터를 잡.. 2022. 12. 3.
[BOJ] 10252번 그리드 그래프 [BOJ] 10252번 그리드 그래프 문제 굉장히 재밌었던 문제다. 먼저, 이 글을 읽는 사람은 반드시 이 문제를 풀다가 막혔거나, 이미 푼 사람이 봤으면 좋겠다. 이 문제는 아주 간단하게 요약하면, 기존 그래프와 달리 위아래, 좌우가 연결되어 있는 토로이드 그래프에서 한 붓 그리기가 가능한지와 있다면 그 경로를 아무거나 출력하는 것이다. 아무거나라는 말에서 알 수 있듯, 이는 구성적(Constructive) + 애드 혹(Ad hoc)의 문제다. 즉, 푸는 방법의 정해는 딱히 없고, 본인이 해결한 그 방법이 정답이 되는 환경의 문제인 셈이다. 그렇기 때문에 서두에 이 문제를 풀다가 막힌 사람이 봤으면 하는 말을 쓴 것이다. 즉, 앞으로 작성될 문제의 정답은 나의 정답이며, 이 외에도 정말 많은 답이 있다.. 2022. 11. 13.
728x90

티스토리툴바