yeony's story

https://www.acmicpc.net/problem/15486 15486번: 퇴사 2 첫째 줄에 N (1 ≤ N ≤ 1,500,000)이 주어진다. 둘째 줄부터 N개의 줄에 Ti와 Pi가 공백으로 구분되어서 주어지며, 1일부터 N일까지 순서대로 주어진다. (1 ≤ Ti ≤ 50, 1 ≤ Pi ≤ 1,000) www.acmicpc.net (처음 든 생각) 항상 완탐부터 생각난다.... 하지만 딱 떠오르는 생각이 없었다. 아무리 생각해봐도 모르겠어서 인터넷 풀이 검색.. (풀이 : dp) 처음에 input()으로 입력값을 받았는데 시간초과, sys.stdin.readlin() 사용하니까 통과함! 이 문제는 완탐으로 하면 시간초과가 뜬다 연산개수가 150만개라서..! 생각해야 하는 부분 1. 해당 날짜에..

pc.net/problem/4779 4779번: 칸토어 집합 칸토어 집합은 0과 1사이의 실수로 이루어진 집합으로, 구간 [0, 1]에서 시작해서 각 구간을 3등분하여 가운데 구간을 반복적으로 제외하는 방식으로 만든다. 전체 집합이 유한이라고 가정하고, www.acmicpc.net (처음 든 생각) 3등분씩 진행하면, N을 3으로 나눈 값만큼 계속 쪼개지는구나... 뭔가 트리 모양처럼 쪼개지네? 반씩 나눠지는 걸 보니.. 재귀함수를 써야하나..? -의 개수가 1개 남을경우까지만 탐색을 해야하니까 재귀함수를 한 번 써봐야겠다 배열을 쓸까 아니면 문자열로 쓸까 고민하다가 그냥 배열 씀.. (문자열 하다가 무슨 이유 때문인지 모르겠지만 그만둠) (처음 풀이) 입력값을 얼마나 넣는 지 알 수 없기 때문에 try..

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 (처음 든 생각) 사실 완탐이 가장 먼저 떠올랐다. 그래서 문제를 풀어보려했으나, 뭔가 더 효율적인 방법이 있을 것 같았다. 그래서 고민해보다가 투포인터를 떠올리게 되었다. 투포인터의 개념은 떠올렸지만 아직 구현이 미숙해서 리스트 정렬을 해야하는 걸 까먹었다..ㅎ 그래서 계속 풀다가 도저히 안 풀려서 풀이를 찾아보니 정렬을 먼저 해야하는 것이..

(처음 든 생각) P가 있는 위치를 중심으로 확인하면서 넘어가려고 했다. 0~7번 자리에 P가 있으면 P 주위에 파티션이 있는지 확인 (만약 P가 아닌 O나 파티션이 있으면 일단 넘어감 어차피, P가 있으면 그 주위 탐색을 하게 될테니까?) dx, dy는 위 그림의 순서처럼 선언해놨다. P 주위에 또 다른 P가 대각선으로 있을때를 생각해봤다. P1일 경우, 4,6번 방향으로 파티션이 있으면, 조건에 위배되지 않는다. P2일 경우에는 0, 6번 방향 P3일 경우엔 0,2번 방향 P4일 경우엔 2,4번 방향 이렇게 조건까지 만들어서 돌렸는데 테스트 케이스를 통과하지 전부 통과하진 못했다 +_+; ''' 거리두기 확인하기 : Programmers Level 2. ''' def solution(places): ..

(처음 든 생각) 일단 맵을 만들자. 그리고 나서 생각을 다시 해보자, 빗물이 차오르게 하려면? 양 옆에 빗물을 가둘 수 있는 기둥이 존재해야 한다. 위 그림에서는 양 옆에 빗물을 가둘 수 있게끔 기둥이 존재하고, 왼쪽 기둥은 높이가 3, 오른쪽 기둥높이는 4이다. 이때는 왼쪽 기둥의 높이에 맞춰야한다. (즉 최솟값) 그래서 이때 든 생각은 바닥부터 탐색을 시작해서 체크를 하자..? 여기서도 마찬가지로 왼쪽 빗물부터 보면, 왼쪽 기둥 높이는 3, 오른쪽 기둥 높이는 4 이때도 3을 선택 오른쪽 빗물은 왼쪾 기둥이 4, 오른쪽 기둥 높이가 2 따라서 2를 선택 위 그림에서는 빗물이 고일 수가 없다. 기둥이 1개만 존재하기 때문이다. (내가 맨 처음에 성공했던 풀이) 맨 아래부터 탐색을 시작한다. h, w ..

[처음 든 생각] 최소를 구하라고 해서 bfs가 제일 먼저 떠올랐다. 근데 bfs 구현을 매끄럽게 잘 해내지 못하는 상태라 사전공부를 하고 왔다. 사다리와 뱀이 이 문제에서는 키포인트! 너비 우선 탐색은 현재 노드에서 갈 수 있는 모든 노드를 먼저 탐색하는 과정이기 때문에, 최단 거리 구할 때 주로 사용한다. https://eboong.tistory.com/253 [이것이 코딩테스트다 Ch5 ] DFS와 BFS 1. 스택과 큐 (1) 스택 - 후입선출 - 삽입은 append(n) , 삭제는 pop() (2) 큐 - 선입선출 - 파이썬에선 큐 구현을 위해 deque 라이브러리를 사용한다. - 삽입 append(n), 삭제 popleft() - queue 라이브러리 대신.. eboong.tistory.com..

[처음 한 생각] s를 t로 바꾸기 위해 2가지 연산만 사용할 수 있다. 그러면 역으로 생각해서 t를 s로 바꿀 수 있으면 그게 답이 아닐까 생각했다. s : A t : BABA이면, BABA에서 맨 오른쪽에 있는 A는 빼내고, B는 거꾸로 한 뒤 B를 빼내고, BA에서 A를 빼내고, B가 남는다..? 근데 예제는 분명 s에서 t로 바꿀 수 있다고 했는데.. 이게 아닌가보다.. 아니다.. 마지막 부분이 잘못된 오류가 있었다! BA에서 1번 연산이 아닌 2번 연산을 취하면 된다. 그럼 A가 남게 되니까 최종값은 1이 된다..! [풀이] T->S 과정을 거치면 답을 구할 수 있다. S->T로 만들면서 나타날 수 있는 경우의 수는 총 4가지 1번 연산 : 맨 끝에 A 추가 2번 연산 : 맨 끝에 B추가 후 문..

https://www.acmicpc.net/problem/13699 13699번: 점화식 다음의 점화식에 의해 정의된 수열 t(n)을 생각하자: t(0)=1 t(n)=t(0)*t(n-1)+t(1)*t(n-2)+...+t(n-1)*t(0) 이 정의에 따르면, t(1)=t(0)*t(0)=1 t(2)=t(0)*t(1)+t(1)*t(0)=2 t(3)=t(0)*t(2)+t(1)*t(1)+t(2)*t(0)=5 ... 주어진 입력 0 ≤ n www.acmicpc.net 매번 점화식을 재귀함수로 구하면 시간이 매우 오래걸려서 메모이제이션 방식을 사용하여 푼다. 처음엔, for문을 한 번만 돌리면 되는 줄 알았다. n=3일경우 f(3)= f(0)*f(2) + f(1)*f(1) + f(2)*f(0)이니까 3번만 돌리면 되..

https://www.acmicpc.net/problem/20207 20207번: 달력 수현이는 일년의 날짜가 1일부터 365일로 표시되어있는 달력을 가지고있다. 수현이는 너무나도 계획적인 사람이라 올 해 일정을 모두 계획해서 달력에 표시해놨다. 여름이 거의 끝나가자 장 www.acmicpc.net 구현 문제 처음엔 2차원 배열에 시작점과 끝점을 다 넣어줘야하나 고민했다. 하지만 그렇게 되면, 연속지점은 어찌저찌 구하더라도 중간에 끊어지는 부분이나, 코팅지 면적의 높이를 구할 수 없게 된다. 이 문제는 일단 365개의 숫자가 들어갈 배열을 구해야한다. 1일부터~ 365일까지니까, 크기가 366인 배열을 만들어서 0번째 배열은 버리고, 1번째 배열부터 사용할 예정이다. calendar 배열에는 row(높이..

import sys t_num = int(sys.stdin.readline()) # input보다는 sys.stdin.readline.rstrip() rstrip()은 줄바꿈 문자 제외 def plus_turn(array, n): num = n // 2 for i in range(n): array[i][i], array[i][num] = array[i][num], array[i][i] array[i][i], array[i][n - 1 - i] = array[i][n - 1 - i], array[i][i] array[i][i], array[num][i] = array[num][i], array[i][i] for i in range(num): array[num][i], array[num][n - 1 - i]..