개발자 노트

문제 설명 구현 문제. 문제를 잘 읽고 이해해서 말하는 대로 구현하라. 예제도 매우 잘 나와있어서 정말 잘 읽어보고 알고리즘을 작성하면 된다. 읽은 내용 바탕으로 설명하자면, 1. K A K A O ↑ K문자는 사전에 있으므로 다음 A로 넘어간다 2. K A K A O ↑ KA는 사전에 없다. 따라서 KA를 사전에 등록하고 K의 인덱스 번호를 출력. 3. K A K A O ↑ A부터 다시 시작. A는 사전에 있으므로 다음 K로 넘어간다. (1~2과정 반복) 4. K A K A O ↑ AK는 사전에 없으므로 사전 등록, A의 인덱스 번호를 출력한다. 5. K A K A O ↑ K는 사전에 있으므로 다음 A로 이동 6. K A K A O ↑ 2.에 의해 KA또한 사전에 있다. 다음 O로 넘어간다 7. K A..

문제 설명 주식가격들이 주어졌을 때 각 시점에 대해 연속해서 떨어지지 않는 날의 수를 구할 것. prices의 길이가 10만이므로 시간복잡도 유의 접근 이 문제는 왜 스택을 이용하면 편할까? 문제만 읽어봤을 때 말로 풀어쓰면 다음과 같다. 매 시점마다 주식가격이 올랐는지 안올랐는지 판단한다. 그리고 주식가격이 올랐거나 같으면 계속 지니고 있어서 시간을 증가시켜줘야 한다. 만약 떨어졌으면 떨어진 가격보다 큰 값들은 모두 제거해줘야 한다. 매 시점마다... -> 시간이 존재한다., 그리고 지니고 있어야 하므로 특정 자료구조에 담아줘야 한다. 그리고 3번을 보면 떨어진 가격을 제거해줄 때가 중요하다. 데이터를 담은 자료형에는 담겨진 순서대로 주식가격이 가격이 같거나 증가한다. 따라서 제거할 때는 역순으로 제거..

문제 설명 문제에서 그림과 함께 잘 설명되어 있기에 pass 봐야할 것이라면 잘린 쇠막대기의 총 수를 구하라 '()'가 레이저. arrangement가 최대 10만이기에 시간초과 주의 접근 딱 보면 뭐 어떻게 해야하는거야... 싶은 문제다. 그래서 나는 문제를 단순화해서 생각해봤다. 단순화할 때 유념해야할 것은 '()'가 레이져, 잘린 갯수 구하는 문제라는 것. case 1. ()만 주어질 경우 잘린 쇠막대기가 없으므로 0 case2. (()) 잘린 쇠막대기가 레이저에 의해 2개가 된다. case3. ((())) 잘린 쇠막대기가 레이저에 의해 4개가 된다. case4. (()()) 잘린 쇠막대기가 레이저에 의해 3개가 된다. case5. ((()())) 잘린 쇠막대기가 레이저..

문제설명 https://programmers.co.kr/learn/courses/30/lessons/49189 어렵지 않은 내용 이므로 패스 접근 적용할 수 있는 알고리즘 다익스트라 알고리즘 다익스트라 알고리즘은 일 대 다 알고리즘으로써 1번 노드에 대해 알고리즘을 적용했을 경우 1번 노드에서 최단거리로 갈 수 있는 모든 노드들을 구할 수 있다. 여기선 노드간 이동 횟수가 곧 거리이므로 모든 노드의 가중치를 1로 두어 구하면 된다. 다 구하고 나서 최댓값의 갯수를 구하면 끝 BFS BFS에서 최단경로를 구할 때 que사이즈만큼 pop하는 과정이 있다. 최종적으로 기록된 size가 곧 마지막 노드들의 수이므로 이를 이용하자. 다익스트라에 비해 BFS가 구현하기 더 쉬우므로 BFS를 적용했다. 자료형 선택 ..

문제설명 단어 begin에서 단어 target으로 words 내에 있는 단어만을 이용해서 이동. 조건은 words단어 이동시 1글자만 달라야 한다. 중요한 조건으로 begin,target,words내 단어들의 글자수는 모두 동일하다. 접근 DFS로 접근해야하나 어떻게 해야 효율적으로 접근할 수 있을지 고민해보았다. 방법1 begin기준 a~z모두 고려 begin의 단어에서 한단어씩 a~z까지 바꿔가며 words내에 있으면 선택하는 방안. 단어의 길이는 최대 10이므로 (26*(words의 길이))^10이 된다. 시간초과나오기 딱 좋다. 어차피 words 단어 내에서 선택해야하는 것 아닌가? words단어에서 1글자 차이나는 것들을 선택하는 방법으로 가보자. 방법2 begin과 target간 다른 문자들만..

문제설명 https://programmers.co.kr/learn/courses/30/lessons/64064 불량사용자 목록을 보고 응모자 아이디가 될 수 있는 경우의 수를 찾는 문제. *가 임의의 한 문자를 의미하므로 이로 인해 경우의 수가 생성된다. user_id의 길이 및 원소의 길이가 최대 8로 경우의 수가 매우 작은 문제이다. 접근방법 문자 비교는 kmp,보이어 무어도 있겠지만 구현이 좀 까다로워서 trie로 접근하였다. trie trie에 user_id넣기 banned_id하나하나에 대하여 2-1. 해당 banned_id가 가질 수 있는 user_id 경우 찾기 ​ 2-1-1. 이때 banned_id의 각 한글자에 대해 탐색하여 *를 만나면 모든 child노드 탐색하여 경우에 추가. ​ 2-..

문제설명 https://programmers.co.kr/learn/courses/30/lessons/64065 카카오답게 문자열 처리하는 문제 예전에 처음 풀었을 땐 문제를 도저히 이해하지 못해서 넘어갔으나... 그 이유는 원소의 개수가 n개이고, **중복되는 원소가 없는** 튜플 `(a1, a2, a3, ..., an)`이 주어질 때(단, a1, a2, ..., an은 자연수), 이는 다음과 같이 집합 기호 '{', '}'를 이용해 표현할 수 있습니다. {{a1}, {a1, a2}, {a1, a2, a3}, {a1, a2, a3, a4}, ... {a1, a2, a3, a4, ..., an}}이렇게 열겨형 정의를 넘어갔기 때문인 것 같다. 이 부분을 잘 보면 튜플의 원소를 ..

문제설명 스택 및 이차원배열을 물어보는 문제 접근 바구니는 단순히 stack만을 이용하면 되고, 이차원 배열에서 뽑을 인형을 잘 두는게 포인트. 이차원 배열도 세로로 스택으로 보기 위해 각열에서 top을 미리 찾은 다음 뽑을 때마다 +1 씩 해주는 방식으로 접근했다. 왜냐하면 아래로 갈 수록 값이 증가하니까.(이 부분에서 디버깅하는데 10분 소요했다. (전체 풀이시간 30분)) 구현 def solution(board, moves): n = len(board) tops = [0 for _ in range(n)] #값이 있는 index for c in range(n): for r in range(n): if board[r][c] != 0: tops[c] = r break answer = 0 basket = ..

문제설명 트라이로 접근하는 것. 전화번호 중 동일한 접두어가 존재하면 NO를, 존재하지 않으면 YES를 반환한다. 접근 TRI 이용 완전탐색으로 접근하지 않는 이유 완전탐색으로 접근하면 시간복잡도는 엄청나다. 매 테스터케이스마다 N개의 전화를 N!번 비교하여 min(P1,P2)만큼 비교해야 하므로 O(T*N*N!*P)이다. (T는 테스트케이스 수, N은 전화번호 수 P는 전화번호의 자리 수) 따라서 최악의 경우 연산량은 50*10000*10000!*10이 된다. tri접근시 공간복잡도 고려 0~9까지 10개의 수 표현을 10개 표현해야하므로 10^104byte(int선언 기준)가 된다. 256MB를 넘지만, 미리 10개를 다 선언하지 않고 있을 때마다 선언하면 공간복잡도는 많이 줄어든다. n이 10000..

문제설명 아주 기초적인 BFS문제. 최단거리를 찾아라. 접근 카카오2020 신입공채 블록이동하기 문제를 풀다가 아주 복잡하게 최단경로 문제를 풀고 있는 것 같아 이 문제를 살펴보았다. 접근1 개별의 이동에 대해 방문정보를 가지고 있어서 모두 탐색하도록 정했다. (1,1)에서 (2,1)이동가능하면 (2,1)노드와 함께 방문정보 (1,1),(2,1)을 que에 넣어준다. (1,1)에서 (1,2)이동가능하면 (2,2)노드와 함께 방문정보 (1,1),(1,2)를 que에 넣어준다. (2,1)과 (1,2)모두 (2,2)이동이 가능하므로 각각의 방문에 (1,1),(2,1),(2,2), (1,1),(1,2),(2,2)를 que에 넣어준다. 굵은 표시에 있는 내용을 보면 '최단거리'를 구하는 문제이므로 ..