[코딩테스트] 백준[골드4]

풀었다고 생각했는데 여러 코너 케이스에 의해서 계속 WA를 받았다. 코너 케이스에 대해서 분석해봤더니 내가 어디 부분에서 틀렸는지 알 수 있었다. 수의 위치가 다르면 값이 같아도 다른 수이다.입력20 1출력0①. 배열에 들어있는 수 중에서 0을 만들 수 있는 방법 →

BFS 탐색 알고리즘을 사용해서 문제를 해결했다.Python3로 제출했더니 시간초과(TLE)가 나와서 PyPy3로 제출했더니 AC를 받았다. 시간초과를 해결하는 방법은 잘 모르겠다...💡문제접근

평소에 풀었던 BFS 탐색 알고리즘과는 다른 문제였다. 일반적으로 풀었던 문제는 대개 한 번의 BFS 탐색을 수행하는 문제였는데 이 문제는 달랐다. 불이 번져나가는 탐색과 상근이가 빌딩에서 탈출하는 탐색 총 두 번의 과정을 수행해줘야한다.큐가 비어있을때까지 수행했다가

💡문제접근 > * 음수 리스트와 양수 리스트를 따로 만들어서 해결했다. > * 음수 리스트는 오름차순으로 정렬하고 양수 리스트는 내림차순으로 정렬했다. python import sys input = sys.stdin.readline N = int(input()) m

고슴도치가 이동할 수 있는 경우를 나타내는 BFS 함수와 물이 넘칠 수 있는 경우를 나타내는 BFS 함수 두 개를 작성해서 문제를 해결했다.다른 사람의 코드를 보지 않고 혼자서 해결하는 그 시간이 정말 고통스럽고 지옥같았다. 하지만 어떻게 풀어야할지 미리 생각해보고 코

최대공약수에 대한 부분을 다루는 문제였다.마지막에서 1을 제거한 다음에 답을 출력하는 방향으로 코드를 적었는데 remove는 답이 될 수 없고 discard()는 답이 될 수 있다고 하여 이 부분이 이해가 잘 안가서 추가적으로 공부했다.Python에서 사용할 수 있는

heap 자료구조를 이용하면 간단히 해결할 수 있다. 자료구조를 활용할 수 있다면 적극적으로 활용해서 문제를 해결하려고 시도해보자.💡소요시간 : 10m

브루트포스 알고리즘이 아니라 BFS 알고리즘을 이용해야한다는 것을 뒤늦게 깨달았다. 연산으로 가능한 경우들을 모두 찾아서 시도해보는 방법을 이용했고 방문한 값의 경우 True로 바꿔주어 방문하지 않은 값의 경우 조건문이 실행되도록 코드를 작성했다. 질문게시판에 있는 접

치즈가 있는 부분 c가 공기와 접촉된 칸이 단 한 칸이라도 존재한다면 녹아없어지므로 0으로 바꿔준다.이중 for문을 돌려 남아있는 치즈의 개수를 저장하도록 코드를 작성한 다음 치즈가 모두 녹기 한 시간 전에 남아있는 치즈조각의 개수 즉, cheese_li\[-2]도 출

힙(heap) 자료 구조를 이용해서 가장 작은 값을 두 개 반환해서 더하여 비용을 구해준 다음 다시 힙에 넣어 과정을 반복한다.💡소요시간 : 10m

3개 이상의 수의 최소공배수를 구할 때에는 두 개씩 수를 묶어서 최소공배수를 구하면 된다.LCM(a, b, c) >> LCM(LCM(a, b), c)이 성립한다.유클리드 호제법을 이용해서 직접적으로 최대공약수를 구할 수 있고 이 때 두 수의 곱을 최대공약수로 나눈 몫이

일반적인 소인수분해 과정을 코드로 작성했으나 시간초과(TLE)가 발생했다.에라토스테네스의 체를 이용해서 소수를 걸러준 다음 소수로 나눠 소인수 분해를 해준다.참, 거짓을 이용하는 에라토스테네스의 체 방법도 있지만 숫자를 넣어 에라토스테네스의 체 방법을 사용할 수 있는

문자열을 스택에 입력함녀서 만약 스택의 마지막 원소가 폭발 문자열의 마지막 문자와 같은지 확인하고 폭발 문자열의 길이만큼 슬라이싱하였을때, 만약 폭발 문자열과 일치한다면 pop을 통해서 폭발 문자열을 반환한다.💡소요시간 : 27m

요즘 들어 문제를 제대로 읽지 않아서 WA를 받는 일이 잦아지는 것 같다.바로 키보드에 손을 대지 말고 문제를 손으로 적어 부족함없이 이해한 다음 천천히 코드를 작성하는 습관을 길들이자.전화번호 목록이 일관성을 유지하려면, 한 번호가 다른 번호의 접두어인 경우가 없어

💡소요시간 : 34m

💡소요시간 : 2h

잃는 비용이 최소가 되게끔 이동해야한다. 따라서 이 부분의 조건문으로 잘 작성해야한다.💡소요시간 : 27m

이전에 포스팅했던 \[백준 11053번 가장 긴 증가하는 부분 수열]과 \[백준 가장 큰 증가하는 부분 수열] 문제를 이미 경험해봐서 그런지 접근하는 부분에 있어서는 엄청 헤매지 않았던 것 같다. 다이나믹 프로그래밍에 대한 문제를 더 풀어보면서 감을 익히고 그 개념이

간단한 소수 판정 문제라고 생각하고 무리없이 코드를 작성하고 제출했는데 25%에서 WA를 받았다.코드에 어떤 문제가 있는지 보아하니 중복을 고려하지 않았고 숫자의 맨 앞자리가 0인 경우를 제대로 체크하지못했다. 중복을 제거하기 위해서 set을 이용해 중복을 제거해주었고

알고리즘 분류에는 깊이 우선 탐색이 나와 있었는데 나는 이 방법보다는 너비 우선 탐색이 더 수월하다고 판단하여 BFS를 이용해서 코드를 작성했다. 큐로 구현해보면 시간초과(TLE)가 발생하는데 집합으로 구현해보면 시간초과가 발생하지 않는다.자료구조에 대한 시간복잡도를

배낭 문제 형태의 동적 프로그래밍 문제였다. 다만 다른 배낭 문제와의 차이점이 있었다.일반적인 배낭 문제의 경우 배낭에 들어갈 수 있는 물건의 개수를 최대 1개로 조건을 걸어두는데 이 문제는 각 사탕의 개수가 매우 많아 원하는 만큼의 사탕을 넣을 수 있다는 것이 조건이

N이 홀수인 경우 2 X 1, 1 X 2 크기의 타일로 빈틈없이 채우는 경우는 불가능하다. 따라서 N이 홀수인 경우 나올 수 있는 모든 경우의 수는 0이 된다. 질문 게시판에 있는 테스트케이스와내가 직접 계산한 경우의 수를 비교해서 문제를 해결했다.💡문제접근

테스트케이스를 바탕으로 어떤 방식으로 코드를 작성해야할지 고민한 다음 코드로 옮겼다.stack 스택을 사용해서 오큰수 조건에 맞도록 작성하면 된다.💡소요시간 : 44m

어떤 결과를 요구하는지 알고는 있었지만 이걸 코드로 옮기는 과정의 시작부터 막막해서 결국 어떤 방식으로 접근을 할 수 있는지 구글링을 해보았다.(코드는 보지 않음)ㅗ, ㅜ, ㅏ, ㅓ 모양의 블록은 DFS를 이용해서 탐색을 해야하고 그 외 모양의 블록들을 DFS를 이용하

각각의 경우에 대해서 나올 수 있는 결과들을 미리 적어서 확인한 후에 코드를 작성했다.만약 문자열 A와 문자열 B가 일치하지 않는다면? → 어떤 변화를 주어도 해결할 수 없음(-1)만약 문자열의 길이가 1 & 문자열 A와 문자열 B가 일치하면? → 0만약 문자열의 길이

문자열의 양끝에서 적합한 연산을 통해서 사전순으로 가장 앞선 문자열을 출력하는 문제였다.양끝에서 적합한 연산을 수행하기 위해서는 투 포인터로 문제를 접근해야했다.만약 왼쪽 포인터가 가리키는 문자가 오른쪽 포인터가 가리키는 문자보다 사전 순으로 앞선다면? → 왼쪽 문자를

처음에는 무작위로 모든 경우를 탐색하는 무식한 방법만 떠올라서 어떻게 풀어야할지 고민이 많았다. 근데 최댓값을 출력하려면 결국 두 단어의 길이를 비교해서 각각의 자릿수를 매겨주면 큰 값이 할당된 문자부터 큰 숫자를 부여해주면 되겠다고 생각하여 딕셔너리와 람다 정렬을 적

전체적인 로직을 이해하는데에 성공했다. 불의 이동과 지훈이의 이동으 둘 다 고려를 해줘야한다는 것을 고려했고 각각의 경우에 대해서 탐색을 진행하는 방식으로 코드를 작성했다.💡소요시간 : 2h

에라토스테네스의 체를 이용한 소수 판정 알고리즘과 BFS 완전 탐색을 이용한 문제였다.로직은 떠올렸으나 코드로 옮기는 과정에서 시간이 소요됐던 문제였다. 꾸준한 연습이 필요해보인다.💡소요시간 : 37m

BFS 탐색을 이용해 해결할 수 있는 문제였다.💡소요시간 : 40m

누적 합 + 투 포인터의 개념을 이용하는 문제였다.수열의 길이가 10 ≤ N < 100,000이라는 점을 활용해 길이가 N인 수열 이후 나머지 부분을 0으로 채워넣어 IndexError가 나오는 것을 방지할 수 있었다.💡소요시간 : 7m

이분 탐색 + 투 포인터를 이용한 문제였다. 일단 이분 탐색을 수행하려면 정렬이 수행된 상태여야 한다는 뜻이므로 오름차순 정렬을 수행한 다음 bisect 라이브러리의 bisect_left, bisect_right를 사용해서 문제를 해결할 수 있다. 접근을 설명하면 아래

버블 정렬을 최적화하는 방법을 고민하는 문제배열의 길이가 n이라면 일반적으로 (n-1)회의 패스가 수행된다.이 때, 인접한 배열 원소 간의 Swap과정이 이루어지는데 Swap과정이 끝까지 돌지 않더라도 중간에 배열이 일치하는 경우가 발생하면 그 즉시 정렬을 멈추고 결과

선택 정렬의 시간복잡도는 O(N^2)배열의 길이 N의 값이 큰 수가 나오면 시간초과를 피할 수가 없다.찾아보니 딕셔너리로 선택 정렬을 구현한 코드가 있어 해당 코드를 참고하고 직접 테스트케이스를 만들어 이해했다.💡소요시간 : 1h 21m

💡소요시간 : 10m

플로이드-워셜 알고리즘 기초 문제💡소요시간 : 42m

데이크스트라 알고리즘 기초 문제💡소요시간 : 50m

플로이드-워셜 알고리즘의 시간복잡도는 O(N^3)Python3로는 시간초과, PyPy3로는 AC두 마을을 왕복하는 경우도 사이클에 포함됨에 주의한다. → 자기 자신에서 자기 자신으로 이동하는 경우를 0으로 계산하지 않는다.💡소요시간 : 27m

개선된 다익스트라 알고리즘을 변형한 문제라 고민을 많이 했던 다익스트라 알고리즘 응용문제1 → N으로 이동할 때 주어진 두 정점을 반드시 거치면서 최단 경로로 이동하는 경우는 2가지가 존재한다.①. 1 → V1 → V2 → N②. 1 → V2 → V1 → N처음에 코드

문제 그대로 구현하는 과정에서 IndexError가 자주 발생했던 문제💡소요시간 : 27m

플로이드-워셜 알고리즘을 이용해서 문제를 해결💡소요시간 : 37m

최소 스패닝 트리(MST)문제 - Minimum Spanning Tree최소 스패닝 트리란, 스패닝 트리 중에서도 사용된 간선들의 가중치의 합이 최소가 되는 트리각 간선의 가중치가 동일하지 않다고 가정할 때 단순히 가장 작은 간선만 사용했다고 해서 최소 비용이 얻어지는

최소 스패닝 트리 문제크루스칼 알고리즘을 이용해서 문제를 해결💡소요시간 : 21m

마을을 두 개로 분할하고 나머지 길의 유지비의 합을 최소로 하려면 선택된 간선들을 오름차순으로 정렬하고 간선의 가중치가 가장 높은 값을 제거해야한다.💡소요시간 : 34m

길의 가로등을 켜 두면 하루에 길이 미터 수만큼의 돈이 들어간다. 일부를 소등하여 그만큼의 돈을 절약할 수 있다.절약할 수 있는 최대 비용을 구하라는 것은 결국 최소 신장 트리에 포함되지 않는 간선의 가중치의 합을 구하라는 문제와 동일하다.💡소요시간 : 48m

크루스칼 알고리즘으로 문제를 해결💡소요시간 : 24m

가중치 C가 양수가 아닌 경우도 존재하므로 벨만-포드 알고리즘을 이용해서 최단 경로를 구할 수 있다.💡소요시간 : 24m

어떤 방법으로 플로이드-워셜 알고리즘을 적용해서 풀어야할지 고민을 많이 했다.입력6 61 53 45 44 24 65 2출력1위의 테스트케이스를 플로이드-워셜 알고리즘을 사용해 키의 관계를 2차원 리스트로 표현하면 다음과 같다.A → B의 관계로 표시할 수 있는데 편의상

A → B의 관계를 A가 B보다 무겁다로 표현할 수 있다고 가정하자.graph\[a]\[b]의 값이 True인 경우 a가 b보다 무겁다고 할 수 있다. 입력5 42 14 35 14 2출력2(5, 4), (2, 1), (5, 1)로 추론하면 5번은 4번보다 무겁고 2번은

크루스칼 알고리즘을 이용해서 문제를 해결모든 도시가 연결이 안 된 경우를 구현하는 부분에서 조금 시간이 소요됨💡소요시간 : 41m

플로이드-워셜 알고리즘i에서 j로의 관계가 False, j에서 i로의 관계가 False인 경우 두 물건을 비교할 수 없다.💡소요시간 : 24m

a → b : 컴퓨터 a가 컴퓨터 b를 의존한다.컴퓨터 b가 감염되면 s초 후에 컴퓨터 a가 감염되는 것이므로 graph\[b].apped(\[a, s])로 코드를 작성해야한다.위의 의존성 개념에 대해서 이해를 하는데 시간이 조금 걸렸다.💡소요시간 : 47m

문제 그대로를 푸는 과정에서 이중 for문에 의한 시간복잡도인 O(N^2)때문인지 시간초과가 나왔고 계속 풀어도 도저히 답을 찾지 못해 구글링을 했는데 쉽사리 이해가 가지 않았다.누적 인구수의 절반을 넘어서는 시점에 마을에 우체국을 설치해야한다.는 이 조건을 문제에서

\[백준 1339번 단어 수학] 문제와 유사한 형태의 그리디 알고리즘 문제다.하지만 그 문제와 다른 점이 있다. 이 문제에서는 0으로 시작하는 숫자는 존재하지 않는다는 것이다.맨 처음 알파벳에 대응하는 값이 0이 나오는지를 확인하기 위해서 first 배열을 만들어 맨

동생의 지점으로 이동할 때 걸리는 최단 시간, 그리고 그 최단 시간으로 찾는 방법이 몇 가지인지를 모두 구하는 문제다.visited 배열을 만들어 방문 여부를 따지고 만약 동생의 위치 K에 더 빠른 시간에 도달할 수 있는 경우가 있다면 해당 경우도 고려해준다.💡소요시

N에서 K로 가는 최단 시간과 해당 경로를 출력해야 하는 문제다.이전 지점이 어디인지를 저장하는 배열을 만들어 같이 출력한다.💡소요시간 : 42m

처음에는 DFS를 이용해서 가장 깊은 노드를 탐색해 가장 최댓값이 나오는 노드를 하나 고르고 해당 노드에서부터 다시 DFS를 이용해서 가장 깊은 노드를 찾아 나오는 값이 트리의 지름이라고 생각해서 구현했는데 구현 과정에서 조금 애를 먹어 BFS로 방향을 바꿔 접근했다.

투 포인터를 이용한 방법도 아니었고 이걸 어떻게 풀어야 하는지 정말 오랫동안 고민했는데 쉽사리 해결방법이 떠오르지 않았다. 질문게시판에 있는 힌트를 참고했다.각 누적합에 대한 개수를 저장하고 현재 수가 M일 때, -M의 개수를 세면 된다는 방법을 알려준 글을 보고 딕셔

국경선을 공유하는 두 나라의 인구 차이 조건 참/거짓 여부를 판별하고 연합을 이룰 수 있는 조건이 형성된다면 union 배열에 저장하고 리턴한 union 배열 원소의 개수가 최소 2개 이상이라면 인구 이동을 시켜주면 된다.인구 이동이 며칠동안 발생하는지를 확인하기 위해