Dalin's Archive

나는 특히 분할 정복이 어렵다..ㅠ 많이 풀어보지 않아서 그런 것 같다... 그래서 🥈실버🥈 분할 정복 문제를 몇 개 풀어봤다. 2630. 색종이 만들기 문제 보러 가기! 정사각형 형태로 종이가 주어진다. 칸마다 파랑일 수도 있고, 하양일 수도 있다. 주어진 범위의 모든 칸이 같은 색깔이면 그만 자른다. 색이 섞여 있으면 4등분을 한다. (세로로 반, 가로로 반. 정사각형 모양으로) 파란 색 종이 개수를 저장하는 blue_cnt, 하얀 색 종이 개수를 저장하는 white_cnt를 0으로 초기화한다. divide_and_conquer함수에 시작하는 인덱스와 끝나는 인덱스, 한 변의 길이를 넣는다. divide_and_conquer 함수 주어진 범위를 쭉~ 보면서(check 함수) 다 같은 색깔이면 하양인지..

https://www.acmicpc.net/problem/13422 풀이 🐸 N개 집이 원형으로 쭉~ 놓여있고 각각 집에는 돈이 있다. 도둑은 연속된 집 M개를 턴다.(각 집에 있는 돈을 다 가져간다) 이 돈이 K 미만이어야만, 도둑이 안전하게 돌아갈 수 있다. 도둑이 무사히 돌아갈 수 있으면서, M개 집에서 도둑질할 때 그 경우의 수를 구해야 한다. 투 포인터로 쭉~ 봐줬다. 도둑질 당하기를 시작하는 집, 끝나는 집을 left, right로 뒀다. 그 집들에서 훔친 돈을 stolen_money로 뒀다. 맨 처음에는 left부터 right까지의 집에 있는 돈을 다 더해서 stolen_money를 초기화했다. 그 후에 한 집씩 옮기면서 stolen_money를 봤다. 한 집씩 옮길 때 left집의 돈을 s..

나에 대한 설명 👩 혹시 참고하실 수도 있으니, 나에 대한 설명을 먼저 쓰겠다. 나는 대학교에서는 역사, 교육학을 전공했고, 작년 7월부터 싸피에서 프로그래밍 공부를 하고 있다~ 1과목(소프트웨어 설계): 싸피 수업, 특강에서 1과목 이야기를 좀 들었고, 프로젝트를 하면서 그 과정을 경험했다. 3과목(데이터베이스 구축): 싸피 수업에서 3과목을 조금 배웠다. 4과목(프로그래밍 언어 활용): 파이썬은 2017년에 대학교 필수 교양에서 배웠고, 가끔 가끔 알고리즘 문제를 풀다가 싸피에 온 후부터 더 자주 다뤘다. C, C++은 잠깐 공부를 했지만 기억이 나지 않는다... => 이렇게 1, 3, 4단원은 배경지식이 있었다. 공부 과정 📖 1월에 신청해뒀던 정보처리기사 필기 시험! 정확한 날짜를 잊고 있다가 저..

🧡 시작하기 전 팀을 자유롭게 짜라고 해서, 팀을 어떻게 짤지 매우 걱정됐다.ㅠ 다행히 1학기 때 같이 스터디하던 다섯명이서 같이 팀을 하기로 했다. 다른 한 분도 잘 구해져서 팀을 빠르게 조직했다. (감사합니다!!) 그런데 내가 실력이 가장 부족한 것 같아서 걱정이 됐다. 혹시 나를 안 좋게 생각하거나, 실망하실까봐 ㅠㅠ 😃 좋았던 점 react, typescript를 공부하고 프로젝트에서 사용해볼 수 있었던 점이 좋았다. 혼자 할 때는 typescript + react로 하다가 타입 에러가 자꾸 많이 발생하니까 그냥 javascript로 바꾼 적도 있었는데.... 나는 react를 처음 써보는데 많이 써보신 분이 계셔서, 그분께 여쭤보고 그분 코드를 볼 수 있어서 좋았다. git을 가지고 협업할 수 ..

백준 500문제를 풀었다 ㅎㅎ 🌸 나의 PS story 🧡 그 기념으로 사학, 교육학을 공부한 내가 어떻게 문제 풀기를 시작했는지 적어보려고 한다~ 2017년 2학기에 필수 교양(컴퓨팅 사고력)으로 파이썬을 배웠다! 그때 매주 과제로 문제를 주시곤 했다. 백준으로 푸는 건 아니고, 풀어서 학교 사이트에 제출하는 것이었다. 별 찍기, 구구단 같은 문제들이었던 것 같다. 그때 마치 (수능) 수학 문제 푸는 것 같은 재미(고민하면서 몰입하면서 풀고, 맞으면 신난다 ~~)가 있었다. 한 동안 잊고 지내다가, 어느 방학이 왔다. 그 전까지는 방학에도 자격증 및 시험 준비, 알바 등으로 바쁘게 지내다가, 그 방학에는 '본격적인 취준(당시에는 대학원 or 임용고시를 생각) 전에 마지막으로 쉬자!'라는 결심을 했다. ..

문제 보러 가기! 풀이 🎊 모든 강연 요청을 (요금, 일자) 형식의 tuple로 이뤄진 리스트에 저장했다. 일자 -> 요금이 큰 순서대로 정렬했다. d일 안에 강연을 해야 한다는 것에 대해 생각해보자. d가 7이라면, 1일 안에 강연해도 되고 2일 안에 해도 되고 3일 안에 해도 되고 .... 7일 안에 강연해도 된다는 뜻이다. 만약 d가 1이라면 1일 안에 강연해야만 돈을 준다는 뜻이다. => 일자가 큰 순서대로 봐준다!! 일자가 큰 순서대로, 그 일자에 가능한 강연의 비용을 우선순위 큐에 넣는다. (같은 d로 요청한 강연이 여러 개라면 모두 넣는다) 그 후 각 일자마다 보면서, 그 일자에 강연을 한다고 했을 때 돈을 가장 많이 주는 강연을 한다. (우선순위 큐에서 heappop) 주의점 👻 heapq..

문제 보러가기! 풀이 🌷 지문이 웹툰 내용 같고 재미있었다 ㅋㅋ 핵심은 슬라임 에너지가 적은 슬라임을 두 개씩 합성하는 것이다!! 그걸 파악한 후에는 카드 정렬하기 문제와 비슷하게 풀었다. 카드 정렬하기 문제에서는 더하기라면, 이 문제에서는 곱하기라는 점 정도만 다른 것 같다. 아래와 같이 풀었다. 처음 슬라임을 리스트로 받은 후에 heapify하기 청구될 전기 에너지 초기값은 1로 시작하기(곱의 항등원은 1이므로) 힙의 길이가 2 이상일 동안은(즉, 슬라임이 두 개 이상일 때) 힙에서 슬라임 에너지가 적은 슬라임을 두 개 꺼낸다. 각각 슬라임 에너지가 A, B 라고 하자. 그 둘을 곱하면 슬라임 에너지가 AXB인 슬라임이 되고, 그걸 힙에 넣는다. 또 청구될 전기 에너지에 A X B한 값을 곱한다. 힙..

문제 보러 가기! 오랜만에 BFS를 풀어서 재미있었다~! 평범한 BFS 문제 + 빙판 부분이 특별했다. 먼저 늑대의 위치를 확인해서 리스트에 넣은 후에, 늑대 한 마리씩 확인했다. (늑대가 여럿 있을 수도 있음) 늑대가 방문할 수 있는 곳인지 방문 체크를 했다. (wolve_can_go 2차원 리스트) 빙판 부분은 while을 이용해서, 쭉~ 미끄러지듯 가줬다. 가고 있는 방향 쪽으로 한 칸 더 갔을 때(범위 확인 후) 빙판이면 한 번 더 가기 초원이라면 그만!(즉 늑대가 방문할 수 있다고 체크한 후, 큐에 넣었다.) 산이라면 그 이전 위치에서 멈추도록 했다. (멈춰서 다른 방향 갈 수 있기 때문이다! 처음에 이 부분을 안 처리해서 틀렸다. 그 이전 위치를 방문 체크한 후, 큐에 그 이전 위치를 넣았다...

문제 풀러 가기! 꼼꼼히 천천히 구현했다~ 사 방향을 일일이 코드로 짜서 좀 긴데ㅠ, 줄일 수 있을 것 같기도 하다. 🧐 헷갈렸던 부분 이미 넘어진 격자의 도미노를 공격수가 무너뜨리려고 할 때는 공격수 점수를 카운트 하면 안된다! x, y, d 는 map(int,input().split())으로 하면 안되는데 해서, 잠깐 에러를 만났다.. d는 숫자가 아니고 알파벳이다.. 다시 도미노를 쌓을 때는, 원래 가지고 있던 높이 만큼 쌓아줘야 하므로 그 높이를 origin_height에 copy.deepcopy를 이용해서 저장해뒀다. 👩‍💻 코드 import sys, collections, copy input = sys.stdin.readline N, M, R = map(int, input().split()) ..

문제!! 풀이 🌷 통나무의 세로로 입력으로 들어오지만 가로만 봐주면 된다. 선 긋는 스위핑 문제처럼 풀면 되는 것이었다. 그 문제 포스팅은 여기..ㅎㅎ 어려웠던 점 🦄 처음에는 통나무의 가로, 세로 좌표 둘 다 봐줘야 하는 줄 알았다.. 좌표는 10^9까지 있다고 하는데, 가로 세로를 고려해서 2차원으로 만들면 너무 클 것 같은데... ㅠ 어떻게 하나 고민했다. 그런데 가로!!!만 봐주면 되는 것이었다. 점프하면 되니까 세로는 볼 필요가 없었다. 원래 입력 받은 리스트를 정렬해서, 그 순서가 망가진다.. 그러니까 원래 인덱스를 가지고 있어야 한다! 그래야 어떤 통나무랑 다른 통나무랑 이어져있는지 체크가 가능하니까!!! 코드 🐸 import sys input = sys.stdin.readline N, Q ..