본문 바로가기

개발/algorithm

[백준 19237번] 어른 상어 문제 링크 https://www.acmicpc.net/problem/19237 19237번: 어른 상어 첫 줄에는 N, M, k가 주어진다. (2 ≤ N ≤ 20, 2 ≤ M ≤ N2, 1 ≤ k ≤ 1,000) 그 다음 줄부터 N개의 줄에 걸쳐 격자의 모습이 주어진다. 0은 빈칸이고, 0이 아닌 수 x는 x번 상어가 들어있는 칸을 의미 www.acmicpc.net 풀이 백준 상어 문제들은 다 복잡한 것 같다.. graph : 상어 번호와 남은 냄새 시간을 저장한다. shark : 상어의 번호가 key, 위치와 방향을 value로 저장한다. priorites : 상어의 방향 별 우선 순위를 저장한다. 시간이 1000초 이하일 때까지 아래 과정을 반복한다. 1. 낮은 번호부터, 상어 별 현재 위치에 냄새를.. 더보기
[백준 19238번] 스타트 택시 - python 문제 링크 https://www.acmicpc.net/problem/19238 19238번: 스타트 택시 첫 줄에 N, M, 그리고 초기 연료의 양이 주어진다. (2 ≤ N ≤ 20, 1 ≤ M ≤ N2, 1 ≤ 초기 연료 ≤ 500,000) 연료는 무한히 많이 담을 수 있기 때문에, 초기 연료의 양을 넘어서 충전될 수도 있다. 다 www.acmicpc.net 풀이 다익스트라 + 구현 문제 1. 다익스트라로 현재 위치에 갈 수 있는 최단 거리 구하기 2. 손님별 현재 위치에서 거리, 행 번호, 열 번호 순으로 정렬 -> 우선순위큐 (heap) 사용 - 현재 위치에서 도달할 수 있는 승객이 없다면 중단 3. 갈 승객 위치와 도착위치, 현재위치에서 손님 출발지까지 연료양 저장 4. 승객 제거 5. 다익스트라.. 더보기
[백준 20061번] 모노미노도미노 - python 문제 링크 https://www.acmicpc.net/problem/20061 20061번: 모노미노도미노 2 모노미노도미노는 아래와 같이 생긴 보드에서 진행되는 게임이다. 보드는 빨간색 보드, 파란색 보드, 초록색 보드가 그림과 같이 붙어있는 형태이다. 게임에서 사용하는 좌표 (x, y)에서 x는 행, www.acmicpc.net 문제 풀이 1. move_blue, move_green : 블록 옮기기 blue는 x 좌표 고정, y 좌표 늘리기 green은 y 좌표 고정, x 좌표 늘리기 2. check_blue, check_green : 제거 될 수 있는 블록 체크하기 행이나 열 모두 채워졌는지 확인하고 제거할 수 있으면 remove 함수 열(행) 번호와 함께 실행 0, 1 행이나 0,1 열에 있으면 .. 더보기
[백준 17471번] 게리맨더링, 게리맨더링 2 - Python 문제 링크 https://www.acmicpc.net/problem/17471 17471번: 게리맨더링 선거구를 [1, 4], [2, 3, 5, 6]으로 나누면 각 선거구의 인구는 9, 8이 된다. 인구 차이는 1이고, 이 값보다 더 작은 값으로 선거구를 나눌 수는 없다. www.acmicpc.net 문제 풀이 - 백트래킹 + bfs 문제 1. 백트래킹으로 가능한 조합 찾기 2. bfs로 모두 연결되어 있는지 확인하기 3. 가능하면 정답 갱신 # https://www.acmicpc.net/problem/17471 from collections import deque def bfs(g): q = deque() check = [False] * n check[g[0]] = True q.append(g[0]) .. 더보기
[프로그래머스][level3] 아이템 줍기 - python 문제 링크 https://programmers.co.kr/learn/courses/30/lessons/87694 코딩테스트 연습 - 아이템 줍기 [[1,1,7,4],[3,2,5,5],[4,3,6,9],[2,6,8,8]] 1 3 7 8 17 [[1,1,8,4],[2,2,4,9],[3,6,9,8],[6,3,7,7]] 9 7 6 1 11 [[2,2,5,5],[1,3,6,4],[3,1,4,6]] 1 4 6 3 10 programmers.co.kr 풀이 - bfs 문제 여기서 중요한 것은 그래프의 크기를 두배로 늘리는 것이다. 예를 들어, 아래 그래프의 (3,5) 위치에서 (3,6)으로 위로 한칸 이동할 수 없는데, bfs에 따르면 이동이 가능하다고 판단하기 때문에 두배로 늘려주는 것이다. 따라서 1. 네모 테두.. 더보기
[백준 17086번] 아기 상어2 - python 문제 링크 https://www.acmicpc.net/problem/17086 17086번: 아기 상어 2 첫째 줄에 공간의 크기 N과 M(2 ≤ N, M ≤ 50)이 주어진다. 둘째 줄부터 N개의 줄에 공간의 상태가 주어지며, 0은 빈 칸, 1은 아기 상어가 있는 칸이다. 빈 칸과 상어의 수가 각각 한 개 이상인 입력만 www.acmicpc.net 문제 풀이 - bfs 풀이 아기 상어가 아닌 위치마다 bfs로 가장 가까운 아기 상어까지 거리를 구한 후 최댓값을 갱신해주었다. # https://www.acmicpc.net/problem/17086 import sys from collections import deque # 8방향 nx = [1,-1,0,0, 1, 1, -1 ,-1] ny = [0,0,1,.. 더보기
[백준 13913번] 숨바꼭질4 - python 문제링크 https://www.acmicpc.net/problem/13913 13913번: 숨바꼭질 4 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 www.acmicpc.net 풀이 - 처음에는 큐에 route라는 배열도 함께 넣어줘서 위치 이동할 때마다 route 배열에 경로 추가해주는 방식으로 구현하였는데 메모리 초과 발생 내가 구현한 것처럼 경로를 모두 다 기록하게 되면 O(n^2)의 메모리가 필요하게 되어 메모리 초과가 발생한다고 한다. 따라서 모든 경로는 저장하는 것이 아니라, 자취를 남기는 식으로 구현해야했다. pat.. 더보기
[백준 2023번] 신기한 소수 - python 문제 링크 https://www.acmicpc.net/problem/2023 2023번: 신기한 소수 수빈이가 세상에서 가장 좋아하는 것은 소수이고, 취미는 소수를 가지고 노는 것이다. 요즘 수빈이가 가장 관심있어 하는 소수는 7331이다. 7331은 소수인데, 신기하게도 733도 소수이고, 73도 소수 www.acmicpc.net 풀이 소수 규칙 맨 앞자리가 2, 3, 5, 7 이어야 한다 dfs와 에라토스테네스의 채 사용 import math # 에라토스테네스의 채로 소수 판별 def is_prime_num(n): for i in range(2, int(math.sqrt(n))+1): # n의 제곱근을 정수화 시켜준 후 + 1 if n % i == 0: return False return True #.. 더보기

티스토리툴바