[백준] Sil3 | 해시 | 17219 비밀번호 찾기 Pythonhttps://www.acmicpc.net/problem/17219 구상직전에 골드 쫌 머리싸매다 와서 싱거운 문제였다그냥 딕셔너리에 때려넣고 꺼내면 될 거 같은데..넴 됨시간 최적화한 다른 코드들 쫌 봤는데 입출력 한번에 하기나 sys.stdout.write나 다른 요상압축코드 써서 줄이고 계셨다간만에 기본 딕셔너리 복습했다날 열어주는 단 하나뿐인 비밀번호야 트러블 슈팅x 코드# v1 : 해시(딕셔너리)#그냥 딕셔너리에 때려넣고 꺼내면 될 거 같은데..넴 됨import sysinput = sys.stdin.readlineN, M = map(int, input().split())dic = {}for _ in range(N) : si..
알고리즘
[백준] Gol5 | 투 포인터,이진탐색 | 9024 두 수의 합 Pythonhttps://www.acmicpc.net/problem/9024 구상직전에 푼 3273번과 매우 유사한 문제! 풀이 1 : 이진탐색 (시간초과)TS : 테케 통과, 시간초과.. pypy는 통과!!! 논리는 맞았으나 시간이 문제.풀이 2 : 투 포인터이진탐색 문제는 투 포인터로도 풀 수 있다! [문제 해석]주어진 서로다른 수들 중 두 수의 합이 특정 수k에 가장 가까운 조합의 수숫자들은 -10^8 ~ 10^8(1억) 사이 정수. 숫자의 개수n는 1,000,000개 이하시간제한 : 1초답 : 합이 k에 가장 가까운 두 수 조합의 개수 구상2천만 연산 내에 짜야 함. n^2이면 시간초과3273번처럼 정렬 + 이진탐색 으로 짜면 될까..
[백준] Sil3 | 정렬,이진탐색 | 3273 두 수의 합 Pythonhttps://www.acmicpc.net/problem/3273 구상유형 : 정렬, 이진탐색시간초과땜에 이진탐색logn 사용완전 + 이진 -> nlogn [문제 해석]주어진 수들 중 두 수의 합이 특정 수x가 되는 경우의 개수숫자는 1~1,000,000 자연수, 숫자의 개수는 100,000 개 이하시간제한 : 1초 구상시간제한이 1초 = 2천만 건 안에 처리 -> n^2이 나오면 안됨2중 완전탐색 : n^2 시간초과완전 + 이진탐색 : nlogn, 통과!탐색 방법정렬해두고 탐색젤 작은거 + 더 큰거 로 시작작은걸 고정해두고 큰걸 옮기면서 반복, 합이 x보다 같거나 작아지면 break다음 작은 수 탐색작은 수는 배열 끝까지 탐색숫자..
[백준] Sil3 | 큐 | 1021 회전하는 큐 Pythonhttps://www.acmicpc.net/problem/1021 구상유형 : 큐 원형, 양방향 큐 -> deque!!!![문제 해석]가능한 연산 3가지 1. 첫번째 원소 추출 : 인덱스 1번 원소 사라짐 (인덱스 1부터 시작) 2. 왼쪽 회전 : 인덱스값 i+1 3. 오른쪽 회전 : 인덱스값 i-1원소는 주어진 순서대로 뽑아야 함답 : 원하는 원소를 뽑아내기 위한 최소 회전연산 횟수[구상]문제 이해가 잘 안돼서 솔루션 봤는데 원소가 뽑히면 맨 앞에서부터 1로 새로 인덱싱이 되는 거고 뽑아낼 수 있는 건 항상 맨 앞 원소인 것. 설마 진짜로 직접 원소 옮겨주는 건지 생각 안하고 인덱스 갖고 놀거나 큐는 가만있고 포..
[백준] Sil3 | 정렬? | 20291 파일정리 Pythonhttps://www.acmicpc.net/problem/20291 구상유형 : 정렬? 파이썬은 다 해주는 걸?...[문제 해석]확장자 별 개수 카운트확장자 개수 출력 시 사전순 정렬sorted(딕셔너리.items()) 일케쓰면 딕셔너리 key값으로 사전순 정렬된 배열 겟 가능~ 트러블 슈팅x 코드# v1 : 정렬? 파이썬은 다 해주는 걸?...# TIP : sorted(딕셔너리.items()) 일케쓰면 딕셔너리 key값으로 사전순 정렬된 배열 겟 가능~'''[문제 해석]- 확장자 별 개수 카운트- 확장자 개수 출력 시 사전순 정렬'''from collections import defaultdictimport sysinput = sys.st..
[백준] Sil4 | 스택? | 10828 스택 Pythonhttps://www.acmicpc.net/problem/10828 구상단순히 스택을 구현하라는 문제그냥 배열써서 구현함... 너무 간단한데 이게 맞나 더 날것으로 만들어야 하나 트러블 슈팅x 코드# v1 : 그냥 배열써서 구현함... 너무 간단한데 이게 맞나 더 날것으로 만들어야 하나# 스택을 구현해랴'''[문제 해석]시간제한 0.5s- 아래 기능들 구현 - push, pop, top, size, empty - 비어있는데 pop, top하면 -1 - empty는 비어있으면 1, 아니면 0'''import sysinput = sys.stdin.readlineN = int(input())com_arr = [list(input()...
[백준] Sil4 | 스택 | 9012 괄호 Pythonhttps://www.acmicpc.net/problem/9012 구상유형 : 스택 전에 풀었던 햄버거 만들기 문제에서 썼던 스택에 쌓아두고 지우기 방식 사용! 트러블 슈팅파이썬은 문자열 마지막꺼 지워야 할 때는 그냥 리스트로 담아서 pop하는 게 쉽다 . . .문자열로 굳이 해보려다가 슬라이싱 한바탕 헤매다 옴(마지막 두글자 삭제하는 부분이, 삭제가 아니라 그거 제외하고 다시 저장하는 식으로 구현해야 해서 잘 안됐음) 코드# v1 : 스택#전에 풀었던 햄버거 만들기 문제에서 썼던 스택에 쌓아두고 지우기 방식 사용!# TS : 문자열 마지막꺼 지워야 할 때는 그냥 리스트로 담아서 pop하는 게 쉽다 . . .import sysinput = sys...
[백준] Gol4 | 조합,스택 | 2800 괄호 제거 Pythonhttps://www.acmicpc.net/problem/2800 크아 쫌 뿌듯했던 문제~~~솔루션 안보고 성공했다!!! 구상[문제 해석]주어진 식의 괄호쌍 포함/미포함 모든 조합 출력괄호는 쌍으로만 포함/미포함 시킴출력은 사전순으로, 중복 없이 구상유형 : 조합, 스택스택으로 괄호쌍 개수 세고, 괄호 위치 저장해둠각 괄호 포함/미포함 조합들을 itertools.combinations()로 조합 생성함. nPr순열 형태로 표현한다면 괄호개수가 4개면 4P0 + 4P1 + 4P2 + 4P3 가 총 조합수가 됨(모두 포함하는 경우인 4P4는 제외)해당 조합에 해당하는 괄호만 포함시켜 출력TIP : 비선형 자료구조 유형에 sorted()를 ..
[백준] Sil2 | 이진탐색 | 18113 그르다 김가놈 Pythonhttps://www.acmicpc.net/problem/18113 구상v1 : 이진탐색 이름이 왜 이런가 했더니..ㅋㅎㅋㅎ 트러블 슈팅TS 1 : 시간초과 -> 이 풀이는 pypy 로 돌려야 풀 수 있다고 함TS 2 : 2% 에서 틀렸습니다 -> mid로 나눗셈 연산을 해야해서 mid가 0이면 안됨. left=1로 시작하고 leftTS 3 : 80%쯤에서 틀렸습니다 -> 이진탐색 if문에서 이번값==목표값 인 경우에도 최적의 정답이 아닐 수 있으므로 바로 break로 탈출하면 안됨. 범위 조절해서 이어서 탐색해줘야 함..(아마도 김밥 남은거 버리고 꼬다리 자르고 뭐 그래서 그런듯...wow 문제에 따라 사용할것) 코드# v1 : ..
[백준] Gol4 | BFS, 이진탐색? | 2412 암벽등반 Pythonhttps://www.acmicpc.net/problem/2412 구상 main idea는 bfs최소경로찾기, 거기에 이진탐색을 쓰면 시간을 더 줄일 수 있음bfs만 써서 풀어봄이게 왜 이진탐색???→ 최소거리 찾는 거 자체는 bfs 해주면 되는데, 간선 데이터가 주어지지 않아서 다음 노드 찾기에 이진탐색을 쓸 수 있음이진탐색 : 홈을 정렬하고, 이진탐색으로 현위치에서 이동 가능한 최소&최대 홈을 구한다. 그 후 정렬된 홈 목록에서 최소&최대 홈 사이의 홈들만 탐색하도록 한다!.→ 이진탐색 안써도 풀리는 문제ㅇㅇ트러블 슈팅시간초과다음 노드를 찾을 때 노드를 모두 확인하는 게 아니라 원하는 숫자 범위 안에 노드가 존재하는지 탐색하..
[백준] Sil2 | 이진탐색 | 2805 나무자르기 Pythonhttps://www.acmicpc.net/problem/2805 구상최적 값 어딘가를 찾기 → 이진탐색~~만만하게 봤다가 오래걸린 문제 ㅎ반례는 찾아봤지만 솔루션 안보고 풀었다! 만세! 트러블 슈팅TS 1 : 클래식해보여도 알고리즘을 외워서 쓰려고 하지 말고 문제에 맞게 말랑하게 생각하거라 . . .TS 2 : 이진탐색 시 양쪽 인덱스가 같은 경우는 문제에 따라 포함여부 달라짐! 문바문 코드# v1 : 이진탐색# 그냥 클래식한 이진탐색으로 구현하면 될 것 같은데？# TS 1 : 클래식해보여도 알고리즘을 외워서 쓰려고 하지 말고 문제에 맞게 말랑하게 생각하거라 . . .# TS 2 : 이진탐색 시 양쪽 인덱스가 같은 경우는 문제에 따라 ..
[백준] Sil4 | 이진탐색 | 1789 수들의 합 Pythonhttps://www.acmicpc.net/problem/1789 구상두가지 방법으로 풀이했다.손구상 풀이 (greedy)내가 손구상한 풀이로도 가능했음. 답까지 모든 경우에 조건을 확인해야해서 더 오래걸리지만..이진탐색문제라고 해서 이진탐색으로도 풀었다이진탐색으로 한번 더 풀어보자 트러블 슈팅이분탐색 시 다음 범위는 현재 중간값을 포함하지 않는 범위로 설정해줄 것!숫자 합 계산에 sum(range()) 를 썼더니 시간초과 발생. 1~n까지의 합 = n(n+1)/2 임을 활용하자! 코드 - greedy# v1 : greedy (60ms)# 그리디 / 이진탐색 둘 다로 풀리는 문제# TS : range 범위 경계값에 걸리는 경우 ..
[프로그래머스] LV2 | DP? | 가장 큰 정사각형 Pythonhttps://school.programmers.co.kr/learn/courses/30/lessons/12905 프로그래머스코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.programmers.co.kr 구상DP로 어떻게 푼다는 건지 모르겠어서 솔루션 봄인덱스를 처음부터 돌고싶어서 그 방향으로 풀어보려고 고집했는데 인덱스 위치는 내 생각보다 중요함.. DP가 이전의 계산값을 활용하는 개념이니 뒤쪽 값을 사용하는 방향으로 설정하는 게 당연했을지도.. 이것저것 해보기점화식dp테이블에 저장할 값은 정사각형 한 변의 최대 길이이다. (답은 ..
[프로그래머스] LV3 | 구현 | 광고삽입 Pythonhttps://school.programmers.co.kr/learn/courses/30/lessons/72414 프로그래머스코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.programmers.co.kr Think누적합 이라는 개념을 사용하는 문제라고 한다.말그대로 누적한 합인데, 이 개념을 사용하면 쉽게 원하는 구간의 구간합을 구할 수 있다.누적합 계산법 1. 주어진 데이터에서 숫자 변동이 생기는 부분만 +, -로 표시한 배열 만듦 2. +, - 되는 만큼 해당 부분의 현재 값 담은 배열 만듦 3. 현재값 배열로 누적값 ..
Think 역순 연결 리스트 2번째 문제. 전에 봤던 206. 역순 연결 리스트도 완벽히 이해하지 못한 상황이라 206번을 설명해주는 영상을 찾아 보고 왔다. 이해가 훨씬 잘 됐다! 반복과 재귀 두 방법 모두.. 그림이 역시 짱이다 https://www.youtube.com/watch?v=G0_I-ZF0S38 206번 풀이했던 내용을 바탕으로 이번 문제는 스스로 풀어보자 반복이 재귀방법보다 공간복잡도도 더 낮고 시간도 짧다. 반복으로 풀어보자 . . . 절반밖에 못풀었다^^! 영상을 찾아봤다! 같은 채널에서 올린 영상이 있었고 이해가 역시 잘 됨... https://www.youtube.com/watch?v=RF_M9tX4Eag 이 문제에서는 주어진 연결리스트의 맨 앞 head노드를 가리키는 root노드..
