본문 바로가기

알고리즘70

[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.
[BOJ] 백준 BOJ solved.ac 티어 < Gold 1 > 달성 꾸준히 알고리즘 문제를 풀다 보니, solved.ac 티어 Gold 1을 달성했다. 등급을 염두에 두고 문제를 푸는 것은 아니다만^_^ 주로 실력 향상을 위해 실버보다는 골드 문제에 중점을 두고 풀고 있는 편이긴 하다. 마지막으로 본 나의 등급은 Gold 3? 4? 정도 였던 것 같다. 같이 스터디하는 팀원들과 어느 날 백준 등급 얘기가 나와서 생각난 김에 몇 달만에 사이트 들어와보니 Gold 1이더라. 조금만 더 풀면 Platinum등급이라고 하니 뭔가 솔깃해지고, 좀더 동기부여가 되는 것 같다 ㅋㅋㅋㅋ 많이 풀수록 익숙해지고 정말 실력이 느는 것 같다. 늘 하던 대로 Gold 문제 위주로 좀더 많이 풀어봐야겠다. 힘든 일상 속 이룬 작은 성취였다. Keep Going~~~~ 2021. 3. 11.

티스토리툴바