알고리즘

알고리즘 문제를 안푼지 한 달 이상 됐다. 마지막 프로젝트를 했을 때 안드로이드 앱을 만드느라고 코틀린을 썼고, 우테코 프리코스 공부를 하느라 자바를 배웠다. 내일 부스트캠프 ai 1차 코테가 있어 일단 급하게 다시 조금이라도 감을 잡으려고 예전에 풀었던 문제의 코드를

전형적인 투포인터 문제이다.

트라이 알고리즘을 찾다가 알게 된 문제지만 트라이를 쓰지 않고 쉽게 해결하는 방법이 있어 쉬운 풀이, 트라이 풀이 둘 다 정리할 예정이다. 참고로 프로그래머스에도 전화번호 목록이라는 아주 비슷한 문제가 있다.

스택2중 for문이나 큐로 푼 사람도 있으나, 스택으로 풀었다.

크레인 인형뽑기 게임2019 카카오 개발자 겨울 인턴쉽 1번 문제이기도 하다.스택내 코드프로그래머스 다른 사람 깔끔한 코드처음 풀었을 때 실수한 부분은 크레인이 내렸을 때 아무 것도 없으면 pick 함수의 결과로 None이 반환되는 것이다. 이 None에 대한 예외처리

프로그래머스 체육복이와 아주 비슷한 문제가 광주 인공지능 사관학교 선발 시험에 나왔었다. 당시에는 다른 방법이 생각나지 않아 그냥 그리디로 풀었다. 그리디프로그래머스에서는 난이도 1이라고 책정하고 있지만 아주 편하지는 않은 문제였다. 생각보다 긴 문제가 부담스러웠고,

문제 링크책: 파이썬 알고리즘 인터뷰의외로 실행 속도에 있어서 큰 차이는 아니지만, '정렬' 방식이 가장 빠르다. 파이썬의 정렬 함수는 팀소트를 사용하며 c로 잘 짜여졌기 때문이다.

트라이(Trie)는 검색 트리의 일종으로 일반적으로 키가 문자열인, 동적 배열 또는 연관 배열을 저장하는데 사용되는 정렬된 트리 자료구조이다.문제 링크여기서는 딕셔너리를 이용해 간결하게 구현한다. 트라이

백준 2210 공유기 설치이분 탐색크게 보면, 설치하는 거리를 최소1, 최대 마지막 집 - 첫 번째 집으로 두고, 이 설치거리를 이분 탐색으로 찾는 것이다. 만약 router_counter()라는 함수에서 count가 필요한 설치 개수인 N보다 더 많이 나오면 거리를

트리의 부모 찾기DFS예전에 풀었던 문제인데도 기억이 잘나지 않아서 트리를 구현해야하나 싶었다.우선 2차원 리스트로 연결되어 있는 것들은 다 이어준다.그리고 DFS를 돌리는데 시작점이 분명하므로, 그 시작점에 연결된 것들은 만약 parents에 부모가 저장되어 있지 않

유효한 팰린드롬주어진 string을 .lower()를 이용해서 소문자로 바꾼 다음 한 글자씩 alphanumeric이라면 (알파벳이거나 숫자)을 isalnum()을 이용해서, 따로 리스트에 저장한다. 만약 그 저장한 리스트와 뒤집은 리스트가 같은지 비교한다.리스트가 아

문자열 뒤집기리스트의 내장함수를 사용했다.투포인터를 이용한 풀이다

로그 파일 재정렬풀지 못했다. 그렇게 어려운 문제가 아닌데 지레 겁을 먹었다. 문제를 차근차근 읽자.문자로 구성된 로그가 숫자로 된 로그보다 앞에 와야하므로 로그가 숫자로 된 것인지 문자로 된 것인지 구분해서 저장한다. 문자로 된 로그는 로그의 식별자 뒷 부분을 우선으

가장 흔한 단어처음에는 그냥 공백을 기준으로 split하고, 정규식을 이용해서 alphanumeric한 것만 딕셔너리에 담고, 그 딕셔너리에서 가장 큰 value를 찾을 때마다 max_word 를 갱신하려했다. 하지만 문제에서 print(mostCommonWord("a

그룹 애너그램각 단어들을 정렬하여 같으면 애너그램 관계에 있는 것이다. 따라서 정렬한 단어를 키로하고, 원래 단어를 value에 추가하는 방식이다. TypeError: unhashable type: 'list' 가 떴었는데, 딕셔너리의 key는 변경되지 않는 값이 들어

가장 긴 팰린드롬 부분 문자열O(n^2) 방식으로 풀어서 시간 초과가 났다.max 함수를 사용할 때, key를 설정하여 비교 기준을 결정할 수 있다.

두 수의 합문제를 보자마자 떠오른 풀이 방법은 브루트포스였으나, 책의 풀이가 기억나서 in을 사용했다. 딕셔너리에 키를 숫자로, value를 인덱스로 잡았다.

빗물 트래핑예전에 이렇게 풀었지만 새로 푸니 아예 풀지를 못했다.현재 높이가 이전 높이보다 높을 때, 격차만큼 물 높이를 채운다. 이전 높이는 들쑥날쑥하기 때문에, 변곡점을 만날때마다 스택에서 하나씩 꺼내면서 이;전과의 차이만큼 물 높이를 채워 나간다. 백준 탑

세 수의 합3중 for 문을 이용한 풀이를 떠올렸으며, 이렇게 풀면 당연히 시간초과가 난다.정렬을 해서 투포인터로 푼다.왼쪽에서부터 하나씩 기준을 잡는다. 하나의 기준을 잡았으니 남은 오른쪽 부분에 대해 left와 right를 잡아서 해결해나간다. 단, 중복되는 요소들

배열 파티션 Imin을 이용하면 어짜피 가장 작은 값만 남으니 큰 값과 작은 값을 매칭시킬 필요가 없다. 가장 가까운 두 값을 매칭시키는 것이 total을 크게한다. 따라서 정렬을 한다음 두 쌍에서 왼쪽 값이 작으니 왼쪽값을 더하면 된다.

자신을 제외한 배열의 곱문제를 보자마자 전체 배열을 다 곱한 수를 구한 다음, 각 배열의 값마다 나눠서 값을 저장하면 되겠다라고 생각했으나 문제 제약 사항에 나누기를 쓰지 말라고 되어있었다.

주식을 사고팔기 가장 좋은 시점시간초과가 났다. O(n^2)이기 때문이다. O(n)으로 돌면서 지나온 값들에 대해 min_price들을 갱신해준다. 그리고 마찬가지로 현재 가격에서 min_price 를 뺸 값과 profit을 비교해 최대값을 갱신해준다.

팰린드롬 연결 리스트속도가 매우 느리게 나왔다.내 풀이와 마찬가지로 리스트를 이용하지만 초기 조건을 주었고, 또한 비교할 때 앞뒤로 하나씩 빼며 비교하였다.책 풀이 1에서 앞뒤로 뺀다는 점에 착안하여 덱을 쓰면 더욱 효율적이다.

역순 연결 리스트주어진 링크드리스트를 순서대로 따라가며 리스트에 숫자들을 저장해 놓는다. 그것을 뒤집어서 거꾸로 링크드리스트를 새로 만든다. 다음 노드 next와 현재 노드 node를 파라미터로 지정한 함수를 계속해서 재귀 호출한다. node.next에는 이전 prev

두 수의 덧셈두 개의 링크드 리스트를 리스트로 변환해서 숫자로 변환하고, 두 숫자를 더해서 다시 링크드 리스트를 만드는 풀이다.숫자형 리스트를 단일 값으로 병합하기실제 덧셈을 하듯이 뒤에서부터 더해가는 방식이다. 만약 carry가 발생하면 다음 게산에서 그것을 더해준다

페어의 노드 스왑처음에는 노드 자체를 스왑해야한다는 생각에 사로 잡혀서 값만 바꿀 생각을 하지 못했다.사실 값만 바꾸는 풀이는 정석적인 풀이가 아니다. 노드가 단순한 구조가 아니라면 복잡할 것이다.복잡해 보이지만 그림을 그려가며 이해하면 충분히 따라 갈 수 있다.

홀짝 연결 리스트홀수 번째 노드와 짝수 번째 노드가 아닌 홀수 값을 가지는 노드와 짝수 값을 가지는 노드로 문제를 잘 못 이해했다.두 칸씩 건너 뛰며 홀수는 홀수 번째 노드끼리만 엮고, 짝수는 짝수 번째끼리만 엮는다. 완성되고 나면 홀수 번째의 마지막과 짝수의 head

역순 연결 리스트 II리스트에 담아서 필요한 부분만 리버스를 하고 다시 그 리스트를 기반으로 링크드리스트를 만들어도 되겠지만, 그것이 정석 풀이는 아닌듯하여 책의 풀이를 참고 하였다. 어떻게 진행되는지 책의 그림을 통해 이해하는 것이 중요하다.

유효한 괄호스택을 대표하는 문제다.

일일 온도앞서 나왔던 빗물 트래핑, 백준의 탑과 아주 유사하다. 스택에서 지금 마주친 것이 더 높으면 스택을 아닐 때까지 비워낸다.

큐를 이용한 스택 구현큐 두 개를 이용한다. 첫 번째 큐에 push를 하면 첫 번째 큐의 기존에 있던 것들을 순서 그대로 두번째 큐에 옮긴 다음, 첫 번째 큐에 push를 한다. 그러고 옮겼던 것들을 다시 그대로 다 옮겨주면 push한 것이 가장 왼쪽에 있다. 조금만

스택을 이용한 큐 구현

해시 테이블 또는 해시 맵은 키를 값에 매핑할 수 있는 구조인, 연관 배열 추상 자료형(ADT)을 구현하는 자료구조이다해시 함수란 임의 크기 데이터를 고정 크기 값으로 매핑하는데 사용할 수 있는 함수를 말한다.로드 팩터(Load factor)란 해시 테이블에 저장된 데

중복 문자 없는 가장 긴 부분 문자열투 포인터까지는 생각했으나, 두 개의 포인터를 하나씩 옮기는 방식으로 구현했다가 실패함딕셔너리의 value로 index를 저장하는 것을 주목하자.

조합a,b,c,d가 있으면 a를 넣고나서, b부터 또 보는 방시깅다. 여기서 중요한 점은 result.append(elements)라고 하면, dfs가 종료되고 elements.pop()이 있기 때문에 result에 있는 elements도 영향을 받을 수 있다는 점이다

부분 집합

일정 재구성여러 일정이 있을 경우 사전 어휘순으로 방문해야하므로, 그래프를 만들고 나서 정렬을 해준다. 하지만 무조건 사전 어휘순으로 방문하려고하면, 방법이 나오지 않을 수도 있다. 따라서 A에서 갈 수 있는 곳이 여러 곳 있을 때, 사전 어휘순으로 하나씩 시도해보아야

코스 스케줄각 코스 별로 순환하는 사이클이 없는지 검사하는 것이다. 하지만 이렇게 풀면, 만약 순환이 아니더라도 복잡하게 서로 호출하는 구조로 그래프가 구성되어 있다면, 불필요하게 동일한 그래프를 여러 번 탐색하게 될 수도 있다. 따라서 한 번 방문했던 그래프느느 두

네트워크 딜레이 타임기본적인 다익스트라 알고리즘인, 전체 노드만큼의 길이를 무한대로 초기화 한후, 시작점은 0으로하고 진행하는 알고리즘만 알고 있었는데, 이 알고리즘은 큐를 이용함으로서 성능이 더 낫다. 처음에는 어떻게 graph에 있는 것이 최적의 시간인지를 보장하는

K 경유지 내 가장 저렴한 항공권K만큼 걸쳐서 갈 수 있으므로, 애초에 K를 주고 한번 이동할 때마다 하나씩 깎는다.

이진 트리의 최대 깊이큐를 이용해서 한 층의 자식 노드들을 모두 담는 것이다. 큐가 한번 돌 때마다 depth가 1씩 깊어진다. 주의해야할 점은 for 문 진입 시 부모 노드의 길이 len(queue)만큼만 반복되도록해서, for 반복문에서 자식 노드가 추출되지 않도록

이진 트리의 직경가장 긴 경로를 찾는 방법은 먼저 가장 말단, 즉 리프 노드까지 탐색한 다음 부모로 거슬로 올라가면서 각각의 거리를 계산해 상태값을 업데이트하며 누적해 나가는 것이다. 그림에서 보면 존재하지 않는 노드에도 -1이라는 값을 부여하는데, 존재하지 않는 자식

가장 긴 동일 값의 경로이진 트리의 직경 문제와 비슷하다. 다만, 리프 노드까지 DFS로 탐색해 내려간 다음, 값이 일치할 경우 거리를 추가하고 아니면 0으로 만드는 방식을 택한다.

이진 트리 반전 self.invertTree(root.right)가 먼저 실행되고, 그 다음 self.invertTree(root.left)가 실행된다. 가장 오른쪽인 노드 9로 가서 바꾼뒤 그 다음 6노드도 하위 노드들을 바꾼다. 그 다음 7노드 왼쪽 오른쪽을 바꾸

두 이진 트리 병합각각 이진 트리의 루트부터 시작해 합쳐 나가면서 좌,우 자식 노드 또한 병합될 수 있도록 각 트리 자식 노드를 재귀 호출한다. 만약 어느 한쪽에 노드가 존재하지 않는다면 존재하는 노드만 리턴하고 더 이상 재귀호출을 진행하지 않는다. 만약 양쪽 노드가

이진 트리 직렬화 & 역직렬화 > '이진 트리' 데이터 구조는 논리적인 구조다. 이를 파일이나 디스크에 저장하기 위해서는 물리적인 형태로 바꿔줘야 하는데, 이를 직렬화(Serialize)라고 한다. 반대는 역직렬화(Deserialize)다. 파이썬에서는 pickle이

균형 이진 트리높이 균형은 모든 노드의 서브 트리 간의 높이 차이가 1 이하인 것을 말한다.

최소 높이 트리최소 높이를 구성하려면 가장 가운데에 있는 값이 루트여야 한ㄷ다. 이 말은 리프 노드를 하나씩 제거해 나가면서 남아 있는 값을 찾으면 이 값이 가장 가운데에 있는 값이 될 것 이고, 이 값을 루트로 했을 때 최소 높이를 구성할 수 있다는 뜻이다. 마지막에

이진 탐색 트리(BST)는 정렬된 트리를 말하는데, 노드의 왼쪽 서브트리에는 그노드의 값보다 작은 값들을 지닌 노드들로 이뤄져 있는 반면, 노드의 오른쪽 서브트리에는 그 노드의 값과 같거나 큰 값들을 지닌 노드들로 이루어져 있는 트리를 뜻한다.정확히 리스트의 중앙이 부

이진 탐색 트리(BST)를 더 큰 수 합계 트리로자신보다 같거나 큰 값을 구하려면 BST에서는 자신을 포함한 우측 자식 노드의 합을 구하면 된다. 이는 중위 순회를 돌며 누적 값을 넣어주면 된다.

이진 탐색 트리(BST)합의 범위이진 탐색 트리는 왼쪽이 항상 작고, 오른쪽이 항상 크다는 것을 이용한다. 현재 노드 root가 L보다 작은 경우, 더 이상 왼쪽은 탐색할 필요가 없다.

이진 탐색 트리(BST) 노드 간 최소 거리이진 탐색 트리이므로 차이가 가장 적게 나는 것은 부모노드와, 왼쪽 서브트리 중 가장 오른쪽 그리고 오른쪽 서브트리중 가장 왼쪽의 것이다.스택을 이용한 DFS 풀이이다.

트라이 구현

팰린드롬 페어이 책에서 나온 문제 중 가장 어려운 문제 같다. 이해하려고 시간을 많이 투자했으나 아직도 완벽히는 이해하지 못했다. 입력을 'd', 'cbbcd', 'dcbb', 'dcbd', 'cbbc', 'bbcd'라고 가정하자. 이 입력 값을 뒤집어서 트라이를 만들

리스트 정렬병합 정렬을 이용한 풀이다. 런너를 이용해서 중앙을 찾는다. 내장함수를 이용한 풀이다.

원점에 K번째로 가가까운 점정렬기준을 lamda를 통해서 넣어주면 된다. x는 element이다. 어짜피 유클리드 거리를 구하는데 sqrt는 있으나마나여서 뺐다.

색 정렬이 문제는 다익스트라가 1976년에 제안한 네덜란드 국기 문제와 동일한 문제로 퀵 정렬의 개선 아이디어와도 관련이 깊다. i, k를 양쪽 포인터로 두고, j가 이동하면서 mid 값을 기준으로 스왑하는 형태다.

가장 큰 수처음에는 리스트를 역순으로 정렬하여 element들을 붙이면 된다고 생각했다. 하지만 리스트가 3, 30, 34, 5, 9일 때 정렬하면 9, 5, 34, 30, 3이 나온다. 가장 큰 값은 9, 5, 34, 3, 30 일때 나온다. String은 사전순으로

이진 탐색 이진 탐색 모듈을 이용했다.

두 수의 합 II투 포인터를 이용한 풀이다.

2D 행렬 검색 II첫 행의 맨 뒤 요소를 택한 다음, 타겟이 이보다 작으면 왼쪽으로, 크면 아래로 이동하게 하는 방법이다. 행렬은 왼쪽에서 오른쪽, 위에서 아래로 오름차순으로 정렬되어 있기 때문에, 작으면 왼쪽, 크면 아래로 이동하면 원하는 위치에 어렵지 않게 도달할

해밍 거리해밍 거리 (Hamming distance)는 두 정수 또는 두 문자열의 차이를 말한다. 문자열의 경우 해밍 거리는 다른 자리의 문자 개수가 되며, 이진수의 경우 다른 위치의 비트 개수가 된다.

1비트의 개수 책 풀이 책 풀이 2

풀이 1 풀이 2 풀이 3

UTF-8 검증초기에 문자를 표현하던 대표적인 방식은 ASCII 인코딩 방식으로, 1바이트에 모든 문자를 표현했다. 게다가 1비트는 체크섬으로 제외하여 7비트, 즉 128 문자를 표현했다. 하지만 이는 부족했고, 이를 해결하기 위해 2~4바이트 공간에 여유있게 문자를

최대 슬라이딩 윈도우시간초과가 났다. 책에서 나온 풀이다. 큐를 이용해서 최적화한 것이다. 하지만 이것 역시 시간 초과가 났다. 알고리즘 시각화(q에는 값이 아닌 인덱스가 들어간다. 큐의 가장 왼쪽에는 max 값의 인덱스가 들어가있다. 만약 새로 만난 숫자가 크다면 그

부분 문자열이 포함된 최소 윈도우코드만 봐서는 직관적으로 이해가 가지 않는다. A에서 시작해서 필요한 ABC가 다 생기면 A를 제외하고 B부터 시작해서 다음 A가 있는 곳까지 찾고.. 반복이다. missing이 0이되면, 즉 필요하누 문자의 개수가 0이 된다면 이제 왼

키에 따른 대기열 재구성각각의 사람은 (h,k)의 두 정수 쌍을 갖는데, h는 그 사람의 키, k는 앞에 줄 서 있는 사람들 중 자신의 키 이상인 사람들의 수를 뜻한다.우선순위 큐 자체가 매번 그때그때의 최소 또는 최댓값을 추출하기 때문에, 그리디에 자주 쓰인다.우선

태스크 스케줄러꽤 어려웠던 문제다. 핵심은 많이 남은 순대로 n에 맞게 뽑는 것을 반복하면된다. most_common은 가장 개수가 많은 아이템부터 출력하는 함수이다. 사실상 최대힙과 같은 역할을 하고, subtract(task)를 통해서 1개씩 개수를 줄여나간다. C

주유소전체 기름의 양이 전체 비용보다 클 경우 반드시 전체를 방문할수 있는 출발점이 존재한다. 원래는 여러 곳이 될 수 있겠지만 이 문제에는 출발점이 유일하다는 제약이 있으므로, 여기서는 반드시 한 군데만 존재하게 된다. 비용이 더 큰 경우는 초기에 예외처리를 해준다.

분할: 문제를 동일한 유형의 여러 하위 문제로 나눈다.정복: 가장 작은 단위의 하위 문제를 해결하여 정복한다.조합: 하위 문제에 대한 결과를 원래 문제에 대한 결과로 조합한다.과반수 엘리멘트쪼갠 다음 과반수 후보군에 해당하는 엘리먼트만 리턴하면서 위로 올려준다. 지금은

괄호를 삽입하는 여러 가지 방법\*, -, + 연산자가 등장할 때 좌/우 분할을 하고 각각 계산 결과를 턴한다. eval() 함수는 문자열을 파이상하고 파이썬 표현식으로 처리해주는 (evaluate) 역할을 한다.append() vs extend()리스트에 또 다른 리

최대 서브 배열dp 배열을 만들고, 상향식으로 풀었다. dpi = i까지 고려했을 때 가장 큰 sum이다. 만약 이전의 것이 음수이면 굳이 dpi-1을 더할 필요가 없다.

2016년a월 b일이 며칠째인지를 계산한다음, 1월1일에서 빼서 나머지를 이용했다.

프로그래머스 - 기능개발큐를 이용해서 실제로 완성도가 100이 넘으면 빼는 방식으로 구현했다.

프로그래머스 - 큰 수 만들기처음에는 감을 못잡고 있다가, 질문게시판에서 스택을 이용하면 된다는 힌트를 보고 풀었다. 그리디에는 정해진 것이 없다. 그리디안에서 다른 자료구조와 알고리즘을 쓸 수도 있다. 사용한 반례들이다. 처음에는 ("7777777", 2) 같은 경우

프로그래머스 - 다리를 지나는 트럭처음에 나는 bridge_length 길이를 가지는 리스트를 만들어놓고, 한번씩 실제로 truck들을 움직이는 시뮬레이션으로 구현했다. 하지만 그렇게하니 답이 1 차이로 맞는 것도 있고 틀리는 것도 있었다.이 풀이는 q를 이용해서 br

단어 뒤집기 2난이도가 실버3은 넘는 것 같다. 꽤나 나에게는 까다롭게 느껴졌다. 이 풀이는 우선 "<"를 기준으로 split하여서 그 split된 것에 ">"이 있으면 한번더 스플릿해줘서 태그와 태그아닌 것을 각각 다르게 처리하고, ">"이 없으면 태그가 아니니

백준 쇠막대기처음 봤을 때는 스택을 어떻게 응용해야하는건지 떠오르지 않았었다. 스택 문제가 직관적으로 스택을 써야겠다고 떠오르지 않는 문제가 꽤 있는 것 같다. 풀이는 ")"이 나오는 경우 직전에 "("가 나오면 레이저로 자르는 것이고, 그것이 아니라면 그냥 쇠 막대기

백준 - 오큰수백준 - 탑 리트코드 - 빗물 트래핑과 근본적으로 비슷한 문제이다.스택에 인덱스를 저장하고, for loop을 돌며, 해당 값이 stack의 값보다 크면 스택을 비워내며, 값을 저장하는 방식이다.

백준 - 오등큰수백준 오큰수 문제와 큰 차이가 없다. 다만 Counter를 써서 값을 한번 꼬아준 것 뿐이다.

백준 - 후위 표기식2후위표기식 ab+ 는 a+b로 계산된다.123\*+45/-16+45/-745/-7 0.8 -6.2이런식으로 연산자를 만나면 앞의 두 피연산자 두 개를 가지고 연산을 하고 스택에 다시 넣으면된다.

프로그래머스 - 위장다른 것은 다 통과하는데 1번 테케에서 시간초과가 걸렸다.하의 2개, 상의 3개가 있을 때잘못된 풀이combinations으로 하의만 입을때, 상의만 입을때, 둘다 입을때 경우의 수를 구한다맞는 풀이(하의 2개+안입은 경우) \* (상의 2개 + 안

프로그래머스 - 가장 큰 수일반적인 정렬로 풀려고 했다. 숫자로 비교해서는 당연히 안되고, 문자열로 바꿔서 정렬해도 되지 않는다. 3, 30, 34, 5, 9 같은 경우 문자열로 바꾼다음 내림차순 정렬을 하면 "9534303"이 나온다. 답은 "9534330"이다. x

프로그래머스 - 소수 찾기에라토스테네스의 체를 이용해서 풀었다.

프로그래머스 - 2 x n 타일링i번째 타일을 만드는 방법은 i-1번째 만드는 방법에서 세로로 타일을 하나 붙이거나 i-2번째 만드는 방법에서 가로로 타일을 두개 붙이는 것이다.

프로그래머스 - 2020 KAKAO BLIND RECRUITMENT 문자열 압축문자열을 하나씩 자를지, 두개씩 자를지 완전탐색을 한다. cut_string함수는 몇 개씩 자를지 매개변수로 받아서 list로 돌려주는 함수이다. index error가 발생하지 않게 마지막

프로그래머스 - 짝지어 제거하기스택을 이용해서 스택의 맨 위에 있는 것과 값이 같으면 스택에서 제거해준다. 스택에는 이 과정을 이미 거쳐온 것이기 때문에 같은 값이 연속해서 2개 들어 있을 수 없다는 전제가 깔려있다.

프로그래머스 - 가장 긴 팰린드롬 \[알고리즘] 가장 긴 팰린드롬 부분 문자열 파이썬 알고리즘 인터뷰 책에 나왔던 리트코드 문제와 완전히 동일하다.

프로그래머스 - 수박수박수박수박수박수?

프로그래머스 - 2021 KAKAO BLIND RECRUITMENT 신규 아이디 추천처음에는 3단계에서 단순히 new_id = new_id.replace("..", ".") 로 했다가 틀렸다. ".."이 안남아있게 계속 해줘야한다.정규식을 이용한 훨씬 간결한 풀이다.

프로그래머스 - 단어 변환

프로그래머스 - N으로 표현5를 이어 붙여 만든 조합을 제외하고 생각해 보면, N이 2인 숫자 조합을 만들기 위해서는 N이 1일때 경우의 수와 N이 1일때 경우의 수를 각각 사칙연산했다.N이 3인 숫자 조합을 만들기 위해서는 N이 1일때 경우의 수와 N이 2일때 경우의

프로그래머스 - 프린터직접 시뮬레이션한 방식이다. 다만 deque으로 element가 빠지고 추가되므로 location으로 주어진 것도 위치가 바뀐다. 따라서 똑같이 동작하되, 처음 주어진 location 정보를 가지고 있는 deque을 만들었다.deque 대신 que

프로그래머스 - 디스크 컨트롤러 import heapqimport functoolsimport itertoolsimport reimport mathimport bisectdef solution(jobs): cur_time = 0 heap =

프로그래머스 - 피보나치 수DP의 연습문제이다.

백준 - 01타일유사한 dp문제들을 많이 풀어봤길래 쉽게 풀었다. 하지만 dp 문제를 오랜만에 풀어서 그런지 정확한 근거를 충분히 세우지 못해 찾아봤다. 해설먼저 길이가 i인 수를 만든다고 생각해보자. 그러면 사용할 수 있는 숫자 카드는 00과 1이다. 즉, 이전에 만

백준 - 영화감독 숌브루트포스를 이용하면 쉽게 풀 수 있는 문제다. 브루트포스 범위를 잡을 때는 충분히 잡자.

프로그래머스 - 같은 숫자는 싫어스택 구조를 이용하면 간단하게 풀 수 있다.

프로그래머스 - 구명보트처음에는 대충 생각하고 역순으로 정렬한 다음, 하나씩 꺼내서 비교하는데 무게가 초과하면 새 보트를 꺼내는 식으로 구현했다. 하지만 그렇게하면, 낭비되는 공간이 있고, 그 낭비되는 공간에 몸무게가 작은 사람들을 넣을 수 있다. 따라서 투포인터로 큰

프로그래머스 - 네트워크 def dfs(i, visited, computers): visitedi = True for k in range(len(computersi)): if computersi == 1 and not visitedk:

프로그래머스 - 입국심사이분탐색 알고리즘을 푼지가 오래되어 구조를 다른 것 안보고 떠올리는데 시간이 조금 걸렸다. 탈출 조건을 어떻게 줘야하나 고민했는데 만약 답을 충족한 상태라면, 그 답을 일단 저장해놓고, 범위를 줄여가며 계속 탐색하는 방식으로 진행하면된다.

프로그래머스 - 등굣길오랜만에 2차원 리스트를 선언해서 잘 생각나지 않았다. 이번에 숙지해두자.dp 문제를 오랜만에 풀어서 조금 해맸다. 이 그림을 통해서 왜 dpi = dpi-1 + dpi이 되는지 알 수 있다.출처처음에 MOD 연산을 해주는 것을 깜빡하고 냈는데 테

프로그래머스 - 카펫 def solution(brown, yellow): total = brown + yellow for row in range(3, int(total\*0.5)+1): if total % row == 0:

프로그래머스 - 이중우선순위큐 import heapqdef solution(operations): heap = \[] for operation in operations: cmd, num = operation.split() if

프로그래머스 - 멀리 뛰기dp 중에서도 제일 기본적인 문제 수준이다.

프로그래머스 - 소수 찾기에라토스테네스의 체를 미리 만들고, 가능한 순열의 수를 완전탐색해가며 소수인지 아닌지 확인한다. 이미 방문한 수라면 visited로 걸러낸다.사실 완전탐색이라고 문제 분류가 되어있지 않았다면 이렇게 풀 시도를 하지 않았을 것이다. 돌려보니 60

2020 카카오 인턴십 - 키패드 누르기\*은 10으로 0은 11로 비슷하지만 각 숫자의 행과 열의 위치를 미리 계산해서 dict로 저장함으로서 \*, 0, #을 치환하는 과정이 없어졌다.

프로그래머스 - 문자열 내 마음대로 정렬하기파이썬의 내장 정렬은 팀소트를 사용하고, 안정 정렬이다. 즉 동일한 값을 가지면 입력 순서를 유지한다는 뜻이다. 참고로 퀵 소트는 불안정 정렬인 단점이 있다. 같은 문자열이 여럿 일 경우, 사전순으로 앞선 문자열이 앞쪽에 위치

프로그래머스 - JadenCase 문자열 만들기(프로그래머스 - JadenCase 문자열 만들기)복잡한 문제는 아니었는데 조건이 충분히 주어지지 않았다. 맨 앞에 공백이 오는 경우 문자로 처리하는지 여부 등이 참에 split에 대해 정리를 했는데

프로그래머스 - H-index가능한 H-index는 0부터 max(citations)이니 이분탐색으로 풀었다.count_h는 mid번 이상 인용된 논문의 개수를 반환하는데 정렬되어있으니 citationsi가 mid이상인 순간 그 뒤의 것은 모두 mid 이상인 점을 이용

프로그래머스 - 가장 큰 정사각형 찾기기본적으로 가장 큰 h가 무엇일지 이중탐색으로 찾아간다. 이중 탐색으로 찾을 때, h에 대해 좌표 기준점을 옮겨 다니면서 만족하는 크기가 있으면 true를 리턴하는 방식이다. 하지만 이것은 for문이 5중 for문이다.출처: htt

프로그래머스 - 다음 큰 숫자

2018 KAKAO BLIND RECRUITMENT - \[1차 캐시]비교적 쉬운 문제였으나 사소한 조건인 대소문자를 구분하지 않는다는 것을 놓쳐서 처음 통과하지 못했고, 그 다음은 cache hit를 했을 때, 그것을 제일 최신 것으로 갱신해줘야한 다는 것을 몰라서

백준 - 트리 순회트리를 구성하는데 여러가지 방법이 있겠지만, 이렇게 Node 클래스를 만들고 Node의 data 를 key로 하는 딕셔너리로 트리를 유지하는 것도 괜찮은 방법이다.

프로그래머스 - 조이스틱세로로 움직였을 때 최단 거리를 찾고, 가로로 움직였을 때의 최단거리도 구해야하는 문제다. 세로로 움직이는 명백히 그리디이고 목표물까지 위로가는 경우, 아래로 가는 경우 두 가지가 있으니 그 중 minimum을 취해야한다.가로로 가는 경우 오른쪽

2019 카카오 개발자 겨울 인턴십처음에는 튜플과 집합의 차이점을 인지하지 못해서 통과하지 못했다. 튜플은 순서가 중요한데 집합에는 순서가 바뀔 수 있다. 따라서 순서가 바뀌지 않는 1개짜리 집합에서 시작해서 하나씩 잡아가야한다. 정규식과 Counter를 이용해서 우아

프로그래머스 - 땅따먹기그리 어렵지 않은 문제다. 직전 위에 행에서 같은 열이 아닌 값중 가장 큰 값을 더해주면 된다. 코드를 쓰다 알게된 것인데 2차원 배열일때는 max(max(arr))를 써주면 2차원 배열에서 가장 큰 값이 나온다.슬라이싱을 이용할 경우, 슬라이싱

프로그래머스 - 게임 맵 최단거리기본적인 BFS 문제이다.

프로그래머스 - 이진 변환 반복하기bin 함수를 이용하면 쉬운 문제였다.

2019 KAKAO BLIND RECRUITMENT - 오픈채팅방uid는 바뀌지 않는다는 것을 이용하여 uid를 기준으로 로그를 남기고, uid를 키로, 닉네임을 값으로하는 딕셔너리로 정보를 저장한다. 마지막 로그에 대해 닉네임을 찾아서 출력하면된다.

프로그래머스 - 정수 삼각형 def solution(triangle): for i in range(1, len(triangle)): for j in range(len(trianglei)): if j == 0:

프로그래머스 - 섬 연결하기처음에는 다익스트라로 풀려고했다가 실패했다. 다익스트라는 한 정점에서 다른 모든 정점들에 대해 최소 비용을 알려주는 것이다. 여기서는 전체 간선이 최소화되어야한다. 프림과 크루스칼 알고리즘 간단 차이프림과 크루스칼 시간 복잡도프림을 이용한 풀

프로그래머스 - 줄 서는 방법시간초과가 난다. 20!이다.n명을 총 줄세우는 방법은 n!입니다. 예를 들어서 위와 같은 3명을 줄을 세우면 3!가지가 전체 줄을 서는 경우의 수입니다. 잘 살펴보면, 각 사람들이 첫 번째에 있을 경우 2가지입니다.(1번 사람이 첫 번째에

백준 - 두 수의 합이분 탐색이랑 다르게 조건이 left < right이다. left <= right가 아니고.

백준 - 두 용액min_val은 최소 차이이다. 만약 두 용액의 차이가 최소 차이보다 작으면 최소차이를 갱신해주고, min_left, min_right도 갱신해준다. 다음 턴에서 만약 이 두 용액의 합이 양수 였으면 right -=1을 하고 음수였으면 left +=1을

프로그래머스 - 점프와 순간 이동역으로 현재위치에서 0까지 도달하는데 얼마나 걸리나 계산하면 된다. 출처: https://velog.io/@ju_h2/Python-%ED%94%84%EB%A1%9C%EA%B7%B8%EB%9E%98%EB%A8%B8%EC%8A%A4

프로그래머스 - 거스름돈백준 - 동전 1과 같은 문제인데 예전에 백준에서는 풀었던 문제인데 이번에 풀지 못했다.

백준 - 집합의 표현분리 집합(Disjoint Set)이란 교집합이 존재하지 않는 둘 이상의 집합을 말한다. 분리 집합은 교집합을 허락하지 않기 때문에 서로 구분되어야 하는 데이터 집합을 다룰 때 유용하게 쓰인다.분리 집합을 만들었으면 연산을 해야 한다. 분리 집합의

프로그래머스 - 기지국 설치N은 최대 200,000,000이고, w는 최대 10,000이니 당연히 실제 시뮬레이션을 하면 효율성 통과를 못한다. stations가 주어지니, 전파가 닿지 않는 곳이 몇개씩 있는지 계산해서 house_counts에 저장한다. 그다음 각 h

프로그래머스 - 스티커 모으기(2)원형이라고 해서 복잡하게 생각했는데, 그냥 2차원 dp를 선언하여 첫 번째 스티커를 때는 경우와 때지 않는 경우로 구분해서 생각하면 된다.

프로그래머스 - 베스트앨범

프로그래머스 - 여행경로파이썬 알고리즘 인터뷰와 리트코드의 일정 재구성과 동일한 문제이다. 하지만 풀이가 정확히 기억나지 않아 다소 비효율적으로 풀었다.애초에 딕셔너리에 넣을 때 sort 해서 넣으면 나중에 하나씩 정렬해줄 필요가 없다. 경로가 끊기는 경우가 없기 때문

프로그래머스 - 단속카메라처음에는 어떻게 접근해야할지 감이 안왔다. 그리디 문제라는 것을 몰랐으면 못풀었을 수도 있을 것 같다. 우선 routes를 reverse로 정렬해서 출발점이 가장 오른쪽에 있는 순서대로 정렬을 한다. 그리고 맨 처음 카메라는 sys.maxsiz

프로그래머스 - 가장 먼 노드일반 다익스트라를 사용하면 풀리는 문제다.

프로그래머스 - 숫자의 표현규칙을 찾으려다가 약수를 이용하면 된다까지는 접근했으나 더 나아가지 못했다.그냥 문제 그대로 구현만 해도 되는 문제였다. 하지만 맨 처음에는 dp인가 생각했고 그 다음에는 약수로 규칙을 구하려다 보니 단순 구현을 생각하지 못했다. 제한 사항에

프로그래머스 - 배달다익스트라를 heap을 이용해서 더 효율적으로 구현해봤다.

프로그래머스 - 최솟값 만들기직관적으로 서로 다르게 정렬해 큰 것과 작은 것을 곱하는 방식을 생각했다. 문제를 푼 이후에 증명을 간단하게 해봤다.$$A = a_1, a_2, ..., a_n \\B = b_1, b_2, ..., b_n\\a_1 < a_2 <

프로그래머스 - 최고의 집합곱을 최대로 만들려면 최대한 중앙에 있는 값들을 서로 곱해야 최대가 된다는 점을 이용했다. (표준 편차가 작아야한다. 즉 집합 원소들 간의 차를 최소화해야 한다.). 예를 들어 S가 9이고 n이 3이라면 3,3,3이어야 한다. 중앙에 있는 값

프로그래머스 - 야근 지수파이썬에서 내장함수 heap은 min heap이므로 음수를 곱해서 max heap으로 사용했다. 남은 works에서 가장 큰 값들을 줄이면 된다.

프로그래머스 - N-Queen백트랙킹인 것은 생각했지만, 같은 대각선에 있는지 구분하는 규칙이 생각나지 않았다. 출처: https://chanhuiseok.github.io/posts/baek-1/

프로그래머스 - N개의 최소공배수x와 y의 최소공배수는 x \* y / (x와 y의 최대 공약수)이다.

백준 - 가장 큰 정사각형프로그래머스 - 가장 큰 정사각형 찾기와 아주 유사하며 스타트업 코딩 페스티벌 1차 3번 문제와도 거의 일치한다. 스코페에서는 완전탐색을 했는데도 통과했지만 효율성을 생각해서 dp로 푸는 것이 맞다. 프로그래머스에서 풀고 풀이를 봤는데, 풀이가

백준 - 사회망 서비스 (SNS)트리에서 dp를 활용하는 문제는 예전에 카카오에 나온적이 있다고 들었는데, 이번 기회에 풀어보게 되었다. 이 문제는 '최대 독립 집합' 개념과 맞닿아 있다. 어떤 그래프 G의 정점들의 집합을 S라고 하자. 이러한 S의 부분 집합 S\`을

백준 - 트리의 독립집합dp1은 자기 자신을 포함했을 때 최대 값이고, dp1은 포함하지 않았을 때이다. dp1은 자기 자신을 포함하므로 자식을을 포함할 수 없으니 dp1의 자식들을 더해주면 된다. dp1은 자기 자신을 포함하지 않으므로 자식들을 포함할 수도 있고 안을

백준 - 내리막길예전에도 다른 사람의 풀이를 보고 풀었더니 풀지 못했다. 이번에 확실히 정리하자.상하좌우에 현재 자신의 위치보다 낮은 지점이 있을 경우, 해당 지점들이 갖는 경로의 수의 합을 현재 위치에 합한다.한 번 방문해서 경로의 수를 갖고 있다면 그대로 반환하고,

프로그래머스 - 숫자 게임프로그래머스의 체육복 문제와 비슷한 문제다. 정렬해서 더 큰 값 중 가장 작은 값을 매칭시키면 된다. 질 수 밖에 없다면 가장 안아까운 패를 버리면서 지는 전략이기 때문에 그리디이다.

프로그래머스 - 도둑질

프로그래머스 - 행렬의 곱셈(프로그래머스 - 행렬의 곱셈)행렬 곱셈의 원리를 그대로 구현하면 되는 문제이다.

백준 - 좋은 수열최대 길이가 80이여서 충분히 백트랙킹으로 풀 수 있고, 매번 새로운 깊이로 들어갈때 탐색을 하고 들어갈 수 있다. 탐색하는 방법은 완전 탐색으로 반복되는 구간이 있는가 없는가 검색하는 것이다.

프로그래머스 - 예상 대진표직접 시뮬레이션 하면서 구현한 것이다. 출처: https://mungto.tistory.com/205

백준 - 1,2,3 더하기재귀 연습을 하기 위해 재귀로 풀어보았다. 결국 n을 1,2,3의 합으로 나타내는 방법은 n-1을 나타내는 방법에서 1을 더하는 것, n-2를 나타내는 방법에서 2를 더하는 것, n-3을 나타내는 방법에서 3을 더하는 것이다.모처럼 자바로 문제

백준 - 피보나치 수

백준 - 1로 만들기

백준 - 치킨 쿠폰더 이상 쿠폰을 얻을 수 없을 때까지 재귀를 호출하는데, 쿠폰은 현재 쿠폰에서 k로 나눈 나머지와 새로 받은 쿠폰이고, 주문량은 이때까지 주문량에서 이번에 시켜먹은 양이다.EOF를 다루는 문제다. 그냥 readLine으로 읽고 null이면 종료하면 된

백준 - 2xn 타일링long을 Long이라고 적었다가 에러가 났었다. Long형 배열을 선언한뒤 출력을 해보니 전부 null이 들어가있었다. 이유를 찾아보니 long은 primitive type이고 Long은 Wrapper class이기 때문이었다.

백준 - RGB 거리자바에는 2차원 배열을 한꺼번에 초기화 하는 방법이 없다. 각 row별로 돌면서 Arrays.fill을 이용해야 한다.1차원 배열에서 최소값을 찾는 방법 중 stream을 이용하면 편하다.

백준 - 일곱 난쟁이예전에 브루트포스로 풀었었는데 백트랙킹으로 풀어보았다. ArrayList를 사용했다. ArrayList는 List 인터페이스를 상속받은 클래스로 크기가 가변적으로 변하는 선형리스트이다. ArrayList는 객체들이 추가되어 저장 용량을 초과하면 자동

백준 - 블랙잭2진법 사용하듯이 해당 인덱스의 수를 취하는 경우, 취하지 않는 경우로 나눠서 backTracking을 진행하였다.

백준 - 계단 오르기dpi를 i번째를 밟았을 떄 i번째까지 최고 점수라고 정의했다. 그러면 dpi = Math.max(dpi-2, dpi-3 + arri-1) + arri가 된다. dpi-1을 사용하지 못하는 이유는 dpi-1의 값이 두번 연속으로 밟아서 얻은 값일 수

백준 - 포도주 시식처음에는 dpi = i번째를 마셨을때 i번째까지 최대값이라고 했다가 틀렸었다. 1000, 1000, 1 같은 경우 세번째는 1001 밖에 되지 않는다. 이렇게 되면 맨 마지막에 최대값이 들어가있다고 장담할 수 없다.처음 dp가 0으로 초기화 되어있고

백준 - 괄호의 값다소 복잡하게 풀었다. 우선 전체 스트링에 대해 for문을 돌면서 stack이 맞아떨어져서 올바른 괄호열이면 그만큼 구분해서 재귀에 들어가게 했다 (단 양측의 괄호는 제거하고 괄호에 따라 점수를 곱한다). 그리고 나머지 부분에 대해 또 재귀를 돌리고해

백준 - 하노이 탑 이동 순서로직은 비교적 간단하다. n개의 원판이 있을 때 우선 n-1개의 원판을 2번으로 옮긴뒤 맨밑 원판을 3번으로 옮기고, n-1개의 원판을 3번으로 옮기는 것이다. 처음에는 Stack을 List로 저장해서 쓰려고 했으나 저장은 되는데, List

백준 - 퇴사처음에는 어떻게 재귀로 풀까 고민하다가 N의 길이가 15가 최대인 것을 보고 백트랙킹으로 풀었다. 해당 날짜에 들어갔다면 경우의 수는 두 가지이다. 그 날에 일을하고, 걸리는 시간만큼 건너뛰거나, 그날 일은 건너뛰고 다음날부터 또 결정하거나.

핵심 로직은 결국 Combination을 구현하는 것 같은데 메모리 초과가 나서 통과하지 못했다.풀이 참고 블로그

백준 - 차이를 최대로처음에는 정렬을해서 풀어야하나 생각했다. 하지만 양수와 음수가 섞여있어 그렇게 풀면 쉽지않다. 또 N의 범위가 8까지로 매우 작은 것을 보고 힌트를 얻어 브루트포스로 풀었다.

백준 - 미로 탐색자바로는 처음 풀어봤는데 파이썬의 동시할당이 되지않아 코드가 조금 길어졌다. 파이썬의 큐와는 달리 큐에 뭐가 들어갈지 알려줘야한다.

백준 - 섬의 개수dfs를 한번 돌면 한 섬을 다 표시하므로 전체에 대해 dfs를 돌려주면된다. 다만 방향이 4방향이 아니라 8방향이다.

백준 - 유기농 배추백준 - 섬의 개수 문제와 거의 동일하다.

백준 - 연구소효율성이 좋지 않았다. 이유는 combination 부분이었다.combination 부분을 이진법하는듯 방법으로 바꾸었다. (탈출조건에 처음에는 그냥 curPos >= emptySpaces.size() 라고 했다가 틀렸다. curPos가 마지막에 넘었더라

백준 - 괄호스택을 사용하지 않고 int로 스택을 대체해봤다.

백준 - 쇠막대기

백준 - 연결 요소의 개수본질적으로 백준 - 섬의 개수 문제와 동일하다.그래프를 코드로 나타내는데 두 가지 방법이 있는데 하나는 이차원 배열을 사용하는 것이고 하나는 리스트를 담는 배열을 이용하는 것이다. 리스트를 담는 배열을 만드는 것에도 익숙해지자.

백준 - 바이러스백준 - 연결 요소의 개수와 동일한 문제다.

백준 - 로마 숫자 만들기

백준 - 로또

백준 - 연산자 끼워넣기

백준 - 캠프 준비처음에는 조건을 확인하는 부분에 습관처럼 return을 넣어서 탈출하게 했다. 하지만 1번과 2번 문제를 선택하는 방법에 이어 1, 2, 3을 선택하는 방법도 있을 수 있다. 따라서 여기서 return을 하지 말아야한다.통과 못한 내 풀이. 왜 통과

백준 - 효율적인 해킹주어진 입력의 방향을 바꿔서 그래프를 만들었다. 그래서 1이 몇개의 컴퓨터를 지나냐 이런식으로 했고, 그 정답은 HashMap에 저장했다.크게 바뀐건 없다. 방향을 원래 입력대로하고, 지나갈때마다 arrnode++해줬다. 하지만 이 코드도 통과했지

백준 - 탑

오랜만에 파이썬으로 문제를 풀어보려하니 낯설다.

백준 - 벽 부수고 이동하기예전에 푼 기억이 있어 30%는 기억에 의존하여 풀었다. 원래 3차원 배열을 이용해서 row벽 부수기 여부 = count로 기록하려고 했는데 자바에서 3차원 배열을 다루는데 익숙하지않아 visited1 = 벽 부술 횟수가 하나 남은 상태에서

백준 - 아기 상어처음 문제 설계를 잘못하여 시간을 많이 잃었다. 처음에는 dx와 dy의 순서를 이렇게 정의하여 문제가 풀릴 줄 알았다. 하지만 현재 위치를 기준으로 오른쪽으로 2칸 떨어진 곳에 대상 물고기가 있고, 왼쪽 아래에 물고기가 있다고 가정해보자. 그러면 가장

백준 - 사다리 조작

백준 - 가르침백트랙킹 중에서도 좀 더 세밀하게 문제 조건을 따져야하는 문제다. 처음에 꼭 배워야 하는 알파벳 다섯개가 주어진다. 그래서 K가 4개이하면 바로 종료 시켜야한다. 또한 문자열 검증을 할때도 앞뒤 4개씩 자르고 하면 속도가 좀 더 빠르다.

백준 - 소풍 내 풀이 > 처음에는 문제를 제대로 이해하지 않아 에러가 났다. 즉 데려갈 K명의 학생들은 모두 서로가 직접적으로 연결되어있어야하는데 중간 친구를 통해 연결되는 것도 된다고 생각했다. > 두번째에는 충분히 가지치기를 해주지 않아 메모리 에러가 났다.

백준 - 사다리 조작https://buddev.tistory.com/23일반적인 2차원 배열은 칸을 나타내는데 주어진 문제에서는 칸이 아닌 행과 열의 교차점이어서 그 부분이 문제를 접근하는데 많이 헷갈렸다. 문제의 searchOddNum 함수는 본인이 내려갈

백준 - 연구소 2결국 바이러스를 놓을 수 있는 곳을 백트랙킹으로 구하고 그안에서 조건을 만족하면 BFS로 시뮬레이션을 해서 걸리는 시간을 구하면 된다.백트랙킹 부분에서 설계를 잘못하여 에러가 많이 났다. 이렇게 2진법스러운 백트랙킹을 했더니 안됐다. 이유가 뭘까

백준 - 동전 1예전에 풀어봤지만 그때도 풀이를 찾아보고 풀었거나 기억에 의존해 풀었기에 이번 기회에 정리를 한다.N가지 종류의 동전으로 K원을 만드는 방법은 두 가지다.1) N번째 동전 없이 N-1가지의 동전으로 K를 만들기2) N가지 동전으로 K - coinsn의

백준 - 동전 2점화식을 어떻게 세우냐가 관건이었다. dpk = k원을 만드는데 드는 동전의 최소 개수 = Min {dp\[k-coin0]+1, dp\[k-coin1]+1, ...}

로봇 청소기

백준 - 이동하기dpi를 위치 i에서 가질 수 있는 최대 사탕 개수다. 그렇다면 dpi = Max(dpi-1, dpi-1, dpi)+graphi다. 다만 인덱스가 벗어나지 않는지 체크해줘야한다.

백준 - 평범한 배낭처음에는 이중 for문에서 j를 0부터 시작해서 K까지 돌게했다. 그랬더니 에러가 났는데 그 이유는 배낭에는 물건이 하나씩 있는데, 예를 들어 무게 4에 행복 8짜리가 있으면 무게 4일때 8을 만들고 무게 8일때 또 카운팅하여 무게 16을 만들기 때

백준 - LCS예전에 풀었던 문제인데 풀지 못했다. 점화식 설명dpi는 str1의 i번째까지와 str2의 j번째까지 비교했을 때 가장 긴 수열이다. Case1: 만약 str1의 i번째 문자와 str2의 j번째 문자가 다르다면 길이는 dpi-1와 dpi중 최대 값이다Ca

백준 - 욕심쟁이 판다그냥 DFS를 다 돌리면 시간 초과가 난다.이번에도 역시 점화식이 중요했는데, dpi를 (i,j)에서 출발해서 갈 수 있는 루트 중 가장 긴 루트의 길이라고 하자. 그러면 이미 dpi는 최적해라는 것이 보장되었기 때문에, 다른 지점에서 길을 찾다가

백준 - 트리와 쿼리기초적인 트리 dp문제다. 그래프를 만들고 dp 배열을 만드는데 dpi는 i를 루트로 하는 서브트리에서 루트를 포함한 정점의 개수라고 정의했다. 그러면 리프노드에서 1을 반환하면 된다.

백준 - 우수 마을거의 다 풀었는데 점화식에서 사소한 실수를 했다.특정 노드가 꺼져 있을 때 최대 값은 그 자손들이 각각 켜져있을때 혹은 꺼져있을 때의 최대값을 더해주면 된다.

백준 - 로봇 조종하기로봇이 왼쪽, 오른쪽, 아래쪽으로 움직일 수 있으니 이전 위치는 현재 위치의 오른쪽, 왼쪽, 위쪽이라는 뜻이 된다. 그 중에서 max 값을 찾으면된다. 하지만 일반적인 이중 for문으로 풀게되면 오른쪽에서 오는 것을 잘 반영할 수 없다. 따라서 t

백준 - 감시 피하기그렇게 어려운 문제가 아니였는데 구현할때 실수가 좀 있었다. 1.최소 한명이라도 발견하면 학생의 실패인데 그걸 제대로 고려안했다. 2. 이름을 simulateSucess라고 지었는데 선생이 다 발견하는걸 success라고 중간에 착각했다. 3. 여러

백준 - 치즈다른 치즈문제보다 더 어렵다. 공기가 안에 있는 경우도 고려해야하기 때문이다. 따라서 공기가 바깥 공기인지 내부 공기인지 찾는 bfs도 따로 해줘야한다. bfs를 돌다가 정해진 크기 밖으로 나가면 외부 공기라 판단하고, 그 외부 공기를 기준으로 bfs를

백준 - 최단경로전형적인 다익스트라 문제지만 자바로 구현했기에 다소 낯선 포인트들이 있었다.bfs/dfs와 달리 이제는 그래프에 다른쪽 노드와 distance까지 보관해야한다. 따라서 List<Integer>\[]가 아닌 List<int\[]>\[]로 그래프

프로그래머스 (2020 카카오 인턴쉽) - 보석 쇼핑처음에는 dictinoary 대신에 set을 썼다가 시간 초과가 났다. 투포인터라는 것을 바로 캐치한 것은 잘했다. 인덱스를 초과하는 예외가 잘 발생하니 조심해서 풀어야 한다.

프로그래머스 - 경주로 건설처음에는 DFS로, 그 다음에는 가지치기를 한 (비용이 넘어가면 진행하지 않는) DFS로 하니 70점이 나왔다. 여기서 DFS+Dp로 하려다가 실패하고, BFS로 풀었다. BFS는 다른 사람들의 풀이와 거의 비슷한데 이유는 알 수 없지만 실패

백준 - 여행 가자

백준 - 도로포장처음에는 K개의 범위가 그리 크지 않아서 백트랙킹으로 완탐을 이용하여 각 경우에 대해 다익스트라를 쓰려고 했다. 하지만 메모리 초과가 났다.dp를 활용해서 풀었다.

백준 - 플로이드각각의 노드를 거쳐가는 가정을 하면서 갱신한다. 3중 for문을 쓰게되며, 시간복잡도는 O(n^3)이다.

백준 - 친구비유니언 파인드를 활용한 문제다. 유니언 파인드를 이용해 그룹화를 시켜주고, 각 그룹별로 제일 비용이 싼 비용들을 총합으로 더해주면 된다. 일반적인 유니언 파인드 문제와 다른 점은, 마지막 갱신을 해줘야한다는 점이다.예를 들어 parents = x, 1,

백준 - 서강그라운드처음 문제를 제대로 읽지 않고 문제를 풀기 시작해서 다익스트라로 풀었다. 물론 각 노드에 대해 다익스트라를 반복해도되지만, 문제의 의도는 플로이드 와샬이었을 것이다.

백준 - 스크루지 민호2문제 랭크는 골드2라고 되어있지만, 트리 DP의 전형적인 문제다. 한 경찰서는 양방향으로 감시를 할 수 있으니, 트리 구조에서 부모가 경찰서이면 자식 노드는 경찰서가 있어도되고 없어도 된다. 반대로 부모에 경찰서가 없으면 자식 노드는 반드시 경찰

백준 - 경로 찾기플로이드 와샬을 이용하면, 비용이 MAX_VALUE가 아니면 비용을 많이 들여서라도 갈 수 있다는 곳이라는 것을 알 수 있다.

백준 - 나무 자르기이분탐색의 대표적인 문제인데 처음보면 헷갈리는 부분들이 조금 있다. mid는 결국 절단기의 높이를 의미한다. 잘려진 나무가 필요양보다 많으면 mid를 올려야하고, 부족하면 내려야한다.범위를 재조정하기 전에 조건을 만족하면 체크 범위를 재조정하는 방법

백준 - 줄 세우기위상정렬: 방향그래프에 존재하는 노드들의 선행순서를 위배하지 않고, 모든 노드를 나열하는 것

백준 - 문제집위상정렬에서는 큐를 사용했다. 따라서 여러개의 답이 나올 수 있었지만 이 문제에서는 여러 개의 답이 아닌, 낮은 숫자부터 나오게 했다. 따라서 힙을 사용했다.

백준 - 공유기 설치큰 구조로 보면 거리 d에 대해 이분 탐색을 하면 된다. 그리고 거리가 정해지면, 그 거리에 대해 countHouse 함수를 호출해서 조건을 만족하는지 확인한다. 처음에는 countHouse의 결과가 정확히 주어진 C와 일치할때만 조건을 만족한다고

백준 - 랜선 자르기일반적인 이분 탐색 문제라고 생각했지만 몇몇 트랩이 있었다. 우선 mid를 구할 때 보통 (left + right) / 2라고 하는데 left나 right의 범위가 int 전체라면 오버플로우가 날 수 있다. 그래서 long타입으로 해주든가 left

그룹내 최대값을 이분 탐색으로 찾는 것이 포인트이다. 그리고 만약 그룹의 개수가 M보다 작으면 분배를 하면된다.

백준 - 키로거예전 백준 에디터 문제 비슷하게 풀었다. 처음 풀었을 때 통과하지 못했는데, 앞에 스택은 팝해서 모은다음 거꾸로 해줘야하고, 뒤에 스택은 팝만 하면 된다.https://ifuwanna.tistory.com/221String과 StringBuffe

백준 - 현수막백준의 섬 개수 세기 문제와 동일하다.

백준 - 점프왕 쩰리 (Large)문제 오류인지 모르겠지만, 성공 조건을 y==N-1 && x == N-1로 하니 실패했다. 결국 오른쪽 가장 아래 위치에 도착하는 것이니 같은 것인데 실패해서 이상했다.

백준 - 홀짝 칵테일comparator를 구현하는 것과, stream을 쓰는 것이 익숙하지 않다. IDE가 없었으면 못했을 것 같다. 홀수가 하나라도 있거나 하나도 없거나이다. 하나라도 있으면, 홀수들만 곱하면 된다. 하나도 없으면 전부 짝수니 전부 곱하면된다.

백준 - 트리전위 순회는 root -> left -> right, 중위 순회는 left -> root -> right, 후위 순회는 left -> rigt -> root 순으로 이루어진다.여기서 우리는 전위 순회로 루트를 구하고, 구한 루트를 기반으로 중위 순회를 통해

백준 - 빈도 정렬빈도수를 세어야하니 맵을 써야겠다고는 생각했는데, 예전 파이썬에서도 키나 밸류를 기준으로 정렬하는 부분에 약했다.우선 만약 같은 빈도수라면 들어온 순서대로 정렬해야하니 LinkedHashMap을 썼다. LinkedhashMap은 순서를 유지해준다. 만

프로그래머스 - 소수 만들기백트랙킹으로 풀 수도 있지만 N의 크기가 크지 않아 3중 for문으로 풀어보았다.

프로그래머스 - 다리를 지나는 트럭차가 다리에서 나오는 것과 들어오는 것이 현실에서는 동시에 일어나지만 프로그래밍에서는 순차를 두고 발생하기 때문에 뭐가 먼저 일어나야하는지 잘 고려해야한다.처음에는 다리에 진입하는 것을 먼저 고려했는데, 차가 나가는 순간 무게 기준을

프로그래머스 - 주식 가격백준의 탑과 매우 유사한 문제이다. 포인트는 스택에 값이 아닌 인덱스를 넣고, 만약 조건을 만족하지 않는 값을 만나면 스택에서 조건을 만족하지 않는 것들을 계속 꺼내주는 것이다.

백준 - 구간 합 구하기 4구간합 관련 알고리즘에 대해 이야기 해보자.구간합을 구하는 것은 원래 O(N)의 시간으로 해결할 수 밖에 없다.효율성문제들에서 구간합 문제는 종종 등장한다. 그리고 O(N)으로 구간합을 구하려 한다면 효율성문제들을 통과할 수 없다. 적어도 O

백준 - 1학년

백준 - 색종이와 가위n의 범위가 매우 크므로 이분 탐색이라고 힌트를 얻을 수 있어야 한다. n번의 가위질은 h번의 가로 자르기와 n-h번의 세로자르기로 이루어져 있다. h번의 가로 자르기와 n-h번의 세로자르기는 (h + 1) \* (n - h + 1)개의 작은 종이

백준 - 봄버맨항상 시간 개념이 나오면 일을 언제해야할지 (초가 지난 후 할지, 지나기 전에 할지) 헷갈리는데, 작은 규모의 예제로 따져보면 그리 어렵지 않다.

백준 - N번째 큰 수 매줄 입력 받을 때마다 크기 N을 넘어가면 정렬해서 필요한 부분만 가지고 있으면 된다.

백준 - 생태학백준에서만 가끔 나오지만, 입력을 무한으로 받는 방법은 자주 까먹게 된다.처음에는 round로 했다가 틀렸다. 파이썬에서 round는 독특한데, round(0.5) 와 round(-0.5) 는 모두 0 이고, round(1.5) 는 2다. https&#x

백준 - 수들의 합 2알고리즘을 오랜만에 해서 그런지, 투포인터 문제라는 것을 알고도 배열이 정렬이 안되어있는데 투포인터를 어떻게 쓰지하고 고민을 했다.

백준 - 출근 경로다른 사람들 풀이를 보고도 이해가 안가서 고민을 많이 했다. 이제는 이해 했다. 결국 DP는 풀고나면 비슷한 형태인 것 같다.

백준 - 개똥벌레항상 이분탐색은 뭐를 이분 탐색의 대상으로 잡을지가 관건이다. 처음에는 나도 당연히 개똥벌레의 높이를 잡으려했으나, 그림만 보고 높이를 어떻게 하든 커질 수도 있고 작아질 수도 있어서 이분 탐색을 어떻게 쓸지 감이 안왔다.포인트는 두 개다. 우선은 종유

백준 - 점프이번에 DFS를 시도하다가 시간이 터졌다. 예전에 쉽게 푼건데도 안풀린다.

백준 - 퇴사2예전에 풀었던 문제인데 풀지 못했다. 대신 확실하게 다시 알고 넘어가자.앞에서부터 뒤로 채워간다. dpi = i일까지 일했을 때 최대 값이다. 그래서 만약 최대 일하는 날짜를 넘어가면 해당 해당 값을 채우지 않는다. i날까지 일했을 때 최대 값은 항상 i

백준 - 0 만들기정확히 말하면 backtracking은 아니고 부르트포스다. 아쉬운 부분은 eval()을 썼다는 점과, 아스키 코드를 찾아봤다는 점이다. 그냥 opr을 정렬하면 알아서 아스키 코드로 적용할 수 있었다. eval()을 안쓰고 푸는 방법도 찾아보자.

백준 - 오타풀이누적합이 음수가 되면 안된다. -1이 되는 시점에서 오타가 난 것이다. 그러면 틀린 것 포함 앞부분 닫힌 괄호의 개수가 정답이 된다.또한 끝이 양수로 나도 안된다.누적합을 끝까지 구했을 때 마지막이 +2 또는 -2일 때, 한 개가 오타난 경우다왼쪽 괄호

2018 카카오 1차겁을 엄청 먹었었지만 생각보다는 어렵지 않은 문제였다.카카오에서는 문자열 로그를 다루는 문제가 자주 나온다고한다. split을 사용했지만, 정말로 형식이 고정되어있으면 슬라이싱으로 가져오는 것도 좋을 것이다.시간을 가져온다음 찍어볼 때 너무 긴 문자

백준 - 블로그슬라이딩 윈도우 문제를 연습을 하고 싶어서 풀었다. 최근에 쳤던 코테 문제와 유사하다. 마지막에 인덱스가 하나 초과하는 문제로 시간을 많이 소비했는데, 예제를 작성해보고하나 오버하는경우에는 그냥 배열에 패딩을 붙여주자.

백준 - 내려가기슬라이딩 윈도우 문제인데 역시나 인덱스 하나 차이로 오류가 계속 발생했다. 정형화된 패턴으로 문제를 풀 수 있게 준비해야하는데, 이번에 정한거는 left =0, right = 0에서 시작하고 right < len(arr)인 동안 반복하는 것이다.

다시 풀자

프로그래머스 - 부족한 금액 계산하기

프로그래머스 - 숫자 문자열과 영단어

프로그래머스 - 메뉴 리뉴얼

프로그래머스 - 실패율실패했지만, 이 기회에 값을 기준으로 딕셔너리 정렬하는 것 확실하게 정리하자.문제를 가장 잘 이해하고 잘 푼 문제다. 그저 급하게 풀면 주어진 stage 리스트를 반복문을 돌릴텐데, 이 풀이는 아예 그냥 stage 별로 돌렸다. 그리고 매 단계에서

프로그래머스 - 뉴스 클러스터링처음에는 집합이라고 해서 바로 set를 썼는데 set를 쓰면 안된다. 왜냐하면 여기서 교집합과 합집합은 중복이 허용되기 때문이다. 파이써닉하게 엄청 잘 푼 풀이다. 만약 중복이 허용되게 집합을 합치거나 공통 부분을 추출하고 싶으면 &나 |

프로그래머스 - 표 편집출처: https://velog.io/@kerri/Swift-Python-%ED%94%84%EB%A1%9C%EA%B7%B8%EB%9E%98%EB%A8%B8%EC%8A%A4Lv3-%ED%91%9C-%ED%8E%B8%EC%A7%91-2021

프로그래머스 - 다단계 칫솔 판매실제 문제를 풀 때는 이것보다 난이도가 높았던 것 같은데 다시 푸니 쉬운 편이다. 다만 소수점 계산 관련해서 조심해야 한다. 10퍼센트를 주느냐, 90퍼센트를 가지고 전체에서 뺴고 주냐에서 답이 차이가 난다. 소수점 버림에서 차이가 나기

프로그래머스 - 5주차\_모음사전완탐으로 사전을 만들고 인덱스를 찾으면 된다.

프로그래머스 - 2주차\_상호평가Counter를 이제 문제풀 때 필요하면 사용하자.numpy를 사용하지 않고 행열 뒤집는 방법

출처 블로그

백준 - 스티커 붙이기단순 구현이었기 때문에 다른 부분에서 특별히 어려운 것은 없었으나, 2차원 배열 90도 회전하는 쉬운 방법들에 대해 찾아보았고 알게 되었다.이전 같았으면 맨 바깥의 한 줄씩 저장해서 다시 깔아주는 방식으로 회전을 구현했을 것이다. 하지만 그것보다

프로그래머스 - 4주차\_직업군 추천하기오랜만에 딕셔너리의 value가 또 다른 dictionary인 형태를 사용한 풀이를 진행했다. 특별할 것은 없었고, value를 기준으로 다시 딕셔너리를 정렬하는 것을 거의 다 기억했는데, key = 을 빼먹고 lambda x :

프로그래머스 - 지형 이동여기 보고 이해하고 코드 수정함

프로그래머스 - 후보키

프로그래머스 - 행렬 테두리 회전하기지정된 위치의 값들을 한바퀴 돌면서 다 저장하고, 한번 rotate한 다음 다시 그 위치들을 돌면서 깔아주는 것이다.

프로그래머스 - 모두 0으로 만들기출처: https://velog.io/@piopiop/%ED%94%84%EB%A1%9C%EA%B7%B8%EB%9E%98%EB%A8%B8%EC%8A%A4-%EB%AA%A8%EB%91%90-0%EC%9C%BC%EB%A1%9C-%E

프로그래머스 - 기둥과 보 설치 실패한 내 풀이 > 테스트케이스는 통과했는데 실제 케이스에서 거의 런타임 에러가 났다.

프로그래머스 더 맵게힙