정신 차리고 살자

문제 (https://programmers.co.kr/learn/courses/30/lessons/72411) 코딩테스트 연습 - 메뉴 리뉴얼 레스토랑을 운영하던 스카피는 코로나19로 인한 불경기를 극복하고자 메뉴를 새로 구성하려고 고민하고 있습니다. 기존에는 단품으로만 제공하던 메뉴를 조합해서 코스요리 형태로 재구성해서 programmers.co.kr - 처음 생각 (시간 초과) orders 반복 -> course 반복 -> course 반복문 내에서 orders 문자열로 next_permutation 돌림 do while문 내에서 orders 문자열을 인덱스 0~j 부분을 잘라준다. 잘라낸 문자열을 정렬하고 set에 존재하는지 확인한다. set에 해당 문자열이 존재하지 않는다면 set에 삽입, map..

문제 (https://programmers.co.kr/learn/courses/30/lessons/1835) 코딩테스트 연습 - 단체사진 찍기 단체사진 찍기 가을을 맞아 카카오프렌즈는 단체로 소풍을 떠났다. 즐거운 시간을 보내고 마지막에 단체사진을 찍기 위해 카메라 앞에 일렬로 나란히 섰다. 그런데 각자가 원하는 배치가 모두 programmers.co.kr 알고리즘 스터디 문제 !! ㅎㅇ JY ㅋㅋ 일단 이 문제는 예전에 풀었던 문젠데.. 그땐 엄청 비효율적으로 짰다ㅠㅠ 이번에는 코드를 간결하게 짜려고 노력함! string 변수에 각자 이름을 뜻하는 "ACFJMNRT"을 저장해 두고 이 문자열로 next_permutation 함수를 실행했다. 문자열 조합이 생성될 때마다 data vector의 모든 요소..

링크 (https://www.acmicpc.net/problem/16398) 16398번: 행성 연결 홍익 제국의 중심은 행성 T이다. 제국의 황제 윤석이는 행성 T에서 제국을 효과적으로 통치하기 위해서, N개의 행성 간에 플로우를 설치하려고 한다. 두 행성 간에 플로우를 설치하면 제국의 함 www.acmicpc.net 무난한 최소 스패닝 트리 문제이다. MST 문제를 항상 크루스칼 알고리즘으로만 풀었는데 이번엔 프림 알고리즘으로 풀어봤다! 정답이 int 범위보다 클 수 있으므로 long long으로 해주어야 한다. [소스코드] 더보기 2022-03-02 Gold 4 - 그래프 이론 - 최소 스패닝 트리

문제 (https://www.acmicpc.net/problem/14621) 14621번: 나만 안되는 연애 입력의 첫째 줄에 학교의 수 N와 학교를 연결하는 도로의 개수 M이 주어진다. (2 ≤ N ≤ 1,000) (1 ≤ M ≤ 10,000) 둘째 줄에 각 학교가 남초 대학교라면 M, 여초 대학교라면 W이 주어진다. 다음 M개의 www.acmicpc.net 최소 스패닝 트리 문제이다. 크루스칼 알고리즘을 사용해서 해결했다. 특별히 어려운 점은 없는데 처리해야 할 조건이 하나 있다. 남초-남초, 여초-여초로 연결되면 안 되고 항상 번갈아가면서 연결되어야 한다. 따라서 나는 두 노드를 union 하기 전, 두 노드의 성별이 다른지 확인했다. 만약 해당 조건이 없다면 위 그래프의 답은 3(CD) + 5(B..

문제 (https://www.acmicpc.net/problem/1253) 1253번: 좋다 첫째 줄에는 수의 개수 N(1 ≤ N ≤ 2,000), 두 번째 줄에는 i번째 수를 나타내는 Ai가 N개 주어진다. (|Ai| ≤ 1,000,000,000, Ai는 정수) www.acmicpc.net 처음엔 검사하는 숫자보다 작은 수들로만 검사하는 숫자가 만들어진다고 생각했다. 하지만 음수도 가능하기 때문에 -4 -2 -2 같은 케이스가 존재한다. (-4가 좋은 수) 또한 자기 자신은 서로 다른 두 수에 해당하면 안 되므로 예외 처리를 해주어야 한다. 나는 그냥 for문을 돌 때마다 원본 벡터를 복사한 벡터에 해당 숫자를 erase로 제거하여 사용했다. - n이 2보다 작거나 같으면 다른 수 두 개의 합으로 나타..

문제 (https://www.acmicpc.net/problem/3078) 3078번: 좋은 친구 첫째 줄에 N과 K가 주어진다. (3 ≤ N ≤ 300,000, 1 ≤ K ≤ N) 다음 N개 줄에는 상근이네 반 학생의 이름이 성적순으로 주어진다. 이름은 알파벳 대문자로 이루어져 있고, 2글자 ~ 20글자이다. www.acmicpc.net 슬라이딩 윈도우로 해결한 문제!!! 문제 설명이 엄청 길지만,, 요약하자면 좋은 친구의 정의는 아래와 같고 좋은 친구가 몇 쌍 있는지 출력하면 된다. 좋은친구: 등수의 차이가 K보다 작거나 같으면서 이름의 길이가 같은 친구 pair (등수, 이름의 길이) 형태로 입력을 받았다. i번째(i등) 학생은 크기가 k인 창문 내의 다른 학생들 중, 이름의 길이가 같은 학생과 좋..

문제 (https://www.acmicpc.net/problem/2096) 2096번: 내려가기 첫째 줄에 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 N개의 줄에는 숫자가 세 개씩 주어진다. 숫자는 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 중의 하나가 된다. www.acmicpc.net DP + 슬라이딩 윈도우로 해결한 문제이다. 두 알고리즘 모두 취약해서...ㅎㅎ 다른 코드를 참고하여 풀었다. 크기가 3인 배열들 minArr, maxArr, minTmp, maxTmp을 사용했는데, minTmp, maxTmp는 현재 행 이전까지의 결과를 저장해둔 배열이다. - 첫 번째 행의 값들은 최솟값이자 최댓값이므로 4개의 배열에 모두 삽입해준다. - 첫 번째 행이 아닐 경우에는 minTmp, m..

문제 (https://www.acmicpc.net/problem/2211) 2211번: 네트워크 복구 첫째 줄에 두 정수 N, M이 주어진다. 다음 M개의 줄에는 회선의 정보를 나타내는 세 정수 A, B, C가 주어진다. 이는 A번 컴퓨터와 B번 컴퓨터가 통신 시간이 C (1 ≤ C ≤ 10)인 회선으로 연결되어 있다 www.acmicpc.net 처음엔 MST를 사용해야하나? 라는 생각이 들었지만 다익스트라로 만들어진 MST와 MST는 서로 다르다는 반례를 보고 다익스트라로 문제를 해결했다. 11779 최소비용 구하기 2 문제에서 사용했던 방식과 유사하다. route라는 배열을 생성하여 배열의 해당 인덱스에 도달하기 위해서는 몇 번에서 와야 하는지를 기록한다. route[a] = b는 "a번에 최소로 도..

문제 (https://www.acmicpc.net/problem/13549) 13549번: 숨바꼭질 3 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 www.acmicpc.net 작년에 BFS로 풀었던 1697 숨바꼭질과 비슷한 문제이다. 다익스트라 알고리즘 스터디 주간에 고른 문제여서 다익스트라로 해결해보려 했지만,, 문제를 읽고 생각을 해봐도 1697번 문제처럼 BFS로 해결하는 방법밖에 떠오르지 않았다...! 그래서 일단 BFS로 해결 완! (코드 첨부) BFS로 해결할 경우 방문 순서에 따라 정답이 되기도 하고 아니기도 한..

문제 (https://www.acmicpc.net/problem/1238) 1238번: 파티 첫째 줄에 N(1 ≤ N ≤ 1,000), M(1 ≤ M ≤ 10,000), X가 공백으로 구분되어 입력된다. 두 번째 줄부터 M+1번째 줄까지 i번째 도로의 시작점, 끝점, 그리고 이 도로를 지나는데 필요한 소요시간 Ti가 들어 www.acmicpc.net N개의 마을에는 각각 한 명의 학생이 살고 있고, 입력받은 X번 마을에서 파티가 열린다. 모든 학생들의 이동거리는 최단거리여야 한다. N명의 학생들 중 (i번째 마을 -> x번 마을) + (x번 마을 -> i번째 마을) 시간이 가장 긴 학생의 소요시간을 출력하면 된다. Dijkstra Algorithm: '한 정점'에서 '모든 정점'으로의 최단경로 인접 리스..