Dalin's Archive

문제 보러 가기! TMI 내 기억 상 처음으로 푸는 영어 문제이다. 풀이 🦄 문제 이해를 돕기 위한 설명용 그림..ㅎㅎ 처음에 1번 섬에서 무조건 시작하고, 그 병력을 가지고 시작한다. 지배한 섬과 이어진 섬은 공격 후보가 된다. 이어진 섬의 병력이 우리(spanning nation) 병력보다 적을 때만!! 그 섬을 지배한다. 우선순위 큐를 활용하면 된다. 우선순위 큐, q에 공격할 수 있는 후보들(섬)을 집어 넣었다. 인접 리스트로 섬들의 연결 관계를 저장한다. 각 섬의 병력을 island_army 리스트에 저장한다. 각 섬을 공격할 수 있는 후보(q)에 넣었는지 여부를 저장하는 visited 리스트를 만든다. 1번 섬에서 시작한다. 우리 병력(spanning_army_cnt)를 1번 섬의 병력으로 업..

문제 보러 가기! 내 근황 (TMI..) 꺄~ 싸피 공통 PJT를 잘 마무리하고 돌아왔다 ~~!! 마지막 열흘 정도는 PJT에 집중하느라고 PS를 못하다가 오랜만에 문제를 풀었다 !! 내가 좋아하는 heapq를 이용하면 되는 문제였다. 설명 카드 묶음 여러 개가 있는데, 두 묶음씩 골라서 합쳐나간다. 합칠 때는 그 두 묶음의 개수만큼 비교를 해야 한다. 최소 몇 번의 비교가 필요한가? -> 적은 것부터 합치는 게 좋다 !!라는 걸 파악하고 heapq를 사용하면 됐다. 비교 개수를 담을 변수인 cnt를 0으로 초기화하고 시작했다. q에 숫자 카드 묶음 각각의 크기를 넣었다. heapify를 이용해서 q를 우선순위 큐로 만들어줬다. 그리고 q의 크기가 1이 될 때까지, 가장 적은 것 두 개씩을 더해서 다시 ..

문제 보러 가기! 간단 소감 오랜만에 dfs 문제를 풀어서 재밌었다 ㅎㅎ 그리고 visited 아이디어를 생각하는 것도 특이하고 재밌었다~~ 문제 설명 로봇이 4방향(동서남북) 중 한 방향으로 N번 이동한다. 각 방향으로 이동할 확률을 준다. 같은 곳을 또 방문하면 이동 경로가 단순하지 않다고 한다. 로봇의 이동 경로가 단순할 확률을 구하는 문제였다. 풀이 로봇이 4방향으로 N번 이동하고, N이 14보다 작다고 해서 딱 순열! 이 생각났다. DFS로 각 방향을 가봤다. dfs를 할 때 가지고 다니는 변수는 지금까지 몇 번 이동했는지, 현재 인덱스, 현재 위치까지 이동할 확률. 그런데 로봇이 단순하지 않은 경로로 이동할 경우, 더이상 볼 필요 없이 리턴해주면 되니까 백트래킹이라고도 할 수 있겠다. visi..

요즘 싸피 프로젝트에 집중하고 있다.. 그러다보니 PS, CS 공부를 별로 못했다 ㅠㅠ 지난 한 달 간은 일주일에 알고리즘 문제를 1~2문제 풀었고, CS 공부도 못했다..ㅠ 그런데 이러다 보면 앞으로도 계속 못할 것 같다..ㅠㅠ 계속 pjt, 취업 준비로 바쁠 테니... ㅠㅠㅠ 해야 한다는 생각만 하고 CS, PS를 못(안) 하고 있었다.. https://blog.shiren.dev/2020-09-07/ 하루 25분 실행하기: 하루를 대하는 14년차 개발자의 자세 code for life, life for music blog.shiren.dev 그러다 이 글을 추천해주셔서 읽었는데, 많이 와닿는 것 같다! 나도 '하루에 한 시간씩은 PS, CS 해야지!' 하고 큰 목표를 잡았는데, 그러다 보니 '2시간..

문제 보러 가기! 모든 지점에서 모든 지점까지 가는 최소 비용(최단 경로)을 구해야 하므로 플로이드 와샬 알고리즘을 썼다. 일반적인 플로이드 와샬과 다르게, 최소 비용 자체가 정답이 아니라, 최소 비용이 되기 위해서는 어디를 가장 먼저 방문해야 할지를 구하는 문제였다. 그래서 이동할 때 드는 최소 비용을 저장한 2차원 리스트에 더해서, 최소 비용이 되려면 어디를 가장 먼저 방문해야 하는지 저장하는 2차원 리스트(move)도 만들었다. 그리고 플로이드 와샬 알고리즘을 사용하면서, i 에서 j 지점으로 가는데 k를 들러서 가는 게 최소 비용이라면 ! 비용을 갱신하면서, 가장 먼저 방문할 지점도 업데이트해줬다. 틀렸던 이유 양방향인데 단방향으로 생각해서 ㅠ 자기 자신으로 갈 때 처음 방문할 지점을 '-..

IPC.. 지난 번에 스터디에서 내가 프로세스와 스레드라는 주제로 발표를 했다. 그때 (같은 프로세스 안의) 스레드끼리는 자원을 공유해서 통신하기 쉬운데, 프로세스끼리는 자원을 공유하지 않아서 통신하려면 특별한 방법이 필요하다고 했다. "그 방법이 IPC인데, 제가 나중에 발표할게요." 라고 했다가 몇 주만에 발표했다. IPC(Inter Process Communication) 프로세스 간 통신 프로세스들 사이에 서로 데이터를 주고 받는 행위, 그에 대한 방법이나 경로 (-위키백과-) 같은 컴퓨터 내의 프로세스 간 통신, 다른 컴퓨터의 프로세스 간 통신(나는 같은 컴퓨터 내 프로세스 간 통신만 생각했었당..) 커널이 IPC 통신하는 방법을 제공 종류 파이프(PIPE) 통신을 위한 메모리 공간(버퍼)를 생..

문제 보러 가기! DP문제 !! 입력이 특이한 것 같다..- 여러 줄에 걸쳐서 N개의 정수가 주어지는 부분, 테스트케이스가 몇 개인지 안 알려주고 맨 끝에 0이 오는 부분. try, except를 이용해서 편하게 테스트케이스 수만큼 동작하게 했다. 여러 줄에 걸쳐서 N개 정수가 주어지는 부분을 위해서, 리스트로 받고 개수를 세다가 N개가 되면 그만 받게 했다. dp table을 2차원으로 만들었다. 세로: 몇 번째 이동한 것인지 가로: 해당 위치 값: 최대로 얻는 수익!! (예- 1번째로 이동해서 1번째 칸에 도달했을 때 얻는 최대 수익) 세로 첫 줄은 채우고 시작한다. (1~S만큼 이동할 수 있으니까 그만큼만 채우기) 그 다음 세로 줄들을 돌면서, 가로를 채운다. 이런 식으로 된다..! 그 가로까지 올..

문제 보러 가기! 처음 풀이- 시간 초과 🎇 가방 많이 넣을 수 있는 것부터 하나씩 보면서, 보석을 가격 비싼 순(가격 같으면 무거운 순)으로 봤다. 그 가방에 보석을 넣을 수 있으면, 보석 없애고 가방도 없애고.. 그 가격을 정답에 더했다. 그 가방에 그 보석을 못 넣으면 그냥 보석을 없앴다. (어차피 이후 가방에도 그 보석이 무거워서 못 넣으니까) 예제는 맞기는 한데,, 그랬더니 시간 초과 ㅠ 코드는 이랬다. import sys, heapq input= sys.stdin.readline N,K = map(int,input().split()) jewelries = [] backpacks = [] for _ in range(N): m, v = map(int,input().split()) jewelries..

문제 보러 가기! NXN의 표에 수가 채워져있고, 모든 수는 자기 한 칸 위의 수보다 크다. N번째 큰 수를 찾는 문제이다. (N은 1~1500이다.) 처음 - 메모리 초과 처음에는 extend를 이용해서 1차원 리스트로 N^2개의 값을 다 받았다. 이 문제에서 N번째로 '큰!!" 수를 찾아야 하므로 최대 우선순위 큐로 쓰려고 했다. 그래서 -1을 곱해서 넣어줬다. 그 후, 그 리스트를 우선순위 큐로 만들었다. heapq.heappop을 N번해서 N번째값을 출력했다. -1를 곱해서 넣어줬으니까, 출력할 때 -1을 곱한 후에 출력했다. 예제는 맞는데, 메모리 초과가 나왔다.. 1500 X 1500 = 2250000 개를 리스트로 만들고 힙으로 만드는 게 너무 힘든가.. import sys, heapq in..

문제를 풀다가 에러를 만났다. valid를 분명히 정의했는데, 변수가 정의 되지 않았다고.. (NameError: name 'valid' is not defined') 'valid가 예약어인가..? 쓰면 안되나?' 싶어서 'isValid'로 바꿔서 하니까 잘됐다. 그리고 나서 valid가 예약어인지 찾아봤는데 전혀 아니었다. 그래서 다시 valid로 바꾸니 잘 됐다.. 다시 보니 오타였다 !!ㅎㅎ valid & vaild ! 위에 sync 함수 안에서는 valid라고 썼고, 아래에서는 vaild라고 썼다.