본문 바로가기
반응형

알고리즘54

플로이드-와샬 알고리즘 해당 알고리즘은 그래프 이론에서 착안된 이론 중 하나로써 반의 가중치가 양수 뿐만 아니라 음수인 경우의 가중치를 가지는 이동 경로에서도 사용할 수 있어 이를 통해 최단 경로를 찾는 알고리즘이다. ​ 플로이드-와샬 알고리즘 자체는 경로를 반환하지 않지만 약간의 수정 작업을 거친다면 경로까지 반환할 수 있는 알고리즘을 만들 수 있다. ​ 해당 알고리즘 같은 경우는 각 꼭지점 쌍을 지나는 그래프의 모든 경로를 비교하기 때문에 3개의 중첩 for문이 사용된다. -> 이 때문에 시간복잡도가 O(n^3)이다. ​ 기본적으로 ShortPath{최단거리}(I, J, 0) = w(i, j) 이고, 이를 재귀적으로 이용할 경우, ShortPath(i,. J, k) = mininum(ShortPath(i, J, k - 1).. 2022. 8. 9.
[이마트] SSAFY 특별전형 코딩 테스트 후기 이마트 SSAFY 전형이라는 좋은 기회가 생겨서 시험을 치르게 되었다. 처음 메일을 받았을 때, 12문제에 160분이라는 안내와 테스트를 진행하면서 알고리즘, SQL, 객관식, 서술형 이렇게 다 나오는 줄 알고 두려움에 떨고 있었다. 게을러서 매일 미루고 있는 CS 공부를 하고 있지 않아 이번에도 쉽지 않은 것이 되겠구나... 이번 신세계 계열사의 첫 시험이라 나에게 어떠한 시험 데이터도 있지 않은 것도 걱정의 대상이었다. 불안한 마음을 가지고 시험을 진행했는데, 예상과는 다른게 알고리즘 1, SQL 1, 객관식 10 문제가 출제되었다. 알고리즘과 SQL의 경우에는 기본적인 지식이 있으면 모두 해낼 수 있는 수준으로 나와서 무난하게 문제를 해결해나갔다. 이렇게 행복 회로를 돌리고 있다가 객관식을 맞이하면.. 2022. 8. 7.
백준 1991번 트리 순회 - python 해당 문제는 이진 트리의 전위 순회, 중위 순회, 후위 순회를 이해하고 있는지에 대한 문제라고 생각한다. 재귀를 이용해서 문제를 풀어 나갔는데, edge의 node들을 defaultdict에 리스트 형태로 저장해서 탐색을 진행해 나갔다. 순회하는 방식은 동일하지만 언제 출력을 진행하는 가에 차이에 따라 전위, 중위, 후위가 결정 된다. 그래서 아래의 함수를 보면 동일한 방식을 채택하고 있지만, 출력문의 위치만 다른 것을 볼 수 있다. def pre_order(n): if n != '.': print(n, end='') pre_order(edge[n][0]) pre_order(edge[n][1]) def in_order(n): if n != '.': in_order(edge[n][0]) print(n, e.. 2022. 7. 26.
[우리은행] 코딩테스트 후기 우리은행 서류 결과가 발표났다. 싸피 6기 졸업생이라서 서류 합격에 대해서는 문제가 되지 않았지만, 금융권 코딩테스트에 대해선 계속 탈락하여 부담을 느끼고 있었다. 그래서 코딩 알고리즘 스터디를 준비하며 꾸준히 칼을 갈고 있었다. 7월 23일 9시에 코딩테스트가 진행 되었고 알고리즘 3문제, SQL 1문제가 나왔다. 1번의 경우에는 DP라는 말이 많았는데, 그렇게 어렵진 않았다. 2번의 경우에는 구현 문제인데 주어진 문제에 대해 반대로 풀어나가면 풀리는 문제였다..이 사실을 시험이 끝나고 난 뒤 깨달아서 아쉬움이 있다. 3번의 경우도 DP 문제로써 최소 비용을 구하는 문제였다. 해당 문제의 경우에는 리스트를 이용하여 문제를 해결해 나갔고 히든케이스도 어느정도 잡았다고 생각한다. 그러나 테케가 3개정도만 .. 2022. 7. 24.
[KT클라우스] kt cloud 온라인 시험전형 결과 발표 kt cloud 코딩테스트 결과가 발표되었다. 이번에도 운이 좋게 합격을 하게 되었다. 솔직히 긴장하고 문제를 풀기도 했고 시간도 일주일정도 지나 문제에 대해서는 생각이 잘 나지 않는다. 지금 생각해보면 4문제 정도 나왔던것 같고 백준 기준으로 실버1의 수준을 가지고 있다면 문제를 다 푸는데 걱정이 없을 것이라고 생각이 된다. kt cloud 를 준비하시는 분들에게 많은 도움을 주고 싶지만 생각이 나지 않아 안타깝게 생각한다. 추후에 면접을 보게 되면 그때 면접과 관련한 내용을 풀어 나가보도록 하겠습니다. 감사합니다. 2022. 7. 22.
백준 2004번 조합 0개의 개수 - python 처음 해당 문제를 봤을 때 팩토리얼을 활용하여 문제를 풀어도 되지만 시간초과가 날 것 같다는 생각이 들었다. 그러나 정말 그런지 궁금하니 한번 돌려보자.. from math import factorial n, k = map(int, input().split()) number = factorial(n) // (factorial(k) * factorial(n - k)) i = 0 while True: if not number % (10 ** i): i += 1 else: print(i - 1) break 해당 코드로 실행하니 당연하게 시가 초과가 발생했다. 이를 해결하기 위해 다른 방법에 대해 고민을 해 본 결과, m과 n-m의 최소값 만큼 반복문을 실행하는 방식을 진행해 보았다. n, k = map(int.. 2022. 6. 20.
[python]백준 21610번 - 마법사 상어와 비바라기 (feat. 삼성 SW 역량 테스트 기출 문제) https://www.acmicpc.net/problem/21610 21610번: 마법사 상어와 비바라기 마법사 상어는 파이어볼, 토네이도, 파이어스톰, 물복사버그 마법을 할 수 있다. 오늘 새로 배운 마법은 비바라기이다. 비바라기를 시전하면 하늘에 비구름을 만들 수 있다. 오늘은 비바라기 www.acmicpc.net 해당 문제를 푸는데 있어서 문제 이해를 하는데 어려움이 좀 있었고 다 구현한 뒤에도 시간 초과를 해결하는데 애를 먹었다. 최대한 함수를 이용하여 보기 쉽게 코드를 작성해봤는데 도움이 될 지 모르겠습니다. 아래 코드 참고 # d, s가 정해졌을 때 범위 안에서 움직이도록 만드는 함수 def moves(val, direction, sep, n): val = val + direction * se.. 2021. 12. 2.
[python]백준 14888번 - 연산자 끼워넣기(feat. 삼성 SW 역량 테스트 기출 문제) https://www.acmicpc.net/problem/14888 해당 문제를 풀어 나갈때 permutations를 이용하는 것은 알았는데 이를 중복 제거하는 법을 잘 몰라 좀 헤매는 문제였다. 그냥 set(permutations())를 쓰면 되는걸 알게 된 문제.. 아래 코드 참고 from itertools import permutations answer = [] # 입력 값 받는 곳 N = int(input()) numbers = list(input().split()) operates = list(map(int, input().split())) # 연산자 어떤게 포함되는 지 저장하는 곳 opers = [] # operates를 순회하면서 각 엽산자의 횟수만큼 저장 for idx in range(le.. 2021. 12. 2.
[python]백준 13458번 - 시험 감독 (feat. 삼성 SW 역량 테스트 기출 문제) 해당 문제는 브론즈 2 수준의 간단한(?) 문제인 것 같다. 저는 해당 문제를 주 각 강의실에 주 감독관이 감독할 수 있는 학생의 수를 먼저 제거한 뒤 나머지 학생애 대해서 필요한 부 감독관의 수를 구하는 방식으로 풀어 나갔습니다. 아래 코드 참조 answer = 0 # 입력을 받는 부분 N = int(input()) A = list(map(int, input().split())) B, C = map(int, input().split()) # 각 강의실 마다 학생 수를 확인하며 for student in A: # 먼저 감독관이 감독할 수 있는 학생의 수를 구하고 감독한 학생의 수를 빼준다 answer += 1 student -= B # 이후에 감독이 필요한 학생이 남는 경우, 부감독관의 수를 구하기 위한.. 2021. 11. 30.
반응형

티스토리툴바