알고리즘

첫 시도 하지만 시간 초과 발생. 이번에도 문제는 input()이었다. 따라서 sys.stdin.readline()으로 변경해줬다. ![](https://images.velog.io/images/hozero/post/9df688d1-f617-4db5-a073-331

카운팅 정렬을 이용하는 문제

문제를 분석해보면, 중복을 제거한 후 정렬된 리스트에서 각 수에 대응되는 인덱스를 출력하는 문제이다.

백트래킹 입문 문제 1, 2

첫 풀이(시간초과)

출처: 2022 KAKAO BLIND RECRUITMENT난이도: 프로그래머스 Lv1

해시를 통해 입력을 받지만 수학공식을 찾아내는 수학문제.

python의 replace를 통해 치환하면 가볍게 풀리는 문제이다.

거리두기를 지키지 않는 경우의 수를 생각한 뒤 각 경우를 if문으로 처리하면 풀리는 문제이다.

효율성 테스트를 통과하기 쉽지 않은 문제

LIS(Longest Increasing Subsequence)를 구하는 문제

가운데 기준점을 옮겨가며 양방향에서의 LIS를 구하면 되는 문제이다.

LIS 응용 문제

LCS(Longest Common Subsequence)를 구하는 문제

누적합을 빠르게 구하는 방법을 이용하고, 이중 for문을 통해 모든 가능한 i,j에 대해 체크하면 시간초과가 발생한다.따라서 다른 방법을 이용해야 하는데,(a + b) % MOD = (a % MOD + b % MOD) % MOD를 생각하여 접근해야 한다.구간합에 따른

다음과 같이 dp를 정의하고 접근했다.dpi: i번째 물건까지 최대 j무게로 했을 때 최대가치

우선순위큐를 통해 시간복잡도를 낮추는 문제

풀이시간: 실패모듈로 연산의 나눗셈을 처리하는 법을 알아야 하고, 제곱 수를 빠르게 구하는 방법 2가지를 알아야 풀 수 있는 문제이다.https://goodteacher.tistory.com/398

이항 계수 3을 풀다가 관련되어서 풀게된 문제이다.한 수의 n승을 분할정복을 통해 빠르게 얻을 수 있고, 나는 재귀를 통해 풀이했다.

제곱수를 분할정복을 통해 빠르게 구하는 로직을 행렬에 적용하는 문제이다.

다음 5단계로 TODO를 적고 하나씩 코드를 작성해 나갔다.1\. 미네랄 제거2\. 클러스터마다 묶어서 좌표 저장(BFS나 DFS)3\. 클러스터 중에 떨어질 클러스터있나 찾기4\. 떨어질 클러스터에서 이동해야 할 좌표수 구하기5\. 이동하기이때, 5번째 단계에서 이동

https://school.programmers.co.kr/learn/courses/30/lessons/92341?language=python3

다음 2가지를 해야 하는 문제이다.소수판정n을 k진수로 변환수가 n까지 주어져서 에라토스테네세의 체로 n까지 소수여부를 모두 계산해두려 했는데, k진수로 바꾼 후 살피므로 n을 넘는 매우 긴 수도 등장한다. 따라서 $$\\sqrt{n}$$까지 계산하는 방법을 이용해야

음양 더하기, 소수 만들기, 키패드, 체육복

없는 숫자 더하기

처음에 푼 풀이는 다음과 같다. 반드시 부모노드를 방문해야 그 자녀노드를 방문할 수 있고, 방문 가능한 자녀노드들은 어디서든 접근 가능하다.

시간복잡도로 효율성 테스트를 통과하지 못하여 다른 접근 방법을 고민하다가 도저히 생각이 안나 우선 $$O(NMK)$$(k:skill의 길이)의 시간복잡도로 작성한 코드는 다음과 같다.

문제에서 구현하라는대로 구현하면 되는 문제이다.

위 코드를 좀 더 pythonic하게 바꾸면 다음과 같다.collections.Counter를 쓰고 most_common을 통해 처리하는 방법도 있다.

모든 사람이 각 쿼리에 해당하는지 확인하는 브루트포스로 풀면 다음과 같다.하지만 이는 시간복잡도 $O(N\*M)$(N: info 배열의 크기<=50,000, M: query 배열의 크기<=100,000)으로 효율성 테스트를 통과하지 못한다.

초반에 제출한 풀이. set을 재귀로 전달할때 .copy()를 안해줘서 삽질을 오래했다.

| | 한 노드 기준 최단 경로 | 모든 노드 쌍의 최단 경로 | |:----------|:----------:|----------:| | Edge에 weight 없음 | Breadth First Search (BFS) | Floyd-Warshall Algorithm

문제에서 최대, 최소값을 구하기 위해 초기 설정해줘야 하는 값이 자주 등장하는데 방법은 2가지다.1\. sys.maxsize2\. float('inf')float('inf')가 코드에서 더 직관적인 것 같다. 출력할때도 inf로 나와서 디버깅에도 유용하다.

누적합 이용하는 문제

ctrl을 누르고 방향키를 누른 경우를 제외하고 풀면 다음과 같다.

반복횟수가 2자리가 넘어가는 경우를 생각못하고 항상 1을 더해서 초반에 틀렸던 문제

올바른 괄호를 체크하는건 푼 경험이 있어서 금방 작성할 수 있었고,문제에서 하라는대로 코드를 작성하면 풀렸다. 재귀여서 복잡할 수 있는데 친절하게 알려줘서 큰 혼란은 없었다.

문제에서 N과 M의 최대값이 20인걸 통해 시간복잡도가 매우 높은 방법으로 접근해도 되겠다고 생각했다.

can_install을 삭제에서도 재활용하는 방법을 생각해내야 한다.

N범위도 작고, 최단경로라 BFS로 하려 했는데, 조건이 까다로워 DFS로 갔다. 생각해보니 경로상 있는 조건이 아니어서 BFS로 하는게 나았을 것 같다. 그리고 BFS로 하면 visited배열도 신경안쓰고 처음 나타난게 정답이니 로직이 좀 더 간단해진다.

정확도만 생각하고 푼 풀이는 다음과 같다.

입장기록을 관리하는 리스트에서는 uid로 모두 기록한 후, uid와 nickname매칭을 관리하는 리스트를 갱신시킨 후 나중에 한번에 다 바꿔주는 방식으로 풀었다.

문제 그대로 코드를 작성하면 된다. 이때 시간복잡도가 널널해서 이용하지 않았지만 누적합을 한번에 적용시키는 로직을 이용할 수도 있을 것 같다.

우선순위 큐로 접근해야하는 문제이다.

약 50분의 풀이시간 끝에 처음 작성한 풀이는 다음과 같다.이때, 대부분은 시간초과가 나고, 런타임에러도 몇개 같이 나왔다.

50분 정도 소요되어서 제출 후 정답처리된 코드이다.전체적으로 문자열을 잘 다뤄야 하는데, 정규표현식이 유용하게 쓰였다.정규표현식 구현 방법은 검색을 통해 참고했는데, 평소에 익혀둘 필요가 있을 것 같다.

처음 작성한 스켈레톤 코드는 다음과 같다.

https://www.acmicpc.net/blog/view/70

구현, 그래프 이론, 그래프 탐색, 너비 우선 탐색, 시뮬레이션

구현, 자료 구조, 시뮬레이션

구현, 시뮬레이션

구현, 브루트포스 알고리즘

구현, 시뮬레이션

구현

수학, 사칙연산

구현 브루트포스 알고리즘 시뮬레이션 백트래킹

구현 시뮬레이션

구현 자료 구조 시뮬레이션 덱 큐

구현 브루트포스 알고리즘 시뮬레이션

https://www.acmicpc.net/problem/15686

구현 시뮬레이션

구현 시뮬레이션

구현 그래프 이론 그래프 탐색 너비 우선 탐색 시뮬레이션

구현 시뮬레이션

https://www.acmicpc.net/problem/17140

구현 시뮬레이션

그래프 이론 브루트포스 알고리즘 그래프 탐색 너비 우선 탐색

https://www.acmicpc.net/problem/20055

구현 시뮬레이션

구현

구현 그래프 이론 그래프 탐색 너비 우선 탐색 시뮬레이션

1. 개인정보 수집 유효기간 2. 택배 배달과 수거하기 3. 이모티콘 할인 행사

구현 그래프 이론 그래프 탐색 너비 우선 탐색 시뮬레이션 깊이 우선 탐색

삼성 기출 구현 문제 중에 가장 어려웠다,, 특히, 시간초과가 뜬 적은 처음이라 풀이보면서 다시 정리해봐야될 듯.아직 시간초과가 뜬다

https://www.acmicpc.net/problem/17837

https://www.acmicpc.net/problem/17822AC까지 1시간 15분 소요되었다.인접하는 예외처리에서 0~M을 벗어나는 경우를 음수만 고려했는데, M을 초과하는 경우에 대해서도 고려해줬어야 했다. python에서는 모듈로 연산으로 처리하는게

문제 https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AWXRUN9KfZ8DFAUo&categoryId=AWXRUN9KfZ8DFAUo&categoryType=CODE&problem

https://www.acmicpc.net/problem/21610

문제 https://www.codetree.ai/training-field/frequent-problems/problems/maze-runner/description?page=1&pageSize=20 풀이 AC까지 약 2시간 소요되었다. 특히 코드 작성 후 틀렸습니다를 받고 원인을 찾는데 원인을 많이 썼다. 원인은 게임이 종료되는 위치를 잘 못 적어서였다...

문제 https://www.codetree.ai/training-field/frequent-problems/problems/destroy-the-turret/description?page=1&pageSize=20 풀이 쭉 작성한 뒤에 놓친 조건들이 몇 군데 있었다.

https://school.programmers.co.kr/learn/courses/30/lessons/43165

평균 일일 대여 요금 구하기

https://www.acmicpc.net/problem/1546

https://www.acmicpc.net/problem/11659내가 작성한 풀이는 다음과 같다.책에서의 풀이는 다음과 같다.

https://www.acmicpc.net/problem/1253

The vector container provides a dynamic arrray. It is defined as std::vector class template inside header file.Vector DeclarationC++ STL Cheat Sheet

https://www.acmicpc.net/problem/11399그리디하게 짧게 걸리는것부터 처리하도록 하여 문제를 풀었다.

https://www.acmicpc.net/problem/1517N이 최대 500,000이므로 $O(N^2)$으로 풀 수 없다는 사실을 알 수 있다. 따라서 $O(N)$ 혹은 $O(Nlog(N))$으로 풀어야 할 것 같은데 고민을 해도 접근 방법이 떠오르지 않

2023년 9월부터 이어진 길고 길었던 채용 프로세스가 끝난 기념으로 삼성의 코딩테스트인 S/W 역량테스트(A형) 합격 후기를 뒤늦게나마 작성하고자 한다.추후 삼성의 코딩테스트를 준비하는 분들에게 도움이 되었으면 한다.삼성은 예전까지 3시간을 주고 2문제 모두 빡구현으

https://www.acmicpc.net/problem/1016문제를 보면 min과 max 사이 텀이 최대 1,000,000인 것을 보고 이 구간을 선형 탐색하면 문제가 없다고 생각했고, 에라토스테네스의 체도 생각했다.다만, 가능한 제곱수가 2^2부터 (10

완전탐색에 해당하는 문제이다.https://school.programmers.co.kr/learn/courses/30/lessons/42839itertools의 permutations를 이용하여 모든 경우의 수를 쉽게 구할 수 있다.또한, 소수인지 판정할 때

https://school.programmers.co.kr/learn/courses/30/lessons/84512itertools의 product를 써서 중복순열을 구할 수 있다. 처음엔 permutations를 사용하였는데, 중복이 허용되므로 'AA'와 같은