본문 바로가기

전체 글146

1258번 - 행렬찾기 1. 문제 1-1. 링크 1-2. 문제 해석 2. 코드 3. 실행시간 1. 문제 1-1. 링크 SW Expert Academy SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요! swexpertacademy.com 1-2. 문제 해석 문제는 간단하다(?) 주어지는 입력에서 사각형을 찾고 사각형의 가로 세로를 순서대로 출력하면 된다. 위 예제에서는 노란색 사각형(3x4), 파란색 사각형(2x3), 초록색 사각형(4x5)이 있다. 입력과 출력에 붙는 조건은 어렵지 않으니 문제에서 확인하면 되고 나는 저 사각형의 가로 세로 길이를 구하는 로직에 대해서 다뤄보려고 한다. 1. 문제를 다 풀고 다른 사람들의 답을 찾아보니 흔히들 푸는 방법은 아닌 것 같아요. 대표적인 풀이를 보고 싶어서 오.. 2021. 9. 4.
1257번 - K번째 문자열 1. 문제 1-1. 링크 1-2. 문제 해석 2. 코드 3. 실행시간 1. 문제 1-1. 링크 SW Expert Academy SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요! swexpertacademy.com 1-2. 문제 해석 부분 문자열을 사전 순으로 나열해 K번째에 위치하는 부분 문자열을 출력하는 문제다. 부끄럽게도 나는 문제를 잘못 해석해 삽질을 좀 했다. 우선 문제에서 말하는 부분 문자열에 대해 알아보자. 문제에서는 문자열의 두 위치를 골라서, 이 사이의 연속한 문자열을 부분 문자열이라고 정의하고 있다. 예를 들어 le는 연속된 문자열이 아니므로 부분 문자열이 아닌 것이다. 나는 모든 조합이 부분 문자열이 되는 줄 알고 조금 헤맸다. 근데 그것도 그거대로 말이 안 되.. 2021. 9. 3.
접미사 배열(Suffix array) 개념과 예제 1. 접미사 배열 1-1. 개념 1-2. 예제 2. LCP 2-1. 개념 2-2. 예제 3. 그래서 이걸 어디다 써먹을 수 있는데? 1. 접미사 배열 1-1. 개념 접미사 어떤 낱말 뒤에 붙어 다른 낱말을 이루는 말을 뜻한다. ex) 임금님, 사장님, 의느님 -> '-님'이 접미사 접미사 배열(Suffix Array) 어떤 문자열의 모든 접미사를 사전 순으로 나열한 배열 LCP와 주로 같이 쓰인다. 2-2. 예제 mommy라는 문자열로 예시를 들어보자 우선 접미사의 종류를 만든다. -y -my -mmy 이런 식으로! 접미사가 들어있는 배열을 사전순으로 나열한 것을 '접미사 배열'이라고 부른다. 우측 표는 접미사 배열이 완성된 모습이다. 접미사는 보기 편하게 우측 정렬로 접미사 배열은 비교가 쉽게 좌측 정.. 2021. 9. 2.
1221번 - GNS 1. 문제 1-1. 링크 1-2. 문제 해석 2. 코드 3. 실행시간 1. 문제 1-1. 링크 SW Expert Academy SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요! swexpertacademy.com 1-2. 문제 해석 숫자를 의미하는 문자열이 주어지고 그걸 정렬해서 출력하는 문제다. 완전 탐색을 돌아도 되고 숫자로 변환했다가 정렬해서 출력해도 되겠지만 굳이 그렇게 하지 않아도 가장 쉽게 풀 수 있는 방법이 있다. 데이터 값의 범위가 0~9이다. 우리는 이 점을 주목해야 한다. 나는 정렬 문제가 나왔을 때 가장 먼저 보는 것이 데이터의 범위이다. 값의 범위가 적을 때 카운팅 정렬을 사용할 수 있기 때문이다. 카운팅 정렬이란? 3 4 2 2 1 1 5 1 예를 들어 위.. 2021. 9. 2.
1248번 - 공통조상 1. 문제 1-1. 링크 1-2. 문제 해석 2. 코드 3. 실행시간 1. 문제 1-1. 링크 SW Expert Academy SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요! swexpertacademy.com 1-2. 문제 해석 공통조상과 서브 트리의 크기를 구하는 문제이다. 문제를 이해하는 건 크게 어렵지 않았고 서브 트리 크기 구할 때 자기 자신도 포함시키는 거? 외에 딱히 주의해야 할 점은 없었다. 공통 조상을 찾는 법 나는 주어진 두 정점을 번갈아 가며 부모 노드로 계속 쭉쭉 올라가도록 했다. 그러면서 지나온 부모노드를 ArrayList에 저장해두었다. 그러다가 둘 중 한 놈이 ArrayList에 저장된 부모 노드를 만나는 순간 공통 조상을 찾은 것으로 처리했다. 위 .. 2021. 9. 1.

티스토리툴바