프로그래머스 1~2레벨 완료! and 일부 문제 후기

연습문제 완료

스킬체크 패스

프로그래머스 1, 2레벨 C++ 문제를 모두 풀었다.

약 130 문제를 푼 셈이다.

레벨2는 구현이 많고 까다로워 쉽지 않았다.

일부 문제는 백준 골드 문제나 프로그래머스 3레벨 문제보다 어려웠다.

일부 기억나는 문제 복기

1. 문자열 압축

처음에 너무 복잡해 풀지도 못했다. 추후 다시 접근해서

문자열 split, 9->10자리로 갈 때 문자열 증가 판단, 마지막 문자열이 정확히 떨어지지 않을 때 처리 등

단계별 구현, 그리고 예외처리에 신경을 써서 패스.

문자열 파싱과 여러 조건분기가 까다로웠다.

2. 오픈채팅방

문자열 split을 직접 구현하고 이름이 바뀌었을 때 갱신하는 부분에 신경써주었다.

이때 다른 사람이 쓴 코드에서 stringstream을 학습할 수 있었다.

3. 카카오 프렌즈 컬러링북

bfs 사이즈 구하기. bfs를 제대로 푼 첫 문제

바보같이 풀었다. 지금은 백준에서 관련 문제도 많이 풀어 지금은 훨씬 더 간단하게 짤 수 있을 듯.

4. 단체사진 찍기

순열 개념, 백트래킹 첫 익힘

다른 순열, 조합, 백트래킹 문제도 꽤 많았는데 이게 젤 기억에 남는다.

5. 멀쩡한 사각형

최대공약수 관련 간단한 식을 구해 푸는 문제

식은 간단하지만 아직도 증명하기 어렵다. 응용해서 나오면 또 못 풀 듯하다.

자료형 long long, 변수 수 범위의 중요성도 처음 깨우침

6. 행렬 테두리 회전하기

다른 알고리즘이 있을 줄 알았는데 그냥 다 더하고 스왑하는 식이었음

범위 설정 디테일이 필요한 문제였다.

‘삼각 달팽이’ 문제와 같이 범위에 따른 규칙을 이용하는 문제였던 것 같다.

7. 메뉴 리뉴얼

조합, 백트래킹 사용 + 최대인지 검사 및 중복 검사 등 예외처리가 쉽지 않던 문제

8. 괄호 변환

마지막에 고생한 6문제 중 하나.

주어가 확실치 않아 뭘 재귀를 돌려야 하는 건지 유추해야 했다.

해설을 본 뒤 나중에 풀어봤지만 그래도 안 풀리다가, 주어에 뭐가 들어갈지 다 실험해보니 풀렸다.

시키는 대로 구현만 하면 되는데, 문제 해석하기 까다롭다.

9. 거리두기 확인하기

자리를 중심으로 상하좌우 검사, 대각선도 검사하고, 유효하면 대각선에 근접한 자리를 또 검사해야 하는데

이러면 대각선 방향마다 조건분기가 다 있어 코드도 길어지고, 실수할 여지도 많았다. 그리고 난 결과적으로 이렇게 구현하다 틀렸다.

상하좌우만 검사해서 푸는 방법이 있었다.

참가자도 조사하지만, 빈 테이블도 상하좌우를 검사해서, 참가자가 2명 이상이면 맨해튼 거리가 2 이하였던 것.

때로는 직관적인 해결보다 다른 아이디어가 필요하단 점을 깨달음

10. 튜플

튜플 개념 학습. sort compare 첫 활용. + map 활용까지

11. 빛의 경로 사이클

마지막즈음 고생시킨 6천왕 중 하나.

첨에 문제 이해가 잘 안 돼 못 풀었었지만, 다른 사람 풀이를 보며

visited 3차원 배열의 활용, 실패했던 길이라도 이미 한 번 돌았던 길이면 안 돌아도 된다는 점, 시간복잡도 상 브루트포스가 가능하단 점

등을 깨닫고 풀 수 있었다.

12. 프린터

std::priority_queue 활용과 std::deque의 활용

인덱스를 따로 세트로 저장해야 한다는 점이 헷갈리게 했지만,

문제 자체는 어렵지 않았다.

후에 백준에 거의 동일한 문제를 풀어서 더 기억에 남는다.

13. 조이스틱

마지막즈음 고생시킨 6천왕 중 하나.

일일이 움직이며 그때마다 조이스틱 위아래 조작횟수 + 옆으로 움직인 횟수를 해주었지만 틀렸다.

반례를 보고 앞->뒤, 뒤->앞을 고려해 두 경우에서 최소한의 지점을 찾았지만 틀렸다.

앞->뒤, 뒤->앞으로 가는 경우의 수를 고려하되,

이를 위해 다음 ‘A’ 안 나오는 지점을 찾고

이동횟수는 그때그때마다 최적의 길을 찾아 갱신해야 하는 문제였다.

그리디 발상이 어려웠다. 이게 2레벨..?

14. 순위 검색

이것도 고생시킨 문제. 시간복잡도가 중요한 문제였다.

조합으로 각 요소를 뽑아야 하는 작업,

문자열을 따로 저장하는 것이 아니라 한 문자열에 다 넣은 파싱 작업,

map에 저장을 해 O(1) 만에 탐색이 가능하게 하는 작업,

마지막에 정렬 후 이분탐색 작업 등

코테 시간 내에 풀기 굉장히 어려울 것 같다. 이게.. 2레벨..?

정답을 봤었는데, 그후로도 계속 틀렸다. 매번 정렬을 해주는 게 문제였다.

그 전에 정렬을 쭉 한 번 돌린 뒤 연산을 해야했다.

15. 후보키

고생 6천왕 중 하나.

조합으로 후보를 쭉 뽑은 후

유일성 검사, 최소성 검사하는 함수를 구현해야 했다. 최소성 검사가 까다로웠다.

마지막에 배열[i]번째까지 돌아야 하는데 배열[0]번째까지 도는 실수를 해서 수 시간을 날려버렸다.

반복 시 초기값, 조건식, 증감식 설정에 유의해야했다.

16. 위장

상의 2개 하의 3개를 고를 때 ‘각각 아무 것도 고르지 않는 경우’가 있다.

그래서 경우의 수는 (2 + 1) * (3 + 1) = 12.

17. 큰 수 만들기

그리디 발상만 하면 매우 쉬운 문제

발상 때문에 백준에서 완전히 같은 문제인데 플래티넘5 급이다. 그 정돈 아닌 것 같지만…

백준에선 단순 문자열 비교, 정렬, 삭제 연산으로 풀었다.

프로그래머스에선 스택으로 풀었다. 스택 풀이는 어떤 거 보고 푼 건지 왜 이렇게 풀었는지 기억이 안 난다.

18. [1차] 프렌즈4블록

재밌는 구현, 시뮬레이션 문제

코드포스 잠깐 풀다가 비슷한 문제를 푼 적이 있다.

몇 개가 모이면 터져서 위의 블록들이 아래로 내려와서, 또 몇 개 모이면 연속으로 터지는…

퍼즐 게임 아이디어.

19. 교점에 별 만들기

두 직선의 방정식에서 교점을 찾는 공식을 학습했다.

사전 수학지식이 없으면 풀지 못하는 문제인 것 같다.

그 이외에도 double과 long long 자료형 설정의 중요성, 반복문 초기식과 조건식의 범위 설정에 유의했다.

20. 전력망을 둘로 나누기

전력망을 하나씩 끊어본 뒤 bfs를 돌려 어떤 노드와 연결된 노드의 사이즈를 구한 뒤,

다시 끊었던 전력망을 잇는 식으로 구현했다.

다른 사람 풀이에 람다식 + 전력망 끊고 잇는 작업 없이 siz만 구한 뒤 siz[j]와 n - siz[j]로 이분하는 코드를 보고

반성했던 기억이 난다.

21. 모음 사전

백트래킹 응용. 문자열 5글자까지 채우는 단계 -> 끝자리 변경하는 단계 처리

22. 캐시

Cash hit, Cash miss, Least Recently Used 등 컴공 지식을 첨 알았던 문제

duque 를 이용했고, 구현 자체는 어렵지 않았다.

23. 3xn 타일링

고생 6천왕 중 한 명. 원래 4레벨이었던 문제가 갑자기 2레벨로 내려와 당황했다.

‘2xn 타일링’처럼 점화식을 세워야 하는데, 그 점화식 유추하기가 풀이 없이는 떠올릴 수 없었다.

풀이를 증명해가며 공부하긴 했지만, 한참 뒤에 다시 봐도 풀기는 어려울 것 같다.

24. 스킬트리

첨에 위상정렬인 줄 알았지만

오히려 Union-Find의 parent 개념을 활용해 index가 노드, 앞서 나온 index는 부모라고 보고 구현했다.

다른 분들 풀이를 보니 벡터 순회하며 비교하는 풀이가 정해인 것으로 보인다.

25. 방문 길이

4차원 배열을 처음 써본 문제.

이제 보니 ‘빛의 경로 사이클’ 처럼 지나온 길에 대한 memo를 남겨 방문 체크를 해주기 위해,

지난 x, y, 새 x, y의 4차원 배열을 만들었다.

26. [3차] 방금그곡

특정 문자열에서 부분 문자열 찾기.

고려1. 찾았어도 뒤에 #이 있으면 안 됨.

고려2. ‘#’이 붙었으면 다음 인덱스부터 또 검사해야 함.

정해는 ‘C#’ -> ‘c’ 등 다른 문자로 대체하는 방식으로 보인다.

나는 kmp 알고리즘을 조금 공부해 외워

’#’ 등을 파싱하지 않고 부분 문자열 포함 여부를 검사했다.

그 때문인지 점수가 굉장히 좋게 나왔다.

하지만 kmp를 제대로 이해하기 어려워 그대로 외워 쓴 탓에 안 맞는 옷을 입은 느낌이다.

27. 가장 큰 정사각형 찾기

전 행, 전 열, 전 대각선의 dp 값과 비교해 최소값을 찾는 문제.

DP LCS 와 유사한 풀이인데 발상하지 못했다.

발상만 하면 풀기는 어렵지 않은 것 같다.

28. 압축

map으로 사전 계속 갱신하며, 중복이면 문자열 하나 더 검사해야 하는 로직이

간단하지만 쉽지 않았다.

29. [3차] N진수 게임

n진수 문제 연습에 좋은 문제

2진수부터 16진수까지 진법변환을 구현, 자동화할 수 있다.

‘k진수에서 소수 개수 구하기’ 문제와 비슷하나 ‘N진수 게임’이 더 쉬운듯

30. 땅따먹기

dp 연습 좋은 문제

첨 볼 땐 발상 못했지만 백준에도 비슷한 문제를 몇 번 풀어 이런 유형은 이제 어렵지 않다.

31. 줄 서는 방법

Lv3 문제였는데 Lv2로 내려온 문제

단순히 next_permutation을 사용하면 시간초과가 떴던 것으로 기억한다.

몇 번째에 몇 번째 자리에 어떤 숫자가 나올지 규칙성(팩토리얼)을 찾아 코드로 구현하는 문제

쉽지 않아 오래 걸렸지만 결국 풀었다.

32. 주차 요금 계산

문자열 파싱, stringstream, 시간 분 연산을 활용한 문제. 쉽진 않다.

33. 하노이의 탑

처음 하노이의 탑을 알려준 문제. 웰-노운 유형이지만 첨 볼 때 풀기는 불가능에 가까웠다.

34. N-Queen

웰-노운 유형 백트래킹 문제. 백준에서 미리 풀어봤는데도 또 다시 실패했다.

행을 인자로 가져와서 그 전까지 행은 반복문으로,

열과 대각선은 조건문으로 검사하는 부분을 작성 못했다.

특히 현재 row 전까지 모든 row를 반복문으로 조사하는 부분을 제대로 이해 못했던 것 같다.

35. 양궁대회

고생 6천왕 중 하나. 브루트포스, 백트래킹 기반 문제

조합으로 인덱스 하나씩 검사하며

하나보다 많은 개수만 찔끔 넣다가 마지막엔 다 남은 거 털어넣는 작업을 했다.

일반적으로 검사할 영역이 10개밖에 안 되서 완전탐색을 바로 떠올렸어야 하는데

그리디인 줄 알고 계속 고심했던 걸 반성한다.

또한 가장 큰 점수 차이일 때 가장 낮은 점수를 더 맞힌 경우를 리턴하기 위해 고민도 여러차례 했다.

마지막에 풀어서 다행인 문제

마치며

바보같이 백준 티어에만 신경 쓰느라 정작 목표인 코테 위한 문제를 안 풀었는데

백준 플레도 찍고 프로그래머스 2레벨까지 다 풀어서 성취감이 든다.

2레벨 한 1/4 정도는 굉장히 어려웠다.

풀이를 안 봤으면 못 풀 문제가 한 둘이 아니었다.

그래도 풀이를 보고 바로 풀지 않고 나중에 풀거나, 단서만 보고 나 혼자 푸는 연습을 해봤다.

더 성장하리라.

3레벨도 게임 개발 공부하며 하나씩 조금씩 풀어가야겠다.