https://www.acmicpc.net/problem/17136처음에 색종이도 5가지에 5개씩 밖에 안 되고, 네모칸도 10 X 10이라서 해봐야 100 X 25 정도되겠다 싶어서 그리디로 풀려고 했다. 그래서 첫 칸부터 큰 사이즈부터 비교하면서 되면 넣
https://www.acmicpc.net/problem/4195처음에는 인접리스트나 뭐 그런거 만들어서 DFS나 BFS같은 걸로 돌려야 하나 싶었다. 그런데 마음속에서 생긴 DFS코드를 만들어야하는 거부감이 생겨서 고민하다가 DFS로도 안 될 것 같아서, 시
https://www.acmicpc.net/problem/7662처음에는 heapq 하나 만들어서 최대값 출력이면 리스트 전체에 -를 곱해서 뽑고 다시 -곱해서 원래대로 돌려주고 이렇게 할까 생각했는데 리스트 최대 개수가 거의 백만이라서 시간초과가 날 것 같아
https://www.acmicpc.net/problem/20040강의에서 문제 설명으로 Union-Find를 사용하면 된다고 해서 예전에 만들었던 Union-find 코드를 확인했는데 이걸로 어떻게 사이클을 탐지할지 고민을 했지만 떠오르지 않았다.조금 달라지
https://www.acmicpc.net/problem/181113중 for문 돌리는 것으로 최소 높이에서 최대 높이까지 일일이 다니며 시간을 구하고 최소 시간과 높이를 구하는 방식을 가장 먼저 생각했다. 그렇게 해도 높이 최대 257, 가로, 세로 각 50
https://www.acmicpc.net/problem/1202틀린 문제 다시 풀다가 다시 못 푼 문제이다. 처음에는 문제 잘못 읽어서 가방이 하나인 줄 알았는데 가방이 여러 개였다. 여기서부터 꼬이기 시작했다.이전 코드를 참고해서 풀었다. 가장 작은 가방부
https://www.acmicpc.net/problem/1520틀렸던 문제를 다시 도전했지만 또 틀린 문제다.처음에는 DP인줄 생각 안 하고 BFS로 모든 경로를 다 찾아보려고 했다. 도착지에 갈 때마다 숫자를 세서 답을 구했다. 그리고 시간 초과가 났다.B
https://www.acmicpc.net/problem/20963열 짜리 배열이 있는데 아래 행으로 가면서 합치는데 +-1의 열에 있는 숫자와 합칠 수 있다. 이렇게 합쳐서 최대, 최소값을 구하라는 문제이다. DP라는 것을 알고나서 원래 하던대로 DP 배열을
https://www.acmicpc.net/status?user_id=rkdgur5381&problem_id=1644&from_mine=1숫자 n을 n보다 작은 연속적인 소수의 합으로 나타낼 수 있는 경우의 수를 구하는 문제이다.먼저 n보다 작은 소수를 전부
https://www.acmicpc.net/problem/11728정렬된 배열 두 개 합치는 문제이다. 예전에 프로젝트할 때 비슷한 상황이 있었는데 그때는 그냥 배열 두 개 연결하고 정렬했었는데, 더 나은 방법이 있는지 확인할 겸 풀어보았다.투 포인터인 만큼
https://www.acmicpc.net/problem/2170최근에 했던 코딩테스트에서 처음 보는 유형의 문제가 나와서 O(n^2) 코드밖에 떠오르지 않았는데 다음에 비슷한 문제가 나오면 어떻게 대응해야할 지 확인하기 위해서 지피티 선생님의 지혜를 빌려 어
https://www.acmicpc.net/problem/2261Sweep 알고리즘 풀다가 여기까지 도달했다. 그런데 1차원 직선 상에 놓인 점 중에 가까운 것은 구할 수 있겠는데 2차원에서는 어떻게 접근해야할 지 감을 잡지 못했다.https://ww
https://www.acmicpc.net/problem/2018
https://www.acmicpc.net/problem/1135상사 id가 있는 리스트가 주어지고, 한 사람당 전화할 때 1분씩 걸린다고 했을 때 뉴스 최종 전파의 최소 시간을 구하는 문제이다.정렬이긴 했는데, 트리로 생각하면 더 빠를 것 같아서 게다가 최소
https://www.acmicpc.net/problem/2531문제를 초밥 먹는 개수를 최대로 하기로 잘못 이해했다.그냥 단순히 쿠폰의 위치를 찾고 쿠폰이 없는 구간 중 k개 이상인 구간을 찾아서 해결했는데 당연하게도 틀렸다.k개만큼 슬라이드 돌면서 set으
https://www.acmicpc.net/problem/1707그래프의 노드에 2가지 색칠하는데 인접한 노드끼리 서로 다르게 색칠할 수 있는지 묻는 문제이다.dfs로 돌면서 색칠하고, 만약 방문했다면 현재 노드와 방문하려고 했던 노드의 색이 같은지 다른지에
https://www.acmicpc.net/problem/17834 사이클이 0개이거나 사이클의 오솔길 개수가 짝수개인 경우에만 영원히 만나지 못하는 상황이 생김. 영원히 만나지 못하려면 사자와 토끼 사이에 오솔길이 홀수개만큼 떨어져있어야함. 사이클 탐지 해서 그
https://www.acmicpc.net/problem/5547육각형 모양으로 배열되는 건물들이 있는데 밖에서 볼 수 있는 부분만 조명을 달려고 하는데 밖에서 볼 수 있는 부분의 길이가 얼마나 되는지 구하는 문제이다.예전에 빙산 문제나 치즈 문제랑 비슷한 결
https://www.acmicpc.net/problem/13334라인스위핑 문제이다. 집과 사무실 좌표로 구성된 선분들 주어지고, 길이가 d인 철도를 설치할 때 가능한 많은 선분을 포함하게 하는 문제이다.기존 스위핑 문제에서는 길이가 가변적이었는데, 이번에는
https://www.acmicpc.net/problem/1744수열에서 임의의 위치에 있는 두 수를 묶을 수 있는데 묶게 되면 두 수는 곱해진다. 묶는 거는 할 수도 있고 안 할 수도 있는데 이렇게 했을 때 수열의 합이 최대가 되게 하는 문제이다.최초에 접근
https://www.acmicpc.net/problem/1002점이 두 개 주어지고, 찾으려고 하는 대상과 두 점 사이의 거리가 주어질 때, 대상이 존재할 수 있는 위치가 몇 가지가 되는 지 찾는 문제이다.처음에는 원 방정식을 활용해서 두 원의 교점을 찾으려
https://www.acmicpc.net/problem/11053 예전에 이해를 못했던 가장 긴 증가하는 부분수열이다. 이 문제는 이미 파이썬으로 풀어봤어서 Java로 풀어보려고 한다. Python next라는 배열을 1로 초기화 시켰다. 해당 요소만 포함하는
https://www.acmicpc.net/problem/121002048 구현하는 문제이다. 최대 5회를 돌렸을 때 최대 값을 출력하는 것이 목표다.방향이 4개이고 5회라서 모든 경우를 고려했을 때 1,024회 밖에 되지 않아서 DFS로 해결하기로 했다.좌우
https://www.acmicpc.net/problem/11403인접행렬을 주고 노드들이 서로 연결되어 있는지 찾는 문제이다.모든 점에 대해서 BFS를 돌려서 BFS 탐색 기록에 노드가 있다면 1로 표시해주는 작업을 했다. 점이 100개라서 가능했나보다.
https://www.acmicpc.net/problem/1389친구 관계를 주고, 케빈 베이컨의 숫자가 가장 작은 사람을 찾는 문제이다.모든 점에 대해서 BFS 돌면서 거리를 구했고, kevin이라는 리스트에 각 사람별로 거리합이 얼만큼 되는지 저장했다. 그
https://www.acmicpc.net/problem/2660월드컵 응원 모임이 있는데 서로 건너건너 아는 사이인 듯 하다. 그중에서 그 건너건너가 가장 작은 사람들을 골라서 건너건너의 길이의 최소값과 해당하는 사람들의 수, 그리고 해당 하는 사람들의 번호
https://www.acmicpc.net/problem/1865시간여행 하는데 웜홀타고가면 시간이 역행한다. 그래서 어떤 점에서 다른 점 타고타고 다시 시작점으로 돌아왔을 때 시간이 역행된 경우가 있는지 찾는 문제이다.벨만 포드 알고리즘을 활용해서 최소신장트
https://www.acmicpc.net/problem/24573월1일부터 11월30일까지 꽃이 한 번도 안 지게 꽃을 선택하는 문제이다.가로등 문제랑 비슷한줄알고 비슷하게 접근하려고 했다가 실패했다.기존까지의 문제와 다르게 기간이 정해진 문제라서 cm, c
https://www.acmicpc.net/problem/2458키를 비교한 데이터를 주고 이 데이터를 기반으로 키 순위를 정확히 특정 가능한 사람의 수를 구하는 문제이다.플로이드 워셜 알고리즘을 사용해야할 것 같은데 어떻게 사용하는지 까먹어서 BFS 두 번
https://www.acmicpc.net/problem/1240n개의 노드와 n-1개의 간선이 있는 그래프에서 특정 두 노드 사이의 거리를 측정하고 싶은 문제이다.BFS로 해결할 수 있었다.tree라는 딕셔너리를 생성하고 이것을 이용해서 인접리스트를 만들었다
https://www.acmicpc.net/problem/4485칸에 숫자가 있고, 0, 0에서 n, n까지 가는데 숫자의 합이 최소가 되도록 하는 문제이다.왼쪽 위에서 오른쪽 아래로 진행하길래 당연히 DP라고 생각했다. 문제를 제대로 안 읽은 것이다. 그래서
https://www.acmicpc.net/problem/1461도서관에 책 갖다놓아야하는데 책의 위치는 직선상에 있으나 위치가 -10000부터 10000사이에 있다. 이 때 책을 한 번에 m권을 들 수 있을 때 책을 갖다놓는 거리가 가장 짧을 때의 거리를 찾
https://www.acmicpc.net/problem/30689미로가 있고, 각 칸에는 어디로 가야하는지 방향이 표시되어 있을때 미로를 탈출하지 못하는 경로가 있다면 해당 경로에 탈출지점을 넣어두려고 한다. 이때 설치 비용이 각 칸 별로 있을 때 설치비용을
https://www.acmicpc.net/problem/2665흰색칸만 이동할 수 있는 미로에서 (0, 0)에서 (n-1, n-1)로 이동할 때 검정 칸으로 길이 막혀있다면, 검정칸을 최소로 변환시켜서 길을 뚫어주는 문제이다.다익스트라라고 문제 유형이 있었는
https://www.acmicpc.net/problem/2179접두사가 가장 비슷한 문자열을 찾는 문제이다.문자열을 index와 함께 저장하고, 정렬한 후에 앞뒤로 문자열을 비교하면서 가장 큰 문자열을 찾는 방식을 사용했다.처음에는 이렇게 했는데 50%에서
https://www.acmicpc.net/problem/2056작업 우선순위가 주어질 때 가장 짧게 작업하는 경우를 구하는 것이다. 위상정렬을 사용해야 한다고 적혀있었다.graph, pre 등 딕셔너리를 생성하고 BFS로 위상정렬을 했다.(고 생각했다)그리고
https://www.acmicpc.net/problem/1022이런모양으로 확장되는 모눈종이의 일부를 출력하는 문제이다입력되는 값 중 최대값을 가지고 필요한 전체 모눈종이의 너비를 구한 후, makeCyclone 함수를 통해서 모눈종이를 그렸다. 그리고 일부
https://www.acmicpc.net/problem/1083버블소트 방식을 사용해서 s번 인접 원소 교환을 하는데 이렇게 해서 내림차순으로 가장 큰 숫자 배열을 만드는 문제이다.단순하게 내림차순으로 가장 큰 숫자배열이니까 내림차순인지 판단하다가 오름차순
https://www.acmicpc.net/problem/17182행성끼리 거리가 주어지고, k부터 해서 모든 행성을 가는 가장 짧은 거리를 구하는 문제이다.플로이드 워셜로 각 행성별 최단거리를 구하고 백트레킹으로 최단거리로 모든 행성 탐사하는 거리를 구했다.
https://www.acmicpc.net/problem/15686도시에 치킨집이 있는데 m개까지 치킨집을 폐업시키는 슬픈 문제이다.치킨집과 가정집의 위치가 2차원 배열로 주어지고, dx+dy만큼을 거리로 계산한다. 이때 가정집에서 가장 가까운 치킨집의 거리
https://www.acmicpc.net/problem/2437양팔저울이 있고, 추가 여러개 있을 때 추를 조합해서 만들 수 없는 가장 작은 정수를 찾는 문제이다.조합으로 접근할지, BFS로 접근할지 고민하다가 답이 안나와서 질문하기를 참고했다.https&#
https://www.acmicpc.net/problem/2169아래, 좌우로만 갈 수 있는 로봇을 조종해서 가장 큰 점수를 얻어서 오른쪽 아래로 도달하는 문제이다.DFS로 풀어보려했다. 재방문을 방지하고 다른 방향에서 계산한 dp가 영향을 주지 않도록 매번