본문 바로가기
728x90
반응형

전체글

알고리즘 - 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[포도주.. 더보기
알고리즘 - Python / 백준 - 2205번 : 저울 추 만들기 2205번: 저울 추 만들기 (acmicpc.net) 2205번: 저울 추 만들기 질량(또는 무게)가 1, 2, 3, …, n인 납덩어리가 있고, 질량이 1, 2, 3, …, n인 주석덩어리가 있다. 각각의 질량을 갖는 덩어리들은 1개씩밖에 없다. 이제 이 납덩어리와 주석덩어리를 한개씩 녹여 합 www.acmicpc.net 풀이 질량이 1 ~ n 까지 각 무게당 한 개씩 주석과 납 덩어리가 존재한다. 주석과 납 덩어리들을 한개씩 적절하게 섞어 모두 2의 거듭제곱 무게가 되도록 만드는 조합을 출력하는 문제다. 문제에서 예외 처리가 없다는 것에서 약간의 힌트를 얻었다. 만약 n의 경우에 따라 모두 2의 거듭제곱 무게가 되지 못하는 경우가 있었다면 , 문제에 그러한 경우는 -1을 출력하시오 처럼 예외 처리가 .. 더보기
알고리즘 - Python / 백준 - 3273번 : 두 수의 합 3273번: 두 수의 합 (acmicpc.net) 3273번: 두 수의 합 n개의 서로 다른 양의 정수 a1, a2, ..., an으로 이루어진 수열이 있다. ai의 값은 1보다 크거나 같고, 1000000보다 작거나 같은 자연수이다. 자연수 x가 주어졌을 때, ai + aj = x (1 ≤ i < j ≤ n)을 만족하는 www.acmicpc.net 풀이 수열 중 ai + aj = x 를 만족하는 쌍의 개수를 찾는 문제다. 투 포인터로 풀 수 있는 가장 기본적인 문제다. 수열을 정렬한 후 앞과 뒤 부터 포인터를 출발시켜 , x보다 크다면 뒤쪽을 당겨 합을 줄이고 x보다 작다면 앞쪽을 밀어 합을 늘인다. 두 포인터가 만날 때 , while 문이 종료되도록 하면 모든 범위에 대해 투 포인터들이 합을 검사하고.. 더보기
반응형

티스토리툴바