[SW Expert Academy] 알고리즘 문제 로그
알고리즘 문제 전략
각 문제는 2시간 해결을 목표로 한다.
Part1. 전략 세우기
-서두르지 말고 연필을 쥐고 충분히 고민한다.
-단계 별로 문제를 단순화한다.
-순서도 / 수도코드를 그려본다.
-코딩 전에 개발 전략이 완성되어야 한다.
-시간 복잡도를 계산해본다.
Part2. 코딩
-모듈화가 디버깅 시간을 좌우한다.
1240, 1242번 - 이진 암호 코드 문제
이진 암호 코드는 구현력을 요구하는 문제였다.
1240의 경우 2시간 내에 풀 수 있었다.
반면, 1242는 문제가 매우 복잡하고 input 데이터도 1MB를 초과하여, 복잡한 input에 대한 디버깅이 사실상 힘들었다.
약 3일에 걸쳐 풀었으나, 20개의 testcase 중 18개까지 도는데 성공하였다.
또, LoC가 450줄을 초과하였다.
정답코드를 보니, LoC가 150줄 이하로, STL이 제공하는 String과 Vector를 적절하게 사용하여 훨씬 짧은 코드를 달성하였다.
또, 문제를 단계별로 분리하여, 단순화한 점이 뛰어났다.
문제답안 https://github.com/jwahn37/Algorithm_Samsung.git
1245번 - 균형점 문제
테스트케이스 1개가 안돌라가서 디버깅이 오래걸렸다.
알고보니 binary search를 위한 caller가 너무 넓은 범위 [d[0], d[N-1]]를 조사하도록 한것임.
수학적으로 d[i], d[i+1]사이로 범위를 줘야 정확히 계산하는 것이었음.
사실상 그 외로 갈일이 없다는걸 인지하지 못한 실수
1244번 - 최대 상금 문제
예외 상황을 고려하지 못해 시간이 생각보다 오래 걸렸다.
다만, 완전탐색의 경우를 처음에 생각해봤다면, 오히려 더 간단한 코드가 나왔을지도 모른다.
STL코드를 좀 정리하고 넘어갈 필요가 있다.
1248번 - 공통 조상 문제
분할 정복 섹션에서 트리문제라니, 연결성을 모르겠다.
문제를 단계별로 세가지 요소로 단순화하여 풀었다.
1. 트리 만들기, 각 노드의 level 구하기
2. 공통 조상 찾기
3. 서브트리의 노드 갯수 구하기
구글에서 정답 코드를 살펴보았다.(https://his130.tistory.com/466)
플로우는 비슷하지만, 배울 점이 많은 코드였다.
1. 모든 노드의 level을 구하지 않았다. 다만, 비교할 두 정점의 깊이만 구하면 충분했다.
2. 공통 조상을 찾을때, 노드의 깊이를 갖게 맞춘 후, 값을 비교하면서 부모노드로 올라가는 코드는 심플해서 인상적이다.
3. bfs로 푼 나와 달리, dfs로 해결한 코드도 return부분에서 배울 점이 있다. [블로그에는 이 부분이 분할 정복방식이라고 쓰여있다.]
1247번 - 최적 경로 문제
기본적인 삼성 입사 시험 문제로, 난이도가 낮은 편이다. dfs+가지치기인 [백트래킹]방식으로 해결하면 된다.
1249번 - 보급로 문제
원래 최단경로 문제이지만, BFS로 해결할 수도 있다. BFS로 해결하려니, visited 대신 distance로 큐 삽입을 정하는 부분이 헷갈리고 오래걸렸다. 또, 시간복잡도를 예상하기가 어려웠다. 사실 최적화하기가 까다로웠던게 사실이다. (그래서 안했지만, 잘 돌아가더라)
1251번 - 하나로
최소 신장 트리 문제이다. 그래프를 생성하고, 신장 트리를 만들어 해결하면 된다.
익숙하지 않아 2시간 10분 소모됨.
하지만 문제를 풀면서, disjoint set(union and find), combination, graph, prim algorithm을 구현해볼 수 있었다. 비록 코드라인은 200줄을 넘겼지만, 다양한 구현을 해볼 수 있어서 좋았음.
1256번 - K번째 접미어
문제는 어렵지 않으나, STL에서 제공하는 string과 sort()을 얼마나 잘 요리하느냐가 중요하다.
1257번 - K번째 문자열
string, sort이용을 잘해야 하며, 중복 제거가 중요함.
1258(행렬 찾기), 1259(금속 막대), 1260(화학물질2)
Dynamic Programming(DP) 문제로, 세문제가 연결된다.
1. 행렬을 찾고, 2. 곱셈이 가능하게 행렬을 정렬한 후, 3. 최소 횟수의 곱셈 순서를 결정해야 한다.
2는 DP를 이용하여 해결하였다.
a[r][c] = max(a[r][c], a[r][k]+a[k][c]+r*k*c), 1<=k<=행렬의 크기
챌린지는 정렬된 행렬의 정보를 출력해야 한다는 것이었다.
따라서 a는 vector로 정의하였다. 이 경우 메모리 할당량이 커지는 문제가 있다.
메모리크기를 제한하는 방식은 떠오르지 않았다.
3도 DP를 이용하여 해결하였다.
1263(사람 네트워크2)
n=1000이라 플로이드 와샬(O(n^3))을 써도 될지 걱정했는데, 쓰는 것이 맞다.
다만, 최적화하지 않으면 시간 초과가 떴다.
생각한 풀이의 복잡도가 문제 조건에 비해 애매하게 크다면(10배 이하), 풀이를 그대로 쓰되, 최적화를 유의하는게 올바른 방향인 것 같다.
늘 그래프 문제는 어렵다. 자주 접하지 않기 때문이다. 한번씩 풀어줘야겠다.
1264(이미지 유사도)
문자열 DP문제
각 문제는 2시간 해결을 목표로 한다.
Part1. 전략 세우기
-서두르지 말고 연필을 쥐고 충분히 고민한다.
-단계 별로 문제를 단순화한다.
-순서도 / 수도코드를 그려본다.
-코딩 전에 개발 전략이 완성되어야 한다.
-시간 복잡도를 계산해본다.
Part2. 코딩
-모듈화가 디버깅 시간을 좌우한다.
-C++ STL을 적절히 활용하여 코드를 줄인다.
-변수 크기는 넉넉하게 (굳이 char쓰지마라)
Part3. 디버깅
-매번 테스트케이스마다 초기화 됐는지 철저히 체크
-데이터 타입 체크
-데이터 타입 체크
이진 암호 코드는 구현력을 요구하는 문제였다.
1240의 경우 2시간 내에 풀 수 있었다.
반면, 1242는 문제가 매우 복잡하고 input 데이터도 1MB를 초과하여, 복잡한 input에 대한 디버깅이 사실상 힘들었다.
약 3일에 걸쳐 풀었으나, 20개의 testcase 중 18개까지 도는데 성공하였다.
또, LoC가 450줄을 초과하였다.
정답코드를 보니, LoC가 150줄 이하로, STL이 제공하는 String과 Vector를 적절하게 사용하여 훨씬 짧은 코드를 달성하였다.
또, 문제를 단계별로 분리하여, 단순화한 점이 뛰어났다.
문제답안 https://github.com/jwahn37/Algorithm_Samsung.git
1245번 - 균형점 문제
테스트케이스 1개가 안돌라가서 디버깅이 오래걸렸다.
알고보니 binary search를 위한 caller가 너무 넓은 범위 [d[0], d[N-1]]를 조사하도록 한것임.
수학적으로 d[i], d[i+1]사이로 범위를 줘야 정확히 계산하는 것이었음.
사실상 그 외로 갈일이 없다는걸 인지하지 못한 실수
1244번 - 최대 상금 문제
예외 상황을 고려하지 못해 시간이 생각보다 오래 걸렸다.
다만, 완전탐색의 경우를 처음에 생각해봤다면, 오히려 더 간단한 코드가 나왔을지도 모른다.
STL코드를 좀 정리하고 넘어갈 필요가 있다.
1248번 - 공통 조상 문제
분할 정복 섹션에서 트리문제라니, 연결성을 모르겠다.
문제를 단계별로 세가지 요소로 단순화하여 풀었다.
1. 트리 만들기, 각 노드의 level 구하기
2. 공통 조상 찾기
3. 서브트리의 노드 갯수 구하기
구글에서 정답 코드를 살펴보았다.(https://his130.tistory.com/466)
플로우는 비슷하지만, 배울 점이 많은 코드였다.
1. 모든 노드의 level을 구하지 않았다. 다만, 비교할 두 정점의 깊이만 구하면 충분했다.
2. 공통 조상을 찾을때, 노드의 깊이를 갖게 맞춘 후, 값을 비교하면서 부모노드로 올라가는 코드는 심플해서 인상적이다.
3. bfs로 푼 나와 달리, dfs로 해결한 코드도 return부분에서 배울 점이 있다. [블로그에는 이 부분이 분할 정복방식이라고 쓰여있다.]
1247번 - 최적 경로 문제
기본적인 삼성 입사 시험 문제로, 난이도가 낮은 편이다. dfs+가지치기인 [백트래킹]방식으로 해결하면 된다.
1249번 - 보급로 문제
원래 최단경로 문제이지만, BFS로 해결할 수도 있다. BFS로 해결하려니, visited 대신 distance로 큐 삽입을 정하는 부분이 헷갈리고 오래걸렸다. 또, 시간복잡도를 예상하기가 어려웠다. 사실 최적화하기가 까다로웠던게 사실이다. (그래서 안했지만, 잘 돌아가더라)
1251번 - 하나로
최소 신장 트리 문제이다. 그래프를 생성하고, 신장 트리를 만들어 해결하면 된다.
익숙하지 않아 2시간 10분 소모됨.
하지만 문제를 풀면서, disjoint set(union and find), combination, graph, prim algorithm을 구현해볼 수 있었다. 비록 코드라인은 200줄을 넘겼지만, 다양한 구현을 해볼 수 있어서 좋았음.
1256번 - K번째 접미어
문제는 어렵지 않으나, STL에서 제공하는 string과 sort()을 얼마나 잘 요리하느냐가 중요하다.
1257번 - K번째 문자열
string, sort이용을 잘해야 하며, 중복 제거가 중요함.
1258(행렬 찾기), 1259(금속 막대), 1260(화학물질2)
Dynamic Programming(DP) 문제로, 세문제가 연결된다.
1. 행렬을 찾고, 2. 곱셈이 가능하게 행렬을 정렬한 후, 3. 최소 횟수의 곱셈 순서를 결정해야 한다.
2는 DP를 이용하여 해결하였다.
a[r][c] = max(a[r][c], a[r][k]+a[k][c]+r*k*c), 1<=k<=행렬의 크기
챌린지는 정렬된 행렬의 정보를 출력해야 한다는 것이었다.
따라서 a는 vector로 정의하였다. 이 경우 메모리 할당량이 커지는 문제가 있다.
메모리크기를 제한하는 방식은 떠오르지 않았다.
3도 DP를 이용하여 해결하였다.
1263(사람 네트워크2)
n=1000이라 플로이드 와샬(O(n^3))을 써도 될지 걱정했는데, 쓰는 것이 맞다.
다만, 최적화하지 않으면 시간 초과가 떴다.
생각한 풀이의 복잡도가 문제 조건에 비해 애매하게 크다면(10배 이하), 풀이를 그대로 쓰되, 최적화를 유의하는게 올바른 방향인 것 같다.
늘 그래프 문제는 어렵다. 자주 접하지 않기 때문이다. 한번씩 풀어줘야겠다.
1264(이미지 유사도)
문자열 DP문제
댓글
댓글 쓰기