728x90 반응형 코딩 리스트형 알고리즘 - Python / 백준 - 9661번 : 돌 게임 7 9661번: 돌 게임 7 (acmicpc.net) 9661번: 돌 게임 7 첫째 줄에 N이 주어진다. (1 ≤ N ≤ 1,000,000,000,000) www.acmicpc.net 풀이 서로 돌을 n개씩 번갈아 가며 가져가다가 가져갈 돌이 없다면 패배하는 게임이다. 백준의 돌 게임 문제들은 게임이론과 관련된 문제로 개인적으로 상당히 좋아하는 문제다. 이전에 돌 게임6 에 관한 풀이도 작성하였다. 알고리즘 - Python / 백준 - 9660번 : 돌 게임 6 (tistory.com) 알고리즘 - Python / 백준 - 9660번 : 돌 게임 6 9660번: 돌 게임 6 (acmicpc.net) 9660번: 돌 게임 6 첫째 줄에 N이 주어진다. (1 ≤ N ≤ 1,000,000,000,000) www... 더보기 알고리즘 - Python / 백준 - 15686번 : 치킨 배달 15686번: 치킨 배달 (acmicpc.net) 15686번: 치킨 배달 크기가 N×N인 도시가 있다. 도시는 1×1크기의 칸으로 나누어져 있다. 도시의 각 칸은 빈 칸, 치킨집, 집 중 하나이다. 도시의 칸은 (r, c)와 같은 형태로 나타내고, r행 c열 또는 위에서부터 r번째 칸 www.acmicpc.net 풀이 정사각형 2차원 배열에 치킨집과 집의 위치가 주어지고 , m개의 치킨집만 남긴다고 할 때 , 집과 가장 가까운 치킨집의 거리가 가장 적게 나오는 경우의 치킨집과 집들 사이의 거리의 합을 출력하는 문제다. 한 줄에 문제를 표현하기 어려워 길게 썼으니 , 위의 문제 사이트에 가서 문제를 읽어보는 것을 추천한다. 일단 문제를 딱 보았을 때 , 2차원 배열 그래프 탐색 문제인가 하였으나 , 천천.. 더보기 알고리즘 - Python / 백준 - 5555번 : 반지 5555번: 반지 (acmicpc.net) 5555번: 반지 당신은 N개의 반지를 가지고 있다. 각각의 반지는 대문자 10 문자로 이루어진 문자열이 새겨져 있다. 반지는 문자열의 시작과 끝이 연결된 형태로 문자가 새겨져 있다. 반지에 각인된 문자열을 www.acmicpc.net 풀이 반지에 문자열이 새겨져 있고 , 이 문자열이 존재하는지 확인하는 문제다. 단 , 반지의 구조는 한 바퀴 도는 구조이기 때문에 좌우가 연결되어있다는 것을 생각해야 한다. 찾고 싶은 문자열이 4글자 라면 0, 1, 2, 3번 옆으로 밀어 보면서 실제 그 문자열이 있는지 체크하면 된다. import sys fw = sys.stdin.readline().replace("\n","") n = int(sys.stdin.readline(.. 더보기 알고리즘 - Python / 백준 - 2358번 : 평행선 2358번: 평행선 (acmicpc.net) 2358번: 평행선 첫째 줄에 n(1 ≤ n ≤ 100,000)이 주어진다. 다음 n개의 줄에는 각 점의 좌표가 주어진다. 만약 입력에 서로 같은 두 점이 주어지면, 그 두 점을 이용하여 직선을 만들 수 있다. 좌표는 절댓값이 231보 www.acmicpc.net 풀이 각점의 좌표가 주어지고 x, y축에 평행하게 직선을 그릴 때 , 2개 이상의 점을 지나는 직선이 몇 개인지 구하는 문제다. 딕셔너리를 통해 해당 x , y 좌표를 지나는 점이 몇개몇 개 있는지 기록하였고 딕셔너리의 전체 요소를 for로 돌며 직선을 몇 개 그릴 수 있는지 세주었다. 주의할 점은 같은 점도 생각해야 한다는 것과 직선의 개수기 때문에 직선위의 여러 개의 점이 있다고 해서 여러 개의 .. 더보기 알고리즘 - Python / 백준 - 1107번 : 리모컨 1107번: 리모컨 (acmicpc.net) 1107번: 리모컨 첫째 줄에 수빈이가 이동하려고 하는 채널 N (0 ≤ N ≤ 500,000)이 주어진다. 둘째 줄에는 고장난 버튼의 개수 M (0 ≤ M ≤ 10)이 주어진다. 고장난 버튼이 있는 경우에는 셋째 줄에는 고장난 버튼 www.acmicpc.net 풀이 리모컨의 고장 난 버튼이 주어질 때 , 해당 채널로 가기 위해서는 버튼을 몇 번 눌러야 하는지 구하는 문제다. 일단 최대 목표 번호가 500,000 이고 현재 채널 번호가 100 이므로 모든 버튼이 고장 났을 때 , +로만 움직이면 499,900번 눌러서 움직인다. 일단 이 부분을 생각하면서 문제풀이에 들어갔고 , 풀이 알고리즘은 2가지로 생각했다. 1. 멀쩡한 번호들로 모든 번호 조합을 구하고 .. 더보기 알고리즘 - Python / 백준 - 10026번 : 적록색약 10026번: 적록색약 (acmicpc.net) 10026번: 적록색약 적록색약은 빨간색과 초록색의 차이를 거의 느끼지 못한다. 따라서, 적록색약인 사람이 보는 그림은 아닌 사람이 보는 그림과는 좀 다를 수 있다. 크기가 N×N인 그리드의 각 칸에 R(빨강), G(초록) www.acmicpc.net 풀이 익숙한 형태의 일반적인 그래프 탐색 문제다. 2차원 배열 형태의 상하좌우가 연결되어 있으므로 , visited를 잘 체크하면서 bfs, dfs를 사용하면 된다. 문제의 포인트라면 적록색약의 경우 R = G 인 경우인데 , 적록색약이 아닌 경우를 bfs로 구한 이후에 새롭게 적록색약 배열을 만들어 준 후 다시 bfs를 진행하여 답을 찾았다. 새로운 적록색약 배열은 전체 2차원 배열을 순회하면서 R인 경우 .. 더보기 알고리즘 - Python / 백준 - 2225번 : 합분해 2225번: 합분해 (acmicpc.net) 2225번: 합분해 첫째 줄에 답을 1,000,000,000으로 나눈 나머지를 출력한다. www.acmicpc.net 풀이 0 ~ N 까지의 정수를 K번 더해서 N을 만들고 , 수를 중복하여 사용하거나 자리가 다르면 다른 경우로 처리한다. 이때 , 만들 수 있는 모든 경우의 수를 출력하는 문제다. 처음 문제를 보자마자 직관적으로 든 생각은 중복 조합 스타일의 문제다 라는 생각이었다. 과거 고등학교 시절 확통문제에서 단골 문제였던 X+Y+Z = 4 를 만족하는 음이 아닌 X, Y, Z 순서쌍의 개수는? 문제와 매우 흡사하다고 생각했다. 생각한 대로 중복 조합으로 문제를 풀고 정답이 나왔다. 골드 5 문제에서 중복조합은 너무 쉬운 풀이라고 생각해서 중간에 풀다가 .. 더보기 알고리즘 - Python / 백준 - 2156번 : 포도주 시식 2156번: 포도주 시식 (acmicpc.net) 2156번: 포도주 시식 효주는 포도주 시식회에 갔다. 그 곳에 갔더니, 테이블 위에 다양한 포도주가 들어있는 포도주 잔이 일렬로 놓여 있었다. 효주는 포도주 시식을 하려고 하는데, 여기에는 다음과 같은 두 가지 규 www.acmicpc.net 풀이 포도주가 잔에 담겨 순서대로 놓여 있을 때 , 3잔을 연속으로 마시지 못한다. 다음 조건에서 최대한 포도주를 많이 먹으려면 어떻게 해야 하는지 출력하는 문제다. 포인트는 3잔 연속 못마시니까 언제 마시는 걸 멈추고 다시 마실까 이다. I 번째 포도주를 마시거나 마시지 않거나 , 마신다면 몇 번 연속으로 마시는지 기록하면서 모든 경우를 확인하면 된다. 따라서 DP 문제로 접근할 수 있다. DP배열은 DP[포도주.. 더보기 이전 1 2 3 4 5 6 ··· 17 다음 반응형
