본문 바로가기

백준13

[자료구조/알고리즘] - Queue/Deque 큐는 FIFO, First-In-First-Out 선입선출로 처리됩니다. 지난번에 스택을 정리할 때 테니스공, 셔틀콕을 넣는 통에 스택을 비유 했었는데, 큐의 경우에는 다른 예시 보다 책 예시가 좋은 거 같아서 적어본다. 우리가 흔히 식당에 들어가기 위해서 대기줄을 서는 경우가 있는데 그 때 제일 먼저 대기줄에 선 손님분들 부터 입장을 하게 된다. 이런 식으로 작동을 하는게 큐라고 보면 된다. 스택의 거의 모든 연산을 파이썬에서 지원해 주듯이 리스트는 큐의 모든 연산을 지원해줍니다. 주의할 점은 리스트는 동적 배열로 구현되어져 있어서 큐의 연산을 수행하기에는 효율적이지 않아, Deque라는 별도의 자료형을 사용해야 좋은 성능을 낼 수 있다. 어제오늘 큐 문제를 최대한 많이 풀려고 했는데 파이썬으로 푼 문.. 2023. 5. 13.
[자료구조/알고리즘] - 스택 자료구조를 배우게 되면 가장 많이 보게 되는 자료형이 아닐까 생각이 듭니다. 운영체제에서도 나오고 다른 CS 지식을 배우는 과정에서도 자주 나오는 자료형이라고 생각이 됩니다. 다음 글로 Queue에 대한 부분도 작성하겠지만 스택의 경우에는 Last-In-First-Out, LIFO(후입선출)에 해당 합니다. 1학년 때 자료구조를 들으면서 들었던 좋은 예시로는 테니스공이나 배드민턴 공을 넣는 통이 생각이 납니다. 위의 그림과 같이 제일 마지막에 넣은 셔틀콕을 우리가 셔틀콕을 사용하기 위해서 제일 먼저 꺼내게 됩니다. 파이썬에서는 스택 자료형을 별도로 제공하지는 않지만 리스트를 통해서 거의 대부분의 연산을 사용할 수 있습니다. 예를 들어서 pop()과 같은 기능을 제공받아서 일일히 스택에서 필요한 기능들을 .. 2023. 5. 11.
[자료구조/알고리즘] - 문자열 문자열 조작이란 문자열을 변경하거나 분리하는 등의 여러 과정을 말합니다. 언어에 따라서 문자형이 다로 없는 경우에는 비교적 조작이 까다로운 편이지만, 대부분의 언어에서는 별도의 문자열 자료형과 문자열 조작에 대한 기능을 제공해주기 때문에 언어에서 기능들을 잘 활용하면 좋습니다. 백준이나 리트코드 문제를 푼지 한참 되서 그냥 기억나는 문자열 문제들의 특징은 항상 전처리(?)를 잘해주면 문제 풀기가 편했다는 점, 그리고 파이썬으로 풀 때 정답 출력을 잘 맞춰줬어야 되는 점 정도 였던 것 같습니다. 문자열 관련 문제를 좀 찾아서 풀었는데, 문제를 풀면서 실수했던 부분이나 자주 사용하는 부분을 정리해봤습니다. 리스트 모아서 문자열로 출력해주기 str = ''.join(arr) # 숫자는 처리를 더 해줘야 함. .. 2023. 5. 10.
알고리즘 다시 공부하기 3일차 정렬 알고리즘 → 도출하는 결과는 같더라도 알고리즘에 따라 성능과 효율이 달라지기 때문에 작동원리와 장단점 파악 필요 → 알고리즘 문제 풀 때 + 코딩테스트 문제 풀 때 기본적으로 자주 사용하게 되는 요소가 아닌가 싶음 버블 정렬 삽입 정렬 병합 정렬 셸 정렬 선택 정렬 → 평소에 안썼던 정렬들이 더 많은 거 같음. ⇒ 파이썬은 느리다는 단점이 있어서 퀵 정렬을 쓰는게 좋다고 배웠는데 내용들 보면서 봤을 땐 병합 정렬이 좋을 수도 있겠단 생각이 들었음(+ 연결리스트?) *파이썬에서 변수 편하게 바꾸기 → a, b = b, a (양쪽 값을 편하게 바꿀 수 있음, 평소에 temp 써서 임시로 담아두는거 안해둬도 됨!) 1. 버블 정렬 가장 간편하지만 속도가 가장 느린 알고리즘, 가장 큰 값을 반복적으로 옮겨.. 2022. 9. 12.
[백준][파이썬] 1193번 분수찾기 브론즈 문제 치곤 상당히 많이 고민했던 문제입니다. 다들 어떤 식으로 고민해서 푸는지는 모르겠지만, (1/1)-(1/2,1/2)-(3/1,2/2,1/3)-... 이런식으로 계속해서 숫자가 이어져 나가고 있을 때 몇 번째의 값을 구하는지 문제에서 주면 답을 찾아 주어야 하는 문제입니다. 생각했던 과정은 1,2,3 계속해서 1씩 늘어나는 숫자를 생각했을 때 2,3,4 순으로 분자+분모 값의 합이 나온다. 그러면 등차수열 처럼 값을 늘려서 계산해주면 되겠네 하지만 중간에 분자+분모 값이 홀수 인지 짝수인지에 따라서 분수의 순서가 달라진다. 그러면 그거는 2로 나눠서 나머지를 확인하면 되겠네 몇 번째 인지는 어떻게 생각을 해줄껀가를 고민했을 때, 저의 경우에는 (1/1)이나 (1/2,2/1) 처럼 대각선으로 한.. 2022. 1. 15.
꾸준히 다시 공부하기 2021.12.26일자로 다시 빡세게 백준 문제를 풀기 시작했습니다. 한 20일 정도 지났는데 하루에 그래도 한문제씩은 푸는 속도로 하나씩 꾸준하게 풀어가보려고 합니다. (이제는 진짜 전역의해가 밝았기 때문에 ㅎㅎ) 일단은 크게 계획을 세워서 풀고 있어서 한번 적어보자면 1. 백준 단계별 풀어보기 1)입출력 단계~12)정렬 단계 까지 정리하면서 기본정도는 쳐야 될거 같아서 하나씩 풀어보고 있습니다. (이전에 풀어봤던 문제도 있고, 아니면 파이썬으로 혹은 다른언어로 풀어본 문제도 있어서 하나씩 차근차근 돌아본다는 느낌으로 풀어보고 있습니다.) 2. 백준 단계별 풀어보기 그다음은 백준 강의에 있는 알고리즘 기초/중급 정도 까지 문제를 풀어볼까 합니다. 확실히 머리는 쓰는 만큼 잘굴러가는 거 같아서 입대하기 .. 2022. 1. 15.
[백준] 1712번 손익분기점 with python 어떻게 접근을 했는가? 처음에는 막연히 생각했던게 그냥 봐도 손익분기점을 구하는 문제였고, 그냥 고정비용 빼주고, 나머지 가변비용을 생각해서 그걸 계산해주면 바로 풀리지 않을까 라고 생각을 했던 거 같습니다. 물론 문제를 풀면서도 그게 어느정도 맞긴 해서 거의 답에 근접 하기는 했었습니다. import sys input = sys.stdin.readline # 이걸로 일단 선언 해두기 b = input().split() un_v = int(b[0]) pl_v = int(b[1]) no_v = int(b[2]) temp = int(un_v / (no_v - pl_v)) temp2 = int(un_v % (no_v - pl_v)) if temp 0 and te.. 2021. 6. 27.
[백준] 4673번 with Python 주말에도 풀다가 문제에 대한 이해가 안되서 미뤄두었던 문제임. 일단 이해가 안된 이유는 문제의 시작을 어디서 부터 집어서 풀어야 될지가 감이 안잡혀서 더 그랬던 것 같음. 처음 문제를 보았을 때 예시를 보고 감이 안잡혀서 이것 저것 시도를 다해보다가 직접 적어보면서 다시 풀어봤더니 그냥 너무 어렵게 생각했던 것 같음. 항상 백준 문제를 풀 때 느끼는 거지만 너무 어렵게 생각해서 쉬운 문제를 못풀게 되는 경우가 많은 것 같음. 다시 쉽게 생각해서 그냥 1부터 다 더해보고 셀프 넘버가 아닌거를 1~10000까지 가지고 있는 리스트 상에서 다 빼버리면 되는 거 였음. import sys input = sys.stdin.readline # 이걸로 일단 선언 해두기 # selfnum을 구해주는 함수 구해서 리스트.. 2021. 6. 16.
[회고일기] 5월 부터 시작한 공부 - 2021년 6월 2주차 지난주에 회고일기를 적었던게 일주일 전인데 일주일이 마치 하루처럼 지나갔습니다. 이것이 공군 군사경찰 크루근무인가.. 싶습니다.(살려줘 도망쳐~) 어쨌든 틈틈히 또 공부를 조금씩 해보았고, 많이는 아니지만 백준 10문제 정도 풀었고, 문제 풀면서 모르던 파이썬 관련 내용도 찾아보는 시간을 가질 수 있었습니다. 약 3주 전쯤에 만들어 뒀던 공부일지에 꾸준히 공부한 내용이나 결과들을 올려두면서 관리가 되가고 있는 것도 보이는 것 같습니다. 일주일에 5번은 싸지방에 가서 공부를 하든 아니면 폰으로 개발과 관련된 내용을 읽는 시간을 가질려고 했는데, 이번주는 백신을 맞기도 했고(목요일날 백신 맞음-> 금요일도 쉬는날이됨) 푹 쉬워줄 수 있는 타이밍이라고 생각을 해서 목금에 좀 잠도 청하면서 쉴 수 있었던 것 같.. 2021. 6. 13.

티스토리툴바