🕹 알고리즘
프로그래머스 :: 개인정보 수집 유효기간 (Python)
문제 링크 https://school.programmers.co.kr/learn/courses/30/lessons/150370 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 접근 방식 문제는 2023 카카오 공채 1번 문제. 문제에서 개인정보를 수집한 날짜와 약관별 개인정보 보관 가능기간을 준다. 주어진 오늘날짜와 비교해서 파기해야 하는 개인정보 번호를 출력하는 문제. “날짜 문제는 단위를 통일해서 풀어라” - 내가 좋아하는 개발자의 명언. 그 말 그대로 년,월,일 포맷으로 되어 있는 날짜정보를 일수로 통일하면 바로 풀리는 문제다. 모든 달이 28일이므로..
프로그래머스 :: 보석 쇼핑 (Python)
문제 링크 https://school.programmers.co.kr/learn/courses/30/lessons/67258 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 접근 방식 문제에서 주어진 보석 배열을 완전 탐색해야하는 문제이다. 그런데 N 이 10만..? 일반적인 탐색 알고리즘은 O(N^2) 이기 때문에, O(N) 인 투포인터를 써야 하나 생각했다. 여기서 left, right 두 포인터를 인덱스로 두고 그 사이에 어떤 보석들이 있는지를 확인해야 하는데, 이 부분에서 효율성 점수가 깎일 수 있다. 어차피 포인터를 하나씩 증가시키기 때문에 gem..
프로그래머스 :: 두 큐 합 같게 만들기 (Python)
문제 링크 https://school.programmers.co.kr/learn/courses/30/lessons/118667 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 접근 방식 먼저 큐에서 pop 을 할 때 pop(0) 보다 deque 의 popleft() 가 시간복잡도가 작기 때문에 deque 를 사용했다. 문제를 풀 때는 두 가지를 고려했다. 정답을 찾는 방법 반복문 종료 시점 예시를 보면서 Greedy 하게 합이 더 큰 큐에서 합이 작은 큐로 원소를 옮겨나가면 된다고 생각했다. 그럼 이제 언제까지 반복문을 돌아야 할지가 중요한데, 예시에서 q..
백준 :: 1043번 거짓말 (Python)
문제 링크 https://www.acmicpc.net/problem/1043 1043번: 거짓말 지민이는 파티에 가서 이야기 하는 것을 좋아한다. 파티에 갈 때마다, 지민이는 지민이가 가장 좋아하는 이야기를 한다. 지민이는 그 이야기를 말할 때, 있는 그대로 진실로 말하거나 엄청나게 www.acmicpc.net 접근 방식 처음에는 파티 참석자들을 순회하면서 진실을 알고 있는 사람과 같이 파티에 참석했다면, 그 참석자들도 진실을 알고 있는 사람들 집합에 추가해주었다. 그치만 이 방식은 파티에 참석하는 순서에 따라 반례가 생길 수 있다 ..! 이 부분에서 계속 삽질함 예를 들어 참석자는 4명이고 1번만이 진실을 알고 있다고 하자. 각 파티의 참석자들이 (2,3), (3,4), (1,2) 라고 했을 때, 처음..
백준 :: 2493번 탑 (Python)
문제 링크 https://www.acmicpc.net/problem/2493 2493번: 탑 첫째 줄에 탑의 수를 나타내는 정수 N이 주어진다. N은 1 이상 500,000 이하이다. 둘째 줄에는 N개의 탑들의 높이가 직선상에 놓인 순서대로 하나의 빈칸을 사이에 두고 주어진다. 탑들의 높이는 1 www.acmicpc.net 접근 방식 문제를 보고 현재 탑보다 이전(왼쪽)에 있는 탑들 중 일단 거리가 가깝고, 현재 탑보다 높이가 크거나 같은 탑이 몇번 인덱스인지 확인하면 되겠다는 생각이 들었다. 예를 들어 예시 입력인 6 9 5 7 4 에서 높이가 5인 탑은 높이가 6인 탑이 있든 없든 상관이 없다. 그래서 스택으로 탑들을 쌓아나가면서 높이를 비교해나가기로 생각했다. 스택이 비면 0 출력 수신할 수 있는 ..
백준 :: 7570번 줄 세우기 (Python)
문제 링크 https://www.acmicpc.net/problem/7570 7570번: 줄 세우기 입력은 2 개의 줄로 이루어져 있다. 첫 줄에는 어린이 수를 나타내는 정수가 주어진다. 둘째 줄에는 처음에 줄서있는 어린이들의 번호가 차례대로 주어진다. 주어진 번호들 사이에는 공백이 하 www.acmicpc.net 접근 방식 정렬을 하려고 삽질을 하다가 결국 다른 분들의 풀이를 참조했던 문제 .. 제일 앞이나 제일 뒤로 보내는 어린이의 수를 구하기 위해서는 현재 어린이들 중에서 잘 서 있는 어린이의 수와, 잘못 서있는 어린이의 수를 구하면 된다. 예를 들어 예제 입력으로 나온 5 2 4 1 3 의 경우 2번과 3번은 “잘 서 있다” 라고 말할 수 있다. 그 외의 5, 4, 1번의 어린이는 제일 앞이나 뒤..
백준 :: 1254번 팰린드롬 만들기 (Python)
문제 링크 https://www.acmicpc.net/problem/1254 1254번: 팰린드롬 만들기 동호와 규완이는 212호에서 문자열에 대해 공부하고 있다. 규완이는 팰린드롬을 엄청나게 좋아한다. 팰린드롬이란 앞에서부터 읽으나 뒤에서부터 읽으나 같게 읽히는 문자열을 말한다. 동호는 www.acmicpc.net 문제 캡쳐 접근 방식 앞에서부터 읽나 뒤에서부터 읽나 똑같은 문자열를을 팰린드롬이라고 하고, 최소한의 문자를 추가해서 팰린드롬으로 만드려고 할 때 그 길이를 출력하는 문제입니다. 먼저 가장 최선의 경우와 최악의 경우를 먼저 떠올려 봤는데 최선의 경우는 이미 팰린드롬이기 때문에 하나도 붙이지 않아도 되는 경우, 최악의 경우는 주어진 문자열만큼을 뒤집어서 뒤에 덧붙여줘야 하는 경우였습니다. 예를..