본문 바로가기
728x90

백준 풀이103

[백준/BOJ] - 18870번 python 풀이 - 딕셔너리 요문제는 보자마자 이건 직관적으로 구현은 쉽겠지만 여차하면 시간 초과가 날 문제라고 느꼈다. N값이 백만인데 리스트에 넣고 정렬하는 시간만 해도 엄청나기에 다른 자료 구조를 고려했다. 딕셔너리의 경우 탐색하는 데 드는 시간 복잡도가 낮기 때문에 해당 구조 채택. 일단 순서를 아래 코드의 주석에 달아놓은 거 처럼 맨처음 리스트에 값을 저장시키고 하나하나 꺼내면서 반복문 변수를 통해 주어진 수의 idx를 value로 설정해줬다. 하지만 단순 dict로 선언할 경우 중복되는 key의 경우, value 값을 list로 변환해주어야 하는데, 해당 과정을 구현하면 반복문이 지저분 해질 거 같아 다른 방법을 모색했다. 바로 defaultdict라는 친구인데 이 친구는 key 값이 추가 되면 value의 디폴트 자료형.. 2023. 9. 11.
[백준/BOJ] - 1107번 python 풀이 - 브루트포스 처음 나의 풀이법 문제를 보고 처음 떠오른 방법이 가능한 숫자를 가지고 목표 채널에 근접하는 방법. 만약 목표 채널이 5457이라면 일단 각 자릿수가 일치하는지 먼저 확인, 일치 하지 않다면 절댓값 1만큼 차이나게 수를 뽑으며 각 자리수 별로 가능한 경우의 수 집합을 만든다.(5457의 맨 첫자리인 5를 기준으로 4 or 6이 있다면 4와6을 set에 집어 넣는다.) 이런식으로 하면 집합이 자릿수 개수 만큼 총 4가지가 생길 것이다. 해당 집합에서 하나씩 값을 골라 순열을 진행하는 방식으로 하면 될거라 생각했으나 순열은 같은 수를 여러번 뽑는 경우를 생각하지 못한다. 최종 풀이법 그렇기에 다른 분의 풀이를 참고하여 브루트포스 방식으로 모든 경우의 수를 훑는다. 코드 부분에 반복 횟수가 1,000,001로.. 2023. 8. 22.
[백준/BOJ] - 16928번 python 풀이 - bfs https://www.acmicpc.net/problem/16928 16928번: 뱀과 사다리 게임 첫째 줄에 게임판에 있는 사다리의 수 N(1 ≤ N ≤ 15)과 뱀의 수 M(1 ≤ M ≤ 15)이 주어진다. 둘째 줄부터 N개의 줄에는 사다리의 정보를 의미하는 x, y (x < y)가 주어진다. x번 칸에 도착하면, y번 칸으 www.acmicpc.net 1부터 시작하여 bfs로 주사위 수인 1~6 만큼 이동하여 100에 최소 횟수만큼 도달하려면? 처음 생각난 방법이 dp와 그래프 탐색이다. 그래프 탐색 방법 중 dfs를 사용하면 100에 도달하는 경우의 수가 여러개 나오는데 그 많은 경우의 수 중 주사위 시도 횟수가 가장 작은 값을 구하기 위해 매번 비교를 해야한다. 하지만, bfs를 사용하여 방문하.. 2023. 8. 21.
[백준/BOJ] - 14500번 python 풀이 - dfs 다음 이미지 형태의 도형에 부합하는 값들의 합 - 최댓값을 도출하는 문제이다. 순간 이 문제를 봤을 때 dfs를 활용하면 될 거 같다는 생각이 들었다. 하지만 코드를 완전히 작성하고 난 후, 테스트 케이스를 돌려보니 기댓값과 다른 값이 출력되었다. 문제를 생각해보니,'ㅜ' 모양의 도형은 단순 dfs로는 해결이 안되는 것. 나머지 도형의 유형은 모두 dfs로 해결 되지만, 유일하게 'ㅜ' 모양만 체크가 불가하다. 이를 해결하기 위해 새로운 함수를 만들어 'ㅜ' 모양만 예외처리 해주었다. 반복문을 활용한다고 가정했을 때, 총 나올 수 있는 형태는 4가지. ㅗ, ㅏ , ㅜ ㅓ 이다. 기준점 하나를 잡았으면, 해당 기준점 당 4가지의 경우의 수가 나올 수 있다는 점. 또한, 각 도형의 모형 별로 반복문 3번을 .. 2023. 8. 21.
[백준/BOJ] - 2096번 python 풀이 - dp https://www.acmicpc.net/problem/2096 2096번: 내려가기 첫째 줄에 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 N개의 줄에는 숫자가 세 개씩 주어진다. 숫자는 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 중의 하나가 된다. www.acmicpc.net 맨처음 각각 최댓값, 최솟값을 저장하는 dp1, dp2 2가지를 deepcop를 통해 만들었더니 메모리 초과가 발생하여 파훼법을 생각해보니 굳이 쓰지 않는 값을 dp에 저장하지 않고 그냥 덮어쓰는 방식으로 진행해도 될 거 같다는 판단이 들었다. import sys,copy input = sys.stdin.readline n = int(input()) arr = [] dp = copy.deepcopy(arr) d.. 2023. 8. 20.
[백준/BOJ] - 2565번 python 풀이 - dp https://www.acmicpc.net/problem/2565 2565번: 전깃줄 첫째 줄에는 두 전봇대 사이의 전깃줄의 개수가 주어진다. 전깃줄의 개수는 100 이하의 자연수이다. 둘째 줄부터 한 줄에 하나씩 전깃줄이 A전봇대와 연결되는 위치의 번호와 B전봇대와 연결되는 www.acmicpc.net 문제의 입력은 랜덤하게 전깃줄이 주어지므로 해당 전깃줄 정보를 하나의 list에 저장시킨 후, 정렬한다. 그럼 그림1과 같이 직관적으로 확인이 가능하다. 문제에서 원하는 것은 서로 교차하지 않게 없애야하는 전깃줄의 개수. 문득 든 생각 중 하나가 각 구간마다 가능한 연속된 전깃줄의 수를 dp에 저장하는 법.(이전 값과 비교하며 갱신하는 것.) 만약 dp 값이 3인 값의 번호와 비교했을 때, 해당 기준 전.. 2023. 8. 20.
728x90

티스토리툴바