티스토리

what ryan do

검색하기

블로그 홈

what ryan do

whatryando.tistory.com/m

놀면머하누😇

구독자: 7

방명록 방문하기

728x90

주요 글 목록

백준 11501 주식 파이썬 코드 풀이 https://www.acmicpc.net/problem/11501 11501번: 주식 입력의 첫 줄에는 테스트케이스 수를 나타내는 자연수 T가 주어진다. 각 테스트케이스 별로 첫 줄에는 날의 수를 나타내는 자연수 N(2 ≤ N ≤ 1,000,000)이 주어지고, 둘째 줄에는 날 별 주가를 나타 www.acmicpc.net 와우 이정도도 이제 혼자 못 풀겠어서 다른사람 글을 참고해서 풀었다 ㅠ 코딩이 어렵진 않은문제 N = int(input()) tc = {} for i in range(N): int(input()) tc[i] = list(map(int, input().split())) ans_list = [] for i in range(N): price_max = 0 ans = 0 for comp in.. 공감수 1 댓글수 1 2023. 2. 18.
백준 18818, iguana instructions 코드/풀이 (이구아나 안내하기), Python, heapq/bfs 풀이 간만에 코테공부 ㅎㅎ 이거 실버1인데 두시간이나 걸렸당... 전에 분명 쉬웠던 유형중 하나가 bfs인데.. 공부좀 다시해야지 자세한 코드가 보고싶은 분은 깃허브 링크 눌러주세용 GitHub - Rhyankwon/algorithms Contribute to Rhyankwon/algorithms development by creating an account on GitHub. github.com 문제 설명 ㄱㄱ 18818번: Iguana Instructions Iggy the Iguana has found himself trapped in a corn maze! The corn maze can be modelled as a square grid where some of the cells are blocked.. 공감수 0 댓글수 0 2022. 6. 4.
백준 17281 ⚾ 문제 코드/해설 (파이썬), 구현 문제, 삼성 A형 기출 으악 푸는데 엄청 오래걸렸다...ㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋ 나.....삼성갈수있을까 문제 코드만 궁금한 분은 깃허브 링크 눌러주세요 GitHub - Rhyankwon/algorithms Contribute to Rhyankwon/algorithms development by creating an account on GitHub. github.com 문제 설명 ㄱㄱ 17281번: ⚾ ⚾는 9명으로 이루어진 두 팀이 공격과 수비를 번갈아 하는 게임이다. 하나의 이닝은 공격과 수비로 이루어져 있고, 총 N이닝 동안 게임을 진행해야 한다. 한 이닝에 3아웃이 발생하면 이닝이 종 www.acmicpc.net 엄청 어려운 문제는 아닌데 ... 딱 봐도 구현이 귀찮아보여서 풀기가 영... 그런 문제이다. 문제 .. 공감수 0 댓글수 0 2022. 1. 5.
백준 11559번 puyo puyo 풀이, 코드 (파이썬) 골드4, 구현 + 그래프 문제 코드만 궁금한 분은 깃허브 링크 눌러주세요 :) GitHub - Rhyankwon/algorithms Contribute to Rhyankwon/algorithms development by creating an account on GitHub. github.com 문제는 여기 11559번: Puyo Puyo 총 12개의 줄에 필드의 정보가 주어지며, 각 줄에는 6개의 문자가 있다. 이때 .은 빈공간이고 .이 아닌것은 각각의 색깔의 뿌요를 나타낸다. R은 빨강, G는 초록, B는 파랑, P는 보라, Y는 노랑이다. www.acmicpc.net 문제 설명 ㄱㄱ 대충 이런 문제이다. 12*6짜리 행렬의 입력이 주어지는데 Y나 R같은 문자들은 색을 나타낸다. 그리고 같은 색이 4개 이상 상하좌우로 붙어있으면 .. 공감수 0 댓글수 0 2021. 12. 18.
백준 11049 풀이/코드(파이썬), 골드3 다이나믹 프로그래밍 문제 코드만 궁금한 분은 깃허브 링크 눌러주세요! :) GitHub - Rhyankwon/algorithms Contribute to Rhyankwon/algorithms development by creating an account on GitHub. github.com 문제는 여기 11049번: 행렬 곱셈 순서 첫째 줄에 입력으로 주어진 행렬을 곱하는데 필요한 곱셈 연산의 최솟값을 출력한다. 정답은 231-1 보다 작거나 같은 자연수이다. 또한, 최악의 순서로 연산해도 연산 횟수가 231-1보다 작거나 같 www.acmicpc.net 문제 설명을 간략하게 하자면 행렬의 경우 분배 법칙..이라고 해야하나? 아무렇게나 막 곱해도 값이 똑같은 그런 규칙이 적용되지 않아서 곱셈 순서에 따라 값이 상당히 달라진다... 공감수 0 댓글수 0 2021. 12. 15.
백준 8911번 거북이 파이썬 해설/코드 (실버2, 쉬운 구현 연습 문제) 코드만 궁금한 분은 여기 링크 눌러주세요!! GitHub - Rhyankwon/algorithms Contribute to Rhyankwon/algorithms development by creating an account on GitHub. github.com 문제 읽으러가기는 아래링크 8911번: 거북이 첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스는 한 줄로 이루어져 있고, 컨트롤 프로그램이 주어진다. 프로그램은 항상 문제의 설명에 나와있는 네가지 명령으로만 이루어져 www.acmicpc.net 처음에 대충 보고, 헐... 돌아다닌 넓이를 구하라고? 라고 생각하고 미친문제라고 생각했는데 다시 문제조건을 제대로 보니, 움직인 영역을 모두 포함하는 최소 직사각형의 넓이를 구하라고 한.. 공감수 0 댓글수 0 2021. 12. 13.
백준 6987 월드컵 문제 해설(파이썬), dfs/시뮬레이션 연습 문제 해설 코드만 궁금한 분은 깃허브 링크 눌러주세요~ GitHub - Rhyankwon/algorithms Contribute to Rhyankwon/algorithms development by creating an account on GitHub. github.com 문제 설명 ㄱㄱ 문제 이해는, 거의 항상 그렇듯, 쉽다. 총 6개 팀이 리그전 느낌으로 모든 팀과 각각 승부를 겨루게 되는데, 이미 결과가 모두 나온 상태로 입력값이 주어진다. 각 6 팀의 승, 무, 패가 기록되어 총 18개의 숫자가 4줄 입력되어 매 줄마다 가능한 결과인지 불가능한 결과인지를 1, 0으로 출력하면 된다. 문제 해결 논리 모든 케이스를 해봐야한다. A팀이 B팀에 대해서 이긴/비긴/진 경우 -> A팀이 C팀에 대해서 이긴/비긴.. 공감수 1 댓글수 0 2021. 11. 20.
백준 16113 파이썬 풀이, 코드 (시뮬레이션 문제!) 코드만 궁금한 분은 깃허브 링크 눌러주세요! 개인적으로 시뮬레이션 문제들은 일반적으로 한시간정도는 구현하는데에 시간이 소요되는 것 같다. 지금도 뭐 풀만한것같아서.. 풀어봤는데 한시간 걸림..ㅡㅜ 문제 설명 문제 해결 논리 맨 윗쪽 줄의 맨 왼쪽 값부터 시작한다. 만약 현재값이 '#'이면 해당칸을 포함해서 3열 * 5행만큼의 칸이 어떤 수인지 확인한다. 만약 해당 값이 1이면 오른쪽으로 2칸만 움직이고, 그 외의 값은 3칸씩 모두 사용하므로 4칸을 옮겨서 다시 그 값이 '#'인지 확인한다. 공백이 1칸 이상이므로 만일 해당 값이 ' . ' 이면 오른쪽으로 1칸만 움직인다. 맨 마지막 혹은 그 앞쪽 열에 1이 들어가는 경우 3열 * 5행만큼의 칸이 확보되지 않으므로 그런 경우는 오른쪽 끝에 ' . '을 붙.. 공감수 0 댓글수 1 2021. 11. 8.
백준 2290 LCD Test 풀이 (파이썬) 시뮬레이션 연습하기 코드만 궁금한 분은 깃허브링크 눌러주세요~ GitHub - Rhyankwon/algorithms Contribute to Rhyankwon/algorithms development by creating an account on GitHub. github.com 문제 설명 ㄱㄱ 숫자를 입력받아 마치 LCD시계에 표시하듯 표시하면 되는 문제이다. 딱봐도 슬라이싱만 잘 활용하면 되는 문제. 문제 해결 논리 흠 논리랄게 있나? 위에 설명한대로 슬라이싱만 잘 하면 되는데, 딱 봐도 구현문제라 그냥 더럽게 푸는게 맞다. 나같은 경우는 8을 봤을때 맨위, 가운데, 맨아래의 '--'부분과 윗쪽의 좌-우 '|' 부분, 아랫쪽의 좌-우 '|' 부분 이렇게 총 7군데를 나눠서 풀었다. 숫자별로 출력 크기는 다르게될지 몰라도.. 공감수 0 댓글수 0 2021. 11. 5.
백준 12869 뮤탈리스크 풀이 (파이썬) dfs는 안되고 bfs는 되는 dp문제 코드만 궁금한 분은 깃허브 링크 눌러주세요..! 일단 나는 이 문제를 처음에 dfs로 풀었었다. 근데 아무리 해도 안돼서;(특히 25%에서 계속 안됨) 이유를 생각해봤다. 문제에서 경우의수가 너무 많은 만큼 dp로 3차원 리스트를 만들어서 이미 확인한 경우는 확인 안 하는 식으로 해서 문제를 풀어야 한다. 근데 이 때 이미 확인 안하는 것은, 이전에 확인한게 최선이라는 확답이 있는 경우에만 가능하다. 그런데 dfs로 문제를 풀면 그때까지의 계산 횟수가 얼마이든간에 우선적으로 많은 부분을 방문하게 되고, 이후에 계산 횟수가 더 적게 같은 상태에 도달할 수 있더라도 그 부분을 방문하지 않아버림으로 인해 오류가 나게 된다. dfs라도 방문/비방문 리스트가 아니라 어떤 값의 쌍까지 오는데에 걸린 계산횟수를 저장.. 공감수 0 댓글수 0 2021. 11. 3.
백준 2616 소형기관차 해설/풀이 (파이썬), 골드4 다이나믹 프로그래밍 문제 풀이 코드만 궁금한 분은 깃허브링크 눌러주세요..!! GitHub - Rhyankwon/algorithms Contribute to Rhyankwon/algorithms development by creating an account on GitHub. github.com 문제 해설 간단히, 숫자들이 입력된 리스트가 있는데 거기에서 s칸씩 연결된 부분리스트들을 3개 만들어야 한다. 이 때 3개의 부분리스트들은 서로 겹치면 안되고, 이 때 부분리스트들의 합이 최대가 되는 3쌍의 부분리스트들을 찾아서 그 합을 리턴하면 된다. 문제 해결 논리 1. 우선 전체 n개의 칸 중 s칸씩만 합할 수 있으므로, 입력된 숫자리스트에서 s칸만큼의 부분합을 저장하는 리스트를 만들고 s부터~n까지 각각 부분합을 저장해둔다. s-.. 공감수 0 댓글수 0 2021. 11. 1.
백준 16506번 CPU 풀이/코드 (파이썬) 간단한 구현문제 해설 코드만 궁금한 분은 깃허브링크 눌러주세요! 문제 설명 위 그림만 보면 뭘까? 싶지만 논리회로?공부를 해본 사람은 금방 감이 올 것 같다. 문제에서 주어지는건 어떤 새로운 언어인데, 그 언어는 opcode, rD, rA, rB로 구성돼있다. 그리고 이것들은 어떤 규칙에 따라서 이진법으로 바꿀 수 있는데 그 규칙에 따라서 10101111.. 이런식의 이진법으로 바꾸면 된다. 감이 안오면 예제를 보면 쉽다. 위에 설명보다 예제를 보는게 더 빠를때가 있다. 다만 세세한 조건은 예제만으로 알긴 힘드니 예제를 보고 다시 문제 읽는 습관을 들여야한다.,, 아무튼ㅋㅋㅋ 그냥 저냥 살짝 까다로운 구현문제라고 보면 된다. 문제 해결 논리 잘 보면 'C'가 있고 없고에 따라서 뒤에 0인지 1인지, 맨 뒤에 rB가 3자.. 공감수 0 댓글수 0 2021. 10. 31.
백준 2281번 데스노트 풀이/코드 (파이썬) 꽤 어려운 다이나믹 프로그래밍 문제 코드만 궁금한 분은 깃허브 링크 눌러주세요! 문제 설명ㄱㄱ 간단히 얘기하자면, 열의 갯수만 지정된 어떤 리스트가 있고 각 칸에 *을 넣는데 이 때 주어진 숫자만큼만 이어서 *을 넣을 수 있고 그 이후에는 한칸만 띠고 다시 *을 넣던가 혹은 다음 행으로 넘어가서 다시 *을 넣어야 한다. 이 때 각 행은 오른쪽 끝에 무조건적으로 0칸 혹은 몇개의 칸이 남게 되는데, 각 칸의 제곱의 합이 최소가 되는 경우를 찾아 그 최소값을 반환하는 문제이다. 이 때 마지막 행의 빈칸은 포함하지 않는다. 문제 해결 논리 1. 우선 dp라는 리스트를 선언하는데, 가로=열의 총 갯수, 세로=숫자의 총갯수이다. 2. n번째 숫자에 해당하는 별을 넣을 때에는 n-1번째의 별의 다음 행에 새로 시작할 수 있고, n-1째 별의 마지막에.. 공감수 2 댓글수 0 2021. 10. 30.
백준 12865 평범한 배낭 해설/코드 (파이썬) 다이나믹 프로그래밍! 문제 해결 코드만 궁금한 분은 깃허브링크 눌러주세요. 풀이가 2개니까 잘 보고 둘 다 실행 해보세요~ GitHub - Rhyankwon/algorithms Contribute to Rhyankwon/algorithms development by creating an account on GitHub. github.com 문제 설명 다이나믹 프로그래밍이란걸 배운다면 가장 처음 배우게되는 배낭 문제. 나도 사실 이 문제는 파이썬 알고리즘 인터뷰에서 봣던 문제라 크게 어렵지 않게 풀었다. 문제 해설이 총 2개인데, 나는 파이썬 알고리즘 인터뷰에서 나온 방식대로 우선 한번 풀어봤다. 문제 해결 논리 1 1. N개의 행, K+1개의 열로 구성된 행렬을 하나 만든다. 2. 1행은 첫번째 물건만 넣었을 때를 의미하고,.. 공감수 0 댓글수 0 2021. 10. 25.
백준 11058번 크리보드 파이썬 풀이/코드 (다이나믹 프로그래밍) 코드만 궁금한 분은 깃허브링크 눌러주세요! GitHub - Rhyankwon/algorithms Contribute to Rhyankwon/algorithms development by creating an account on GitHub. github.com 문제 설명 문제 해결 논리 우선 출력-선택-복사-붙여넣기 이 과정만 해도 4번은 눌러야하고 극초반에는 그렇게 해봣자 효율이 안 좋기때문에 5까지는 그냥 A를 출력하는게 최대값이다. 이 이후에는 각 값에서의 최댓값을 계산할때마다 맨 앞부터, 현재 버튼 누르는 횟수 - 3 째 까지 모두 훑으며 이전의 갯수-전체선택-복사-(남은 횟수는 모두)붙여넣기를 하면서 그중 가장 큰 값을 현재의 최댓값으로 하면 된다. -3째까지만 훑는 이유는 그렇게 해야 최소 한.. 공감수 0 댓글수 0 2021. 10. 20.
백준 12026번 BOJ거리 풀이/코드 (파이썬, 156ms) 다이나믹 프로그래밍! 코드만 궁금한 분은 깃허브링크 눌러주세요! GitHub - Rhyankwon/algorithms Contribute to Rhyankwon/algorithms development by creating an account on GitHub. github.com 문제 설명 문제 해결 논리 다이나믹 프로그래밍이 항상 그렇듯, 변수 리스트 몇개 설정하고 적당히 잘 ..섞어서 풀면 된다. 나같은 경우에는 0. 처음문자부터 끝문자까지 각각 방문하는데에 필요한 최소에너지를 저장하는 리스트를 생성한다. 1. 우선 BOJ순서대로만 점프할 수 있으므로 딕셔너리에 J->O, O->B, B->J를 호출할 수 있게 키/값으로 저장해둔다. 2. 어떤 문자를 호출하는 경우 앞쪽의 모든 경우를 다 호출해야 하므로 B, O, J각각.. 공감수 0 댓글수 1 2021. 10. 18.
백준 15486 퇴사 2 풀이/코드 (파이썬) 다이나믹 프로그래밍 코드 복사해보실 분은 깃허브링크 눌러주세요! GitHub - Rhyankwon/algorithms Contribute to Rhyankwon/algorithms development by creating an account on GitHub. github.com 문제 설명 문제 해결 논리 1. 입력받는 값의 갯수가 N개라고 할때 N번째부터 시작한다. 2. 뒤에서부터 매번의 최대값을 갱신하는데, 임의의 시점을 n이라 하고 그때 걸리는 시간을 t라고 하면 n에서의 최대값은 [n+1 값(바로 직전값)]과 [n+t 값(t시간 전의 값) + 현재값]을 비교한 최대값이다. 3. 0일째까지 2를 반복해서 0일째에 나오는 값을 출력 후 끝낸다. 간단히 얘기하자면, 만약 t번째 전 값과 현재 값을 더한 것보다 이전 값이.. 공감수 0 댓글수 0 2021. 10. 14.
백준 1495번 기타리스트 해설/코드 (파이썬) 좋은 다이나믹 프로그래밍 문제 문제 해설 코드만 궁금한 분은 깃허브링크 눌러주세요..!! GitHub - Rhyankwon/algorithms Contribute to Rhyankwon/algorithms development by creating an account on GitHub. github.com 문제 설명 문제 해결 논리 얼핏 보면 bfs문제같은데 시간초과로 bfs는 안된다. 생각해보면 계속 갯수가 2씩 곱해지고 최대 100번 반복해야하니까 최악으로는 가장 마지막 경우에 2^N개의 값을 계산해야될 수도 있다(O(2^(N^2))). 따라서 매 곡 순서마다 가능한 음량을 체크하는 리스트를 만들어서 가능한 음량을 체크하는 형식으로 계산하면 반복문을 활용, O(NM)으로 문제를 풀 수 있다. 1. 음량은 0부터 입력된 값 M까지 .. 공감수 0 댓글수 0 2021. 10. 11.
백준 15989번 1,2,3 더하기 4 해설/코드(파이썬) 다이나믹 프로그래밍 문제 풀이 코드만 궁금한 분은 깃허브링크 눌러주세요..! GitHub - Rhyankwon/algorithms Contribute to Rhyankwon/algorithms development by creating an account on GitHub. github.com 문제 설명 결국 1, 2, 3을 적당히 잘 섞어서 어떤 수를 만드는데 그게 가능한 경우의 수를 모두 찾아야 한다. 문제 해결 논리 : 1. N이라는 값이 있을 때 그 값의 가능한 경우의 갯수를 dp[N]이라고 하자. 2. 이 때 dp[N]은 dp[N-1] + dp[N-2] + dp[N-3]이다. 그 이유는 N-1째에서 1을 더하고, N-2째에서 2를 더하고, N-3째에서 3을 더하는 것 모두 N을 만족하기 때문에 세 경우의 수를 모두 더해.. 공감수 1 댓글수 0 2021. 10. 11.
백준 1890번 점프 해설/코드 (파이썬) 다이나믹 프로그래밍 문제 문제 풀이 코드만 궁금한 분은 깃허브링크 눌러주세요,,!! GitHub - Rhyankwon/algorithms Contribute to Rhyankwon/algorithms development by creating an account on GitHub. github.com 문제 설명 문제 해결 논리 어차피 값들은 아랫쪽, 오른쪽으로만 진행할 수 있다. 따라서 맨 윗 행은 왼쪽 값들에만 영향을 받고 맨 왼쪽 열은 윗쪽 값들에만 영향을 받는다. 따라서 0행부터 N행까지, 왼쪽부터 오른쪽으로 차근차근 계산해나가면 우리가 원하는 답을 얻을 수 있다. 1. 문제에서 주어진 게임판과 똑같은 크기의 0으로만 구성된 리스트 dp를 만들고 시작부분 (0,0)을 1로 표시한다. 이건 해당 요소로 갈 수 있는 경우의 수.. 공감수 0 댓글수 0 2021. 10. 11.
백준 13549번 숨바꼭질3 풀이/코드 (파이썬) 우선순위 큐를 활용한 bfs문제! 코드만 궁금한 분은 깃허브링크 눌러주세요! GitHub - Rhyankwon/algorithms Contribute to Rhyankwon/algorithms development by creating an account on GitHub. github.com 문제 설명 숨바꼭질2 문제와 많이 비슷하다. 숨바꼭질2 문제와 다른점은 이번엔 2*x의 위치로 가는 경우에는 시간추가가 되지 않고, 그리고 움직이는 경우에 따라 움직이는 횟수와 관계없이 시간에 차이가 생기게되면서 이번엔 최소의 시간..값을 찾는 프로그램을 만들어야 한다. 문제 해결 논리 1. 현재의 위치에서 +1, -1, *2만큼 한 경우 이동하는 위치와 그 때마다 지나는 시간을 큐에 저장한다. 2. 큐에서 시간이 가장 작은걸 꺼내서 다시 1번을 .. 공감수 0 댓글수 0 2021. 10. 11.
백준 12851 숨바꼭질 2 문제 풀이/해설/코드 (파이썬) 생각보다 간단한 큐, bfs 문제 코드만 궁금한 분은 깃허브링크 GitHub - Rhyankwon/algorithms Contribute to Rhyankwon/algorithms development by creating an account on GitHub. github.com 문제 설명은 스킵! 개인적으론 문제 이해는 쉬운데 풀기는 조금 까다로웠달까.. 문제 해결 논리 1. 큐에 0, 시작값 넣기. 0을 넣는 이유는 연산의 수를 기록해야하기때문. 2. 큐에서 시작값을 빼고 거기에 -1, +1, *2 한 값을 다시 큐에 넣는다. 이 때 1을 같이 넣어준다.(연산 횟수 = 0 + 1 = 1) 3. 2번을 반복하는데 이 때 힙을 사용해서 연산횟수가 작은 순서대로 꺼낸다.(우선순위 큐) 4. 이렇게 하면n번의 횟수만에 시작값에서 우리가 원.. 공감수 0 댓글수 0 2021. 10. 7.
백준 2606번 바이러스 문제 풀이/해설/코드 (파이썬) 사이클을 확인하는 문제. 코드만 궁금한 분은 깃허브링크 GitHub - Rhyankwon/algorithms Contribute to Rhyankwon/algorithms development by creating an account on GitHub. github.com 문제 해결 논리 1. 1번 컴퓨터를 방문 표시 후 2. 1번 컴퓨터에 연결된 다른 컴퓨터 모두 스택에 넣기. 3. 스택에 들어가있는 컴퓨터 하나씩 꺼내서 아직 방문 표시가 안돼있으면 다시 스택에 넣기 반복 4. 스택에 남은 값이 더이상 없는 경우 방문표시돼있는 컴퓨터의 갯수 - 1 (1번 컴퓨터는 제외)값을 출력한다. 기본적인 그래프문제. 공감수 0 댓글수 0 2021. 10. 7.
백준 16953 A -> B 풀이/코드 (파이썬) 간단한 dfs문제! 문제 코드만 궁금한 분은 깃허브링크 문제 설명 : 1. [2, 162]와 같이 임의의 두 수가 주어진다. 2. 앞의 수를 2배 하거나 앞의 수의 끝에 1을 붙일 수 있다. 가령 2는 4가 될수도 있고 21이 될 수도 있다. 3. 이 때 2번의 방식을 반복해서 앞의 수를 뒤의 수로 만들 수 있다면 몇 차례나 반복해야하는지를 출력하고, 만일 만들 수 없으면 -1을 출력한다. 문제 해결 논리: 1. 두 수를 받는다. 2. 앞의 수, 0(연산 횟수)을 dfs함수에 넣는다. 3. dfs 함수에서는 다시한번 해당 함수를 2회에 걸쳐 호출하는데(재귀함수), 한번은 입력값*2를, 다른 한번은 입력값+문자열(1)을 각각 dfs에 입력값으로 넣는다. 4. 이 때 dfs함수에 또다른 입력 값으로, 연산 횟수를 넣는다. 가령.. 공감수 0 댓글수 0 2021. 10. 6.
백준 1743번 음식물 피하기 풀이/코드 (파이썬) 기본 스택 문제 코드만 궁금한 분은 깃허브링크 문제 설명은 스킵하겠습니다. 문제 해결 논리 1. 주어진 크기만큼 (N, M)의 격자를 만들고 해당 리스트는 모두 0으로 초기화해둔다. 2. 쓰레기가 있다고 입력되어지는 행/열의 격자 부분을 1로 바꾼다. 3. 격자의 각 요소가 1인지 확인 후 만일 1이면 인접 요소중에 1이 있나 확인하고 0으로 바꾼다. 4. 인접 요소중에 더이상 1이 없으면 그때까지 1이였던 요소의 갯수를 저장한다. 5. 저장한 쓰레기 갯수 리스트에서 가장 큰 값을 출력한다. 사실 거의 비슷한 스택문제를 오늘 벌써 두개나 풀어서 이 문제를 풀까말까 고민을 많이 했다. 근데 그냥 이전 코드 살짝 바꾸고 살짝 추가하면 될것같아서 풀었다. 공감수 0 댓글수 0 2021. 10. 6.
백준 2178번 미로 탐색 풀이/코드 (파이썬) 우선순위큐/힙/스택 활용문제 코드만 궁금한 분은 깃허브링크 문제 설명은 스킵하겠습니다..! 문제 해결 논리 1. 스택에 [1, 0, 0] 넣은 후 1 -> 0 으로 표지(재방문 막기위해서). 이 때 [0, 0]은 시작점이고 1은 지금까지 지나온 노드의 갯수를 세기 위해서 저장한다. 2. 인접 요소 중 1로 표지돼있는 요소의 행/열값과 지금까지 지나온 노드의 수(이번의 경우에는 2)를 스택에 넣고 해당 요소를 1 -> 0으로 변경한다. 3. 스택을 힙으로 활용해, 지금까지 방문했던 수가 가장 작은 값을 스택에서 꺼내서 1~2번을 다시 반복한다. 가령 지금 [4,2,1]이라면, 0,0에서 2,1까지 오는데 총 4개의 요소 (예를 들자면 [0, 0], [1,0], [2,0], [2,1])를 지났다는 뜻이다. 이 문제를 우선순위 큐를 사용.. 공감수 0 댓글수 0 2021. 10. 6.
백준 1303번 전쟁 풀이/코드 (파이썬) 기본 스택 활용문제 코드만 궁금한 분은 깃허브링크 문제 설명은 스킵하겠습니다. 문제 해결 논리 1. 반복문으로 처음부터 끝 요소까지 W인지 B인지 확인 하는데, 2. 이 때 인접한 요소가 앞서 확인한 요소 (W 혹은 B)와 동일한지 확인 후 3. 만일 같으면 계속 인접 요소중에 같은 알파벳이 있는지 확인하면서 갯수 확인. 4. 값을 계산해야하니까 W리스트, B리스트를 만들어서 W인경우 B인경우의 갯수^2를 각각 저장해둔다. 5. 각 리스트의 합을 출력하면 끝 공감수 0 댓글수 0 2021. 10. 6.
백준 1260번 DFS와 BFS 풀이/코드 (파이썬) 자꾸 오류가 나는 경우 간단한 해결 방법 일단 코드만 궁금한 분은, 언제나 처럼 깃허브링크 GitHub - Rhyankwon/algorithms Contribute to Rhyankwon/algorithms development by creating an account on GitHub. github.com 정말 간단한.. 기본중의 기본탐색문제이다. 이거 못풀면 아무- 그래프 문제도 못 푼다고 보면 된다..라고 생각했는데 날 거의 3시간 가량 괴롭혔다. 하지만 여전히, 엄청 엄청 기초문제라는 사실은 변하지 않는다. 우선 어떻게 푸는지 설명 대강 하고, 마지막에 왜 내가 세시간 날려먹었나 한을.. 풀도록 하겠-다. 내가 푼 논리 (그냥 bfs dfs라 사실 논리랄것도없지만) 0. 미리 딕셔너리나 리스트에 각 노드마다 어떤 노드와 연결돼있는지 저장.. 공감수 0 댓글수 0 2021. 10. 6.
백준 2667번 단지번호붙이기 문제 해설/풀이/코드 (파이썬) 기본 스택 문제 코드만 궁금한 분은 깃허브링크 제목에 쓴것처럼 기초 스택문제이다. 주어진 이중리스트는(이하 격자) 1과 0으로 구성돼있다. 해당 격자에서 1끼리 서로 인접해있는 경우 그걸 한 덩이로 봤을때 총 몇 덩이가 있고 각각 몇개의 격자로 구성돼있는지를 알아내야하는 문제이다. 문제 풀기 1. 이중 for문으로 모든 요소에 대해서 1인지 확인. 2. 만약 1인 요소 찾으면 스택에 넣고 근처에 인접한 요소중에 1이 있는지 확인하기 2. 이 때 이미 1을 찾은 부분은 0으로 표시하고 1->0으로 바꾼 갯수를 센다. 4. 근처 인접한 요소에 더이상 1이없으면 갯수 저장하고 1번부터 반복. 기본중의 기본중의 기본 스택문제이다. 이거 못풀면 아무 스택문제도 못푼다고 보면된다. 다시 말하면 스택 기본 연습하기에 좋은 문제. 공감수 0 댓글수 0 2021. 10. 5.
백준 1038번 감소하는 수 풀이/해설/코드 (파이썬) 다소 까다로운 재귀 + 구현문제 코드만 궁금한 분은 링크 GitHub - Rhyankwon/algorithms Contribute to Rhyankwon/algorithms development by creating an account on GitHub. github.com 문제 풀이는 스킵! 우선 문제를 보면 바로 알겠지만 적당히 재귀나..브루트포스같은걸 활용하면 되겠거니 싶지만 구현이 다소 귀찮거나 어려울거라는 감이 딱 오는..문제이다. 내가 푼 방법은 두개가 있는데, 위의 풀이부터 설명하자면 1. 10의자리까지만 감소하는 수가 가능하므로 1~10의 자릿수..의 길이에 따라서 반복하는데, 2. 맨 앞자리는 아무 숫자나 와도 되고, 그 뒤부터는 앞자리보단 작은 수가 오도록 한다. 3. 자릿수가 전부 채워질 때마다 숫자를 1씩 카운트 .. 공감수 0 댓글수 0 2021. 10. 4.

728x90

문의안내

티스토리
로그인
고객센터

티스토리는 카카오에서 사랑을 담아 만듭니다.