PS - python

문제silver / 구현, 자료구조, 시뮬레이션, 큐다시 문제를 풀기 시작했다.오랜만에 이런 문제풀기 코드를 짜려니 문제를 봤을 땐 쉽네! 한 것도 잘 풀리지 않았다.역시 꾸준함이 답이라는걸 다시 한번 느낀다.흐름은 이렇다.현재 큐에 들어있는 이동할 트럭들을 1칸씩 이

문제gold 4 / 그리디 알고리즘가장 먼저 생각했던 특징은 버튼을 누르는 순서는 상관없다 라는 점이다.가령 문제에서 제시된 예제 테스트케이스를 생각했을 때, 1-3-2 순서로 스위치를 누르든 3-2-1 순서로 스위치를 누르든 상관이 없다는 얘기다.하나의 스위치 입장에

문제githubgold 3 / 그래프 이론, 그래프 탐색, 너비 우선 탐색, 비트마스킹일단 친절하게 지도 그림도 첨부되어있기도 했고, 문제 읽고나니 확실히 bfs구나 했다.이 문제에서 출력해야하는 답안은 3개이다.이 성에 있는 방의 개수가장 넓은 방의 넓이하나의 벽을

문제gold 3 / 그래프 이론, 그래프 탐색, 너비 우선 탐색문제를 읽으면 이해가 좀 안될 수도 있다.이 문제에서의 "길"은 벽과 같다고 이해해야한다.길은 보통 건널 수 있는 요소로 등장하기 때문에 좀 헷갈릴만한 것 같다.문제를 간단하게 설명하자면 농장에서 길로 나누

문제Lv. 1 / 구현어제까지만해도 없었는데 문제가 새로 업데이트 됐다.PCCP 기출문제라니 궁금하기도하고 바로 풀어봤다.특별히 필요한 알고리즘은 없는 것 같다.주어진 mm:ss형식의 시간을 모두 초 단위로 바꾼 뒤 모든 계산이 끝난 뒤 다시 정해진 포맷에 맞추는 방법

문제silver 5 / 해시python에서는 딕셔너리나 집합을 사용하여 문제를 해결할 수 있다.내 경우는 집합을 사용하였다.만약 집합에 없는 이름이라면 추가하고, 있는 이름이라면 삭제한다.물론 이 풀이는 status가 이상한 입력(출근하지 않았는데 퇴근한다든지, 출근하

문제silver 4 / 해시포켓몬을 입력받으면 names와 numbers 딕셔너리에 각각 값을 저장한다.주의해야할 점은 input받은 값에 rstrip()을 해줘야 한다는 점..그리고 포켓몬 번호가 1부터 시작한다는 점이다.이 두가지를 주의한다면 크게 어려운 점은 없다

문제silver 3 / 해시딕셔너리 line에 들어오는 학번을 key, 순서를 value로 저장한다.이렇게 저장하면 자연스럽게 중복 클릭한 학생은 뒷 순서로 밀리게된다.그러고나면 value를 기준으로 정렬을 해야한다.key를 사용하는 방법이 잘 기억이 안났었는데 분명

문제gold 5 / 다이나믹 프로그래밍, 자료 구조, 해시를 사용한 집합과 맵사실 해시에 대한 문제들을 풀고있기 때문에 당연히 해시라고 생각하고 문제를 읽었는데이거.. dp 아닌가? 하는 생각이 들었다.하지만 n, n+1, n+2 와 같이 순차적으로 저장되는 게 아니기

문제✔️ silver 2구현자료 구조문자열해시를 사용한 집합과 맵예제 입력2에서 제때 퇴장을 안찍어서 출석 날아간 나같은 느낌이 강하게 들었다..개총 시작시간s, 종료시간e, 스트리밍 종료시간q를 모두 분단위로 계산해준다.채팅 로그를 try-except를 이용해 비정상

문제✔️ silver 3수학자료 구조조합론해시를 사용한 집합과 맵이 문제에서 확인해야할 점은 해시, 조합 정도겠다.경우의 수를 조금만 생각해본다면 금방 풀 수 있다.옷 정보를 저장할 딕셔너리 closet을 생성한다.옷의 이름name과 종류category를 입력받고 cl

문제✔️ silver 3자료 구조해시를 사용한 집합과 맵걸그룹 마스터 준석이가 친구 정우에게 걸그룹 퀴즈내는 문제 ,,일단 그룹명으로도 퀴즈를 내고 멤버 이름으로도 퀴즈를 내니까 해시의 장점을 챙기기 위해서 둘 모두 각각 key로하는 딕셔너리를 만들어줘야한다.이후는 크

문제✔️ gold 4다이나믹 프로그래밍자료 구조그래프 이론그래프 탐색깊이 우선 탐색해시를 사용한 집합과 맵분명 해시 문제집을 풀고있는데 뭔가 문제를 읽어보니 DFS같았다.맞나..? 싶어서 확인해봤더니 다행히 맞았다.현재의 위치에서 최선의 선택을 하는 방식으로 작고 반복

문제✔️ silver 3자료 구조문자열해시를 사용한 집합과 맵트리를 사용한 집합과 맵정말 단순하게 접근했다.첫 문자부터 1개, 2개, 3개씩 묶어서 문자열을 일일이 체크했다.중복 없이 세기 때문에 parts를 집합으로 정의했다.바킹독 해시 문제집 마지막 문제였다.해시를

문제 silver 2 그래프 이론 그래프 탐색 문제 흐름 friends 딕셔너리에 입력받은 친구 관계를 넣어준다. 코드 마무리

문제✔️ silver 2그래프 이론그래프 탐색너비 우선 탐색깊이 우선 탐색이전에도 풀었던 문제다.방향이 없는 그래프를 입력받고 그래프의 연결 요소의 개수를 구하는 문제다.그래프에서 연결 요소란 한 그래프 안에 경로가 존재하는 노드의 집합 하나를 말한다.위와 같은 그래프

문제✔️ silver 2그래프 이론그래프 탐색너비 우선 탐색깊이 우선 탐색방향이 없는 그래프에서 DFS와 BFS 방식으로 각각 탐색한 결과를 출력하면 된다.이전에 수강한 baaaaarkingdog님의 실전 알고리즘 강의 0x18강-그래프 에서도 나왔듯이 비재귀 방식의

문제✔️ silver 3그래프 이론그래프 탐색너비 우선 탐색깊이 우선 탐색시작 노드의 역할을 하는 1번 컴퓨터를 제외하고 1번 컴퓨터가 포함된 연결 요소의 구성 노드 수를 구하면 되겠다.탐색은 내가 BFS보다 DFS에서 덜 익숙한 것 같아서 DFS를 이용했다.방문 체크

문제✔️ Lv. 2이런 알고리즘은 뭘까?감이 잘 안잡혔다.잘 모르는 사람의 눈에서는 시뮬레이션?(아직 모름) 아니면 브루트포스? 같이 느껴졌다.정말 주어진 조건에서 시키는 대로 진행되도록 했다.코드를 보다시피 조건문이 엄청 많고 체크도 굉장히 많이 한다.주석을 잔뜩 달

문제✔️ silver 1그래프 이론그래프 탐색최단 경로플로이드–워셜처음에는 그래프에서 그나마 안다고 할만한 게 BFS, DFS 뿐이라서 바로 그쪽으로 접근했다.방문 가능 여부만 체크하는 것이고 가중치도 없는 그래프이기 때문에 괜찮을 것이라고 생각했다.근데 생각할수록 비

문제✔️ gold 5그래프 이론그래프 탐색너비 우선 탐색최단 경로플로이드–워셜두가지 방법으로 풀었다.처음 보고는 그냥 모든 노드에 대해서 BFS를 통해 순회해서 점수를 계산하고 최저점수를 찾으면 되겠다 생각했는데,보다보니 최근에 새로 공부한 알고리즘인 플로이드-워셜 알

문제✔️ silver 1그래프 이론그래프 탐색너비 우선 탐색최단 경로플로이드–워셜이 문제 역시 플로이드-워셜 알고리즘을 이용해 풀었다.거리(가중치)가 1이고 방향이 없는 그래프에서 모든 노드에서 모든 노드로의 최단 거리를 구하는 식으로 진행했다.구해진 최단거리 인접행렬

문제✔️ silver 1그래프 이론그래프 탐색너비 우선 탐색깊이 우선 탐색모든 노드에서 탐색했을 경우 가장 많은 노드를 탐색할 수 있는 노드를 찾는다.BFS, DFS 모두 가능하지만 역시 BFS보다 DFS가 덜 익숙해서 DFS로 선택했다.이 회사의 컴퓨터는 신뢰하는 관

문제✔️ silver 1그래프 이론그래프 탐색너비 우선 탐색최단거리를 구하는 다른 문제들과는 달리 최장거리를 구해야하는 문제다.BFS 알고리즘을 사용해 노드를 탐색했다.큐에 노드넘버와 거리를 함께 삽입해 계산했다.거리가 max_value보다 크다면 최장거리가 갱신되어

문제✔️ gold 2그래프 이론그래프 탐색너비 우선 탐색구현 자체는 생각보다 단순하게 시작했다.최단거리를 찾는 문제이기 떄문에 BFS를 선택했고,그냥 같은 하이퍼튜브에 포함된 노드(역)을 모두 엣지로 이어주었다.생각보다 쉽게 구현됐으나 메모리 초과를 맞았다. ^^메모리

문제(gold 4그래프 이론그래프 탐색너비 우선 탐색깊이 우선 탐색이분 그래프처음에는 "두개 이상의 연결요소로 나누어질 수 있는 그래프"라고 생각했는데, 문제를 다시 잘 읽어보니 아녔다.하나의 그룹 내에서 서로 인접한 노드가 없어야하니 어떤 노드 x가 1그룹이라면 이와

문제✔️ gold 4자료 구조그래프 이론그래프 탐색분리 집합노드(사람)들 사이에 "파티"라는 연결점이 있다는 부분에서 최근에 풀었던 환승(boj_5214)의 하이퍼튜브가 생각났다. 이 문제에서도 역들을 잇는 하이퍼튜브들이 주어지는데, 이를 가상의 노드로 보고 거쳐가도록

문제✔️ gold 4그래프 이론그래프 탐색깊이 우선 탐색최단 경로플로이드–워셜문제를 풀기 위해 먼저 무게순 정렬에서 중간이 될 수 없는 구슬의 조건을 알아야한다.내가 세운 조건은 다음과 같다.어떤 구슬 X 보다 큰 구슬, 또는 작은 구슬이 전체 구슬 수의 반 이상이면

문제✔️ silver 3다이나믹 프로그래밍규칙이 주어져있고 이를 반복해서 특정 값을 구하는 흐름! => DP초기값인 1이 0이 되도록 하고, 그 뒤는 규칙들을 적용시켰을 때 최솟값을 가지도록 했다.DP와 백트래킹은 왜인지 모르겠지만 항상 헷갈린다.둘 다 빠른 시일 내에

문제silver 3다이나믹 프로그래밍DP는 초반에 점화식(?)을 어떻게 파악하고 잡느냐가 중요한 것 같다.이 문제에서는 다음과 같은 패턴을 통해 파악할 수 있다.n을 1, 2, 3의 덧셈으로 표현하고자 한다면 n을 표현할 수 있는 경우의 수는 다음과 같다.n-1의 경우

문제✔️ silver 3다이나믹 프로그래밍이 문제에서 부분 문제는 "현재 계단까지 도달하면서 얻을 수 있는 최대 점수를 구하는 것"이다.이 문제를 풀기 위해서는 두가지 경우를 비교해 더 큰 점수를 구해야한다.i-1번째 계단을 밟고 i번째 계단에 온 경우\-> i-1,

문제silver 1다이나믹 프로그래밍바로 주의해야할 점부터 얘기해보자면 두가지(또는 그 이상)의 컬러의 비용이 같다면 이 둘중 어느쪽을 선택하는지가 선택지가 또 갈리게 된다는 점이다!아래는 질문게시판에서 찾은 반례인데, 말이 이상해서 이해가 안된다면 이를 참고하면 좋을

문제✔️ silver 3다이나믹 프로그래밍이 문제의 점화식은 다음과 같이 찾았다.n=1과 n=2인 경우를 초기값으로 다음과 같이 계속 반복하여 다음 값을 구할 수 있다.직접 그려가며 찾느라 노가다를 살짝 했지만 패턴을 찾기 어려운 문제는 아니었다.

문제 ✔️ silver 3 누적 합 문제 흐름 처음에는 그냥 sum을 이용해서 풀면 안되나? 했다. 물론 M이 100,000이나 되니 메모이제이션을 하지 않으면 안되겠구나 하는 생각을 해서 아래와 같이 썼었다. memo[x] = sum(nnum[:j]) - sum(

문제 ✔️ silver 3 다이나믹 프로그래밍 그래프 이론 그래프 탐색 문제 흐름 DP를 활용해서 해결했다. memo[x]에 x를 주어진 세가지 연산을 통해 1로 나타낼 경우 최소 연산의 수를 저장했고, seq[x]에 그 과정을 저장했다. 처음에는 1 <= n <=

문제 ✔️ silver 3 다이나믹 프로그래밍 문제 흐름 fibonacci(x)가 출력하는 0, 1의 수는 정해져있다. 각 x마다 output이 정해져있고, fibonacci(x)는 fibonacci(x-1)과 fibonacci(x-2)를 호출하니 두 함수를 호출했

문제gold 5다이나믹 프로그래밍퇴사 직전 날짜 n부터 1까지 거꾸로 올라가며 계산을 진행했다.time에 상담 기간, price에 상담 수익을 저장한다.memo\[x]에 퇴사일부터 x일까지의 최대 수익을 저장했다.초기값은 memo\[n - 1]으로 마지막 날의 상담 기

문제✔️ D31부터 n까지의 합을 구하는 중간 과정에서 p와 일치하는 값이 존재한다면맨 처음에 한 층을 움직이지 않는다를 선택하면 가장 최대로 p와 겹치지 않게 이동이 가능하다.dp라고 해놓고 풀긴 했는데, 막상 풀이를 보니 dp가 아니라 단순 구현으로 생각된다.새롭게

문제✔️ D2DP 문제를 풀던 차에 본 문제라 DP로 풀 수 있겠다 생각이 든건지,우연찮게 DP 문제를 잡은건지 알 수가 없다.제출 페이지 양식을 따라 바로 작성해서 따로 함수로 구분되지는 않았지만, DP를 이용했다.번갈아가면서 a += b와 b += a를 반복해줘야

문제silver 1처음에는 memo를 1차원 배열으로 줄까지 온 경우 최대 값을 저장하도록 하려고 했는데,그 다음 줄으로 넘어가면서 윗줄의 결과까지 전부 바뀌어버리는 경우도 존재하기 때문에 어떻게 해야할지 고민했었다.그러다 GPT에게 힌트를 받고 memo를 triang

문제✔️ silver 3다이나믹 프로그래밍이전에 이번 문제인 2×n 타일링을 풀고 정리한 적이 있다.이번 문제 또한 이전의 풀이법을 참고한다면 쉽게 해결책을 찾을 수 있다.위 그림에서 알 수 있듯이 이전에는 2×2 칸을 채우는 방법이 1×2 타일을 두개 놓는 방법 뿐이

문제✔️ silver 3다이나믹 프로그래밍천천히 패턴을 적어보면 금방 알 수 있는 문제였다.이전 단계의 0으로 끝나는 수만큼 0과 1으로 끝나는 수가 생겼을 거고, 1으로 끝나는 수만큼 0으로 끝나는 수가 생겼을 것이다.따라서 0으로 끝나는 수와 1로 끝나는 수를 각각

문제✔️ D3queueN의 크기가 크지 않으므로 처음부터 순회하면서 확인하는 방식을 사용했다.정가를 계산해 넣을 queue q와 할인가를 저장할 list result를 준비한다.처음부터 i번째 원소를 탐색하며 만약 q의 가장 앞 원소와 일치한다면,현재 원소는 정가이기

문제✔️ silver 2다이나믹 프로그래밍문제는 다음과 같은 흐름을 따라 진행했다.nums에 input 수열을 입력받아 저장한다.누적합을 저장할 sum과 각 수까지의 최대 연속합을 저장할 memo를 생성한다.초기값으로 memo\[0]을 nums\[0], sum을 num

문제✔️ silver 2수학조합론백트래킹재귀갑자기 감 잃을까봐 푸는 다른 유형 (=백트래킹)문제~while문을 통해 0이 들어올 때까지 입력을 받아준다.수열은 s에 리스트의 형태로 저장한다.백트래킹 함수 bt를 호출한다. (4~lst는 경우의 수를 저장해 출력하는 용도

문제✔️ silver 2수열을 앞부터 순회하면서 i번째 수를 포함한 경우의 최대 증가 부분 수열 합을 구한다. ➡️ DPi번째 수를 포함한 경우의 최대 증가 부분 수열의 합 이라고 하니 굉장히 길고 이해가 안 될 수도 있다.내가 샘플로 계산했던 인풋은 아래와 같다.문제

문제✔️ silver 3삼각형이 처음에 어떻게 시작하는지 감만 잡으면 수월하게 풀 수 있다.삼각형은 다음과 같은 순서로 구성된다고 봤다.노란색으로 칠해진 부분, 5개의 값은 앞의 값을 이용해 구할 수 없으므로 초기값으로 설정했다.앞의 값을 이용해 같은 방법으로 다음 값

문제✔️ silver 3dp이전에 정확하게 같은 문제를 풀었던 것 같은데..! 하는 생각이 스쳐지나갔다.역시 퇴사 2문제를 풀었었다.퇴사 2 문제와 완전히 같지만 인풋 조건이 퇴사 2보다 훨씬 작다는 점에서 더 쉬운 버전이다.당시에도 어렵다고 느꼈었지만 이미 한 번 풀

문제✔️ gold 5memo\[i]\[j]를 i번째 자두가 떨어질 때 j번 이동한 경우 받은 최대 자두 수로 설정하고 규칙을 찾았다.각 memo\[i]\[j]는 memo\[i-1]\[j-1], memo\[i-1]\[j] 를 통해서 구할 수 있다.처음 자두가 위치한 나무

문제✔️ silver 2저번엔 가장 큰 증가하는 부분 수열을 풀었는데, 이번엔 "긴"이다.하지만 "증가하는 부분 수열"이라는 큰 틀은 같기 때문에 비슷한 흐름을 가져갔다.memo\[i]는 i번째 수까지의 수열에서 i번째 수가 가장 큰 증가하는 부분 수열의 최대 길이이다

문제✔️ silver 1전에 풀었던 계단 문제가 떠오르는 문제였다.memo\[i]를 i번째 잔을 마신다고 가정할 때 맛볼 수 있는 최대 포도주의 양으로 설정했다.중요한건 i가 3번째 잔이 되지 않게 해주는것인데, 이를 고려하며 생각하면 memo\[i]를 구하는 방법에는

문제✔️ silver 1경우의 수 문제는 오랜만인 느낌이었다.일단 memo는 2 x n 배열로 선언했는데, memo\[i]\[0]은 i번째 좌석에 본인이 앉는 경우 앉을 수 있는 방법의 수, memo\[i]\[1]은 본인이 앉지 않는 경우 앉을 수 있는 방법의 수로 정

문제동전을 사용해 특정 금액을 만드는 경우의 수를 구하는 문제였다.일정한 조건이 주어지고 특정 값에 대한 결과값을 찾는다는 점에서 DP를 생각해볼 수 있다.처음에는 "i번째 값의 동전의 수"를 기준으로 규칙을 찾아보고자 했다.메모의 차원도 커지고 규칙을 뭐라 특정하기

문제 silver 1memoi를 i개의 카드를 모을 때 가장 최대 금액으로 정의했을 때,0 ~ i-1의 memo를 가지고 memoi를 구할 수 있다.i개의 카드를 모을 때 경우의 수는 다음과 같다.i개 카드팩 금액1개 카드팩 금액 + (i-1)개 카드를 모으는 최대 금

문제✔️ silver 31x2 타일이었나 이런 문제를 전에 마주친 기억이 난다.아무래도 이 문제가 그 문제보다 쉬울 것 같다.경우의 수이기 때문에 dp 접근을 생각해볼 수 있다.앞서 몇가지 패턴을 살펴봐보자.memo\[i]를 현재 타일으로 i 자릿수의 2진수를 만들 수

문제✔️ gold 5문제를 읽고 또 비슷한 생각에 빠졌다. 경우의 수? dp아니야? 했는데,경우의 수를 구하는 게 아니라, 모든 케이스를 출력해야하는 점에서 백트래킹이 더 적합하겠다는 생각이 들었다.또한 앞의 케이스를 이용해서 뒤 케이스를 구할 수 있지만, 단순 계산으

문제✔️ silver 3정렬문제의 정렬에는 세가지 기준이 있다.길이가 짧을 경우 앞 순서로 정렬한다.포함된 숫자의 합이 작은 경우 앞 순서로 정렬한다.위 두 경우가 일치할 경우 사전순 정렬을 따른다.물론 python에는 정렬을 위한 내장 함수가 있고, 이의 정렬 기준을

문제(https&#x3A;//school.programmers.co.kr/learn/courses/30/lessons/42862?language=python3GreedyGreedy 문제임을 알고 시작하니 확실히 푸는게 수월했다.문제 유형을 알고 풀면 그 유형을 파악하며

gold 4 / 1922: 네트워크 연결최소 비용으로 모든 노드를 연결시키는 문제로 MST 문제라고 할 수 있다.만약 노드의 수만 주어지고 어떤 두 노드든 연결시킬 수 있었다면,잠정적으로 nC2 = (n \* (n-1)) / 2 개의 간선이 생길 수 있으므로Prim

gold 3 / boj-16954: 움직이는 미로 탈출2가지 함수를 통해 구현했다.grid를 입력받아 벽을 한칸씩 아래로 밀어 변환하는 함수다.grid와 q를 입력받아 현재 들어있는 큐에 대해서 아래의 작업을 한 뒤,다음 반복문 실행 여부 플래그인 next와 다음 q에

gold 3 / boj-4386: 별자리 만들기모든 별(노드)를 연결할 때 최소 비용을 구하는 문제이므로 MST를 적용할 수 있다.두개의 별을 연결하는 데는 두 별 사이의 거리 만큼의 비용이 소모되고,미리 연결된 별은 없으며,모든 별이 이어질 수 있는 잠재 간선으로 연

gold 3 / 11812: K진 트리두 노드 사이의 거리를 구하려면 두 노드의 가장 가까운 조상까지의 각 거리의 합을 구하면 되겠다.따라서 LCA 알고리즘을 적용시켜야한다.먼저 문제에서 설명한 K진 트리의 특성에 대해 이해해야한다.1 ≤ N ≤ 10^15 이고, 1