분류 전체보기
백준 :: 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번의 어린이는 제일 앞이나 뒤..
JWT가 뭔데요?
스터디에서 쿠키와 세션방식에 대해서 함께 토론하던 중 토큰 방식에 대한 얘기가 나왔다. 토큰에 대해 얘기하다보면 빠지지 않고 나오는 주제인 JWT 에 대해 공부해보았다. 맨날 안다고 하면서 잘 모르는 나 Session vs Token. (with JWT) 먼저 웹 서버에서 Session 기반으로 인증하는 시나리오 를 생각해보자. 유저 로그인 로그인 성공 시 Session 을 서버 단(메모리, DB 등)에 저장 Session ID 를 클라이언트로 전송, 클라이언트는 Session ID 를 Cookie 로 저장 브라우저는 매 요청마다 request 에 Session ID 를 쿠키에 담아 전송 서버는 Session ID 가 일치하는지 확인 Session 기반 인증의 장점 은 아래와 같다. 서버 쪽에서 사용자 ..
백준 :: 1254번 팰린드롬 만들기 (Python)
문제 링크 https://www.acmicpc.net/problem/1254 1254번: 팰린드롬 만들기 동호와 규완이는 212호에서 문자열에 대해 공부하고 있다. 규완이는 팰린드롬을 엄청나게 좋아한다. 팰린드롬이란 앞에서부터 읽으나 뒤에서부터 읽으나 같게 읽히는 문자열을 말한다. 동호는 www.acmicpc.net 문제 캡쳐 접근 방식 앞에서부터 읽나 뒤에서부터 읽나 똑같은 문자열를을 팰린드롬이라고 하고, 최소한의 문자를 추가해서 팰린드롬으로 만드려고 할 때 그 길이를 출력하는 문제입니다. 먼저 가장 최선의 경우와 최악의 경우를 먼저 떠올려 봤는데 최선의 경우는 이미 팰린드롬이기 때문에 하나도 붙이지 않아도 되는 경우, 최악의 경우는 주어진 문자열만큼을 뒤집어서 뒤에 덧붙여줘야 하는 경우였습니다. 예를..
백준 :: 1202번 보석 도둑 (Python)
문제 링크 https://www.acmicpc.net/problem/1202 1202번: 보석 도둑 첫째 줄에 N과 K가 주어진다. (1 ≤ N, K ≤ 300,000) 다음 N개 줄에는 각 보석의 정보 Mi와 Vi가 주어진다. (0 ≤ Mi, Vi ≤ 1,000,000) 다음 K개 줄에는 가방에 담을 수 있는 최대 무게 Ci가 주어진다. (1 ≤ Ci www.acmicpc.net 접근 방식 먼저 각 가방에 담을 수 있는 보석의 최대 가격을 구하는 문제라서 보석을 가격 순으로 내림차순 정렬하고 가방마다 보석을 순회하면서 최대한 높은 가격의 보석을 담으려고 했다. 하지만 그렇게 생각하고 제약사항을 봤는데 보석과 가방의 개수가 각각 최대 30만.. 내가 생각한 풀이의 시간복잡도를 계산해보면 30만의 제곱이라..
백준 :: 1541번 잃어버린 괄호 (Python)
문제 링크 https://www.acmicpc.net/problem/1541 1541번: 잃어버린 괄호 첫째 줄에 식이 주어진다. 식은 ‘0’~‘9’, ‘+’, 그리고 ‘-’만으로 이루어져 있고, 가장 처음과 마지막 문자는 숫자이다. 그리고 연속해서 두 개 이상의 연산자가 나타나지 않고, 5자리보다 www.acmicpc.net 접근 방식 +, - 연산만 가능한 상태에서 식의 결과를 최소값으로 만드려면 최대한 큰 값을 빼주면 된다. 즉, - 뒤에 나오는 + 연산을 먼저 해주면 된다. 첫번째 예제로 살펴보면 55-50+40 의 값을 최소로 만드려면 55-(50+40) 으로 괄호를 쳐주면 된다. 그렇다면 - 를 기준으로 식을 자르고, 자른 식들을 먼저 계산한 후 전부 빼주는 식으로 구현해보자 ! 풀이 코드 i..