live the life you love

www.acmicpc.net/problem/20058 20058번: 마법사 상어와 파이어스톰 마법사 상어는 파이어볼과 토네이도를 조합해 파이어스톰을 시전할 수 있다. 오늘은 파이어스톰을 크기가 2N × 2N인 격자로 나누어진 얼음판에서 연습하려고 한다. 위치 (r, c)는 격자의 r행 c www.acmicpc.net DFS 함수에서 재귀가 터져서 sys.setrecursionlimit을 사용했다. 실제 삼성 코딩테스트에서는 sys 라이브러리를 사용할 수 없으니, DFS를 재귀로 짜지 않고 스택으로 짜거나 BFS로 대체하여 풀어야 할 듯 하다. 회전하는 부분을 제대로 구하지 못해서 다른 블로그 글을 참조했다. 리스트의 회전은 어렵다.. 소스코드 import sys, copy sys.setrecursionl..

www.acmicpc.net/problem/20056 20056번: 마법사 상어와 파이어볼 첫째 줄에 N, M, K가 주어진다. 둘째 줄부터 M개의 줄에 파이어볼의 정보가 한 줄에 하나씩 주어진다. 파이어볼의 정보는 다섯 정수 ri, ci, mi, si, di로 이루어져 있다. 서로 다른 두 파이어볼의 위치 www.acmicpc.net 문제에서 구현하라는 대로 푸는 전형적인 시뮬레이션 문제였다. 하지만, 시간이 3980ms로 가까스로 TLE를 면한듯 하다. 같은 칸에 파이어볼이 여러개 있을 수 있으므로 board 안에 deque를 넣어서 파이어볼이 추가로 들어오면 append 시켜줬다. 소스코드 import sys, copy from collections import deque dy = [-1, -1, ..

www.acmicpc.net/problem/2473 2473번: 세 용액 첫째 줄에는 전체 용액의 수 N이 입력된다. N은 3 이상 5,000 이하의 정수이다. 둘째 줄에는 용액의 특성값을 나타내는 N개의 정수가 빈칸을 사이에 두고 주어진다. 이 수들은 모두 -1,000,000,000 이상 www.acmicpc.net 투 포인터를 활용해서 문제를 풀었다. 기존의 투 포인터와 다른 점은 확인해야 할 값이 1개 더 있는것인데, 이것은 추가적인 포인터를 1개 더 두어 해결하였다. 포인터가 1개 더 추가 되면서 포인터끼리 겹치는 경우가 발생할 수 있기 때문에 따로 체크를 해줘야 한다. 세 용액의 합이 0이 되는 경우는 여러개 있을 수 있고, 그 중 아무거나 출력하면 되기 때문에 세 지점에서의 값들의 합이 0 이..

www.acmicpc.net/problem/20168 20168번: 골목 대장 호석 - 기능성 첫 줄에 교차로 개수 N, 골목 개수 M, 시작 교차로 번호 A, 도착 교차로 번호 B, 가진 돈 C 가 공백으로 구분되어 주어진다. 이어서 M 개의 줄에 걸쳐서 각 골목이 잇는 교차로 2개의 번호와, 골목의 www.acmicpc.net 다익스트라 문제를 풀려고 했는데, 백트래킹으로 풀었다. 처음에는 문제의 설명이 조금 헷갈렸는데, 고려해야할 조건은 다음과 같았다. 가진 돈을 목적지까지 도착하기 전에 전부 사용하지 않기 목적지에 도착했다면 지금까지 지나온 노드 중 가장 비용이 큰 값이 어떤 것인가? 목적지에 도착하는 길이 2개 이상인 경우 가장 비용이 큰 값 중 최소가 정답 위의 조건들을 백트래킹에 맞게 풀어주..

www.acmicpc.net/problem/18061806번: 부분합첫째 줄에 N (10 ≤ N < 100,000)과 S (0 < S ≤ 100,000,000)가 주어진다. 둘째 줄에는 수열이 주어진다. 수열의 각 원소는 공백으로 구분되어져 있으며, 10,000이하의 자연수이다.www.acmicpc.net 문제의 이름에서도 알 수 있듯 부분합을 활용하는 문제이다. 부분합이란 시작점과 끝점을 정해서 해당 구간 내에 있는 원소들의 합을 구하는 것이다. for i in range(1, n+1): prefix[i] = prefix[i-1] + _list[i-1] 이 문제는 굳이 부분 합을 사용하지 않고, 투 포인터로도 풀 수 있는 문제였다. 투 포인터 소스코드import sys n,s = map(int, inp..

www.acmicpc.net/problem/9376 9376번: 탈옥 상근이는 감옥에서 죄수 두 명을 탈옥시켜야 한다. 이 감옥은 1층짜리 건물이고, 상근이는 방금 평면도를 얻었다. 평면도에는 모든 벽과 문이 나타나있고, 탈옥시켜야 하는 죄수의 위치도 나타 www.acmicpc.net 첫 플레문제였다. 단순히 다익스트라나 BFS로 하면 될 것 같았는데 아무리 고민을 해도 시간복잡도를 알맞게 할 수 없을 것 같아서 다른 블로그를 보고 풀었다. 찾아보니 이런 유형의 문제는 0-1 BFS라고 한다. 가중치가 0과 1만 있는 그래프에서 사용할 수 있는데, 기존의 BFS는 방향탐색을 마치고, 다음에 갈 지점을 큐에 삽입할 때 단순히 큐의 맨뒤에 push 했다. 또한, 다익스트라의 경우도 우선순위 큐를 사용하여 항..

www.acmicpc.net/problem/10711 10711번: 모래성 첫째 줄에는 모래성의 가로세로 격자 크기 H, W가 주어진다. (1 ≤ H, W ≤ 1,000) 그 다음 H줄에 걸쳐 W개의 문자로 모래성의 상태를 나타내는 문자가 들어온다. 각 문자는 1~9 사이의 숫자, 또는 '.' 이 www.acmicpc.net 맨 처음에는 단순히 전체 배열을 탐색하는 BFS 코드를 짰더니 시간 초과가 발생했다. 최악의 경우 O(N^3) 까지 들어 올 수 있기 때문에 그렇다. 그래서 조금 다른 방법을 사용했다. 비어있는 부분의 위치를 모두 큐에 삽입하고, 이를 기준으로 BFS 탐색을 한다. 8방 탐색을 하는 동안 모래성을 만나면 해당 모래성에서 1을 빼주고, 큐에서 popleft를 한다. 만약 모래성의 값이..

www.acmicpc.net/problem/14620 14620번: 꽃길 2017년 4월 5일 식목일을 맞이한 진아는 나무를 심는 대신 하이테크관 앞 화단에 꽃을 심어 등교할 때 마다 꽃길을 걷고 싶었다. 진아가 가진 꽃의 씨앗은 꽃을 심고나면 정확히 1년후에 꽃이 피므 www.acmicpc.net 백트래킹을 활용하는 문제였다. dfs 함수에서 반복문을 돌면서 백트래킹을 하는 부분을 블로그 참고해서 풀었다. 소스 코드 import sys sys.stdin = open("input.txt", "r") flower_dir = [(0,0),(-1,0),(1,0),(0,-1),(0,1)] # 현위치, 상, 하, 좌, 우 n = int(input()) board = [list(map(int, input().spl..

가끔 알고리즘 문제에 나오는 소수계산을 위해 정리하는 글이다.소수란, 1과 자기 자신 이외에 약수를 가지지 않는 1보다 큰 자연수 이다. 1은 소수가 아니다 소수 판별 알고리즘은 대표적으로 두가지 방법으로 구현 할 수 있다. 일반적인 방법 우선, 반복문을 사용하는 것이다. 이 방법은 1개의 숫자가 소수인지 아닌지 판별하는데 사용하면 좋다. 여러 숫자를 소수 판별해야하는 경우는 아래 있는 에라토스테네스의 체가 더 유용하다. n이라는 숫자가 소수인지 확인하기 위해서는 2부터 n-1까지 나눠보면서 나머지가 0이 나오는 숫자가 한개도 없으면 n은 소수이다. 하지만 n-1까지 나눠보지 않더고 √n 까지만 확인해봐도 된다. 소스코드 import sys, math # 소수 판별 알고리즘 : 제곱근까지 구하기 def ..

www.acmicpc.net/problem/1747 1747번: 소수&팰린드롬 어떤 수와 그 수의 숫자 순서를 뒤집은 수가 일치하는 수를 팰린드롬이라 부른다. 예를 들어 79,197과 324,423 등이 팰린드롬 수이다. 어떤 수 N (1 ≤ N ≤ 1,000,000)이 주어졌을 때, N보다 크거나 같고, www.acmicpc.net 소수 판별과 팰린드롬을 사용하는 문제이다. 파이썬의 경우 팰린드롬은 굉장히 쉽게 판별할 수 있으므로 패스한다. 소수 판별은 에라토스테네스의 체 2부터 제곱근까지 나머지 확인 2가지 방식으로 테스트를 해봤는데, 시간복잡도는 크게 차이나지 않는 것 같다. 다만, 소수의 갯수보다 팰린드롬의 갯수가 더 많으므로 팰린드롬인지 확인해주는 것을 먼저 해주는게 시간복잡도 측면에서 효율적이..