본문 바로가기
  • 컴공생의 공부 일기
  • 공부보단 일기에 가까운 것 같은
  • 블로그

📊 Algorithm/BOJ46

🌳백준 - 1967 트리의 지름 # 1967트리의 지름🥇골4 흑흑 자료구조 다 까먹었자나 트리(tree)사이클이 없는 무방향 그래프어떤 두 노드를 선택해도 둘 사이에 경로가 항상 하나만 존재  트리에 존재하는 모든 경로들 중에서 가장 긴 것의 길이찾기 임의의 한 정점에서 bfs해서 가장 멀리 잇는 정점 찾고ㄱㅡ 정점에서 같은 짓 한번 더 하면그 거리가 지름!!  트리의 지름 구하기트리의 지름velog.io  sys.setrecursionlimit = 100000.....sys.setrecursionlimit(100000)가 맞다 2024. 10. 2.
🧭 백준 - 1504 특정한 최단 경로 오잉~ 로봇아닙니다 왜 받았징그냥 사적으로 뵌 건 안 되고 행사에서 봐야 하는 건가 보넹 UCPC때문인강# 1504특정한 최단 경로🥇골4  특정한 => 2개의 노드를 더 거쳐야 함! 다 다른1번/v1번/v2번/n번 을 거쳐야 하니깐  1 -> v1 -> v2 -> N1 -> v2 -> v1 -> N 이 두 개의 경로 중 최단인 걸 고르면 된다 하나노드에서 모든 노드에 대한 거리를 알려주는 다익스트라를1에서v1에서v2에서 해도 되지만!무방향 그래프이기 때문에v1에서v2에서2회만 다익스트라 하고 답을 구할 수 있다.아 졸리다......  ✨스.꾸✨(백준스트릭꾸미기라는뜻)혈기왕성하던 시절.. 🔮 백준 스트릭 잇기 🔮중요한 것은 꺾이지 않는 마음! 백준배지 새싹 1의 충격 새싹 9 가져보겠다. 적어도 6?.. 2024. 9. 24.
🧪 백준 - 14502 연구소 # 14502연구소🥇4  흠...오,,,N M이 엄청 작고 2초그냥 브루트해도되겟다 for i1 in range(N): for j1 in range(M): for i2 in range(N): for j2 in range(M): for i3 in range(N): for j3 in range(M): if ((i1,j1) != (i2,j2) and (i2,j2) != (i3,j3) and (i1,j1) != (i3,j3)): if ( 0 == now_map[i1][j1] and 0 == now_map[i2][j2] and.. 2024. 9. 3.
5️⃣ 백준 - 17299 오등큰수 저녁 때는 다른 팀이랑도 밥 먹었다!# 17299오등큰수🥇3 웰논 오큰수를 생각나게 하는 네이밍.. 오큰수는 어떻게 풀었냐면..스택에 쇽샥쇽샥    Ai의 오등큰수: 오른쪽에 있으면서 수열 A에서 등장한 횟수가 F(Ai)보다 큰 수 중에서 가장 왼쪽에 있는 수등장한 횟수로 바뀌었군.. 우선 그럼 각 수에 대해 등장 횟수를 카운트한다그다음에 스택 슥삭슥삭import sysN = int(sys.stdin.readline())A = list(map(int, sys.stdin.readline().split()))A_list = []for a in A: A_list.append((a, A.count(a))) my_stack =[]result = []A_list.reverse()for a in A_list:.. 2024. 9. 2.
🗳️ 백준 - 2660 회장뽑기 뉴클린언니랑 원밀리언을 다녀왔다 짱맛잇는 유럽여행선물 초코를 받았다# 2660회장뽑기🥇5  "모든 지점에서 다른 모든 지점까지의 최단 경로를 모두 구해야 하는 경우"에 쓰는 알고리즘!=> 플로이드 워어셔얼어 그리고그냥 그거 쓰면 됨.  실수 cut어케 다들 동작을 한시간만에 숙지하는 거지?댄서는 암기력이 좋아야 할 수 있을 듯 2024. 9. 2.
🤯 백준 - 9935 문자열 폭발 단계별 풀기 스택 2를 끝내자~폭🤯발은 요즘 내가 좋아하는 단어다풀어보자.# 9935문자열 폭발🥇4  이미.. 스택 카테고리를 타고 들어온 시점부터 이 문제는 폭발이다ㅅㅡ택으로 숑숑하면 될 듯 중간에 동생의 뉴진스 앨범 깡 구경 및 스티커 구걸탱크게임의 유혹ㅇㅣ 있었지만이겨내고 탱크게임 한판하고 자야겠따 2024. 8. 17.
👿 백준 - 9507 Generations of Tribbles 어제 푼 게임이론 DP에 이어서 DP난 DP가 싫다DP를 통해 내 뇌 주름의 한계를 가늠해볼 수 있다젠장....엄마 옆에 있을 때 창 넘기다가 들켜버림..........올리지말걸...# 9507Generations of Tribbles🥈실4  dp미리 구했던 dp값이 있으면 다시 계산하지 않도록 해서 시간복잡도를 줄이는 것이 포인트다def koong(n): if n 이게 아니라def koong(n): if n 이거! 2024. 8. 14.
⚠︎ 백준 - 4158 CD 파이팟파티 후의 백준# 4158CD🥈실5 이제 그냥 비교하면 (한 요소당 다른 리스트 요소 전부 보기) n*n 근데 이건 정렬되어 잇으니까 각 배열의 시작에 포인터 한 개씩 놓고 N*2 오 젠장...저번에도 그랬는데..0 0이 왜 잇지 그냥 무시해야지~하다가 "입력은 여러 개의 테스트 케이스로 이루어져 있다." 화나네근데 set.intersection도 시간초과안남set1 = set(a_CD)set2 = set(b_CD)result = len(list(set1.intersection(set2)))이번주 스터디 과제다 2024. 8. 11.
⚠︎ 백준 - 25682 체스판 다시 칠하기 2 # 25682체스판 다시 칠하기 2🥇G5 흠흠그니까일단 크기는고정이니까 원래 판 위에서 밀면서 훔 2차원슬라이딩윈도우처럼 하면 되지 않을까~검정이 모서리일 때 / 흰이 모서리일 때 : 중에 작은 걸로하나가 n개 새로 칠해야 하면 다른 하나는 K*2 - n둘 중에 작은 게 정답 후보그럼 들어오는 줄이랑 나가는 줄이랑 다르게 생긴 개수만큼 아닌데그걸로는 계산할 수 없는데검정이 모서리일 때 / 흰이 모서리일 때 : 각각 틀린 네모를 표시해놓고하고 kk 움직이면서 바뀐줄만갱신해서최솟값찾기 으으 구현...을ㄹ머리꼬였아..시간초과남....화나네.......이럴거면브루트포스했지 아 누적합...누적합이네...화나네...난 멍청이야누적합왜생각못했지 나도 똑똑하고 싶어! 2024. 8. 7.
⚠︎ 백준 - 1904 01타일 DP....더 이상 물러날 곳이 없다# 190401타일🥈 S3 음..100,11001, 100, 111 1001,0011,1100,1111,000010000,00001,00100,11111,10011,11001 그리고으ㅓㄹ 근데 꼭 DP로해야하나? 수학으로할수잇잖아 sum( C(i+N-(i*2),i) for i in range(N//2))는 O(N^2)네  ..DP ㅇ직전 거에 1 사이사이 끼워넣기직직전 거에 00 사이사이 끼워넣기는 아니고 그냥 직직전거에서 0만으로 이루어진것만영향이잇네고럼 직전거에서 아 헷갈은그냥이미 이이전거에서 이전 거로 올라오는 거에 그 사이 것들은 다 반영이 되어 잇구나 새로 뒤에 추가되는공간만생각하면됨그냥 더하기하기! 태진오빠가 우리가 다 안 푼 문제로 문제 골라주는 딸깍 만.. 2024. 8. 6.

티스토리툴바