python알고리즘

문제: 1로 만들기 이 문제는 두 번째로 풀어보는 문제다. 처음 풀어볼때는 dp의 개념을 제대로 이해하지 못해서 어려웠는데, 두 번째는 훨씬 수월했다. 입력과 출력은 위에 링크를 통해 확인할 수 있다. 이 문제의 연산하는 방법은 총 세가지이다. X가 3으로 나누어

문제: 만취한 상범 요즘 백준 알고리즘의 dp문제집을 풀고있다. 이 문제는 내용이 재밌었다. 만든 사람 천재인 것 같다. 이번 문제는 공책에 n=1일때부터 n=4일때까지 시뮬레이션을 해본 후 규칙을 찾았다. 수의 약수와 관련된 문제였다. 예를 들어 n=10일 때 1

문제 : 1,2,3더하기이 문제는 흔하게 볼 수 있는 dp문제이다.처음에 이렇게 풀었더니 런타임 에러가 떴다. 1부터 n까지 모두 구하는 것이 에러의 원인이였다.재귀를 이용하는 방식으로 해결해줬다.

문제 링크: 계단오르기처음 dp알고리즘을 배울 때 접했던 유형이 계단오르기였다. dp문제의 기본 문제라고 생각한다. 기본문제와 차이점은 한칸씩 밟는 것은 세 번 연속으로 할 수 없다는 점이다.처음에는 stair와 dp배열의 크기를 n으로 뒀는데 런타임 에러가 떴다. 그

문제링크 : 기타리스트이 문제는 이중배열을 사용해서 풀었다. 맞왜틀!!만 외쳤던 문제다. 알고보니 쉼표를 괄호로 적었던 것이였다,,,,노래의 순서와 음 하나씩을 배열로 주었다. 배열에 1이 표시되어 있으면 해당음은 가능하다는 뜻이다.범위를 잘 측정하여 연주가능한 음에

문제링크 : 환승삼성 sw역량테스트를 대비하기 위해 기출문제 풀기를 시작했다.너무 어려웠다..그래서 고민하다가 다른 블로그를 참고하여 풀었다.우선 bfs를 사용해야 한다는 것은 알았지만 hyper와 station 배열을 어떻게 구상해야 하는지 어려웠던 것 같다.다른 블

문제 링크 : 달이 차오른다,가자문제의 스토리가 장황에서 처음 읽을 때는 이해되지 않았다. 자세히 읽어보니 미로문제였다. 다른 문제와 다른 점을 알파벳 키를 가질 수 있다는 것이다.키를 판별해주는 과정이 너무 어려웠다. 그래서 다른 분의 블로그를 참고했다.이 분은 이진

문제링크 : 구슬탈출달이 차오른다 문제와 비슷하지만 조건이 더 까다로운 문제다.구현하는게 복잡한 문제이다. 파란공이 먼저 구멍에 들어가는 경우, 파란공과 빨간공이 겹치는 경우 등을 따져줘야한다. 처음에 왜 방문했던 경로를 visited 배열로 쌓을까 생각했었는데 한칸씩

문제 링크 : 컨테이너 벨트 위의 로봇구현 문제인데 문제이해가 조금 어려웠다. 문제 설명 그대로 구현하면 되는 문제였다.벨트가 각 칸 위에 있는 로봇과 함께 한 칸 회전한다.가장 먼저 벨트에 올라간 로봇부터, 벨트가 회전하는 방향으로 한 칸 이동할 수 있다면 이동한다.

문제링크 : 톱니바퀴(2)재밌는 구현문제이다. 그림그리면 문제를 이해하기 용이하다.deque의 rotate를 쓰는 것이 이 문제풀이의 핵심인 것 같다. 다른 언어에서도 가능한지 모르겠지만 python은 이런것이 편리하다.회전시키는 톱니바퀴를 기준으로 왼쪽에 있는 톱니바

문제 링크 : 배열돌리기3

문제링크 : k번째 최단경로 찾기최단경로 문제=>대부분 다익스트라다익스트라 문제는 여러 문제를 접하면서 패턴을 익히는 게 중요한 것 같다.dpi에 k개의 공간을 만들어 값을 넣고 정렬한 후 마지막 값=1부터 i까지 k번째 최단 경로이것만 명심하면 다른 다익스트라 문제와

문제링크 : 최소비용 구하기2최소비용구하기=>다익스트라이 문제의 경우 경로까지 출력을 해야해서 path라는 배열을 만들어서 경로를 저장하는게 포인트다!저장된 경로의 비용보다 더 작은 비용이 나타나면 path를 리셋하고 새로운 경로를 저장한다.

문제링크 : 면접보는 승범이네 모든 면접장을 heap에 넣어주고 가장 가까운 거리를 찾는다. 모든 지원자의 최소거리 중에 가장 먼 지원자를 찾아서 출력한다.

문제링크 : 플로이드단순히 최소비용을 구하는 문제인줄 알았는데 플로이드-와샬이라는 알고리즘을 사용하는 문제였다.플로이드-와샬에 대해서는 처음 접하게되었다.플로이드-와샬 알고리즘은 하나의 정점에서 모든 정점으로의 최단거리를 구하는 알고리즘이다.i부터 j까지 가는 방법에서

문제링크 : 스택 간단한 스택을 구현하는 문제이다. 배열의 명령어를 사용해서 풀어줬다.

문제링크 : 이항계수 1이항계수이항식을 이항정리로 전개했을 때 각 항의 계수이항계수 점화식nCk = n!/k!(n-k)!math를 사용해서 쉽게 factorial함수를 사용했다.

문제 링크 : 가장 긴 바이토닉 부분 수열증가하는 부분과 감소하는 부분을 각각 계산해서 더해주었다.

문제 링크 : 늑대와 양울타리를 최소로 설치해야하는 줄 알았는데 그런 제약이 없었다. 그래서 .을 만났을 경우 모두 울타리로 바꿔주었다.늑대일때상하좌우에 양이 있는지 확인, 있으면 0출력양일때continue.일때울타리 설치하기

문제 링크 : 지뢰찾기어려워서 다른분의 코드를 참고했다.최대갯수를 찾아야하기 때문에 숫자와 인접한 그리고 숫자는 int처리 하는 것 까지는 했는데 그 이후의 알고리즘을 풀지 못했다.dfs함수 안에 있는 else가 이해되지 않았다.위치가 이상하다고 생각했다. 무엇에 대한

문제링크 : 구간 합골드에서 쉬운 문제를 발견하면 항상 런타임 에러가 뜬다. 골드문제인 이유가 있었다. 처음 문제를 보고 단순 구현으로 푼 코드는 아래와 같다. 풀면서도 런타임 에러가 뜰 것 같았다.그래서 찾아보니 세그먼트 트리를 사용해서 푸는 문제였다. 세그먼트 트리

문제링크 : 전자레인지몇일 전 코딩테스트에서 그리디 문제를 틀려서 한동안 그리디 문제만 익힐 예정이다.기초인 브론즈레벨 문제부터 차근히 풀어나갈 예정이다.이번문제는 브론즈6레벨의 문제였다. 최소횟수를 찾기위해 제일 큰 단위부터 계산했다.

문제링크 : 편의점 2이번 문제는 실버2레벨 문제다.풀어보니 그리디 문제는 아닌것같다.거리의 평균이 최소가 되려면 위치를 정렬해 그 중간값을 선택해야 한다는 것만 이용하면 되는 문제다.

문제링크 : 신입사원처음에는 이중 for문을 써서 비교를 해줬더니 시간초과가 났다.그래서 for문을 하나만 쓰는 방법을 고민하며 풀어줬다.이 문제의 포인트는 두가지 항목 모두가 나보다 높은 사람이 있으면 뽑힐 수 없다는 것이다.우선 서류를 기준으로 정렬해줬다.서류 1위

문제링크 : 통나무 건너뛰기

문제링크 : A->B

업로드중..문제링크 : 배

업로드중..문제링크 : 크게만들기

문제링크 : 카드 정렬하기

문제링크 : 보석도둑최대한 비싼 보석을 훔치는 방법을 찾는 문제이다.heapq는 자동으로 정렬이 되는 효과가 있기 때문에 정렬이 시간초과가 날 경우 유용하게 사용할 수 있다.heap은 작은 값이 부모노드로 큰 값이 자식노드로 들어간다.heappop을 사용할 경우 roo

문제링크:저울이 문제는 코드는 간단하지만 논리를 이해하는데 시간이 오래걸렸습니다. 핵심논리는 현재 가지고 있는 추로 만들 수 있는 무게가 1, 3, 5, 7, 8 이라면 x무게의 추가 추가됐을 때 1+x, 3+x, 5+x, 7+x, 8+x의 무게를 더 만들 수 있다는

그리디 알고리즘각 단계에서 가장 최선의 선택을 하는 방법탐욕 알고리즘을 적용시키려면 두가지 조건을 만족해야 한다.1-앞의 선택이 이후의 선택에 영향을 주지 않아야 한다.2-문제의 최적해가 부분 문제에 대해서도 최적해여야 한다.<문제 설명>사람들은 자기보다 큰 사람

<코드>

<문제>콜라 빈 병 a개를 가져다주면 콜라 b병을 주는 마트가 있다. 빈 병 n개를 가져다주면 몇 병을 받을 수 있는가?<코드>

<문제>강철부대가 위치한 지역을 포함한 총지역의 수 n, 두 지역을 왕복할 수 있는 길 정보를 담은 2차원 정수 배열 roads, 각 부대원이 위치한 서로 다른 지역들을 나타내는 정수 배열 sources, 강철부대의 지역 destination이 주어졌을 때, 주어

<문제>롤케이크에 올려진 토핑들의 번호를 저장한 정수 배열 topping이 매개변수로 주어질 때, 롤케이크를 공평하게 자르는 방법의 수를 return 하도록 solution 함수를 완성해주세요.<코드><풀이>counter와 dictionary의 개념을

<문제>원형 수열의 모든 원소 elements가 순서대로 주어질 때, 원형 수열의 연속 부분 수열 합으로 만들 수 있는 수의 개수를 return 하도록 solution 함수를 완성해주세요.elements result7,9,1,1,4 18<코드><

<문제>길이가 같은 두 개의 큐가 주어집니다. 하나의 큐를 골라 원소를 추출(pop)하고, 추출된 원소를 다른 큐에 집어넣는(insert) 작업을 통해 각 큐의 원소 합이 같도록 만들려고 합니다. 이때 필요한 작업의 최소 횟수를 구하고자 합니다. 한 번의 pop과

<문제>건물의 내구도를 나타내는 2차원 정수 배열 board와 적의 공격 혹은 아군의 회복 스킬을 나타내는 2차원 정수 배열 skill이 매개변수로 주어집니다. 적의 공격 혹은 아군의 회복 스킬이 모두 끝난 뒤 파괴되지 않은 건물의 개수를 return하는 solu

<문제>정수 n, left, right가 주어집니다. 다음 과정을 거쳐서 1차원 배열을 만들고자 합니다.n행 n열 크기의 비어있는 2차원 배열을 만듭니다.i = 1, 2, 3, ..., n에 대해서, 다음 과정을 반복합니다.1행 1열부터 i행 i열까지의 영역 내의

<문제>Ax + By + C = 0으로 표현할 수 있는 n개의 직선이 주어질 때, 이 직선의 교점 중 정수 좌표에 별을 그리려 합니다.별이 그려진 부분은 , 빈 공간(격자선이 교차하는 지점)은 .으로 표현하면 다음과 같습니다."..........."".......

<문제>n개의 송전탑이 전선을 통해 하나의 트리 형태로 연결되어 있습니다. 당신은 이 전선들 중 하나를 끊어서 현재의 전력망 네트워크를 2개로 분할하려고 합니다. 이때, 두 전력망이 갖게 되는 송전탑의 개수를 최대한 비슷하게 맞추고자 합니다.송전탑의 개수 n, 그

<문제>각 칸마다 S, L, 또는 R가 써져 있는 격자가 있습니다. 당신은 이 격자에서 빛을 쏘고자 합니다. 이 격자의 각 칸에는 다음과 같은 특이한 성질이 있습니다.빛이 "S"가 써진 칸에 도달한 경우, 직진합니다.빛이 "L"이 써진 칸에 도달한 경우, 좌회전을

<문제>사전에 알파벳 모음 'A', 'E', 'I', 'O', 'U'만을 사용하여 만들 수 있는, 길이 5 이하의 모든 단어가 수록되어 있습니다. 사전에서 첫 번째 단어는 "A"이고, 그다음은 "AA"이며, 마지막 단어는 "UUUUU"입니다.단어 하나 word가

<문제>처음 표의 행 개수를 나타내는 정수 n, 처음에 선택된 행의 위치를 나타내는 정수 k, 수행한 명령어들이 담긴 문자열 배열 cmd가 매개변수로 주어질 때, 모든 명령어를 수행한 후 표의 상태와 처음 주어진 표의 상태를 비교하여 삭제되지 않은 행은 O, 삭제

<문제>5개의 대기실을 본 죠르디는 각 대기실에서 응시자들이 거리두기를 잘 기키고 있는지 알고 싶어졌습니다. 자리에 앉아있는 응시자들의 정보와 대기실 구조를 대기실별로 담은 2차원 문자열 배열 places가 매개변수로 주어집니다. 각 대기실별로 거리두기를 지키고