본문 바로가기

분류 전체보기414

백준 2178 미로 탐색 문제 URL : https://www.acmicpc.net/problem/2178 2178번: 미로 탐색 첫째 줄에 두 정수 N, M(2 ≤ N, M ≤ 100)이 주어진다. 다음 N개의 줄에는 M개의 정수로 미로가 주어진다. 각각의 수들은 붙어서 입력으로 주어진다. www.acmicpc.net 문제접근법 : 2차원으로 bfs를 이용하는 간단한 문제입니다. 연결표현은 좌우상하 총 4개의 연결선이 되겠고 bfs를 이용하여 0,0 에서 n-1,m-1로 한칸한칸 움직이면 가장 빠른 경로로 갈수있는 간단한 문제입니다. 작년에 c++ 로 풀어서 이번엔 다시풀었을때 파이썬으로 풀었습니다. 파이썬의 입력방식과 2차원 배열선언이 어려워서 많이 찾게되었지요 2가지 코드 다 올려드리겠습니다. 소스코드: 파이썬코드 1 2 .. 2020. 8. 6.
백준 1822 차집합 문제 URL : https://www.acmicpc.net/problem/1822 1822번: 차집합 첫째 줄에는 집합 A의 원소의 개수 n(A)와 집합 B의 원소의 개수 n(B)가 빈 칸을 사이에 두고 주어진다. (1≤n(A), n(B)≤500,000)이 주어진다. 둘째 줄에는 집합 A의 원소가, 셋째 줄에는 집합 B의 원소가 www.acmicpc.net 문제접근법 : 소스코드만 봐도 바로 알수 있습니다. 문제제목대로 A - B의 집합을 구하는겁니다. 중요한건 집합을 표현하기위해 set을 이용하면되었고 너무 쉬운문제라 python 코드로 올려드리겠습니다 . 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 # -*- coding: euc-kr -*- n1,n2=map(int,inpu.. 2020. 8. 6.
백준 17088 등차수열 변환 문제 URL : https://www.acmicpc.net/problem/17088 17088번: 등차수열 변환 크기가 N인 수열 A = [A1, A2, ..., AN]이 있을 때, 모든 1 ≤ i < N에 대해서, Ai+1-Ai가 모두 일치하면 등차수열이라고 한다. 예를 들어, [3], [6, 6, 6], [2, 8, 14, 20], [6, 4, 2]는 등차수열이고, [4, 5, 4], [6, 3, 1]�� www.acmicpc.net 문제 접근법 : 연산을 최대 1번 ,즉 1을 더하거나 혹은 1을빼거나 혹은 안하거나 해서 등차수열을 만다는 거지만 이것을 어떻게 만드냐에 따라 시간초과나느냐 안나느냐 문제입니다. 단순하게 정말로 모든 경우의수를 만들고난후 첫번째인덱스부터 n번째 인덱스까지 확인해서 공차가.. 2020. 8. 5.
백준 16197 두 동전 문제 URL : https://www.acmicpc.net/problem/16197 16197번: 두 동전 N×M 크기의 보드와 4개의 버튼으로 이루어진 게임이 있다. 보드는 1×1크기의 정사각형 칸으로 나누어져 있고, 각각의 칸은 비어있거나, 벽이다. 두 개의 빈 칸에는 동전이 하나씩 놓여져 있고, �� www.acmicpc.net 문제 접근법 : bfs로 두동전을 좌우상하 같은 방향으로 동시에 움직이지만 하나가 벽때문에 움직일수 없어도 다른하나는 움직일수있다면 하나라도 움직이게 해줘야 합니다. 1. map의 사이즈를 [n+2][n+2] 까지 잡아 움직이는 행열의 범위를 0~n+1 까지 움직일수 있게해줍니다 다만 행열의 위치가 0 이나 n+1 일때는 밖으로 나가는 것을 표현해주고 그외는 맵의 범위대로 .. 2020. 7. 31.

티스토리툴바