안녕

0. 문제 링크 https://www.acmicpc.net/problem/1039 1039번: 교환 첫째 줄에 정수 N과 K가 주어진다. N은 1,000,000보다 작거나 같은 자연수이고, K는 10보다 작거나 같은 자연수이다. www.acmicpc.net 1. 풀이 방법 완전 탐색 비슷하게 풀었다. 참고로 BFS이다. 다만 최대 10억 개를 탐색해야 하는데, 이렇게 하면 무조건 시간초과가 난다. 최대 1,000,000의 길이이지만, 각 위치의 숫자는 0~9이다. 따라서 무조건 중복이 발생한다. 그러므로 중복을 잘 체크한다면 빠르게 풀 수 있다. BFS를 할 때는 실제로 자리를 바꿔줘서 해결하면 된다. *참고로 string끼리 대소비교 가능하다. 2. 코드 import sys from collection..

0. 문제 링크 https://www.acmicpc.net/problem/2812 2812번: 크게 만들기 N자리 숫자가 주어졌을 때, 여기서 숫자 K개를 지워서 얻을 수 있는 가장 큰 수를 구하는 프로그램을 작성하시오. www.acmicpc.net 1. 풀이 방법 while(특정 숫자가 들어오면 스택의 앞선 숫자와 비교한다.) 이때 들어오는 숫자가 더 크다면 스택을 팝한다. (k에 1씩 빼면서) 위 방식을 사용하면 앞자리가 큰 순서대로 스택에 쌓인다. 반복문을 탈출했는데, k가 0이 아니라면 이는 숫자가 대체적으로 내림차순이라는 의미이므로 스택에서 앞의 n - k개의 숫자를 출력한다. 2. 코드 import sys input = sys.stdin.readline def sol(): n, k = map(..

0. 문제 링크 https://www.acmicpc.net/problem/1644 1644번: 소수의 연속합 첫째 줄에 자연수 N이 주어진다. (1 ≤ N ≤ 4,000,000) www.acmicpc.net 1. 풀이 방법 에라토스테네스의 체로 maps에 소수인 부분은 True 설정한다. 기존의 방식(left, right를 양 끝에서 시작하여 점점 조여 오는 방식)이 아닌 left, right를 왼쪽부터 시작한다. total은 left와 right 사이에 있는 소수를 모두 더한 숫자이다. total을 기준으로 left 혹은 right을 옮긴다. 이때 left, right가 위치하는 index는 반드시 maps[index] == True여야 한다.(소수) total == n이라면 정답 += 1을 하고, l..

0. 문제 링크 https://www.acmicpc.net/problem/2252 2252번: 줄 세우기 첫째 줄에 N(1 ≤ N ≤ 32,000), M(1 ≤ M ≤ 100,000)이 주어진다. M은 키를 비교한 회수이다. 다음 M개의 줄에는 키를 비교한 두 학생의 번호 A, B가 주어진다. 이는 학생 A가 학생 B의 앞에 서야 한다는 의 www.acmicpc.net 1. 풀이 방법 2023.08.13 - [Computer Science/알고리즘] - [백준 - Python] 1766 - 문제집 [백준 - Python] 1766 - 문제집 0. 문제 링크 https://www.acmicpc.net/problem/1766 1766번: 문제집 첫째 줄에 문제의 수 N(1 ≤ N ≤ 32,000)과 먼저 푸..

0. 문제 링크 https://www.acmicpc.net/problem/16637 16637번: 괄호 추가하기 첫째 줄에 수식의 길이 N(1 ≤ N ≤ 19)가 주어진다. 둘째 줄에는 수식이 주어진다. 수식에 포함된 정수는 모두 0보다 크거나 같고, 9보다 작거나 같다. 문자열은 정수로 시작하고, 연산자와 정수가 www.acmicpc.net 1. 풀이 방법 **코드 길이 주의 해당 알고리즘은 브루트포스로 풀었다. 최대 길이는 19이고, 따라서 연산자는 최대 9개가 가능하다. 중첩된 괄호는 불가능하므로, 연산자는 최대 5개까지 선택이 가능하다. 물론 연산자 5개는 단 한 번만 가능하다. 연산자 4개를 뽑는 경우도 의외로 적다. 중첩된 괄호라는 조건을 제외하면 최대 9C5 + 9C4 + 9C3 + 9C2 ..

0. 문제 링크 https://www.acmicpc.net/problem/16724 16724번: 피리 부는 사나이 첫 번째 줄에 지도의 행의 수를 나타내는 N(1 ≤ N ≤ 1,000)과 지도의 열의 수를 나타내는 M(1 ≤ M ≤ 1,000)이 주어진다. 두 번째 줄부터 N개의 줄에 지도의 정보를 나타내는 길이가 M인 문자열이 주 www.acmicpc.net 1. 풀이 방법 해당 문제의 핵심은 그룹 번호이다. DFS를 수행하던 도중 같은 그룹 번호를 만난다면 이는 싸이클이 생긴 것이고, Safe Zone을 하나 추가해야 한다. 하지만 만약 다른 그룹 번호를 만난다면, 그 그룹은 이미 Safe Zone이 있으므로, 그냥 break 하면 된다. 내 그룹이 해당 그룹에 편입한다고 생각하면 편할 것이다. (..

0. 문제 링크 https://www.acmicpc.net/problem/1766 1766번: 문제집 첫째 줄에 문제의 수 N(1 ≤ N ≤ 32,000)과 먼저 푸는 것이 좋은 문제에 대한 정보의 개수 M(1 ≤ M ≤ 100,000)이 주어진다. 둘째 줄부터 M개의 줄에 걸쳐 두 정수의 순서쌍 A,B가 빈칸을 사이에 두고 주 www.acmicpc.net 1. 풀이 방법 해당 문제는 위상 정렬 알고리즘을 사용해야 한다. 위상 정렬 알고리즘은 싸이클이 없는 그래프에서, 각 노드들이 순서를 지켜야 할 때 사용된다고 한다. 해당 문제의 풀이 방법은 다음과 같다. 우선 나의 자식이 되는 문제들을 입력한다. -> 즉 인접한 노드를 입력한다. 또한 자식 노드는 앞서서 몇 개의 문제를 풀어야 하는지 기록해 놓는다...

0. 문제 링크 https://www.acmicpc.net/problem/5430 5430번: AC 각 테스트 케이스에 대해서, 입력으로 주어진 정수 배열에 함수를 수행한 결과를 출력한다. 만약, 에러가 발생한 경우에는 error를 출력한다. www.acmicpc.net 1. 풀이 방법 기본적으로 덱으로 해야 한다. 이유는 링크드 리스트이기 때문에 리스트로 관리한다면 pop(0) 과정에서 리스트의 모든 원소를 앞으로 가져오기 때문에 O(n)의 시간이 걸린다. 그리고 뒤집는 것도 하면 안 된다. 왜냐면 뒤집는 과정이 O(n)이기 때문이다. 따라서 뒤집는 '표시'를 써야한다. 2. 코드 import sys from collections import deque input = sys.stdin.readline ..

0. 문제 링크 https://www.acmicpc.net/problem/18808 18808번: 스티커 붙이기 혜윤이는 최근에 다양한 대회를 참여하면서 노트북에 붙일 수 있는 스티커들을 많이 받았다. 스티커는 아래와 같이 사각 모눈종이 위에 인쇄되어 있으며, 스티커의 각 칸은 상하좌우로 모두 연 www.acmicpc.net 1. 풀이 방법 가능한 좌표를 찾는 함수 놓을 수 있는지 판단하는 함수 스티커 붙이는 함수 회전 함수 이 모든 것을 조화롭게 사용하면 풀 수 있음 2. 코드 import sys input = sys.stdin.readline def canCoordinate(sticker): # 가능한 좌표를 찾는 함수 coordinate = [] yOffset = len(sticker) xOffse..

0. 문제 링크 https://www.acmicpc.net/problem/6087 6087번: 레이저 통신 크기가 1×1인 정사각형으로 나누어진 W×H 크기의 지도가 있다. 지도의 각 칸은 빈 칸이거나 벽이며, 두 칸은 'C'로 표시되어 있는 칸이다. 'C'로 표시되어 있는 두 칸을 레이저로 통신하기 위해서 www.acmicpc.net 이전 풀이 2023.02.03 - [Computer Science/알고리즘] - [백준 - Python] 6087 - 레이저 통신 [백준 - Python] 6087 - 레이저 통신 0. 문제 링크 https://www.acmicpc.net/problem/6087 6087번: 레이저 통신 크기가 1×1인 정사각형으로 나누어진 W×H 크기의 지도가 있다. 지도의 각 칸은 빈 ..