https://www.acmicpc.net/problem/1700 그리디 문제이다.본인은 첫트에 틀렸다.. (어렵더라..)왜 틀렸냐면은 멀티탭이 꽉차 있는 상태, 아닌 상태, 사용중인지 아닌지를 판별하고 있었다. 멀티탭이 꽉차있지 않다면 그냥 꼽고 해당 제품 번호를 사용중으로 변경해주면된다.근데 문제는 '멀티탭이 꽉차 있을 때' 이다.이때 뭘 뽑아야 최적의 선택으로 이어질지 고민을 해야한다. 본인은 멀티탭이 꽉차 있을 때, 앞으로 사용횟수가 가장 작은 것을 찾아 해당 제품을 뽑으면 최적이 아닐까? 생각했었고 이대로 코드를 짜서 O(N^2)로 풀었는데 틀렸다. 최적의 경우는 '앞으로 사용할 번째 수가 가장 뒤에 있거나가장 나중에 사용) 사용하지 않을 제품을 뽑는 것'이 최적이다.예시로 ' 1 2 3 2 4..

https://www.acmicpc.net/problem/13305 해설그리디 문제이다.(첨에 문제가 길어서 좀 쫄았는데 쫄지말자)처음에 좀 고민을 했다. 이거 DP인가 그리디인가??한 10~15분쯤 고민하니까 딱 명확하게는 아니지만 언제 최소가 되는지 숨겨진 규칙?을 찾아 냈다.42 3 15 2 4 1순으로 입력을 받는다고 했을 때 5 : A, 2 : B, 4 : C, 1 : D라고 하자.A에서는 딱 2리터만 주유해야하고 B에서는 4리터를 주유해야 최소값이 나온다.여기서 알 수 있는게 다음 마을의 기름값이 더 싸다면 다음 마을까지 가는 거리 만큼만 주유해야 최소값이 나온다는 것을 알 수 있다.B에서는 B마을 보다 가격이 싼 주유소가 있는 마을이 나오는 거리만큼 주유를 해야한다는 것을 알 수 있었다.A에..

https://www.acmicpc.net/problem/11967 문제해설해당 문제는 BFS문제이다.정답은 아니지만 본인은 입력받은 정점을 인접리스트로 관리하고 BFS탐색시 인접리스트의 원소들에 대해서 '불을 먼저 킨다' 그 후에 상하좌우를 살펴 불이 켜져 있으면 이동하는 식으로 로직의 흐름을 짯다. 주의할 점은 '불을 켜는 과정에서 무조건 큐에 넣으면 안된다'는 것이다.혹시 (1, 1) -> (1, 2) -> (1, 3)이후 (1, 3)에서 (2, 1)에 대해 불을 킬 수 있다고 해서 (2, 1)을 바로 넣으면 안된다. 본인은 처음에 베시가 불을 킬 수 있는 영역에 대해서 불을 킨다음에 불을 킨 정점을 큐에 추가하였는데, 잘못된 로직이였다. (1, 1) -> (1, 2) -> (1, 3) 순으로 방문..

https://www.acmicpc.net/problem/9663 백트레킹 문제이다.어렵고 까다롭지만 좋은 문제라서 따로 정리해두려고한다.더 좋은 풀이는 https://cryptosalamander.tistory.com/58 이분의 풀이를 추천드린다. 풀이 흐름해당문제는 일단 하나의 row에 하나의 퀸만 배치할 수 있다는 것을 전재로 두는게 좋다.탐색 자체는 현재 row(행)의 특정 col(열)에 퀸을 배치할 수 있는지 없는지를 판단할 것이다.현재 row라는 값이 필요하기 때문에 탐색할 때 param으로 현재 현재 ‘row’를 받아와야한다.row의 특정 col에 조건을 따져 배치할 수 있다면 배치하고 그렇지 않다면 되돌아 가준다.계속 배치를 하다가 row가 n과 같다면 한 row당 하나의 퀸을 배치한 것..

https://www.acmicpc.net/problem/1525 1525번: 퍼즐 세 줄에 걸쳐서 표에 채워져 있는 아홉 개의 수가 주어진다. 한 줄에 세 개의 수가 주어지며, 빈 칸은 0으로 나타낸다. www.acmicpc.net 후기 조금 어려웠던점 점은 원본 상태에 대한 상태를 변경해야한다는 부분을 어떻게 처리할 줄 몰랐었습니다. 기존의 조금 까다롭다고 생각되는 문제들은 2차원 배열을 탐색하는 것이 아니라 값 자체를 탐색하는것에 추가적으로 특정 상태를 기억한다음에 탐색을 이어 가는데 해당 문제는 이 두가지 가 모두 포함된 상태에서 탐색을 하는 대상자체와 방문 표시를 하는 부분에 대한 신경도 썻어야 하는 문제입니다. 풀이 "103425786"에 대한 상태를 문자열로 관리를 해줍니다. '0'이 있는 ..

https://www.acmicpc.net/problem/1722 1722번: 순열의 순서 첫째 줄에 N(1 ≤ N ≤ 20)이 주어진다. 둘째 줄의 첫 번째 수는 소문제 번호이다. 1인 경우 k(1 ≤ k ≤ N!)를 입력받고, 2인 경우 임의의 순열을 나타내는 N개의 수를 입력받는다. N개의 수에는 1부터 N www.acmicpc.net 순열 + DP문제입니다. 순열은 nPr이고 n개 중에 r개를 뽑는데 순서를 고려하여 뽑는 경우를 뜻합니다.(사전순 정렬) 문제의 입력 최대값이 20이므로 O(20!)을 가지기에 next_permutation을 사용하면 무조건 시간초과로 틀리기 때문에 시간 복잡도를 줄이기 위해 고민이 필요한 문제인거 같습니다. 풀이순서 1. 먼저 입력조건에 따라 입력을 받는다. 2. ..

문제 https://www.acmicpc.net/problem/17472 17472번: 다리 만들기 2 첫째 줄에 지도의 세로 크기 N과 가로 크기 M이 주어진다. 둘째 줄부터 N개의 줄에 지도의 정보가 주어진다. 각 줄은 M개의 수로 이루어져 있으며, 수는 0 또는 1이다. 0은 바다, 1은 땅을 의미한다. www.acmicpc.net BFS, DFS, MST 개념이 다 들어간 문제이고 단계적으로 풀이하여 문제에서 요구하는 바를 구현할 수 있는지가 중요한듯 합니다. 풀이순서 1. 입력으로 받은 데이터의 섬마다 번호를 매겨준다. (BFS 사용) 2. 상하좌우로 각 섬마다 연결될 수 있는 다리가 있는지 탐색하고 연결이 가능하면 경로에 추가한다. (DFS 사용) 3. 추가된 경로들을 가지고 최단거리를 구한다..

https://www.acmicpc.net/problem/2696 2696번: 중앙값 구하기 첫째 줄에 테스트 케이스의 개수 T(1 ≤ T ≤ 1,000)가 주어진다. 각 테스트 케이스의 첫째 줄에는 수열의 크기 M(1 ≤ M ≤ 9999, M은 홀수)이 주어지고, 그 다음 줄부터 이 수열의 원소가 차례대로 주 www.acmicpc.net 이번글은 백준사이트의 중앙값 구하기에 대한 설명입니다. 먼저 평균값과 중앙값은 다릅니다. 1 2 3 4 5가 있을 때 평균은 1+2+3+4+5 / 5 가 평균값이고 중앙값은 말 그대로 1~5사이에 있는 딱 중앙에 있는 값을 의미합니다. 그리고 우선 시간제한이 1초라는점과 입력값의 최대치를 확인해줍니다. TC가 1000이고 하나의 TC에 대한 M의 입력이 9999입니다...