내 잡다한 노트

요새 전공수업에서 c++을 해야해서 c++ 연습할 겸 백준 문제를 풀면서 공부하는 중입니다. 이 문제는 단순한 이분탐색 문제입니다. 그런데 아무리해도 시간초과가 계속 나는거에요 ㅠㅠ 방법을 찾으러 30분동안 웹 서핑을 하던 도중... 답을 찾았습니다. #include #include #include using namespace std; bool binary_search(vector& n, int temp) { int low = 0; int high = int(n.size()) - 1; int mid; while (low > 1; if (temp == n[mid]) { return true; } if (temp > n[mid]) { low = mid + 1; } else{ high = mid - 1; } ..

문제) https://school.programmers.co.kr/learn/courses/30/lessons/154540 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 소스코드 ) def solution(maps): answer = [] dx = [0, 0, 1, -1] dy = [1, -1, 0, 0] visited = [] for _ in range(len(maps)): # visited 셋팅 temp = [] for _ in range(len(maps[0])): temp.append(False) visited.append(temp) for i in..

문제) https://www.acmicpc.net/problem/13549 13549번: 숨바꼭질 3 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 www.acmicpc.net 감각을 찾기위해 오랜만에 알고리즘을 풀었지만 접근도 잘못했다. 숨바꼭질같은 문제를 dfs로 푼 기억이 있어 dfs로 풀려했지만 풀리지 않아 다른 분들의 풀이를 보니 이 문제에서 가중치가 다르다는 걸 인지를 못하고 있었다. 나의 잘못된 풀이) import math import sys ans = math.inf visited = [] n, k = map(int..

피드백) 계속 시간초과가 났다 분명 맞게 한 것 같은데... 왜 자꾸 시간초과가 나는지... 입력이 백만이라 그런걸까 계속 생각해봤지만 답이 나오지 않아 질문하기란을 살펴보던 도중 나랑 같은 케이스인 분이 계셨다 답글을 읽어보니 visited의 위치가 문제였다. 꺼내면서 visited를 갱신하면 큐에 중복되는 층 들이 계속 쌓여서 큐의 길이가 무지막지하게 커지는 것이다. 그래서 시간초과가 나온 것이다... 앞으론 꺼낼때 visited를 갱신하지 말고 큐에 넣으면서 동시에 visited를 갱신하는 식으로 해야겠다. 오랜만에 해서 감이 떨어졌나보다 ㅋㅋ; 소스코드) from collections import deque totalFloor, ghcurrent, startlinkf, up, down = map(..

시간제한은 1초인데 입력받는 호수의 크기는 1500 * 1500로 크기가 크다. 그래서 단순히 bfs로 탐색하면 시간제한에 걸린다. 그래서 물과 얼음이 만나 얼음이 녹을 때 얼음의 자리를 임시물 큐에 넣어놓아 다음날 다시 탐색을 할 때 전체 물을 탐색할 필요없이 임시물 큐에 있던 자리만 탐색을 해서 중복을 없앤다. 이 같은 방식으로 백조도 다른 백조를 만날 수 있는지 확인한다.

구현, 시뮬레이션 문제이다. board에는 deque를 기본값으로 둬서 상어가 해당 자리에 들어갈 수 있게 했다. 상어가 움직이는 것은 사이클을 구하려 했는데 못구해서 맨 끝으로 갈 수 있는지를 확인하고 갈 수 있다면 방향을 바꿔주고 맨끝으로 한번에 이동하는 과정을 반복하도록 했다. 처음엔 2번 틀렸었는데 그 이유가 상어가 다른 상어를 잡아먹을때 shark 리스트에서 제거도 했어야했는데 remove를 안해서 좀비 상어가 발생했었다...ㅎ # 소스코드 from collections import deque r, c, numShark = map(int, input().split()) shark = [] fishing_board = [[deque() for _ in range(c)] for _ in range(..

# 문제 https://www.acmicpc.net/problem/1717 1717번: 집합의 표현 첫째 줄에 n(1 ≤ n ≤ 1,000,000), m(1 ≤ m ≤ 100,000)이 주어진다. m은 입력으로 주어지는 연산의 개수이다. 다음 m개의 줄에는 각각의 연산이 주어진다. 합집합은 0 a b의 형태로 입력이 주어진다. 이는 www.acmicpc.net 유니온-파인드 알고리즘을 사용하는 기본 문제이다. 기본 문제라 굉장히 쉽다. 노드 수가 최대 100만개라 좀 걱정이 됐는데 유니온 파인드 알고리즘의 시간복잡도는 높이와 관련이 있어서 그런지 해결이 됐다. 유니온은 합치는 것. 즉 노드들을 연결시키는 것 파인드는 루트 노드를 찾아 루트 노드가 같은지 확인을 해 두 노드가 같은 노드 집합에 속해있는지 ..

문제) https://www.acmicpc.net/problem/7579 7579번: 앱 입력은 3줄로 이루어져 있다. 첫 줄에는 정수 N과 M이 공백문자로 구분되어 주어지며, 둘째 줄과 셋째 줄에는 각각 N개의 정수가 공백문자로 구분되어 주어진다. 둘째 줄의 N개의 정수는 현재 활 www.acmicpc.net 배낭문제는 담을 수 있는 물건이 나눌 수 있냐 없냐에 따라 나눈다고 한다. 담을 수 있는 물건이 나누어질 때 (설탕 몇 g 등) : 분할가능 배낭문제 담을 수 있는 물건이 나누어 질 수 없을 때 : 0-1 배낭문제 해당문제는 0-1 배낭문제의 경우이다. 처음엔 dp를 만들 때 인덱스에 byte를 넣고 for문으로 돌릴려고 했는데 byte가 천만이라 시간초과가 날 것 같아서 어찌해야 하나 고민.....