Coding Kitsune

문제링크 : https://www.acmicpc.net/problem/17299 17299번: 오등큰수 첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000,000)이 주어진다. 둘째에 수열 A의 원소 A1, A2, ..., AN (1 ≤ Ai ≤ 1,000,000)이 주어진다. www.acmicpc.net 풀이과정 : 바로 전에 풀었던 오큰수와 흡사한 문제지만, 배울것이 있는 문제였다. 등장횟수를 기준으로 삽입하는것이기 때문에, 처음에는 count_lst 라는 리스트를 만들어 그 안에 lst.count[lst[i]] 이런식으로 만들어 for문을 돌려 길이가 N인 등장횟수 리스트를 만든 뒤에, 전 문제랑 같은 형식으로 풀었다. 그랬더니 역시 시간초과,,,! 길이가 N인 리스트를 count과정을 N번 ..

class Node: #기본 노드 클래스 def __init__(self, key=None): self.key = key self.next = None def __str__(self): #객체를 호출하면 이 함수가 호출된다. return str(self.key) 한방향 연결리스트 (SinglyLinkedList) => 노드들이 한 방향으로 연결된 리스트 head node와 tail 노드가 있고, 특정 key값을 찾는데 걸리는 시간은 가장 앞인 head노드로부터, 떨어진 거리의 시간과 같다. 삽입연산(pushFront(), pushBack()) / 삭제연산(popFront(), popBack()) / 탐색연산 / 제거연산 이 있다. 그렇다면, 이 한방향 연결리스트를 구현해보자 class SinglyLink..

문제링크 : https://www.acmicpc.net/problem/17298 17298번: 오큰수 첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄에 수열 A의 원소 A1, A2, ..., AN (1 ≤ Ai ≤ 1,000,000)이 주어진다. www.acmicpc.net 풀이과정: 처음에는 해당 인덱스 뒤로 포문을 돌려서 첫번째로 나오는 큰 수를 저장하고 break 하는식으로 풀었는데 시간과촤가 나왔다. 한 인덱스에 n번 연산이니 O(n**2)가 되므로 시간초과가 뜰만하다. """ #시간초과 import sys lst_len = int(input()) lst = list(map(int, sys.stdin.readline().split())) answer = []..

문제링크 : https://www.acmicpc.net/problem/10799 10799번: 쇠막대기 여러 개의 쇠막대기를 레이저로 절단하려고 한다. 효율적인 작업을 위해서 쇠막대기를 아래에서 위로 겹쳐 놓고, 레이저를 위에서 수직으로 발사하여 쇠막대기들을 자른다. 쇠막대기와 레이저 www.acmicpc.net 풀이과정 : 남들은 다 스택을 사용한것 같은데, 본인은 좀 다르게 풀었다. 그냥 레이저의 역할은 범위 내 쇠막대기를 자르는(두배로 만들어주는) 역할이고, 범위 내 쇠막대기가 몇개인지만 추적해주면서 레이저가 나오면 범위내 쇠막대기 만큼 더해주고, 쇠막대기가 끝나면 범위 내 쇠막대기의 개수를 줄여주고, 하면 풀리는 문제였다. 스택을 쓰면 더 편한가,,? 싶어서 남들의 풀이를 봤는데, 그다지 더 간단..

A라는 [3, 9, -1, 2, 5] 배열이 있을 때 중간에 값을 insert 하려면 데이터값들이 밀리기 때문에 많은 시간이 걸리며 Worst case의 경우 n만큼의 시간이 걸려 O(n)의 시간복잡도를 가진다. 연결리스트는 순차적 자료구조로, 이런 경우 더 효율적인 연산을 가능하게 해준다. 가장 기본적인 연결리스트의 구조이며, 각 노드들은 (data값(key값), link(next노드를 가르키는 값)) 두가지 정보를 담고있다. 그리고 가장 앞의 노드는 head 노드이며, 마지막 노드가 가르키는 값은 NULL값이다. 이제 앞에서 O(n)의 시간이 걸렸던 insert 연산을 다시 해보자. B와 C 사이에 K라는 값을 대입하고자 할때, K값을 갖는 노드를 하나 만들어주고, B노드를 next를 K노드로, K노..

📌Only using HTML, CSS (No JS) . . . . . 소요시간: 약 3시간 30분 문제점 : 모바일 버전에서도 최대한 호환이 되도록 margin 값을 절대값으로 잘 안주고 상대적으로 주거나, blank를 만들어 비율 위주로 코딩을 했고, 저번 당근마켓 보다는 (당근마켓 경우 완전히 잘렸음) 호환이 되지만 여전히 모바일 버전 관련해서는 100% 호환이 잘 되지 않아 어려운 점이 많다. 또 스토리 부분에 아이디가 이를 포함하는 parent 태그와 축이 잘 안맞아 우선 임시적으로 붙혀놨는데, 이유를 알게되면 수정할 예정이다. 앞으로 html, css로 한두개 정도만 더 만들어보고, 만들어놓은 것을 기준으로 자바스크립트 및 css를 활용하여 반응형 웹페이지로 수정하는 과정들을 포스팅할 예정이다..

문제링크 : https://www.acmicpc.net/problem/1463 1463번: 1로 만들기 첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 정수 N이 주어진다. www.acmicpc.net 풀이과정: dp를 처음접해서 사실 처음에는 그냥 큰 수(3->2->1)부터 나누고 빼고 하면 되는거 아닌가? 3으로 나누어 떨어지면 나누고 안되면 2로 나눠보고 안되면 1빼고 반복하면 되겠네 라고 생각했다가 혼났다... 동적 프로그래밍을 이용하는 문제이고, 처음 풀이를 보았을때, 한번에 이해가 되지 않았다. 핵심은 이 dp는 정확한 계산방법이 없으며 약간 브루트포스와 비슷한 방식으로 모든 경우에 대해 생각을 해보고 이것들의 최대값 또는 최솟값을 구한다. dp[i] = dp[i-1] + 1 2와 3으..

FCFS (선착순 알고리즘) (비선점) => 도착시간을 기준으로 하며, 들어온 순서대로 일만하기 때문에 자원을 효율적으로 사용, 즉 스케줄링 오버헤드가 작다. 배치시스템(일괄처리)에 적합하며, interactive에는 부적합한 방식 RR (Round Robin) (선점) => 도착시간을 기준으로 하며, 자원 사용에 대한 제한시간(time quantum)이 있음. 제한시간이 지나면 자원을 반납해야하며, context switch 오버헤드가 크다. interactive 시스템에 적합하고, 제한시간이 성능을 결정하는 핵심 요소이다. SPN (Shortest process next) (비선점) ====> 변형된 것이 SRTN(선점)(잔여시간 추적) => 실행시간을 기준으로 대기 프로세스들 중 Burst time..

문제링크: https://www.acmicpc.net/problem/10866 10866번: 덱 첫째 줄에 주어지는 명령의 수 N (1 ≤ N ≤ 10,000)이 주어진다. 둘째 줄부터 N개의 줄에는 명령이 하나씩 주어진다. 주어지는 정수는 1보다 크거나 같고, 100,000보다 작거나 같다. 문제에 나와있지 www.acmicpc.net 풀이과정 : 덱이란 앞과 뒤 모두 삽입 삭제가 가능한 양방향 큐이다. 큐와 마찬가지로 핵심은 모든 연산이 시간복잡도 O(1)에서 끝나야한다.(O(n)은 시간초과..) 처음에는 데큐 없이 push_front를 짜려고 하니 고생하다가... 데큐를 쓰기로 결정..! 나머지는 풀이랄것 없이 저번에 했던 큐 구현과 거의 동일하다. #덱을 사용하고, 시간복잡도가 O(1)이어야함 i..

문제링크 : https://www.acmicpc.net/problem/1158 1158번: 요세푸스 문제 첫째 줄에 N과 K가 빈 칸을 사이에 두고 순서대로 주어진다. (1 ≤ K ≤ N ≤ 5,000) www.acmicpc.net 풀이과정: 몇일전 자료구조 수업을 다시들으면서 큐와 요세푸스 개념을 들었기 때문에, 쉽게 해결될 것이라 생각하였는데, 시간초과 때문에 생각보다 꽤나 고전했다. 처음에 풀었던 풀이다. #처음 시도(시간초과) def josephus(N, K): answer = [] current = 0 lst = [i for i in range(1, N+1)] while len(lst[current:]) != 1: if (current+1)%K == 0: answer.append(str(lst[..