일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
1 | 2 | 3 | 4 | |||
5 | 6 | 7 | 8 | 9 | 10 | 11 |
12 | 13 | 14 | 15 | 16 | 17 | 18 |
19 | 20 | 21 | 22 | 23 | 24 | 25 |
26 | 27 | 28 | 29 | 30 | 31 |
- CI/CD
- Air Table
- ICPC
- 이분탐색
- 우선순위 큐
- REACT
- 데이터 분석
- 백준 1753번
- BFS
- 종만북
- 시뮬레이션
- 생활코딩
- 수학
- dp
- JavaScript
- r
- 삼성SW역량테스트
- 컴퓨터 구조
- Bit
- 펜윅 트리
- Cloud Run
- 고속 푸리에 변환
- jpa
- 다익스트라
- Cloud Pub/Sub
- 삼성 SW 역량테스트
- 다이나믹 프로그래밍
- 접미사 배열
- 그리디
- LCS
- Today
- Total
목록전체 글 (153)
코딩스토리
백준 16900번 - 이름 정하기 www.acmicpc.net/problem/16900 16900번: 이름 정하기 첫째 줄에 S와 K가 주어진다. S는 알파벳 소문자로만 이루어져 있고, 길이는 500,000보다 작거나 같다. K는 1,000,000보다 작거나 같은 자연수이다. www.acmicpc.net KMP 알고리즘 문제이다. 사실 KMP라 하기도 조금 아쉽지만 어쨌든 Pi (접두사 == 접미사 인 최장길이)만 사용하면 해결 가능하다. 계속해서 더해갈 건데 이때 pi가 중요하다. 이유는 접두사==접미사 라면 그만큼의 길이를 빼고 더해줘야 한다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 3..
백준 9248번 - Suffix Array www.acmicpc.net/problem/9248 9248번: Suffix Array Suffix Array란, 문자열 S가 있을 때 그 접미사들을 정렬해 놓은 배열이다. 예를 들어, 문자열 S=banana의 접미사는 아래와 같이 총 6개가 있다. Suffix i banana 1 anana 2 nana 3 ana 4 na 5 a 6 이를 Suffix 순으로 정 www.acmicpc.net 이 문제는 접미사 배열 문제이다. 오전에 맨버 마이어스 알고리즘을 공부해서 쉽게 풀 수 있을 것 같아서 풀어보았다. 테스트 케이스도 다 정확히 나오길래 드디어 플래 문제를 풀어보는구나 했는데 시간 초과.. 도저히 어디가 문젠 지도 모르겠고.. 구글링은 귀찮고.. 뭔가 이상해서..
* 이 글은 "알고리즘 문제 해결 전략(종만북)" 中 20장 문자열에 나온 내용을 바탕으로 작성하였습니다. 개요 이전에 KMP알고리즘에 대해 알아 보았었다.그럼에도 문자열 문제는 쉽지 않다. 가장 최근 2020 카카오 코딩 테스트를 보면 문자열 문제가 시작부터 연달아 나옴을 알 수 있다. 그만큼 중요하면서도 어려운 유형이다. 이번에는 접미사를 통해 문자열 알고리즘을 좀 더 확장시켜 보려고 한다. 1. 접미사 배열 문자열을 다룰 때 빼놓을 수 없는 자료구조로 접미사 배열이 있다고 한다. '문자열의 맥가이버 칼' 이라고도 부른다는데 한번 공부해 보도록 하자. 먼저 접미사 배열은 말 그대로 한 문자열의 모든 접미사들을 사전 순으로 배열에 저장해 놓은 것을 말한다. 이때 접미사들을 그대로 저장하면 문자열의 길이..
* 이 글은 "알고리즘 문제 해결 전략(종만북)" 中 20장 문자열에 나온 내용을 바탕으로 작성하였습니다. 개요 '문자열'은 간단한 문제여도 쉽지 않은 문제들이 많다. C++의 STL을 사용하며 많은 부분에서 편리함이 생겼지만, 그럼에도 문자열 문제들은 많은 시간이 소요된다. 하지만 문자열 문제는 카카오 코딩테스트 문제 유형에도 자주 나오며 그 외 많은 문제에서 찾아볼 수 있다. 항상 나를 괴롭혀 왔던 '문자열'에 대해 자세히 공부해 보고자 한다. 1. 문자열 검색 문자열을 검색하는 알고리즘에 대해 공부해보자 주어진 긴 '짚더미(Haystack)' 문자열 H가 '바늘(Needle)' 문자열 N을 부분 문자열로 포함하는지를 확인하고, 포함한다면 N과 일치하는 부분 문자열의 시작 위치를 찾는 문제를 문자열 ..
백준 1543번 - 문서 검색 www.acmicpc.net/problem/1543 1543번: 문서 검색 세준이는 영어로만 이루어진 어떤 문서를 검색하는 함수를 만들려고 한다. 이 함수는 어떤 단어가 총 몇 번 등장하는지 세려고 한다. 그러나, 세준이의 함수는 중복되어 세는 것은 빼고 세야 한� www.acmicpc.net 최근에 KMP알고리즘에 대해 공부 한 뒤라 자신 있게 풀어보려 들어갔다. 문제 n제한과 시간 제한을 보니 KMP 쓰기에도 아깝다고 생각이 들었다. 가볍게 브루트포스로 풀고 넘어가려 했는데... 반전!! 삐빅!! 틀렸습니다. 삐빅!! 런타임 에러. 하... 역시 문제는 풀어도 풀어도 어렵다... 실버 4 문제라고 절대 방심해선 안된다는 걸 깨달았다. 처음 틀렸습니다는 내가 문제를 제대로..
백준 9663번 - N-Queen https://www.acmicpc.net/problem/9663 9663번: N-Queen N-Queen 문제는 크기가 N × N인 체스판 위에 퀸 N개를 서로 공격할 수 없게 놓는 문제이다. N이 주어졌을 때, 퀸을 놓는 방법의 수를 구하는 프로그램을 작성하시오. www.acmicpc.net 이 문제는 백 트래킹 알고리즘 문제이다. 백 트래킹에 대해서 공부하다 보니 백 트래킹의 가장 기본 문제라고 하여서 풀어보았다. 공부하고 풀었는데도 생각보다 어려웠다. 처음에는 2차원 배열로 놓고 모든 지점의 좌표에서 dfs를 돌릴 생각이었는데 생각보다 너무 지저분한 것 같아서 다른 방법을 생각해보다가 구글링을 통해서 알아낸 방법으로 풀었다. 분명 2차원 배열로도 풀 수 있겠지만 ..
백준 2447번 - 별 찍기 - 10 https://www.acmicpc.net/problem/2447 2447번: 별 찍기 - 10 재귀적인 패턴으로 별을 찍어 보자. N이 3의 거듭제곱(3, 9, 27, ...)이라고 할 때, 크기 N의 패턴은 N×N 정사각형 모양이다. 크기 3의 패턴은 가운데에 공백이 있고, 가운데를 제외한 모든 칸에 별이 � www.acmicpc.net 이 문제는 재귀 알고리즘 문제이다. 단계별로 풀어보기 문제들 중에서 안 풀었던 문제가 있길래 풀려고 보니 별 찍기.. 쉬울 거 같아서 빨리 풀어야겠다 하고 풀었는데 2시간 넘게 고민해도 답이 안 나오네?? 결국 구글링을 통해 알아낸 사실은 2차원 배열을 사용하는 것!! 이 문제의 핵심은 저거였다.. 그것도 모르고 몇 시간을 고민했..
백준 14266번 - 이모티콘 https://www.acmicpc.net/problem/14226 14226번: 이모티콘 영선이는 매우 기쁘기 때문에, 효빈이에게 스마일 이모티콘을 S개 보내려고 한다. 영선이는 이미 화면에 이모티콘 1개를 입력했다. 이제, 다음과 같은 3가지 연산만 사용해서 이모티콘을 S개 만�� www.acmicpc.net 이 문제는 BFS문제(다이나믹 프로그래밍을 사용한)이다. 최근 풀었던 BFS문제중에 가장 어려웠다. 처음에는 가볍게 queue에 pair로 현재 이모티콘 숫자와 클립보드의 개수를 받아서 풀어보려 했는데 문제의 조건 중 '클립 보드에 복사'라는 조건이 자꾸 걸렸다. 생각해보다가 2차원 배열을 사용하면 될 것 같아서 써봤는데 바로 틀렸습니다.. 디버깅해보니 너무 많은 ..