알고리즘 인터뷰

인접리스트의 구현 in Python파이썬은 포인터가 따로 존재하지 않으므로, 연결리스트를 구현하기 까다롭다. 따라서 인접 리스트를 출발 노드를 키로, 도착 노드를 값으로 표현하는 딕셔너리 형태로 표현한다. 도착 노드의 경우에는 여러 개의 노드가 가능하므로 값은 리스트

dfs 구현 부분이 조금 달라져서 C++ 코드를 참조해서 Python으로 아래처럼 변환했다. Python 으로 구현하면 어려웠던 문제가 이렇게 dfs 함수만 잘 구현하면 쉬워진다. 다만 이 문제에서 실수하기 쉬운 부분이 두 군데 있었는데 하나는 bit masking을 할 때 모두 0비트로 이루어진 경우와 모두 1비트로 이루어진 경우를 제외하도록 for ...

https://www.acmicpc.net/problem/5430reverse() 함수를 사용하면 쉽게 풀 수 있을 것 같았지만 reverse() 함수는 O(n)의 시간복잡도를 가지기 때문에 실패하였다. 이 문제의 해법은 실제로 reverse() 연산을 수행하

문제 https://www.acmicpc.net/problem/16234 전략 Python에서 메모리 초과, 시간 초과 문제 해결에 오래 걸린 문제. visited 배열의 활용 뿐만 아니라 다음 interation에서 이전에 인구 이동이 있었던 구역을 추가로 배제해주는 logic도 포함하니 AC를 받을 수 있었다. 효율적으로 한번만 돌려야했지만 중복...

1차 시도 시간초과, 메모리 초과 permutation 수행은 O(6) 이지만 BFS 탐색은 (60,60,60) 의 모든 체력이 0이 될 때까지 진행되어야 하므로 최대 타격 9를 기준으로 보아도 max depth가 약 21개이다 (정확히는 부수 타격으로 이미 SCV가 손상되어 있으므로 depth 가 더 적음) O(6^21) 은 대략 O(N^2) 임. ...

여러가지 방법이 있지만 bit masking 방식이 가장 좋았다. 여기서 비트를 확인하면서 0,0,0 세 elements들에 대한 각 bit를 키꺼나 끄는 모든 조합을 확인하는 아이디어다. shift를 이용하기 때문에 shift 0, 1, 2 이렇게 확인하면 비트는 거

https://school.programmers.co.kr/learn/courses/30/lessons/181188세달 전만해도 라인 스위핑의 개념을 모를 때는 어떤 노력을 해도 풀 수가 없었던 문제였다. 하지만 라인스위핑이라는 간단한 컴퓨터적 사고를 이용하면

라인스위핑 문제 응용이다.백준에서는 반례찾기가 힘들다. 이번에도 sort 기준을 잡는데서 틀렸는데, 처음에는 회의 끝나는 시간만을 기준으로 sort (key = lambda x: x\[1]를 했다가 반례에서 잡혔다.반례는 이것이다. \[9,9],\[1,9] 이 반례에서

배열을 이용하면 O(n) 으로 쉽게 풀 수 있는 문제이다. 가장 처음 풀었을 때는 if 문의 순서를 잘 못 짜서 시간이 더 많이 걸렸다. 그러니깐 처음부터 mem 리스트에 기록을 하고 난 뒤에, 판별을 해버리게 되면 k/2 == i 인 경우에는 두 수의 합으로 기록되지

투포인터가 아니면 메모리 초과로 안풀리는 문제.투포인터를 써도 되는 이유는 이미 한번 탐색해서 지나간 부분은 중복해서 다시 탐색할 필요가 없기 때문이다.예를 들어서 \[1,2,3,4,5,1,2,3] 에서 1,2,3,4,5 까지는 중복 없이 지나간 부분이라는 것을 확인했

반례찾기가 어려웠던 문제..가장 마지막 줄에서 라고 처리하는게 맞는데 if 문으로 처리하고 있었다. 그러다보니 jew 라는 리스트가 소진되기만 하면 바로 프로그램에 종료되어버려서, 아직 temp_q에 요소가 남아있는데도 나머지 가방에 집어넣지 못하는 문제가 발생하는 것

levenstein의 편집 거리 알고리즘을 응용해야만 하는 문제가 있었다.이 것은 알고나면 쉽지만 편집 거리 알고리즘을 사전에 알지 못한다면 푸는데 상당한 어려움이 있을 수 있는 문제다. 알고리즘을 숙지 하지 못했다면 즉석에서 응용할 수 있는 감각도 필요하다.우리는 두

코테의 실력은 경험에서 나온다.

https://leetcode.com/problems/balanced-binary-tree/ 이 문제는 DFS를 이용해서 가장 아래 트리노드에서부터 올라가는 방식으로 풀 수 있다. answer를 기록하는 방식에 아이디어가 필요했는데 처음에는 비효율적인 방법으로 기록했

https://www.acmicpc.net/problem/13913간단한 문제였지만 파이썬에서 사소한 오류로 반례를 찾는데 오랜 시간이 걸렸다. 다른 것이 아니라 While 문을 쓸때 매우 유의해야 한다는 점이었다.보통 While 문을 쓸때는 종료조건이 0이

https://school.programmers.co.kr/learn/courses/30/lessons/12946아주 오래전에 recursion을 배웠을 때 접했던 문제다. 처음 보는 문제라면 아래와 같은 알고리즘을 생각하는게 쉽지는 않다.

nested 되어있는 dictionary를 다룰 때에는 copy를 주의 해야 한다. 반드시 deepcopy를 사용해야 한다.

파이썬 함수 안에서 바깥에 list를 조작하고자 할때는 a+=b, 와 같은assign 명령어를 사용하지 말라.파이썬에서 list 를 다룰 때 주의할 점이 있다. 실제 현장에서는 거의 그럴일이 없지만, 알고리즘 테스트에서는 함수 바깥 scope 에 있는 list 에 접근

정수 n이 주어졌을 때 알파벳 26자 중에서 동일한 개수의 알파벳을 이용하여 임의의 문자열을 반환하라.만약 n이 3이면 'abc' 'bcd' 와 같은 결과가 나오면 되고n이 30인 경우 2개씩 사용하여 'aabbcc ....' 또는 'ccddee ...' 와 같은 임의

응용된 DFS 문제이다. 내 경우에 중요했던 첫번째 포인트는 문제에서 DFS를 수행하는 경우가 두 가지 경우로 나누어진다는 점.그리고 두 번째 포인트는 불가능한 case를 정확히 찾는 것이다.기본적으로 이문제는 for 문 수행순서를 d l r u 네 가지를 정확하게 표

https://school.programmers.co.kr/learn/courses/30/lessons/81302일반적인 BFS에서 한 가지 아이디어가 필요했다. 먼저 사람이 앉아있는 위치를 찾고 visited 배열을 선언한 후에 BFS를 출발한다. BFS를

세 가지 중요한 포인트를 기록한다. 먼저, do_score에 결함이 있었다. aim -1 for 문에서 돌려주었는데, 문제는 continue 조건에서는 aim -=1을 수행할 수 없었기 때문에 문제가 발생했다. (디버깅하는데 엄청 오래걸렸다. for문의 구조를 rang

주석처리는 소괄호()로 표기한다. 총평 : parameter가 코드 작성 과정에서 자꾸 늘어나고 이것은 함수의 추적 가능성을 지나치게 나쁘게 만들었다. 그것은 정확한 로직을 끝까지 완성하지 않고 작성을 시작했기 때문이었다.상하좌우, Ctrl상하좌우 8가지 방향으로 탐색

함수 check_unique() : uniqueness를 판단하기 위한 execution 함수 조합된 키를 이용하면 unique하게 사용할 수 있는지를 dictionary의 count를 이용해서 판단한다. 2개 이상이 존재한다면 False이다.함수 dfs(): 후보키를

처음에 풀지 못했다. 포화 이진 트리의 개념을 정확히 알고 난 후에 단서를 찾았다. 포화 이진 트리에서는 늘 정 가운데가 root가 되고 좌우를 반씩 나눈 후에 다시 가운데를 subtree root로 보고 이진분할, 이진탐색을 할 수 있다.

https://www.acmicpc.net/problem/9663작은 동작하는 프로그램에서 큰 동작하는 프로그램으로 만드는 경험이 무척 좋았다. 유명한 문제인 것 같다.처음에 이 문제를 실패 한 후에 아이디어를 들었고 DFS로 접근하는 방식을 알게 된 이후로는

코드 길이가 100줄이 넘기 때문에 자잘한 실수라도 있으면 틀릴 수 밖에 없는 문제다. 당연히 한 번에 푼 것은 아니고 각 함수들의 뼈대를 먼저 구성한 다음에 구체적인 요건들을 조금씩 더해가면서 풀었다. 그럼에도 불구하고 오답이었는데, 그 이유는 최대 박멸 장소를 찾는

아이디어 https://tech.kakao.com/2020/07/01/2020-internship-test/ 위의 카카오 해설을 해석해보면 최단 거리 문제(BFS)로 뼈대를 잡은 뒤, 변형 구조인 코너 개수 부분을 고려해주는 문제로 권하고 있다. 코너 개수를 고려하는

이 문제는 라인스위핑 문제이다. https://www.acmicpc.net/problem/1911라인 스위핑은 쉽지만 자칫 잘못하면 수렁에 빠질 수 있다. 경우의 수를 잘 판단하고 접근해야 한다. 라인스위핑에서는 시작점(s), 종점(e)을 기록하는게 가장 중요

mlflow 서비스를 처음 시작하다보니 다소 헷갈리는 부분이 있다. 프레임워크 문서를 먼저 읽어보지 않고 시작을 해서 그런 것 같기도 하다. 헷갈렸던 부분을 정리하고 오늘은 mlflow ui와 mlflow server에 대해서 간단히 살펴보고자 한다. 먼저 MLfl