코딩테스트 2020 KAKAO 신입 공채 를 풀다보니 2차원 배열의 90도 회전을 요구하는 문제가 있었다. 파이썬에서 2차원 리스트를 다룰 때 종종 사용되는 개념이므로 코드공식에 적어두고 필요할 때마다 꺼내봐야겠다. 그 전에 회전 알고리즘 원리를 먼저 파악해보자. 해당 2020 카카오 문제를 풀면서 2차원 배열 회전을 처음 맞닥뜨렸다면 절대 제시간 내에 풀지 못했을 것이다.. 보다 이해하기 쉽게 정리해봤다. 시계방향으로 90도 회전할 때, 회전 후의 행과 열 값을 알아야 한다. 2차원 배열이 회전할 때는 일정한 규칙이 있다. 90도 회전할 때의 위치를 모두 연결해보면 일정한 사이클이 있다. 사이클이 생긴다는 것은 요소의 합이 N일 가능성이 있다. (이때 N은 사각형의 크기) 그래서 나온 공식이 사진의 1..
이코테 책에서 풀다가 복습할 내용들만 정리해본다. 자세한 문제는 '이것이 코딩테스트다 with 파이썬 (나동빈)' 책에서 확인하기 구현 문제란 특별한 알고리즘 기법은 필요 없는 정확한 풀이가 핵심이 되는 문제를 말한다. 풀이를 떠올리는 것은 쉽지만 소스코드로 옮기기 어려운 문제를 의미하며 나는 이런 부분에 많이 취약한 것 같다. - 알고리즘은 간단한데 코드가 지나칠만큼 길어지는 문제 - 특정 소수점 자리까지 출력해야 하는 문제 - 문자열이 입력으로 주어졌을 때 한 문자 단위로 끊어서 리스트에 넣어야 하는 문제 - 2차원 배열에서의 이동, 회전 등 까다로운 문제 특히 완전탐색과 시뮬레이션 유형은 모두 구현 유형으로 볼 수 있다. 완전탐색은 모든 경우의 수를 주저 없이 다 계산하는 해결 방법을 의미하고, 시..
이코테 책에서 풀다가 복습할 문제들만 정리해본다. 자세한 문제는 '이것이 코딩테스트다 with 파이썬 (나동빈)' 책에서 확인하기 1️⃣ 만들 수 없는 금액 (K 대회 기출) N개의 동전으로 양의 정수 금액 중 만들 수 없는 최솟값을 구하는 프로그램을 작성하라. 첫번째 풀이) 1원부터 만들 수 있는 최대값까지 주어진 N개의 동전으로 만들 수 있는지 확인해야 하므로 먼저 화폐 단위를 내림차순으로 정렬한다. 예를 들어 3, 2, 1, 1, 9 가 주어졌다면 9, 3, 2, 1, 1 로 정렬한다. 그리고 1원부터 주어진 동전 조합으로 만들 수 있는지 coin[0]부터 체크한다. 즉, 9부터 3, 2, 1, 1 순으로 1원을 만들 수 있는지 확인하고 coin[3] = 1로 만들 수 있음을 확인하면 다음 숫자인 ..
📂 분할상각기법 어떠한 임의의 알고리즘에 대해서, 어떤 연산은 자원적 측면에서 상당한 비용을 소모할 수 있지만, 반면 다른 연산은 그렇게 고비용을 소모하지 않을 수 있다. 분할상환 분석은 알고리즘의 전반적인 연산 집합에 대해 비용이 높은 연산, 그리고 비용이 덜한 연산 모두를 함께 고려하는 기법이라 하겠다. 이것은 다른 종류의 입력, 입력의 길이, 이 알고리즘의 성능에 영향을 미치는 다른 요인들을 전부 고려한다. 수행된 모든 연산에 대해 자료구조 연산만의 어떤 시퀀스를 수행하는데 필요한 시간의 평균을 구한다. 비록 그 시퀀스에서 하나의 연산비용이 비싸더라도, 그 일련의 연산에 대해 평균을 구하면 연산 하나의 평균 비용이 작다는 것을 분할 상환 분석을 이용해 보일 수 있다. 분할 상환 분석은 확률이 포함되..
📂 해시테이블 정렬알고리즘에 비해 탐색알고리즘은 수시로 탐색이 진행된다(ex. 데이터베이스에서 원하는 데이터를 찾을 때) 따라서 탐색 알고리즘에서 탐색에 소요되는 시간을 단축시키는 것은 굉장히 중요한 이슈이다. 원소가 저장될 자리가 원소의 값에 의해 바로 결정되는 자료구조 → O(1) 시간으로 매우 빠른 응답을 요구할 때 사용되는 기법 cf. 탐색 트리의 경우 원소의 값에 의해 위치가 결정되지만 트리를 탐색해 내려가는 시간이 소요됨 최소값, 특정값 바로 전/후의 값 등을 찾아낼 수 없으며 그냥 특정값의 위치를 찾아내기만 하는 '탐색'의 기능만 함 해시테이블에서는 해시함수 h(x) = (ax + b) mod p 를 이용해 원소가 저장될 위치를 결정함 h(x) = x mod 11 값을 균등하게 배분할수록 좋..
📁 최단거리문제 보통 시작노드부터 도착노드까지의 최단경로를 구하는 형식의 문제이다. MST에서 알 수 있듯이 최단경로는 절대 사이클을 포함하지 않는다. 최단거리 문제는 가중치 유무에 따라, 가중치가 있을 경우엔 가중치의 음양에 따라 알맞은 알고리즘을 사용한다. 양의 가중치만 있을 때 : 다익스트라 알고리즘(Dijkstra's Algorithm) 음의 가중치만 있을 때 : 벨만포드 알고리즘(Bellman-Ford Algorithm) n 대 n의 최단거리를 모두 구하고 싶을 때 : 플로이드와샬 알고리즘(Floyd-Warshall Algorithm) 📁 다익스트라 알고리즘 Dijkstra's Algorithm 에지의 가중치가 양수일 때 사용한다. 음수 가중치를 고려하지 않으므로 가중치의 합이 최단거리를 좌우한..
📂 최소신장트리 (Minimum Spanning Tree) 신장트리 : 그래프 G의 노드 V를 모두 포함하는 E에 속하는 에지를 사용해 만든 트리 최소신장트리 : 가중그래프 G의 신장트리 중에서 트리에 속한 가중치의 합을 최소로 하는 신장 트리 최소신장트리를 만드는 2가지 방법 : Prim's Algorithm, Kruskal's Algorithm 최소신장트리의 간선 개수는 (정점의 수 - 1) 이다. (N-1개의 간선으로 연결되어 있으면 필연적으로 모든 노드가 연결된다) 간선들의 가중치 합이 최소인 경우 서로 다른 최소신장트리가 하나 이상 있을 수 있다. 📂 크루스칼 알고리즘 (Kruskal's Algorithm) 가중치가 가장 작은 간선부터 차례대로 간선을 선택해 나가는 방법으로, 탐욕적(greedy..
그래프 그래프 G = (V, E) 이때 V는 노드, E는 에지이다. 에지 E는 V * V 의 부분집합이다 (즉 노드와 노드를 연결하는 모든 쌍의 부분집합) 유향그래프 vs 무향그래프 : 에지의 방향성에 따라 유향그래프 : (i, j) ≠ (j, i) 무향그래프 : (i, j) = (j, i) 양방향 유향그래프 가중그래프 G = (V, E, W) 가중그래프(weighted graph)는 에지마다 가중치 W를 가진다 보통 사람은 그래프를 손으로 그려 시각적으로 보는 걸 선호하지만, 컴퓨터로는 2차원 행렬 또는 리스트로 표현한다. 그래프의 탐색 자체는 그리 어렵지 않다. 효율적인 탐색을 위해 깊이우선, 너비우선 탐색으로 분류할 수 있다. 그리 어렵지 않은 내용이므로 그림은 과감히 생략ㅎ 깊이우선탐색 (Dept..
