🔗 문제2623번: 음악프로그램  ✏️ 풀이 문제에 알고리즘 힌트가 대놓고 있다.아래의 문장을 읽어보자.이제 여러분이 해야 할 일은 보조 PD들이 가져 온 순서들을 보고 남일이가 가수 출연 순서를 정할 수 있도록 도와 주는 일이다. 답이 여럿일 경우에는 아무거나 하나를 출력 한다. -> 여러 답이 나올 수 있는 위상정렬의 특징  위상 정렬이라는 문제 유형을 파악했기 때문에 문제를 바로 풀 수 있었다.위상 정렬이란 선후관계를 고려하여 여러 원소의 하나의 줄로 쭉 줄세울 수 있는 알고리즘이다.우선순위가 똑같은 원소가 있다면 순서가 상관 없으니 답도 여러개 일수도 있다.  구현 방법은 선후 관계를 고려하는 것 부터 시작된다.a → b 의 간선 관계라면 a는 선, b는 후며 b 입장에서는 a가 진입하므로 아래..

🔗 문제https://www.acmicpc.net/problem/23031  밤이 되면 어두워지는 다솔관에는 좀비가 나온다는 괴담이 있다. 그 좀비들의 정체는 바로 시험 기간에 공부하느라 지친 학생들이었다. 지친 학생들은 멀리서 보면 흡사 좀비이므로 학생 좀비라고 부르자. 아리는 낮에 공부하다가 깜빡하고 책을 두고 와서 밤에 다시 다솔관 4층으로 가야 한다. 밤에 다솔관 4층에 도착한 아리는 겁이 많아서 학생 좀비들을 마주친다면 기절해버리고 말 것이다. 아리는 기절 하지 않고 무사히 책을 찾아 돌아가고 싶다. N × N으로 이루어진 다솔관 4층 곳곳에는 형광등 스위치와 학생 좀비들이 있다. 아리는 가장 왼쪽 위인 (1, 1)에서 출발하고 아리와 학생 좀비들은 모두 아래 방향을 보고 있다. 아리는 주어진..

🔗 문제https://www.acmicpc.net/problem/8913  ✏️ 풀이  [문제 분석] 주어지는 문자의 타입은 2개 밖에 없다.문자를 뽑을 수 있는 조건은 문자의 연속된 개수다.-> 문자가 얼마나 연속되었는지 이 숫자를 이용할 수 있는 방법을 강구하자!! [아이디어] 나의 아이디어가 아닌.. ys님에게 받은 아이디어같은 타입의 문자열을 그룹화하자! 그 그룹에 포함된 요소의 개수가 연속된 문자의 개수다. 이 값 활용해 우리에게 친숙한 숫자로 바꾸어 배열로 저장하자.  이건 어차피 문자의 타입이 2개기 때문에 할 수 있는 방법이다.aaabbaa == {3, 2, 2}abab == {1, 1, 1, 1}  [구현] 위 아이디어를 구현할 수 있는지 검토해보자.문자열을 문자의 연속된 수로 변환하자..

🔗 문제https://www.acmicpc.net/problem/1938 ✏️ 풀이 문제에 나와 있는 배열을 보면 뭔가 막막한 감정이 들게 한다.. 하지만 쫄지 않으면 무조건 풀 수 있다!    문제를 읽으며 "가중치가 없는 최단 경로"구하기라는 것을 알았고 BFS로 알고리즘을 특정했다.BFS의 재방문 방지를 위한 유니크한 값이 필요하다. 그래서 통나무가 차지하는 3칸 중 하나의 위치를 기준으로 잡아주었다.나는 중간에 있는 위치를 기준으로 잡았다.회전을 할 때 중심을 기준으로 8방 탐색을 하면 쉽기 떄문이다!그리고 재방문체크는 3차원 배열을 이용해준다.bool visited[가로니?][x][y]같은 좌표라고 하더라도 통나무의 방향이 (가로)인지 (세로)인지에 따라서 갈 수 있는 방향이 달라지기 때문에 ..

🔗 문제https://www.acmicpc.net/problem/1041  ✏️ 풀이 소요시간100분 (고민 40 + 구현과 최적화) 알고리즘수학(도형의 특성), 조합 풀이눈에 보이는 주사위의 면 개수를 이용하자.  3면 : 상단의 꼭지점 4개2면 : 모서리에서 위, 아래의 꼭지점 2개를 뺀 N-2의 길이만큼 상단과 옆면에 각각 4개씩 존재 (N-2)*8 + 최하단의 꼭지점 4개1면 : 바닥에 깔린 면을 제외한 모든 면의 개수인 5에는 모서리를 제외한 (N-2)(N-2)개 (총 (N-2)(N-2)*5개) + 최하단의 모서리  (N-2)*4     (1)주사위 평면도를 고려해서 각 면이 만날 수 있을 때만 계산해야 한다.아래는 인덱스가 0으로 시작했을 때의 공식이다.2면 계산 시 i, j의 합에서 i +..

🔗 문제https://www.acmicpc.net/problem/2179  ✏️ 풀이입력을 N번 받는다. 입력받은 문자열이 중복이면 저장하지 않고 무시한다.std::set check 변수로 중복 확인을 하며, 오직 중복 확인만을 위해 사용한다.입력받은 문자T를 앞에서 하나씩 떼어서 부분 문자열을 만든 후, 현재 입력받은 순서를 저장한다.abc -> {a, ab, abc}ab -> {a, ab}map에는 {a, {0, 1}}, {ab, {0, 1}}, {abc, {0}} 이렇게 저장된다.부분 문자열을 만들고 map에 저장하는 과정에서 가장 긴 prefix의 길이를 갱신한다. (max_prefix) map의 key-value key : prefixvalue : 해당 prefix를 만들 수 있는 문자열T의 ..

🔗 문제https://www.acmicpc.net/problem/22255 ✏️ 풀이 완전탐색으로 풀기에는 너무 많은 경우의 수가 생긴다는 것을 알 수 있다.이 문제는 다익스트라 문제다.DP[i][j]를 시작점부터 (i, j)에 도달할때까지 받은 총 충돌량의 최소값으로 정의하고, 기존 DP보다 값이 작을 때만 그 방향으로 탐색을 해주게 되면 경우의 수가 가지치기 되므로 시간 안에 문제를 풀 수 있다. 문제 포인트 #매 이동 시 마다 움직일 수 있는 방향이 다르다.이동 횟수(k)가 갈 수 있는 방향을 결정한다.3k, 3k+1, 3k+2는 k%3으로 바로 바꿔 사용할 수 있다.k%3==0 : 상하좌우k%3==1 : 상하좌우k%3==2 : 상하좌우상하좌우를 변수로 선언해두고 range를 설정해주어서 이동 가..

https://www.acmicpc.net/problem/1987 1987번: 알파벳문제 세로 R칸, 가로 C칸으로 된 표 모양의 보드가 있다. 보드의 각 칸에는 대문자 알파벳이 하나씩 적혀 있고, 좌측 상단 칸 (1행 1열) 에는 말이 놓여 있다. 말은 상하좌우로 인접한 네 칸 중의 한www.acmicpc.netDFS와 되추적 기법(1,1)에서 시작되는 노드를 따라 갔던 정점 빼고 가장 많은 정점의 수를 출력해야한다. 즉, (1,1)에서 시작하여 모든 노드를 방문하며 - > DFS / BFS모든 경우의 수를 생각해야한다 -> 되추적 기법 모든 경우의 수를 생각해야하는 거면 DP도 되지 않나라는 생각을 했는데2차원 배열이 사용되는 그런 길? 타일 같은 공간이 필요하면 되추적으로 하는 것 같다(..) 되추..

사실 이 문제 예전에 풀었던 문제입니다.처음 풀 때는 시간 초과 때문에 인터넷의 도움을 받았던 기억이 생생합니다.  그래도 예전에 푼 문제를 다시 풀 때는 언제나 긴장됩니다.과연 성장했는가, 제자리인가 ..   솔직 고백하자면  뿌듯해서 올리는 풀이글입니다.저 이 문제 JAVA 기준 1등이에요 ✌🏻🎶💖나보다 나은 사람 코드 훔쳐보려고 등수봤는데 감격해서 굳이 굳이 씁니다.  풀이 (C++) https://viin.tistory.com/152 [C++] 백준 10711번: 모래성🔗 문제 10711번: 모래성 10711번: 모래성 첫째 줄에는 모래성의 가로세로 격자 크기 H, W가 주어진다. (1 ≤ H, W ≤ 1,000) 그 다음 H줄에 걸쳐 W개의 문자로 모래성의 상태를 나타내는 문자가 들어온다..

🔗 문제https://school.programmers.co.kr/learn/courses/30/lessons/258705 프로그래머스코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.programmers.co.kr   ✏️ 풀이https://github.com/BE-Archive/Algorithm-Study/pull/557 #include using namespace std; int solution(int n, vector tops) { vector > dp(n, vector (2, 0)); const int mod = 10007; ..." data-og-host="github.com" data-o..