plzfday's notes

11726: 2xn 타일링풀이Dynamic Programming으로 풀 수 있는 문제다. dp[i] = dp[i - 1] + dp[i - 2]코드123456789#include int main(){ int n, i, dp[1001] = { 1, 1 }; scanf("%d", &n); for (i = 2; i

문제 링크풀이분기점이 총 3개가 나온다. i와 i-1번째가 다르고 처음 보는 단어인 경우i와 i-1번째가 같고 처음 보는 단어는 아닌 것(같은 문자가 연속된 것)i와 i-1번째가 다른데 이미 확인 된 것(서로 떨어져 있는 경우) - 예) aabba --> 이때가 그룹 단어가 아닌 경우을 바로 확인 가능하다. 즉, i + 1번째 단어들은 볼 필요가 없다.필요한 변수 : bool형 alpha배열(처음 보는 단어인지 아닌지 확인한다), char형 prev 변수(i번째 기준으로 i -1번째 문자를 기억하는 용도) 나는 함수를 사용해서 구현 할 것이므로 3번째 경우일 때 바로 return false를 해주면 되고 나머지 경우일 경우일 때는 alpha배열과 prev변수를 업데이트만 해주면 되는 상황이 나온다. 코드

문제 링크 DFS + DP 방식으로 풀었다. 위상 정렬이라는 것으로 풀 수도 있는 것 같은데 다음 시간에 다시 풀어보도록 하고... 나는 처음에 1번부터 시작해서 N까지 다 시간을 구한 후에 dp[w]을 출력해줄려고 했는데 각각의 dp[i]값을 지정해줄 방법을 생각하지 못하다가 결국 다른 분들을 보니 w부터 시작해서 (그래프라면) 위로 연결된 자신의 부모를 탐색하신 것을 봤다. 그래서 만약 7번 노드가 5번 6번과 연결되어 있다면 dp[7] = max(dp[5], dp[6]) + 7번의 시간(d[7]) 이런 형식이였다. 그래서 이 부분은 재귀함수를 돌려서 1번 노드까지 찍고 내려오면 되는 것이였다;;잡소리를 좀 하자면 결국 답은 인접 행렬로 풀었는데 원래 인접 리스트(vector)로 풀려다가 겁나 뻘짓해..

1004: 어린 왕자문제 풀기 원 안에 점이 있는지 없는지 확인하는 걸 짜는 문제였다. 다만 조심해야 하는 것은 거리가 int 범위로는 커버할 수 없기 때문에 long long 같은 걸 써줘야 한다.

문제 풀러 가기 링크 1920번: 수 찾기이분 탐색을 이용하면 된다. 나는 속도가 60ms가 나왔는데 적게 나오신 분들의 코드를 보니 입력 받는 부분이 특이하던데 어떻게 하는지는 모르겠다.이분탐색에서 int mid = (left + right) / 2하는 부분에서 / 2 부분을 쉬프트 연산자를 써서 >> 1로 바꿔주니 나의 경우에는 64ms -> 60ms로 바뀌었다. 코드

문제 풀러가기 링크 2606번: 바이러스문제 분류가 플로이드 와샬 알고리즘으로 되어 있는데 나는 DFS로 풀었다. 플로이드 와샬을 짜본적이 아직 없고 사실 BFS 연습 문제 추천에서 나온 문제라 풀려고 한 건데 BFS보단 DFS가 더 쉬울 것 같았기 때문이다 ㅋㅋ 문제 자체는 간단한데 1번 컴퓨터에서 바이러스가 시작되서 연결이 되어 있는 모든 컴퓨터까지 감염이 되는데 그 감염되는 컴퓨터의 개수를 세라는 것이다. --> 탐색 DFS와 BFS라는 문제를 풀어 봤다면 엄청 쉽게 풀 수 있다. 사실 컨셉만 다른 거지 문제는 똑같다고 보면 된다. 코드

1932번 문제 풀기! 1932번: 숫자삼각형정말 고민을 많이 했는데 생각보다 간단했었따... 이게 왜 DP인지 궁금하신 분들을 위해 설명을 하자면 문제 자체가 위층에서 다음을 위해 적절한 녀석을 골라서 현재 층에서 가장 적절한 녀석을 골라 더해주는 것이다. 좀 깔끔하게 설명하지 못해서 그렇긴 한데 재귀적인 성격이 나오는 문제이다. 문제를 보면 ↘, ↙으로 갈 수 있다고 했다. 이건 위에서 아래로 내려갈 때 가정(1)이고, 아래에서 위로 간다고 가정하면 ↖, ↗으로 갈 수 있다.(2) 개인적으로 이런 문제들은 바텀-업 방식을 사용하는 것을 선호하기 때문에 (2)의 가정이 점화식을 세우기에 좋았다. [1] [2] [3] [4] [5] [1] 7 [2] 3 8 [3] 8 1 0 [4] 2 7 4 4 [5] ..

문제 풀러 가기1978번: 소수 찾기소수는 1과 자기 자신으로만 나눠지는 수이다. 예를 들어 2, 3, 5, 7 등이 있다.여기서는 안 쓰이는 방법 같은데 N(자연수)까지의 소수의 개수를 구하는 많은 양을 작업할 때는 에라토스테네스의 체라는 것을 사용한다고 한다.하지만 여기서 사용하진 않았다.참고: 위키피디아코드

문제 풀러 가기 2193번: 이친수 처음에는 문제를 잘못 보고 n이 주어졌을 때 n을 이진수로 바꿔서 이친수인지 확인하는 문제인줄 알았다. 이래서 문제를 잘 읽어야 한다;; 어쨋거나 이 문제는 DP문제인데 처음에는 왜 DP인가 했지만 주어진 조건들을 보고 손으로 하다보니 DP라는 사실을 알게 되었다. 맨 끝자리가 0으로 끝나면 파생될 수 있는 숫자가 '0'과 '1'로 두 개이고 1로 끝나면 '0'으로 파생된다. 규칙은 찾았고 분명히 개수에도 규칙이 있을 것 같아 몇 개 적은 것을 보니깐 피보나치 수열이라는 사실을 알았다. 아! 그리고 참고로 처음에 제출했을 때 틀려서 질문 올라온 것을 보니깐 90자리까지 나올 수 있는데 그러면 long long이 필요할 것 같아서 고쳤더니 맞았다. + 추가: 2020/0..

[BOJ]2669번: 직사각형 네개의 합집합의 면적 구하기접근처음에 접근을 무작정 빼고 더하고... 하려고 했으나 감히 그 행동을 하지 못하겠어서 질문 검색을 해봤습니다 ㅠㅠ 풀이메모리를 포기하고 정신을 챙겨간다! 100x100의 배열을 만들고 그 칸들을 채워나가는 방식으로 문제를 풀어봤습니다. 코드