본문 바로가기

전체 글43

[백준] 회문 (골드5, 시간복잡도는 왜 선형을 유지할 수 있을까.. N^2이 아니고?) https://www.acmicpc.net/problem/17609 17609번: 회문 각 문자열이 회문인지, 유사 회문인지, 둘 모두 해당되지 않는지를 판단하여 회문이면 0, 유사 회문이면 1, 둘 모두 아니면 2를 순서대로 한 줄에 하나씩 출력한다. www.acmicpc.net 설명 회문(palindrome)은 앞 뒤 문자가 같아, 앞으로 읽어도 뒤로 읽어도 같은 문자가 되는 문자열을 의미한다. 우선 회문의 개념은 알았으니 문제를 좀 살펴보면, O(N^2) 풀이로는 도저히 풀 수 없을 것 같다는 걸 문자열의 범위만을 봐도 알 수 있다. 문자열의 길이는 최대 10만 까지 주어지므로, T개의 케이스를 모두 연산해야 하기 때문에 O(T * N^2) 만큼의 시간이 소요되게 알고리즘을 작성하면 시간초과가 난다.. 2024. 2. 8.
[백준] 두 수의 합 [왜 여기까지만 생각했을까.. JAVA] 투 포인터 https://www.acmicpc.net/problem/3273 3273번: 두 수의 합 n개의 서로 다른 양의 정수 a1, a2, ..., an으로 이루어진 수열이 있다. ai의 값은 1보다 크거나 같고, 1000000보다 작거나 같은 자연수이다. 자연수 x가 주어졌을 때, ai + aj = x (1 ≤ i < j ≤ n)을 만족하는 www.acmicpc.net 설명 실패했던 문제 중 가장 의미 있게 풀어낸 문제라고 생각해서 기록을 남겨보려고 한다. 이번 문제는 투 포인터에 관련된 문제다. 최근 들어 시간 복잡도를 계산하는 연습을 틀리더라도 최대한 정확하게 해 보려고 노력하고 있다. 그래서 시간 복잡도가 어떻게 되는지와 어떤 방식으로 생각을 해볼 수 있는지 작성해보려고 한다. 투 포인터를 .. 2024. 2. 3.
[프로그래머스] 뒤에 있는 큰 수 찾기 - [투 포인터 말만?] 구현, 투 포인터, 이중 포문 https://school.programmers.co.kr/learn/courses/30/lessons/154539 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 설명 코드부터 먼저 올리고 설명을 하는데, 이번에는 순서를 좀 바꿔서 설명해야 할 필요성이 있는 문제라서 설명과 코드 순서를 바꿨다. 또 지고의 영역인 분들에게 배운 기본이론을 바탕으로 증명과 동시에 설명해보려고 한다. 우선 이 문제를 먼저 읽고 와서 내용을 보아야 이해가 간다. 만약 저 문제를 읽고 왔다면 혹시라도 본인이 풀지 못했거나, 이게 왜 틀린 풀이일까를 .. 2024. 1. 23.
2023년 회고 - 실패할 것 같았던 대학생은 없다. 2023 생각보다 다사다난했던 2023년, 각오와 열정을 안고 복학을 결정했다. 1년 휴학을 하고 생활비와 자취방 비용을 마련했다. 군휴학 1년과 일반휴학 1년 총 2년 휴학을 통해 내가 과연 대학을 다시 가는 게 맞을까. 내가 대학을 간다고 해서 지금 내 현실이 달라지는 것은 무엇일까 참 고민을 많이 했다. 생각 끝에 도달한 내가 내린 결론은 대학을 다시 가보자였다. 이런 결정을 내린 이유에는 '학사 취득' 이라는 명분을 얻기 위함도 있었지만, 가장 중요한 이유로는 '나는 아직 준비되지 않은 사람'이란 생각이 계속 나를 자극했기 때문이었다. 남들보다 뛰어나지도 않다. 남들보다 똑똑하지도 않다. 그렇다고 고등학교 때 피나게 공부를 해본 것도 아니다. 그저 '어중간했다'. 그럼 나는 진짜 이대로 사회에 나.. 2023. 12. 31.

티스토리툴바