[백준] Sil5 | 해시 | 7785 회사에 있는 사람 Pythonhttps://www.acmicpc.net/problem/7785 구상풀이 1 : 딕셔너리 쓰면 곰방곰방 풀린다딕셔너리 값 삭제는 del이나 pop을 쓴다.items()를 쓰면 key, value 쌍을 얻지만keys()를 쓰면 key만 얻을 수 있고 더 빠르다.풀이 2 : set을 써서 풀 수도 있다. dictionary써도 value에 넣을 게 딱히 없음.. key만 갖고있는 set으로도 풀어봤다.공간, 시간 복잡도는 거의 차이가 없었다. 신기하네join을 쓰면 출력이 훨 빨라져서 츄라이!sys.stdout.write도 써볼까.. 트러블 슈팅x 코드 - set# v2 : 해시 - setimport sysinput = sys.stdi..
백준
[백준] 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 : 이진탐색 시 양쪽 인덱스가 같은 경우는 문제에 따라 ..
