본문 바로가기

Algorithm77

[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.
[Algorithm] 백트래킹(Backtracking)이란? Backtracking은 제약조건 만족문제에서 해를 찾는 방법이다. 개념 : 여러가지 경우의 수가 있는 문제에서 특정조건을 만족하는 찾는 데 있어, 조건을 탐색하다가 어느 순간 조건이 맞지 않는 것으로 판단되면 그 쪽의 경우의 수는 더이상 체크하지 않고 다른 경우의 수를 체크하는 것. 일종의 문제 푸는 전략으로, 알고리즘은 아니다. 고려할 수 있는 경우의 수를 상태공간트리로 표현 DFS 방식으로 후보군 확인 상태공간트리 탐색하며 제약조건을 만족하지 않으면 해당 부분에서 파생될 수 있는 모든 경우의 수를 더이상 보지 않는다. 이후 해의 후보가 될 만한 곳을 바로 넘어가서 탐색을 이어간다. 이를 통해 체크해야 하는 조건의 수를 확연히 줄이므로 계산량을 줄일 수 있는 기법이다. Promising : 조건 검사.. 2021. 3. 9.
[SWEA] 5658. 보물상자 비밀번호(Python) swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AWXRUN9KfZ8DFAUo SW Expert Academy SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요! swexpertacademy.com # 18분 소요 삼성 SW역량테스트 모의 문제 중 가장 쉬운 난이도의 문제이다. 특별한 알고리즘 X 리스트 슬라이싱을 이용해 회전 처리 나온 값에 16진수 처리를 하면서 중복없이 리스트에 담아줌 내림차순 정렬 후 K번째 수 출력 파이썬 코드는 다음과 같다. T = int(input()) for tc in range(T): N, K = map(int, input().split()) A = list(input()) .. 2021. 3. 9.
[BOJ] 8911. 거북이(Python) / Simulation www.acmicpc.net/problem/8911 8911번: 거북이 첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스는 한 줄로 이루어져 있고, 컨트롤 프로그램이 주어진다. 프로그램은 항상 문제의 설명에 나와있는 네가지 명령으로만 이루어져 www.acmicpc.net 실버2 문제라 그리 어렵지 않은 시뮬레이션 문제였다. 맵을 그릴 필요 없이 (0, 0) 위치에서 시작하여 문제에 주어진 조건 그대로 구현한다. L과 R의 경우는 방향만 바꿔준다. 이 때, 현재 방향을 각 경우별로 만들어놓은 방향 전환 리스트(dirL, dirR)를 참조하여 현 방향에 해당하는 인덱스로 바꾼다. F와 B의 경우는 현재 방향으로 한 칸 나아간다. 이 때, 이동한 위치를 min_r/c, max_r/c 최솟값과 .. 2021. 3. 9.

티스토리툴바