개발자 노트

문제 설명 구현 문제. 문제를 잘 읽고 이해해서 말하는 대로 구현하라. 예제도 매우 잘 나와있어서 정말 잘 읽어보고 알고리즘을 작성하면 된다. 읽은 내용 바탕으로 설명하자면, 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. ((()())) 잘린 쇠막대기가 레이저..

문제 설명 queue인데 다음과 같은 우선순위를 고려하는 큐이다. 1. 인쇄 대기목록의 가장 앞에 있는 문서(J)를 대기목록에서 꺼냅니다. 2. 나머지 인쇄 대기목록에서 J보다 중요도가 높은 문서가 한 개라도 존재하면 J를 대기목록의 가장 마지막에 넣습니다. 3. 그렇지 않으면 J를 인쇄합니다.priorities = [2, 1, 3, 2] 문서의 우선순위가 위와 같이 주어졌을 때, 특정 위치(location)에 있는 문서가 몇 번째에 출력될 것인가? 제한사항(조건) 1 삽입도 시간복잡도 1이 되서 더 빠름.) 구현 from queue import PriorityQueue from collections import deque class MaxPQ: def __init__(self): self.pq = Pr..

문제 설명 전형적인 BFS문제이다. 설명한다면 이 문제에 대해 말하기 보단 BFS에 대해 말하므로 설명은 생략. 접근 문제를 이해하는 건 쉽다. 하지만 전에 이런 종류의 문제를 비효율적으로 구현한 적이 있어 효율적으로 탐색하는 방법에 대해 적으려 한다. 문제의 상황은 다음과 같다. 점들을 bfs로 탐색해야 하는데, 모든 위치를 방문해야 한다. 초기 접근 visited 모든 배열을 탐색한다. 미방문 했다면 그 부분 기준으로 BFS 탐색 다시 visited 모든 배열을 탐색한다. 미방문 한 지점이 있다면 그 부분 기준으로 BFS 탐색 모두 방문했다면 종료. 이렇게 구현하면 visited탐색이 반복되므로 매우매우~ 비효율적이다. 최근 접근 방법 visited 탐색한다. 탐색 중 방문 여부 확인 미방문 BFS ..

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

문제설명 https://programmers.co.kr/learn/courses/30/lessons/17678 셔틀 버스가 9시부터 시간간격 t로 n회온다. 사람들은 이 셔틀버스를 타기 위해 00시01분부터 23시 59분 사이에 줄을 선다. 이때, 어떻게 줄을 서야 가장 타이트하게 회사로 가는 차를 탈 수 있을지(막차를 타고 갈 수 있을지) 시간을 찾는 문제이다. 시간은 1분 단위이다. 접근 문제 이해에 따른 목표값 찾기 문제를 이해하는데만 20분이 걸렸다. 문제를 정확히 이해했다면 결국엔 언제 줄을 서야 막차를 타고 갈 수 있는지에 대한 문제이므로 마지막 차에 타려고 줄을 섰을 때는 2가지 경우로 나눌 수 있다. 1)마지막 차가 도착했을 때 대기줄 인원이 버스의 정원을 초과했을 경우 이땐 가장 마지막에..

문제설명 단어 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}}이렇게 열겨형 정의를 넘어갔기 때문인 것 같다. 이 부분을 잘 보면 튜플의 원소를 ..