프로그래머스 문제풀이

시간이 너무 오래 걸리는 게 있어서 수정한 코드x 안에 있는 값을 비교할 때 문자열 -> 숫자로 변경하는 int()를 사용하지 않고 문자열 그대로('1') 비교더 빨라졌지만 count() 함수를 사용한 게 제일 빨랐다

수학적인 풀이 방법이 있을 거 같았지만 도저히 생각이 나지 않아서 브루트포스로 풀었다. n이 10,000이하의 자연수이기 때문에 O(

단순 브루트포스one : n의 2진수로 변환했을 때의 1의 개수 n에서 1씩 증가시키며 2진수의 1의 개수가 같은 값 찾아서 반환

나의 풀이재귀로 접근했다가 아닌 거 같아서 반복문으로 바꿨다n이라는 숫자까지 반복하는 건줄 알았는데 횟수였다중간중간에 1234567로 계속 나눠줘야 계산이 빠르게 진행된다dp라는 배열을 만든다음에 1칸, 2칸 전의 값을 가져와서 더해나가는 걸 n번 진행하는 방식다른 풀

완전한 브루트포스 방식으로 문자 두개가 같으면 pop을 하는 방식테스트 케이스는 금방 통과했지만 제출하자마자 무한 시간초과 로직은 틀린 게 없다고 생각했는데 시간초과가 나서 너무 멘붕이었다. 힌트를 보니 스택을 사용하면 쉽게 풀린다고 해서 두 번째 멘붕이었다. 진짜 1

언급된 단어들을 저장할 자료구조 필요일반 배열로 저장하면 in으로 찾아야하는데 시간복잡도가 O(n)이기 때문에 이 방법은 비효율적일 거 같았다. 대신 단어를 키 값으로 저장할 수 있는 딕셔너리를 사용하면 현재 단어가 있는지 확인하는데 시간복잡도가 O(1)이라 더 효율적

카펫의 가로 길이는 세로 길이와 같거나, 세로 길이보다 깁니다.가로와 세로의 길이는 결국 전체 타일 수의 약수들의 순서쌍 중에 있다갈색과 노란색 타일의 수를 다 합한 다음에 그 수의 약수들을 구해서 하나씩 일치하는지 확인해보는 브루트포스 방식 사용약수를 구하려는 수의

대략 백만개의 숫자가 있지만 토너먼트 형식이기 때문에 총 라운드 수는 최대 20번매 라운드마다 이긴 숫자들만 모아둘 리스트를 만들어서 만날 때까지 반복하면 되지 않을까 했는데 A와 B가 아닌 다른 숫자들을 굳이 저장해둘 필요가 없을 것 같아서 다른 방식을 떠올렸다일단

처음엔 닮음을 이용해서 각각의 길이를 구해서 피타고리스 정리로 대각선 길이를 구하고 더하는 복잡한 식인줄 알았는데 입사각과 반사각이 같으니까 대칭으로 돌려서 하나의 큰 직각삼각형으로 만들고 그 대각선 길이는 구하는 거였음단, 이때 문제에 모서리에 대해서 언급이 되는데

✅ 2명만 태울 수 있다순서대로 태워야 한다는 말도 없고, 2명의 무게를 합쳐서 limit를 넘는지 아닌지 여부가 중요하기 때문에 우선 무게 순으로 정렬heavy와 light 는 각각 현재 기준 가장 무거운/가벼운 사람을 나타낸다. 무거운 사람(heavy)과 가벼운 사

🔍 처음엔 그래프 탐색 문제거나 다익스트라인줄 알았다. 그런데 K칸이라는게 정해져 있지 않고 1~무한대까지 가능해서 이렇게 찾으면 시간 초과가 날 거 같았다🔍 생각해보면 결국 현재까지 온 칸의 2배를 하면 N칸에 도달할 수도 있다는 말이 된다. N에서부터 2로 나눠

✅ 오직 1칸 또는 2칸만 이동할 수 있다n번째 칸까지 오기 위해서는 n-2칸에서 2칸, n-1칸에서 1칸 이동해야 한다전체 문제를 해결하기 위해 부분의 값을 저장해두고 가져와 풀 수 있는 다이나믹 프로그래밍을 통해 해결했다. dp라는 배열에 n번째 칸까지의 방법을 저

스택을 사용한 올바른 괄호 판별check 함수에서 올바른 괄호라면 1을 그렇지 않다면 0을 반환괄호의 여는 부분((, \[, {)이 들어온다면 스택에 추가하고, 닫는 부분(), ], })이 들어온다면 스택의 가장 위에 있는 괄호와 비교해 짝이라면 꺼내고, 짝이 아니라면

💡 우선 순위 큐같은 모양이라서 힙으로 풀어야 하나? 고민했다하나의 인덱스에서 시작해서 길이를 늘려가면서 더하려고 했는데, 생각을 잘못한 게 길이를 늘릴 때마다 매번 start에서 다시 시작해서 값을 더하고를 반복하려다보니 반복문이 무한대로 늘어났다. for문 중첩이

‼️ h편 이상 인용된 논문이 h편 이상✅ h편의 논문은 citations 배열의 인덱스✅ h편 이상 인용은 citations 배열의 값✅ 배열은 정렬✅ 비교를 쉽게 하기 위해 배열의 가장 앞에 -1 추가값이 정렬되어 있기 때문에 최대값을 찾기 위해서는 뒤에서부터 인덱

곱했을 때 나오게 되는 행렬의 길이 잘못 생각해서 런타임 에러for x in range(len(arr2)) 이 부분에서 range 안의 값을 계속 answer 행렬의 열 길이와 같다고 해줘서 틀렸다. (2x3)행렬과 (3x2)행렬을 곱해주게 되면 (2x2)행렬이 나오게

2차원이 아니라 1차원 배열을 만들어서 슬라이싱 하려고 했는데 n은 최대 10^7까지 될 수 있다. 아무리 1차원이어도 10^14의 길이는 = 거의 10조...?2차원 배열의 각 칸에 들어간 숫자들이 어떤 규칙을 갖고 들어가 있는지 생각해봐야 한다. 각 칸에 들어가게

⏰ 아이디어 1️⃣ 먼저 target을 (s, e) 순서대로 정렬 2️⃣ 가장 처음 타겟을 요격 가능한 위치(s1, e1)로 설정 3️⃣ 타겟들을 비교하면서 요격 가능한 위치와 겹치는 부분이 있다면 요격 가능 위치를 업데이트

가장 최소가 되는 값 구하기1️⃣ 곡괭이의 순서 정하기2️⃣ 곡괭이 하나당 5개의 광물 캐기3️⃣ 곡괭이를 다 사용하거나 or 광물을 다 캐면 종료먼저 재귀로 곡괭이의 순서를 정한다.각 곡괭이에는 사용가능한 횟수 제한이 있으므로 사용이 가능할때만(>0) 사용을 한다.

📝 문제 풀이

📝 문제 > 자신보다 크면서 가장 가까이에 있는 수를 찾아라 풀이 💡 아이디어 일단 당연히 브루트포스로 풀어봤고 시간초과가 발생했다. 배열의 길이 범위가 백만이기 때문에 O(n^2) 방식으론 사실상 불가능 다음은 힙 자료구조를 활용해봤다. O(n^2)이 안

deque를 활용한 풀이큐에서 프로세스를 꺼내고 큐를 돌면서 더 우선순위가 높은 프로세스가 있나 확인한다. 더 높은 우선순위를 가진 프로세스가 있다면 지금 꺼낸 프로세스는 다시 큐에 넣는다. 이 과정의 반복

각 의상의 종류를 키 값으로, 종류별 개수를 값으로 가지는 딕셔너리를 만든다. 종류별 개수만 뽑아서 조합을 돌리고 몇 개의 조합이 나올 수 있는지 계산한다.단, 이때 각 의상의 종류에는 그 의상을 입지 않는 경우가 포함되어야 하기 때문에 모두 1씩 더 추가한다. 아무것

📝 문제 풀이

❌ n = 20, k = 20! 이기 때문에 완전탐색으로는 불가능n = 4라고 했을 때, 첫 번째 자리의 숫자가 1이 되는 방법은 총 3 x 2 x 1 이다. 첫 번째 자리의 숫자가 정해졌으므로 나머지 자리는 총 3자리가 되고 남은 숫자는 2, 3, 4로 총 3가지이다

리스트 + 딕셔너리 활용한 풀이단순히 in 사용하고 싶지 않아서 이렇게 풀었다. used는 딕셔너리로 키 값을 도시 이름으로 갖고, value 값으로는 참조 시기를 가진다. 참조 시기가 0이라면 현재 캐시에 존재하지 않는 것.LRU 방식은 이 데이터가 언제 캐시에 추가

itertools 라이브러리 permutations 사용한 풀이가능한 모든 순서를 중복 for문으로 탐색최소 필요 피로도는 내림차순으로 소모 필요도는 오름차순으로 정렬한 뒤 비교이 경우는 테케가 반례가 되는데, \[80,20,50,40,30,10] 의 경우 첫 번째 던

chess : 각 행의 몇 번째 열에 체스가 놓여있는지 나타내는 1차원 배열cols : 행에 상관없이 각 열에 체스가 놓여있는지를 나타내는 boolean 타입의 값을 갖는 1차원 배열행이 1칸씩 증가하면서 체스를 놓게 된다. 이때 가능한 모든 열을 확인한다. 아직 사용

할인 품목의 배열 길이가 10만이기 때문에 재귀 등으로는 풀 수 없고, O(n)의 시간복잡도로 풀어야 한다. 항상 10일치라는 제한이 있기 때문에 discount 배열을 처음부터 끝까지 10일치씩 탐색하면서 현재 구하려는 품목의 배열 number 와 일치 여부만 확인하

math 를 사용하지 않으면 2번이 에러, //를 사용하면 11번이 에러

그리디의 탈을 쓴 브루트포스 원랜 그리디로 풀렸던 거 같은데 22년에 테케가 추가된 이후로는 그리디로 안 풀린다는 질문글이 폭주하고 있다. 원래 그리디는 현재 상황에서 최적의 해를 탐색해나가는 방식인데, 이 문제는 그렇게 풀리지 않는다. 모든 상황을 다 탐색하고 최적의

파이썬에 1000x1000 배열까지는 감당 가능하다고 해서 배열을 그린 뒤에 하나씩 숫자를 써넣었다. 방향은 ⬇️ ➡️ ↖️ 이렇게 세 방향을 계속해서 반복했다. n = 4라고 할때, 처음에는 4칸 ⬇️, 다음은 3칸 ➡️, 다음은 2칸 ↖️, 다음은 1칸 ⬇️ 과 같

현재 위치의 주가가 앞으로 몇 초 동안 유지될 수 있는지를 묻는 문제. 같거나 높다면 유지되는 것이고 1이라도 떨어진다면 떨어지는 것이다. 만약 1이라도 떨어진다면 그 이후는 비교할 필요

2022년 카카오 공채 문제1번이었을 것 같다k진수로 변경하고, 소수가 될 숫자들은 0 기준으로 다 잘라내서 모은 다음에 소수인지 아닌지 판별하는 문제솔직히 지금 이렇게 푸니까 쉬운거지 공채 문제에서 만났으면 못 풀었을듯? ㅎㅎ

가로, 세로, 대각선에 같은 표시가 된 게 있어도 같은 표시가 되고 한쪽이 승리하고 게임이 끝난 거라면 잘못된 게 아니다. 테스트케이스만 보면 그렇게 판단해야 될 것 같은데 일부러 그렇게 유도한 것 같다.예를 들어 위의 반례처럼 'O'가 승리했는데, O의 개수가 X의

길이가 10만이기 때문에 완탐으로 하면 시간초과가 난다.같은 값이 중복으로 여러 개 있을 수 있고 하나의 값이 가질 수 있는 짝꿍의 개수도 정해져 있기 때문에 Counter를 사용해 각각의 개수를 키 값으로 갖는 딕셔너리를 만들어준다. 이제 각 딕셔너리의 키 값을 돌면

어마어마한 제한사항을 생각하지 못하고 사실상 거의 완전탐색에 가깝게 풀었다.✔️ 길이를 한 칸씩 늘려가면서✔️ 큰 수 부터 차례대로 k개를 제거한다(힙 사용)✔️ 남은 합이 n보다 작은 경우 통과그런데 가장 긴 길이를 찾는 거기 때문에 길이를 한 칸씩 늘리는 것보다 한

10의 단위로 끊어서 방문하기 때문에 최대 9자리여도 가능한 가지수는 2^9 = 512 정도라 BFS로 풀었다. limit는 이 값을 넘어가는 값을 가지면 더 이상 최소가 될 가능성이 없다고 판단하고 설정해둔 한계 값. 3자릿수라면 1000, 4자릿수라면 10000과

처음엔 그래프 탐색같다고 생각해서 dfs나 bfs를 사용해야 하나 고민했다. 하지만 1인 곳을 탐색할 수는 있어도 그 모양이 정사각형인지를 찾으려면 엄청 복잡할 것 같았다. 전부다 리스트에 넣어놓고 정사각형인지를 하나씩 판별한다던가... 다음으로는 한칸씩 이동하면서 정

`deliveries`와 `pickups`를 스택으로 사용해서 풀었다. 배달과 수거는 같이 이뤄지는 것 같지만 사실은 개별적으로 이뤄지는 거나 다름 없다. 배달해야 할 것과 수거해야 할 것 중 가장 멀리 있는 걸 기준으로 두면 된다.

두 개의 큐는 길이가 최대 30만이기 때문에 실제로 pop, append를 사용하면 시간초과가 발생한다. 두 개의 큐를 연결해서 하나의 배열로 만든 다음에 투 포인터 방식으로 큐를 구현했다. i는 첫 번째 큐(queue1)의 가장 첫 번째 원소, j는 두 번째 큐(qu

이모티콘의 할인율은 10%, 20%, 30%, 40% 네 개로 제한되어 있다. 각각의 이모티콘에 대해 4개의 할인율을 전부 적용한 중복 순열을 만드는 함수 find_product와 그렇게 설정된 각각의 할인율 조합에 대해 가능한 모든 가입자수와 판매액을 계산하는 pri

10진법이 124진법(?)으로 바뀐 문제이다. 숫자가 124 밖에 없다고 생각하고 쭉 써나가면서 규칙을 찾으면 된다. 대충봐도 숫자가 3개니까 3으로 나눠보면 될 것 같았다. 처음엔 너무 어렵게 접근해서 3의 제곱수를 더해나가면서 찾는건가? 싶었는데 그냥 3으로 나눈

문제의 조건에서 배열의 크기가 전부 다 5x5이다. 중복으로 완전 탐색을 하면서 심지어 백트래킹을 하지 않아도 시간초과가 안 날 것 같다. 처음에는 P의 위치에서 맨해튼 거리내의 P들을 전부 조사한 다음에 그 사이에 X가 있는지의 여부를 판별하려고 했다. 그런데 거리두

현재 1번 마을에 있는 음식점에서 각 마을로 음식 배달을 하려고 합니다. 각 마을로부터 음식 주문을 받으려고 하는데, N개의 마을 중에서 K 시간 이하로 배달이 가능한 마을에서만 주문을 받으려고 합니다. 1번 마을에서 다른 마을까지의 모든 최단 거리를 구하는 문제이다.

현재 숫자 n의 루트 n까지의 숫자까지 일일이 나눠가면서 소수인지 아닌지를 판별한다. 하나라도 나눠 떨어지는 숫자라면 소수일 수 없다. 이 문제에서는 문제의 조건이 크지 않아서 가능했지만 아주 큰 숫자라면 시간초과가 발생할 가능성이 높음.근데 이게 더 느린데

문제분류가 다익스트라가 아니었으면 삽질 좀 했을 것 같다. 대놓고 알려주는 문제여서 쉬웠다고 생각. 아래쪽과 오른쪽으로만 이동한다는 힌트가 있고 물이 잠겨있는 곳만 피하면 된다. 물이 잠겨있는 곳을 제외하고 나머지 공간에 도착하면 반대로 위쪽과 왼쪽의 데이터를 가져와서

처음엔 현재 위치에서 다른 노드까지의 최단 거리를 너무 강조해서 다익스트라인줄 알았는데 일반 bfs로 풀면 되는 문제였다.현재 위치에서 bfs로 탐색해서 가장 마지막에 탐색되는 위치의 개수를 구하면 된다. 일반적으로 visited에 현재까지 거린 거리를 저장해나가면서

set()을 사용해서 전체 배열을 탐색하면서 양쪽의 중복을 제거한 값의 개수를 구하려고 했으나 시간초과로 실패했다.방법은 전체 토핑의 개수를 구한 다음에 한 칸씩 잘라가면서 양쪽의 개수가 같아지는 순간을 하나씩 구하는 것이다. 철수의 토핑 개수는 count, 동생의 토

중복순열 product 사용해서 해결. 문자가 5개 밖에 안 되기 때문에 중복순열로 다 구해도 3905개 밖에 안 된다.

브루트포스로 1씩 증가시키며 찾는 방식은 비효율적이다. 규칙을 찾으면 수월하다. 0으로 끝나는 경우 : 0을 1로 변경0으로 끝나진 않지만 2진수 사이에 0이 하나라도 있는 경우 : 0 위치의 이전에 있던 1을 0으로 옮기기2진수에 0이 하나도 없는 경우 : 가장 앞에

길이가 1이 될 때까지 4등분을 하고 그 값을 리턴하면서 4칸이 일치하는지 여부를 확인했다. 길이가 1이면 해당 칸의 값을 반환하고, 1이 아니면 4개의 칸으로부터 오는 값들을 검사한다. 길이가 1일 때 이미 해당 값의 개수를 카운트 해줬기 때문에 4칸이 동일하다면 3

단순 구현 문제. 우선 딕셔너리에 한 글자 알파벳에 대한 정보를 모두 저장한 후 탐색한다. 딕셔너리에 일치하는 문자가 있다면 탐색을 이어나가고, 일치하는 문자가 없다면 그 문자에 대한 인덱스 값을 저장한다. 이때 result에 추가되는 인덱스 값은 직전에 일치하는 문자

합이 S가 되면서 곱해서 최대가 될 수 있는 수의 집합(중복 가능)곱해서 최대가 되려면 무조건 큰 수가 많을 수록 좋을 것 같다. S=8이라고 생각해보자. 더해서 8이 되면서 가장 큰 수를 가질 수 있는 경우의 수는 (1, 7)이다. 하지만 둘을 곱하면 1이 너무 작기

최단 거리를 구하는 그래프 탐색 유형의 문제라서 BFS로 풀었다.1\. 한 번에 한 개의 알파벳만 바꿀 수 있습니다. 처음엔 두 문자를 set으로 변환한 다음에 차집합을 구하는 방식을 택했는데 이렇게 하면 중복되는 문자를 구별할 수가 없었다.어차피 문자의 길이가 최대

n이 최대 100이라 완전 탐색으로 풀어도 O(n^2) = 약 1만번의 연산이다. 모든 경로를 한 번씩 다 나눴다. 1-3 경로를 나눠보고 2-3 경로도 나눠보는 방식. 단 이미 나눠본 경로를 또 나눌 필욘 없으므로 1-3을 나눠봤다면 3-1이 나눠지지 않도록 했다.

우선순위 큐를 두 개 구현. 파이썬의 heapq 라이브러리를 사용함.최대값과 최소값을 둘 다 출력해야 하는데 파이썬의 힙큐 라이브러리는 최소힙이기 때문에 최대힙을 구현하기 위해서는 값을 넣을 때 -를 붙여 수의 부호를 변경해야 한다. 둘 중 어느 하나의 힙에 출력연산이

\+, -, \* 3개의 연산 우선순위를 어떻게 하느냐에 따라 값이 달라지고 그 값들 가운데 최대값을 구하는 문제. 우선 (1) 3개의 연산자 순서를 어떻게 할 것인지에 대한 처리와 (2) 연산자 우선순위에 맞춘 계산방식 부분을 처리하면 될 것 같았다. 연산자 순서 순

역시 카카오... 너무 어려워...각 지원자 분류하기언어, 분야, 경력, 음식 크게 4가지로 분류한 후 각 분류에 맞는 지원자들의 점수를 리스트 형태로 저장했다. 전체를 의미하는 -는 고려하지 않았다. 크게 4가지라서 전체 가지수는 24가지가 되고, 각 조건에 따라서

(1)table의 퍼즐 조각들을 찾아서 (2)game_board의 칸에 하나씩 끼워맞추면 된다. 보통 그래프 탐색은 개수를 세거나 몇 칸 이동해야 하냐 정도의 문제인데 여기서는 그래프 탐색을 통해 퍼즐 조각이 어떤 모양으로 생겼는지(?)를 파악해야 했다. 일단 퍼즐 조

가장 많이 함께 주문한모든 메뉴들의 조합들 중에서 2번 이상 주문됐으면서 조합의 길이별로 가장 많이 주문된 조합들을 찾아야 한다.'AB'라는 메뉴가 3번, 'CD'라는 메뉴가 4번 주문됐다면 길이가 2인 조합 중에서는 'CD'가 반환되어야 한다.만약 횟수가 같다면 둘

KMP 알고리즘을 써야 풀리는 문자열 문제라고 생각했는데 그 정도 난이도는 아니다. 문제를 잘 읽어보면 풀리는 문자열 구현문제. 문제가 복잡한데 요약하면 아래와 같다.A 문자열이 B 문자열 안에 있는가?A 문자열은 m이고, B는 주어진 문자열에서 만들어내면 된다. 음에

가능한 경우의 수를 전부 다 구해서 사전순으로 정렬한 다음에 가장 앞의 값만 반환한다. 당연히 안 된다. 50x50이고 모든 칸에 다 방문할 수 있기 때문에 최대 2500개의 칸이 4방향의 값을 다 가질 수 있어 4^2500으로 시간 초과 발생

유일성 : 튜플을 유일하게 식별할 수 있어야 한다최소성 : 꼭 필요한 속성으로만 구성되어야 한다.만약 a라는 튜플이 유일성을 만족한다면 a를 포함하는 모든 조합에 대해서는 유일성을 만족하더라도 최소성을 만족할 수 없다. 이미 a만으로도 식별이 가능하기 때문이다. 각 조

보통의 그래프 탐색과 다르게 이 문제는 경로를 목적으로 한다. 일반적인 그래프 탐색 문제는 (0, 0)과 같은 특정 위치에서 다른 위치로 옮겨다녔지만 이 문제는 (0, 0)에서 (1, 1)으로 갔다는 경로와 방향성이 중요한 것이다. 위치를 탐색하는 걸 경로를 탐색하는

우선 문자열의 최대 길이가 1,000이기 때문에 완전 탐색으로 비교해도 O(n^2) = 1,000 x 1,000 = 1백만이다. 1개짜리 단위부터 몇 개의 단위까지 자를 수 있는지를 먼저 고민해봐야 한다. 만약 길이가 14인 문자열이 있다고 가정하자. 그럼 7개까지는

불량 사용자 아이디 하나는 응모자 아이디 중 하나에 해당하고 같은 응모자 아이디가 중복해서 제재 아이디 목록에 들어가는 경우는 없습니다.불량 사용자 아이디와 응모자 아이디는 1:1로 대치되고, 같은 아이디가 중복해서 들어가는 경우는 없으므로 둘의 개수는 같을 것이다.

이 블로그의 풀이를 참고했다.라이언의 화살 배열을 구성할 수 있는 경우의 수는 아래와 같이 3가지다어피치가 쏜 과녁에 라이언이 쏠 경우어피치가 쏘지 않은 과녁에 라이언이 쏠 경우어떤 과녁이든 쏘지 않고 넘어가는 경우어피치가 쏜 과녁에서 점수을 내려고 하는 경우, 라이언

k와 d의 최대값이 백만이기 때문에 가능한 경우의 수를 전부다 구하거나 저장하면 시간초과.0부터 k간격으로 x좌표를 늘려가면서 가능한 좌표의 개수만 구해서 더해나간다. 각 x좌표에서 최대로 가질 수 있는 y좌표의 값을 구한 후 k로 나눠주면 된다. y좌표도 k간격으로

각 배열의 최대 길이가 10만이라 혹시 몰라서 힙을 썼는데 그 정도 문제는 아니었던 것 같다. O(n)이내에 통과할 수만 있으면 힙을 쓰지 않아도 가능하다.순서가 반드시 지켜지지 않아도 상관없으므로 두 배열을 정렬해서 각각의 값을 비교한다. A배열 현재 인덱스 값을 B

이 풀이를 참고했다. 탐색해야 할 대상이 10만개가 넘어가면 보통 이분탐색, dp, 그리디, 우선순위 큐, 트리 중 하나로 해결해야 하는 것 같다.전에 스터디할 때 누가 이 문제를 dp로 풀었었다고 해서 dp로 계속 풀려고 해봤다. 그런데 안 되더라ㅠㅠ 애초에 k칸 이

이런 경우를 생각해야 한다.알파벳 순서라서 a에서 b로 먼저 가야하지만 b에서는 더 이상 갈 수 있는 곳이 없어서 다시 a로 되돌아와야 한다. 현재 출발지에서 방문할 수 있는 목적지를 스택에 추가한다. 그런 다음 스택의 가장 끝에 있는값(스택은 LIFO)를 출발지로 설

🔗 풀이

정점 s에서 출발하여 a, b로 갈 수 있는 최소 비용을 찾아야 한다. 처음 출발점부터 각각의 방향을 향해 갈 수도 있지만 그렇지 않은 경우도 존재할 수 있다. 그럴 경우 겹치는 경로는 같이 택시를 탄다고한다. 같은 경로를 지나가게 될 경우 돈은 한 번만 낸다는 것이다

🔗 풀이 최대한 셔틀을 늦게 타야 하므로 사실상 마지막 버스를 탈수록 정답에 가깝다. 하지만 다른 크루들과 같은 시간에 도착한다면 그 중에서는 가장 마지막이라고 한다. 그렇다면 모두가 9시에 왔고, 먼저 도착한 크루들의 인원이 셔틀의 인원과 정확하게 딱 맞아 떨어

🔗 풀이

열쇠로 자물쇠의 모든 홈을 채울 수 있는가를 묻는 문제이다. 반드시 모든 홈을 채워야 하는데 그게 열쇠의 모든 돌기 부분을 사용하지 않을 수도 있다. 이 부분을 오해해서 한참을 헤맸다. 반대로 열쇠의 모든 돌기를 사용했더라도 자물쇠의 홈이 하나라도 채워지지 않았다면 F

순환구조가 없는 그래프 형태이므로 트리 구조라고 볼 수 있다. 판매원을 자식이라하면 판매원을 소개시켜준 사람은 부모가 된다. 즉, 자식 노드가 얻은 이득의 10%를 부모가 갖게된다. 이 과정은 루트 노드에 도달할 때까지 반복한다라는 게 된다. 총 판매원은 1만명까지 존

기둥과 보를 조건에 따라 설치하거나 제거할 수 있는지를 구현하는 문제이다. 구현의 난이도 자체는 어렵다고 할 순 없었지만 고려해야 할 게 많아서 까다로웠다. 각각의 위치에 대해 기둥과 보가 설치되어 있는지에 대한 정보가 필요하다. 특정 위치에서 위쪽으로는 기둥이 오른쪽

& : AND 연산자| : OR 연산자^ : XOR 연산자비트 연산자를 사용하면 빠르게 풀 수 있는 문제. 근데 만약 실전에서 만났으면 비트 연산자 몰라서 노가다 했을 거 같다.벽을 1이라고 하고 공간을 0이라고 했을 때, 둘 중 하나라도 1이면 1이 되는 XOR 연산

기존에 한 칸씩 하던 그래프 탐색을 두 칸씩 해야 하는 문제. 최단거리를 구해야 하기 때문에 BFS를 사용했고, 계속 현재 이어진 두 칸이 가능한가에 대해 고려하면서 풀어나갔다. 가로든 세로든 무조건 상하좌우로 다 이동할 수 있다. 회전할 때만 조금 다른데 두 점

풀이 2018년 카카오 공채 7번 문제였고 정답률은 17%였다고 한다. 지금은 좀 올라서 21%이다. 시간문제인데 초에서 끝나는 게 아니라 밀리세컨드까지 고려해야 하기 때문에 모든 경우의 수를 고려하면 3백만을 넘어서 시간초과가 난다. 그래서 그냥 카카오 문제 풀이

(0, 0)에서 (N-1, N-1)까지 갈 수 있는 모든 경로 비용 중 최소 비용을 찾으라는 문제였다. 처음 보자마자 아무 생각 없이 그래프 탐색 문제라고 생각했고, 25x25=625니까 전부 탐색해도 무리없겠다 싶어서 완전 탐색을 돌렸다. 결론은 ❌모든 경우를 탐색해

switch문의 특징인 해당하는 case가 실행되면 그 아래 case들이 전부 다 실행되는 걸 간과한 풀이였다. 기본적으로 해당 조건문의 case가 실행되고, 그 조건문 안에서 if문을 다시 실행해서 값을 비교하는데 이게 참이라면 return 1을 반환하고 종료되어야

트리를 순회하면서 최대한 많은 양을 수집하는 게 문제의 목적이다. 단 순회 도중에 현재까지 모인 양의 개수가 늑대의 개수와 같아지면 늑대가 양을 모두 잡아먹게 되기 때문에 주의해야 한다. 늑대가 양을 모두 잡아먹게 되면 그 이후 노드로는 이동할 필요가 없다. 그림의 파

입국 심사를 기다리는 사람이 최대 10억명이고 심사관은 최대 10만명이기 때문에 매 분에 대해서 어떤 심사관에게 심사를 받아야 최소가 되는지 완전 탐색으로 구하는 것은 시간초과가 발생한다. 우선 해당 조건을 활용하면 각 심사관의 최대 심사 시간은 10억이고 입국심사를

반드시 한 팀에서 최소 1명 이상 참석해야 한다.참석한 직원들의 매출액 합이 최소가 되어야 한다.팀장이 참석한 경우 팀원들은 참석해도 되고, 하지 않아도 됨. 둘 중 최소 값. 팀장이 참석하지 않는다면 반드시 최소 1명의 팀원은 참석해야 함.1번 직원부터 시작해서 트리