백준[실버2]

DFS와 BFS 알고리즘을 공부할 수 있는 가장 기본적인 문제였다.BFS는 큐를 이용해서 DFS는 재귀 개념을 이용한다.💡소요시간 : 15m

배추가 심어져 있는 땅 1에 방문하면 상하좌우 네 방향의 위치에 있는 좌표를 0으로 만든 다음 배추흰지렁이의 개체 수를 1만큼 증가시킨다. 모든 좌표가 0으로 바뀔때까지 BFS를 반복한다.💡소요시간 : 30m

1 ~ N까지의 수들로 이루어진 수열과 스택 수열을 비교하여 만들 수 있으면 그 과정을 출력하고 만들 수 없다면 NO를 출력하는 방식을 택했지만 그 과정이 너무나 복잡하여 결국 포기하고 다른 방법을 찾았다. 💡소요시간 : 1h

문제 이해는 빨랐지만 코드로 옮기는 과정에서 정말 많은 시간이 소요되었던 문제였다. 여러 코드를 작성하고 돌려봤지만 WA, 런타임에러(ValueError), 런타임에러(SyntaxError) 등이 계속해서 나왔다.매개변수로 받은 expression(식)을 문자열로 받아

테스트케이스를 기준으로 문제를 접근했다.입력42 3 15 2 4 1출력18첫 번째 주유소에서 2km × 5원 = 10원의 비용이 발생한다. 두 번째 주유소에서 주유를 할지 말지 결정을 해야 하는데 만약 두 번째 주유소에서 주유를 하게 된다면 총 2km × 5원 + 3k

"한 정사각형과 가로, 세로, 대각선으로 연결되어 있는 사각형은 걸어갈 수 있는 사각형이다." 옮길 수 있는 경로를 가로, 세로 뿐만 아니라 대각선도 추가해줘야 한다.w와 h를 헷갈려서 계속 WA를 받았다. ※ (9시 방향 기준으로 반시계방향으로 돌았을 때)※ (9시

이전 포스팅에 있었던 \[백준 25418번 정수 a를 k로 만들기] 문제와 동일한 유형이다. 계산 방법을 이용해서 접근했는데 역방향 접근 방식을 선택했다.문제에서 주어진 연산 방식을 역방향 연산 방식을 적용하면 다음과 같이 바꿀 수 있다.①. 연산1 : A에 2를 곱한

음수값을 만나면 연속된 수의 합이 최대가 나올 수 없으므로 이전 항과 현재 항의 값을 더해 최댓값을 저장하는 방식으로 코드를 작성했다.💡소요시간 : 20m

에라토스테네스의 체를 이용하여 n보다 크고 2n보다 작거나 같은 소수를 모두 찾아내는 방식으로 코드를 작성했다.💡소요시간 : 5m

팩토리얼 값을 DP를 이용해서 저장한 다음 DP에 접근해 이항 계수를 출력하는 방식으로 코드를 작성했다.💡소요시간 : 2m

에라토스테네스의 체를 이용하여 소수를 걸러준 다음 두 소수의 차이가 가장 작은 파티션을 출력한다. 이 때, 두 소수의 차이가 가장 작은 파티션을 출력하기 위해서 중간값을 기준으로 중간값을 이용해 조건에 맞는 값을 출력하도록 코드를 작성했다.💡소요시간 : 1h 11m

전체적인 코드는 작성하는 과정에서 문제가 없었지만 반례가 존재하여 코드를 거듭 수정했다. 💡소요시간 : 10m

이미 가지고 있는 랜선의 개수 K의 범위는 1 ≤ K ≤ 10,000이고 필요한 랜선의 개수 N의 범위는 1 ≤ N ≤ 1,000,000이다. 이전 포스팅에 있었던 \[백준 2805번 나무 자르기]와 동일한 유형의 이분 탐색 문제다.💡소요시간 : 8m

힙(heap) 자료구조에 대해서 알게 된 문제였다. 힙을 사용하기 위해서는 import heapq을 명시해줘야 사용이 가능하다.heappop(heap)는 heap에서 가장 작은 항목을 pop하고 반환해주는 메소드이다.heappush(heap, item)는 item값을

이전 포스팅에 있었던 \[백준 1927번 최소 힙]을 변형한 문제다.heap에 heappush수행할 때 마이너스 부호를 붙여 넣어준 다음 가장작은 원소를 출력하는 heappop을 수행할 때 앞에 마이너스 부호를 붙여준다.💡소요시간 : 4m

크기가 양수인 부분수열 즉, 원소의 개수가 최소 1개 이상인 모든 부분수열을 combination을 이용해서 찾은 다음 합이 S가 되는지 판단해 만족하는 부분수열의 개수를 출력하는 코드를 작성했다.💡소요시간 : 5m

factorial값을 직접 계산하거나 아니면 factorial값을 DP에 저장한 다음 2와 5의 개수를 찾아서 둘 중 최솟값을 찾는 방식으로 접근했으나 메모리 초과가 발생했다. 왜냐하면 n, m의 범위가 0 ≤ n, m ≤ 2,000,000,000(n ≠ 0)이므로 2

처음엔 당연히 그리디 알고리즘이라고 생각해서 코드를 작성했는데 WA를 받았다. 질문게시판을 참고해보니 어느 분이 답변하길... "항상 큰 제곱수를 빼준다고 해서 최적의 해가 나온다고 100% 장담할 수 없다."는 것이었다.결국 직접 제곱수 최소 항의 개수를 구해서 점화

명령어별로 각각의 기능을 수행할 수 있는 코드를 작성했는데 시간초과가 나왔다. 질문게시판을 참고해보니 insert를 사용하면 시간초과가 나온다고 했다. 다른 답변들을 보니 이 문제는 커서를 기준으로 왼쪽에 있는 문자열과 커서를 기준으로 오른쪽에 있는 문자열 즉, 두 개

현재 지점에서 오른쪽 한칸, 아래 한칸, 오른쪽 대각선 아래 한칸 이동할 수 있으므로 왼쪽과 위쪽 라인에 0을 추가해줘서 IndexError를 방지했다. DP문제치곤 쉬워서 매우 간단하게 풀었다.💡소요시간 : 10m

모든 순열을 하나하나 비교해서 최댓값을 구했다.💡소요시간 : 4m

permutations을 이용해서 간단하게 해결할 수 있었다.

이전 포스팅에 있었던 \[백준 1406번 에디터 ★]와 동일한 유형의 연결 리스트 문제였다. 커서 기준 왼쪽 스택과 커서 기준 오른쪽 스택 두 개의 스택을 만들어서 코드를 작성했다.입력1<BP<A>>Cd-출력BAPC결과 : 커서 기준 오른쪽 스택을 뒤집고 커

중복 선택과 오름차순 정렬을 이용하여 해결할 수 있었다.

앞에 있는 상자의 크기가 뒤에 있는 상자의 크기보다 작으면 넣으면 되고 크다면 넣지 않으면 되는 간단한 DP문제다.앞에서부터 모든 박스를 다 넣어야 하는 일반적인 그리디 알고리즘 문제가 아니다. 몇 개의 박스를 뽑아서 넣을 때 한 번에 넣을 수 있는 최대의 상자의 개수

조합과 정렬을 이용해서 간단히 해결했다.

📌 잘못된 코드(IndexError)입력73 201 1004 502 1603 301 60출력IndexError이 문제의 답은 50 × 160 - 20 × 60 = 6800이다. 하지만 위의 코드대로라면 남북 방향은 3, 4, 3으로 인접하는 값이 일치하지 않고 동서

combinations을 이용해서 문제를 해결할 수 있었다.💡소요시간 : 5m

시간초과(TLE)의 늪에서 빠져 헤어나오지 못했다. 문제는 간단하게 dp를 이용하는 문제였는데 시간초과의 원인은 아마 이중 for문이 아닐까싶다.1,000,000보다 작거나 같은 배열을 만든 후 값이 엄청나게 커지는 것을 방지하기 위해서 1,000,000,009로 나눈

중복순열과 중복 제거, 오름차순 정렬을 이용하면 해결할 수 있다.💡소요시간 : 3m

알고리즘 분류를 보고 해당 문제를 heapq을 이용해서 접근했다.heappush와 heappop를 이용해서 작성했는데 메모리초과가 나와서 결국 다른 방법으로 heapq.nlargest를 이용해서 N번째 큰 수를 출력하는 방법의 코드를 작성했다.최대힙, 최소힙도 문제를

BFS알고리즘으로 접근했다. 방문횟수 배열을 만들어서 상근이의 친구와 상근이의 친구의 친구까지 올 수 있도록 코드를 작성했다.다른 그래프 탐색 문제에 비하면 정말 쉬웠던 문제였다.💡소요시간 : 12m

이틀동안 고민했던 문제였다. 어떻게 풀어나가야할지 도통 방법을 몰랐다. 2일째 되던 날에 질문게시판을 통해 접근법을 봤는데 중학교 때 배웠던 수열의 합 공식을 조금 변형하면 될 것 같다고 나와있었다.고난도 문제에서 자주 나올 것 같아 이 방법은 꼭 기억해야겠다....(

기본적인 BFS/DFS 문제였다. 만약 방문한 횟수가 없다면 두 사람의 친척 관계가 전혀 없는 촌수이므로 -1을 출력하고 만약 0보다 큰 값이라면 입력에서 요구한 두 사람의 촌수를 나타내는 정수를 출력하면 된다.💡소요시간 : 22m

누적 합, 누적 곱 개념을 이용해서 접근했는데 이 방법은 모든 재료를 다 사용하는 경우라면 해결이 되는데 일부 재료를 사용하는 경우라면 되게 까다로워져서 결국 포기했다.combinations을 이용해 나올 수 있는 모든 조합을 확인해 신맛에서 쓴맛을 뺀 절댓값을 구해

딕셔너리를 이용해서 접근하면 된다고 생각하고 바로 코드를 작성했는데 계속 시간초과가 나와서 어떻게 하면 줄일 수 있나 하고 구글링을 해보니 defaultdict를 사용해야한다고 질문게시판에 나와있었다.입력값이 없을 때까지 입력을 하는 문제로 아래 조건문처럼 공백이 들어

인접 정점은 오름차순으로 방문한다는 조건이 있었으므로 DFS 함수 내에서 인접 정점들을 오름차순으로 정렬하는 sort()를 넣어준다.재귀를 사용해서 풀어야 하는 DFS, 재귀함수 문제라면, 아래의 코드를 상단에 쓰는 것은 선택이 아니라 필수이다.💡소요시간 : 10m

처음엔 모든 수의 사이에 들어갈 수 있는 연산자 순열을 구해서 중복을 제거해 최대한 메모리 사용을 방지한 다음 permutations을 이용해서 최댓값, 최솟값을 구하는 방식으로 코드를 작성했지만 시간초과(TLE)가 발생했다. 두 번째로 택한 방법은 백트래킹이었다. 사

주가를 뒤에서부터 비교했더니 접근이 수월했다. 만약 해당 날의 주가가 이전 날의 주가보다 높다면 이전 날에 주식을 살 것이고 만약 해당 날의 주가가 이전 날의 주가보다 낮다면 이전 날에 주식을 사지 않을 것이다.💡소요시간 : 17m

동생이 있는 위치에서 수빈이의 위치 S를 빼준 값의 절댓값을 리스트에 저장한 다음 리스트에 있는 수의 최대공약수를 유클리드 호제법을 이용해서 구한다.그 다음 리스트에 들어있는 수의 최대공약수를 구해 정답을 출력한다.두 수의 최대공약수를 구하는 방법은 간단하다. 그렇다면

입력한 T개의 숫자 중에서 가장 최댓값을 구해 1부터 최댓값까지의 수 중에서 에라토스테네스의 체를 통해서 소수를 걸러내는 작업을 수행한다.매 테스트케이스마다 에라토스테네스의 체를 돌리는 것보다 최댓값만 찾아서 그 범위까지 에라토스테네스의 체를 한 번만 시행해주면 시간을

매 수마다 약수를 구하고 그 약수들의 합을 구하기엔 너무 많은 시간이 소요된다. 뿐만 아니라 애초에 자연수 N의 범위는 1 ≤ N ≤ 1,000,000이라 매우 큰 수가 들어올 경우... 답이 없게 된다.입력4 출력10\* g(4) = f(1) + f(2) + f(3)

딕셔너리를 이용해서 해당 key값을 문자로 처리한 다음 value값만큼 곱해준다. 💡소요시간 : 4m

구하고자 하는 K번째 소수에서 K의 범위는 1 ≤ K ≤ 500,000이다. 즉, K = 500,000일때도 답을 출력할 수 있는 범위를 찾아야 한다.IndexError를 범하면서 기어코 답을 찾았는데 범위의 마지막 값은 10\*\*7이었다.💡소요시간 : 8m

BFS의 기본 코드 + 별도로 오름차순 정렬 수행💡소요시간 : 7m

BFS 기본 코드 + 별도로 내림차순 정렬 수행💡소요시간 : 3m

BFS 기본 코드정점 방문 여부💡소요시간 : 11m

BFS 기본 코드 + 별도로 오름차순 정렬 수행노드의 방문 깊이와 노드의 방문 여부를 둘 다 고려해야함💡소요시간 : 9m

DFS 기본 코드 + 별도로 오름차순 정렬을 수행💡소요시간 : 5m

DFS 기본 코드 + 별도로 내림차순 정렬을 수행💡소요시간 : 5m

DFS 기본 코드 + 별도로 오름차순 정렬 수행코드 정점 방문 여부💡소요시간 : 7m

DFS 기본 코드 + 별도로 내림차순 정렬 수행노드 정점 방문 여부💡소요시간 : 4m

DFS 기본 코드 + 별도로 오름차순 정렬을 수행방문 깊이와 방문 순서를 모두 고려💡소요시간 : 11m

DFS 기본 코드 + 별도로 내림차순 정렬 수행방문 여부와 방문 순서를 모두 고려💡소요시간 : 7m

극악의 정답률을 보고 처음엔 경악했다. 입력값의 최대가 1,000,000인 점으로 미루어 보았을 때 일반적인 방식인 factorial을 이용하는 방법은 아닌 것 같았다.앞에서부터 곱하는 방식을 사용해서 대충 15자리와 같거나 큰 경우가 된다면 슬라이싱을 통해 구간 숫자

n의 값을 점점 늘려가면서 규칙을 찾았고 규칙을 바탕으로 점화식을 세워 문제를 해결할 수 있었다.💡소요시간 : 17m

math라이브러리에 있는 factorial을 이용해서 팩토리얼 값을 구한 다음 0이 아닌 가장 낮은 수를 구해주었다.💡소요시간 : 15m

너비 우선 탐색(BFS) 알고리즘을 이용해서 코드를 작성했다. 방문 여부를 나타내는 배열 visited와 캠퍼스를 나타내는 배열 campus 두 개의 배열을 이용했고 조건별로 조건문을 작성하여 도연이가 만날 수 있는 사람의 수를 출력하도록 코드를 작성했다.💡소요시간

실버2 문제치고는 조금... 복잡해서 애를 먹었던 문제였다. import copy를 통해서 기존의 2차원 배열을 하나 복사하여 현재 상태의 지도와 50년 후의 지도 두 개를 별개로 만들어 코드를 작성했다.

종이에 표를 그려가면서 각각의 경우에 대한 답을 찾아서 해결할 수 있었다.💡소요시간 : 27m

소스 코드의 함수를 그대로 구현하면 간단하지만 a, b, c의 값이 큰 값일 경우 값을 계산하는데 매우 오랜 시간이 걸린다. 따라서 dp배열을 이용해서 만약 값이 존재한다면 함수를 호출하지말고 그대로 그 값을 반환해주는 방식으로 코드를 작성했다.💡소요시간 : 20m

종이에 그려가면서 어떤 동작을 취해줘야하는지 일일이 체크해주면서 정확하게 코드를 작성했다.💡소요시간 : 7m

팰린드롬 문자열은 앞에서부터 읽으나 뒤에서부터 읽으나 같은 문자열인 것을 의미한다.슬라이싱을 활용하여 구간별 문자열을 추가하였을때 팰린드롬이 성립된다면 최소 팰린드롬의 길이를 출력할 수 있다.

문제 예시를 직접 그려보면서 어떻게 유도가 되는지를 확인한 후 결론을 도출하는 코드를 작성했다.(는 그냥 스택에 넣는다)가 나오면 두가지 경우로 나누어진다.)가 나오고 이전 문자가 (이었다면 해당 파트는 레이저이다. 따라서 현재 stack에 쌓인 (개수(=쇠막대기 개수

다음 순열 즉, next_permutation을 구하는 문제다. 이런 문제는 itertools의 permutations를 사용하면 시간초과(TLE)가 나오기 쉽다.이번 문제를 통해서 다음 순열 알고리즘을 익히고 다른 문제에 직접 적용해보면서 연습하는 것도 좋을 것 같다

방향 없는 그래프가 주어졌을 때, 연결 요소(Connected Component)의 개수를 구하는 DFS 완전 탐색 문제였다. 연결 요소는 나누어진 각각의 그래프를 말한다. 이 문제의 테스트케이스를 예로 들어 설명하면 다음과 같다.6 51 22 55 13 44 62첫

재귀를 이용하여 숫자판을 지나다니면서 만들어지는 숫자의 길이가 6자리가 되면 리스트에 해당 숫자가 있는지를 확인한 후에 없으면 추가하고 있으면 넣지 않는 방식을 이용했다. 또한 이 문제는 왔던 곳을 다시 지나갈 수 있으므로 방문 여부를 따지는 배열이 필요하지 않다.💡

W, H를 잘못 입력받아서 IndexError가 나왔다. 문제 똑바로 읽었으면....💡소요시간 : 18m

일반적인 소수 판정 알고리즘을 사용해 문제를 해결했다.N의 값의 범위는 1 ≤ N ≤ 1e+16이므로 나의 로직대로 선형탐색을 진행하면 Python3에서 시간초과가 발생할 수 밖에 없다. 그래서 같은 논리지만 PyPy3로 제출했더니 AC를 받았다.💡소요시간 : 11m

Xi를 좌표 압축한 결과 X'i의 값은 Xi > Xj를 만족하는 서로 다른 좌표 Xj의 개수와 같아야 한다. 해당 문제의 범위는 1 ≤ N ≤ 1,000,000, -10^9 ≤ Xi ≤ 10^9이므로 2중 반복문을 통한 브루트포스 탐색은 답이 될 수 없다.테스트케이스를

위에서부터 사전 순으로 쌓으려면 몇 번을 움직여야하는지에 대한 문제다.테스트케이스를 예로 들어 설명하면 다음과 같다.입력3321출력2위의 테스트케이스에서 움직일 필요가 없는 책은 3번 책이다. 2번 책을 빼서 3번 책 위에 놓으면 2, 3, 1 순서가 될 것이고 1번

각 원자의 질량값을 딕셔너리로 선언하고 괄호 문자 내의 원자의 경우 ( 문자가 나오고서부터 )가 나올 때까지의 값을 계산하는 temp 변수를 만들어 구한 다음 stack에 넣어주는 방식으로 코드를 작성했다. 스택과 문자열을 같이 다루는 부분에서 연습이 좀 더 필요하다고

이전에 풀었던 \[백준 1992번 쿼드트리] 문제를 풀어서 확실히 접근하기가 수월했다.💡소요시간 : 48m

이전에 풀었던 \[백준 1992번 쿼드트리] 문제를 먼저 풀고 나서 풀었더니 수월하게 풀 수 있었던 문제💡소요시간 : 17m

이진 탐색을 이용하는 문제였다. ZeroDivisionError와 문제를 잘못 이해하여 예상보다 시간이 좀 더 걸렸다.입력3 101 2 3 4 5 6 7 8 9 10출력8길이가 8, 9, 10인 과자를 최소 길이인 8로 나누면 3명의 조카들에게 과자를 균등하게 나눠줄

N의 값을 따졌을 때, 점이 보이려면 기울기의 분자, 분모 값이 서로소 관계여야 (0, 0)에서 보이는 점이 된다. 분자, 분모의 값이 서로소 관계가 성립하려면 분자, 분모의 최대공약수는 1이어야 한다.💡소요시간 : 27m

완벽하게 자신이 이기기 위한 방법으로 게임을 한다고 가정규칙성을 하나하나 파악하여 코드를 작성돌의 개수가 1개인 경우 : 상근이가 시작해서 1개를 가져가므로 창영의 승돌의 개수가 2개인 경우 : 상근이와 창영이가 각각 1개씩 가져가므로 상근의 승돌의 개수가 3개인 경우

BFS(상하좌우 + 대각선) 유형 너비 우선 탐색💡소요시간 : 27m

깊이 우선 탐색을 이용해서 트리의 부모를 찾을 수 있다.💡소요시간 : 15m

규칙을 찾아서 점화식을 세워 문제를 해결하는 1차원 dp 테이블 문제로는 해결할 수 없었던 문제였다. 질문게시판을 찾아보니 2차원 dp 테이블을 이용해서 문제를 해결하는 코드가 상당히 많았다. N의 합을 구성하는 순서쌍 중에서 1로 끝나는 경우, 2로 끝나는 경우, 3

다이나믹 프로그래밍을 이용하는 문제로 이중 for문으로 구현할 수 있었다.💡소요시간 : 19m