알고리즘

이분 탐색 문제 풀이 시 겪은 문제 알고리즘 문제 중 이분탐색 문제를 풀다보면 항상 헷갈리는 부분이 있다. 이분탐색의 원리는 알겠는데 while문의 조건을 `left* 이분 탐색(Binary Search)은 결정 문제(Decision Problem)의 답이 이분적일

백준 11000번 강의실 배정 문제 링크위 문제를 보고 크게 2가지를 떠올릴 수 있었다. 바로 정렬과 우선순위 큐이다.먼저 입력값들을 배열에 저장해야한다. 이후 저장한 배열을 정렬해야한다. 그런데 여기서 중요한 점이 있다. 강의 시작 시각을 기준으로 정렬해야할지, 강의

백준 12904번 A와 B 문제 링크되게 간단한 문제라서 이게 왜 골드5지? 싶었다. 그런데 함정이 있었다. 바로 시간복잡도다.S -> T로 갈 때 두가지 경우가 있고 입력 조건에 따라서 S가 1이고 T가 1000일 경우 최대 2^1000의 시간복잡도를 가진다. 그래서

백준 3164번 패턴 문제 링크문제를 보고 바로 든 생각은 좌표 대신 사각형으로 생각해서 풀어야겠다는 것이었다. 실제로 회색 상자의 개수를 구하는 것이므로 그렇게 푸는게 편할 것 같기도 했고, 더 직관적일 것이라 생각했다.입력 받은 좌표들을 사각형 중 가장 왼쪽 아래에

백준 21608번 상어 초등학교 링크오늘은 문제가 길어서 입출력만 올렸다.문제를 보면 입력값의 범위가 최대 20이므로 굉장히 작은 것을 알 수 있다. 따라서 매번 완전탐색을 해도 제한시간을 넘지 않는다는 것을 생각했다.먼저 문제를 보자마자 든 생각은 방향이 있는 그래프

백준 1213번 팰린드롬 만들기 링크백준을 풀다보면 팰린드롬 문제를 많이 만난다. 팰린드롬이란 뒤집어도 같은 문자열을 말한다. 따라서 홀수개인 알파벳이 0개이거나 1개만 있어야한다. 이것만 알고 있다면 이번 문제는 어렵지 않아 쉽게 풀 수 있다.전반적인 흐름은 입력받은

백준 2225번 합분해 링크이 문제는 잘 보면 패턴을 파악할 수 있다. b개의 숫자를 더해서 a를 만드는 방식은 b-1개의 숫자로 c를 만들어 놓고 c와 마지막 숫자 d를 더하면 된다.즉 마지막 숫자를 0 ~ a 중에서 하나로 잡고 b-1개의 숫자로 b-a를 만드는 방

백준 19951번 태상이의 훈련소 생활 링크처음엔 문제를 쉽게 생각해서 1차원 배열에 연병장 높이들을 넣은 뒤 각 작업마다 연산을 해주려고 했다. 그런데 문제 조건을 보면 N과 M이 최대 100,000이기 때문에 1초를 초과한다.M은 작업의 수라서 무조건 반복해야하기

백준 11265번 끝나지 않는 파티 링크처음에는 BFS로 접근했었다. 그래프 문제인건 확실했고, 최단거리를 통해서 갈 수 있는지 여부를 확인해야했기 때문이다.아래가 내가 처음에 작성한 코드이다.그런데 시간초과가 났다. 위 코드를 보면 calculate()에서 아래 코드

문제 백준 17352번 여러분의 다리가 되어 드리겠습니다! 링크 풀이 방법 1. 2. 3. 정답 코드

백준 1106번 호텔 링크보자마자 DP 문제라는 것을 알았다. 그리고 DP중에서도 냅색 문제라고 생각했다. 그런데 일반적인 냅색 문제와는 달랐다.일반적인 냅색 문제는 0-1 냅색문제로 짐이 1번 들어가거나 0번들어가거나 둘 중 하나의 경우인 상황이다.그러나 이 문제를

백준 28107번 회전초밥 링크간단한 문제라고 생각한다. 특별한 알고리즘 기법이 들어가기보다는 문제 조건대로 큐를 사용해서 구현하면 된다.또한 초밥 리스트 배열과 손님별 먹은 초밥 수 배열을 사용해야겠다는 아이디어만 있으면 충분히 풀 수 있다.먼저 그래프를 구현하는 것

백준 1987번 알파벳 링크간단한 DFS 문제다. visited\[] 배열을 각 문자열에 대해서 만들고 이미 방문한 문자를 방문하지 않게 하는 방식으로 풀어나가면 된다.문제에서 대문자들로 배열이 주어지므로 아스키 코드로 65번부터 90번까지의 문자이다. 따라서 visi

백준 16472번 고냥이 링크먼저 문제를 잘 읽어야한다. 사실 나는 처음에 문제를 잘못 읽어서 틀렸기 때문이다.입력으로 받은 문자열 종류 최대 개수 안에서 최대 문자열 길이를 출력해야한다.먼저 알파벳 최근 출현 배열을 만들어야한다. 그 이유는 새로 검사한 알파벳을 추가

백준 1953번 팀배분 링크처음에 문제를 보고 유니온 파인드가 떠올랐다. 그런데 잘보니 유니온이 아니라 다른 팀이 되야하는 연산을 해야하므로 유니온 파인드로 풀기는 어려웠다.이후 아래 코드를 구현했다.그런데 이 코드는 통과할 수 없다. 반례를 구하기 어려워 내가 직접