본문 바로가기

전체 글121

[BOJ] 1342. 행운의 문자열(Python) / DFS www.acmicpc.net/problem/1342 1342번: 행운의 문자열 민식이와 준영이는 자기 방에서 문자열을 공부하고 있다. 민식이가 말하길 인접해 있는 모든 문자가 같지 않은 문자열을 행운의 문자열이라고 한다고 한다. 준영이는 문자열 S를 분석하기 시작 www.acmicpc.net 내가 짠 코드는 15분만에 간단한 DFS로 순열(Permutation)을 구현했지만, 중복 고려하지 않고 문자열 그대로 완전탐색해버리니, 3300ms로 겨우 통과했다.. 부끄러워서 차마 내 코드는 올릴 수가 없다. 이번에 소개할 코드는 내가 짠 건 아니고, "뚱이"라는 나의 짝꿍이 짰다. 토실토실 아주 귀여운 친구다. 문자열의 각 알파벳별 카운트로 계산한다. 아스키 코드 변환(ord()함수 사용)으로 a~z까지 0~.. 2021. 3. 18.
[BOJ] 1149. RGB거리(Python) / DP www.acmicpc.net/problem/1149 1149번: RGB거리 첫째 줄에 집의 수 N(2 ≤ N ≤ 1,000)이 주어진다. 둘째 줄부터 N개의 줄에는 각 집을 빨강, 초록, 파랑으로 칠하는 비용이 1번 집부터 한 줄에 하나씩 주어진다. 집을 칠하는 비용은 1,000보다 작거나 www.acmicpc.net 실버 1 문제라 간단한 DFS로 Brute Force(완전탐색)으로 풀릴 줄 알았는데, 47%에서 시간초과 나더라.. # 소요시간 20분 DFS 완전탐색으로 접근한 파이썬 코드는 다음과 같다.(47%에서 실패한 코드) from sys import stdin input = stdin.readline def dfs(depth, temp): global MIN if temp > MIN: # 가지.. 2021. 3. 17.
[BOJ] 6603. 로또(Python) / DFS www.acmicpc.net/problem/6603 6603번: 로또 입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스는 한 줄로 이루어져 있다. 첫 번째 수는 k (6 < k < 13)이고, 다음 k개 수는 집합 S에 포함되는 수이다. S의 원소는 오름차순으로 www.acmicpc.net 간단한 DFS로 조합(Combination)을 구현한 문제다. # 소요시간 12분 lottos에 담긴 숫자들 중 순서를 고려하지 않고 6개를 뽑아 차례로 출력한다. 이미 배열은 오름차순으로 되어있기 때문에 그대로 이미 뽑혔는지 확인해주며 뽑히지 않았다면 뽑은 표시 후 다음 자릿수에서 탐색한다. depth == 6이 될 때 출력한다. 파이썬 코드는 다음과 같다. import sys input = sys.. 2021. 3. 17.
[BOJ] 13305. 주유소(Python) / Greedy www.acmicpc.net/problem/13305 13305번: 주유소 표준 입력으로 다음 정보가 주어진다. 첫 번째 줄에는 도시의 개수를 나타내는 정수 N(2 ≤ N ≤ 100,000)이 주어진다. 다음 줄에는 인접한 두 도시를 연결하는 도로의 길이가 제일 왼쪽 도로부터 N-1 www.acmicpc.net 문제 이해하는 건 금방이었다. 그리디(Greedy) 알고리즘으로 접근했다. 그리디하게 for문으로 1번 인덱스부터 현재 위치에서의 주유비와 이전의 주유비와 비교, 최솟값으로 갱신한다. 최소 주유비로 거리를 곱한 값을 전체 가격 total 변수에 더해준다. 늘 느끼듯 Greedy나 DP는 발상이 힘들지, 코드는 짧다. 파이썬 코드는 다음과 같다. import sys input = sys.stdin... 2021. 3. 12.
[BOJ] 3055. 탈출(Python) / BFS www.acmicpc.net/problem/3055 3055번: 탈출 사악한 암흑의 군주 이민혁은 드디어 마법 구슬을 손에 넣었고, 그 능력을 실험해보기 위해 근처의 티떱숲에 홍수를 일으키려고 한다. 이 숲에는 고슴도치가 한 마리 살고 있다. 고슴도치는 제 www.acmicpc.net # 59분 소요 골드 5 난이도로, 무난한 BFS 문제였다. input 받으면서 고슴도치의 좌표와 물의 좌표를 각각의 큐에 저장, 물과 고슴도치 visited의 해당 위치를 0으로 표시 물의 이동을 wbfs() 함수로 도달할 수 있는 거리 표시(water) 고슴도치의 이동을 hbfs() 함수로 갈 수 있는 곳으로 퍼트린다(hedgehog) 이동 중 비버의 집(D)를 만나면 거리 출력하고 종료 다 퍼트렸는데 비버의 집에 도달.. 2021. 3. 12.
[BOJ] 1063. 늑대와 양(Python) www.acmicpc.net/problem/16956 16956번: 늑대와 양 크기가 R×C인 목장이 있고, 목장은 1×1 크기의 칸으로 나누어져 있다. 각각의 칸에는 비어있거나, 양 또는 늑대가 있다. 양은 이동하지 않고 위치를 지키고 있고, 늑대는 인접한 칸을 자유롭게 www.acmicpc.net 실버 4 문제인데 문제와 예시 출력을 여러 번 보면서 어떻게 하면 이런 출력이 나오는지 꽤 고민했다,, 도대체 울타리를 어디에 설치해야 하는지! 너무 막막해서 다른 블로그를 보면서 아이디어를 조금 참고했다. 페이지를 좀더 내려보니, 내가 간과한 이런 문구가 있었다. "이 문제는 설치해야 하는 울타리의 최소 개수를 구하는 문제가 아니다." 이것이 핵심이었다. 즉, 울타리에 대한 제한 조건이 존재하지 않는다는 .. 2021. 3. 11.

티스토리툴바