난이도: Lv.3유형: 다익스트라해결 여부: 틀림내가 생각했던 아이디어/큰 가닥길의 가짓수를 줄이기 위해 길을 매워나가야 하나 생각했다.경로 가짓수 길어지는 것도 어케처리할지 잘 몰랐다. 오답 이유해답어떤 방향에서 진입했는지 기록을 어케하지 싶었는데 걍 차원 하나 더 만들어서 해주면 된다.다익스트라기 떄문에 항상 최소값 갱신하는 형태로 해서 하면 문제되지 않는다. 방향에 따라 달라지는걸 기록하기 위해서 아예 3차원으로 기록을 했다. 다익스트라 특) 한 지점 잡고 비용기준 우선순위 큐로 쌓는데 가망없으면 바로 버리기 #기억할 문법 #내 오답코드def solution(board): length=len(board) def check(y,x): total=0 cover=0 ..
Algorithm/Greedy
난이도: Lv.3유형: 그리디해결 여부: 힌트 봄내가 생각했던 아이디어/큰 가닥이걸 어케풀지? 잘 모르겠어서 딕셔너리나 배열로 다 기록해야 되나 싶었는데, 그건 아닌거 같아서 힌트 봤다.오답 이유그러고 나서 정렬하기 이전에 최초값 코드 순서때문에 한번 틀렸다해답후열 정렬 그러니까 선출시간 기준으로 정렬하고 기록하는 방식이었다.회의실 문제도 비슷한 방식이였는데 이렇게 시작시간-끝나는시간 있는 문제에서는 끝나는 시간으로 정렬하고 봐야한다.진출 지점이 곧 그 기회를 잃게 되는 한계점"이기 때문입니다. 모든 구간 문제에서 **"가장 먼저 끝나는 것(Earliest Finish Time)"을 기준으로 정렬하는 이유가 바로 이 '한계점'을 관리하기 위함입니다.#기억할 문법 #내 정답코드def solution(rou..
난이도: Lv.3유형: 그리디해결 여부: 오답내가 생각했던 아이디어/큰 가닥-#다익스트란가? 근데 최단거리가 문제가 아니라 최소 비용으로 모두 연결시키는게 문제 잘몰루겠다. 일단은 비싼다리순으로 하나씩 빼보고, 다리가 유지되는지 하는식으로 확인해보자말이 안될듯, 차라리 모든 다리 있는지 없는지에 따라 2^n 배열 만들고, 그 때의 가중치 다 더한다음에 최소비용부터 시작해 답나오면 바로 return근데 큰거 빼면서 하든, 2^n으로 모든 경우 다하든 차피 오답일것 같긴했음 오답 이유크루스칼 or 프림 알고리즘을 써야 했다. 그냥 이걸 몰라서 틀림 해답전형적인 MST 문제. 즉 최소 신장트리 문제다. 최소의 비용으로 사이클이 없이 모두 연결하는 트리 만들기. 이걸 구하는 대표적인 알고리즘 2개가 크루스칼, ..
난이도: Lv.3유형: 그리디해결 여부: 정답내가 생각했던 아이디어/큰 가닥그 뭉텅이로 간격의 길이들만 기록하는 배열이 필요하다는 건 캐치했다.그 배열을 만들기 위해 보조로 범위를 표시하는 리스트나 visited 배열을 만들어야 하나 생각했다.근데 복잡한 visited나 배열 연산 없이 그냥 바로 연산해서 나올 수 있다는 걸 깨닫고 그렇게 했다.오답 이유정답임해답다듬는 다면 이런것들을 다듬을 수 있다고 한다.지금처럼 temp 에 추가 한후 다시 temp를 순회하며 처리하는게 아니라 바로 처리해버리기if- else로 나머지에 따른 올림 처리 하지말고 (a + b - 1) // b 하는 식으로 천장을 구현하기#기억할 문법 #내 정답코드def solution(n, stations, w): answer =..
난이도: Lv. 3유형: 그리디해결 여부: 오답아이디어그리디가 가능한가? 를 남은 이동횟수랑 칸으로 일일이 확인한다. d->l->r->u 순으로오답 이유 혹은 알게 된것그리디가 아니라 그냥 쌩 시뮬레이션 문제라고 생각해 잘못풀었따.d -> u -> d 이런구조가 있을줄 알았다. 실상은 그렇지 않았다. 애초에 사전순 특성상 그럴리가 없음. 그 밖에도 //2 가 아니라 /2를 써서 소수처리되서 반복 실패. dx,dy 바꿔씀. 이는 좌표 자체에서 1,1이 어디인지 안보았기 때문. 그리고 사전순에 대한 이해 부족과 오타도 있었다. abs()를 안쓴다던가..def solution(n, m, x, y, r, c, k): # 1. 출발지에서 목적지까지의 최단 거리 계산 dist = abs(x - r) + ..
https://www.acmicpc.net/problem/2615 C++로 작성한 백준 문제 2615번 오목에 대한 문제 풀이다. 그리디 알고리즘 문제로 brute force가 문제를 푸는데 필요한 주요 지식이다. 문제 설명 문제 오목은 바둑판에 검은 바둑알과 흰 바둑알을 교대로 놓아서 겨루는 게임이다. 바둑판에는 19개의 가로줄과 19개의 세로줄이 그려져 있는데 가로줄은 위에서부터 아래로 1번, 2번, ... ,19번의 번호가 붙고 세로줄은 왼쪽에서부터 오른쪽으로 1번, 2번, ... 19번의 번호가 붙는다. 위의 그림에서와 같이 같은 색의 바둑알이 연속적으로 다섯 알을 놓이면 그 색이 이기게 된다. 여기서 연속적이란 가로, 세로 또는 대각선 방향 모두를 뜻한다. 즉, 위의 그림은 검은색이 이긴 경우이..
https://www.acmicpc.net/problem/1931 1931번: 회의실 배정 (1,4), (5,7), (8,11), (12,14) 를 이용할 수 있다. www.acmicpc.net C++로 작성한 백준 문제 1931번 회의실 배정에 대한 문제 풀이다. 실버 1 문제고, 그리디 알고리즘과 정렬이 문제를 푸는데 필요한 주요 지식이다. 문제 설명 문제 한 개의 회의실이 있는데 이를 사용하고자 하는 N개의 회의에 대하여 회의실 사용표를 만들려고 한다. 각 회의 I에 대해 시작시간과 끝나는 시간이 주어져 있고, 각 회의가 겹치지 않게 하면서 회의실을 사용할 수 있는 회의의 최대 개수를 찾아보자. 단, 회의는 한번 시작하면 중간에 중단될 수 없으며 한 회의가 끝나는 것과 동시에 다음 회의가 시작될 수..
https://www.acmicpc.net/problem/1541 1541번: 잃어버린 괄호 첫째 줄에 식이 주어진다. 식은 ‘0’~‘9’, ‘+’, 그리고 ‘-’만으로 이루어져 있고, 가장 처음과 마지막 문자는 숫자이다. 그리고 연속해서 두 개 이상의 연산자가 나타나지 않고, 5자리보다 www.acmicpc.net C++로 작성한 백준 문제 1541번 잃어버린 괄호에 대한 문제 풀이다. 실버 2 문제로 수학, 그리디 알고리즘, 문자열, 파싱이 문제를 푸는데 필요한 주요 지식이다. 문제 설명 문제 세준이는 양수와 +, -, 그러고 괄호를 가지고 식을 만들었다. 그러고 나서 세준이는 괄호를 모두 지웠다. 그리고 나서 세준이는 괄호를 적절히 쳐서 이 식의 값을 최소로 만들려고 한다. 괄호를 적절히 쳐서 이 ..
