No Limitation

본격적으로 취준 전쟁에 뛰어든지 약 2달이 되어간다. 많은 기업에 원서를 냈고 감사하게도 2군데 면접, 3군데 코딩테스트를 치르고, 또 다른 서류 결과를 기다리고 있다. 정신 없게 면접과 시험을 보는 와중에 일전에 제출했던 저널에 revision 결과가 나왔다. 솔직히 Reject도 각오하고 낸 높은 저널이었는데 major revision이라도 온 것에 감사했다. 봄 바람이 불고 벚꽃이 여느 때와 같이 아름답게 피지만, 나는 안타깝게도 올해 역시 정신 없는 하루의 풍파 속에서 꽃의 향기를 누릴 여유가 없다. 아니 어쩌면 스스로 그럴 자격이 없다고 판단해서 미리 마음을 내려놓은 것인지도 모르겠다. 정말 가고 싶었던 기업의 면접을 조지고(?) 많은 서류 광탈과 코테 탈락의 향연에서, 또 자식 같이 소중한 논..

https://school.programmers.co.kr/learn/courses/30/lessons/86971 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr Union Find를 이용해 disjoint set을 찾아 노드의 수에 따른 차가 가장 큰 경우를 찾으면 되는 문제. 특별히 자체 구현 코드에서 마지막에 최종적으로 parents를 업데이트 하는 코드를 잊지 말자 def Find(v,parents) : if parents[v] != v : parents[v] = Find(parents[v],parents) return parents[v] def U..

https://www.acmicpc.net/problem/12904 12904번: A와 B 수빈이는 A와 B로만 이루어진 영어 단어가 존재한다는 사실에 놀랐다. 대표적인 예로 AB (Abdominal의 약자), BAA (양의 울음 소리), AA (용암의 종류), ABBA (스웨덴 팝 그룹)이 있다. 이런 사실에 놀란 수 www.acmicpc.net 아이디어를 공부하면 좋을 거 같은 문제 이 문제를 푸신 다른 분들 풀이가 좋아서 공부하면 좋을 듯 https://growth-coder.tistory.com/231 [백준 12904][파이썬][그리디] A와 B https://www.acmicpc.net/problem/12904 12904번: A와 B 수빈이는 A와 B로만 이루어진 영어 단어가 존재한다는 사실에..

https://school.programmers.co.kr/learn/courses/30/lessons/68645 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 이전에 풀었던 문제였는데, 다시 복습 차 시도 다시 풀어도 어려운 문제다.. 단순히 indexing으로 시도해보려고 했지만, 틀린 문제도 있었고 뒤에 유형에서는 시간초과가 발생. 처음 시도한 코드 def solution(n): triangle = [ [0]*i for i in range(1,n+1)] k = 0 triangle[0][0] = 1 cum = 2 ### 외곽 먼저 처리 for i in..

https://school.programmers.co.kr/learn/courses/30/lessons/87946?language=python3 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 본 문제는 완전 탐색 카테고리에 해당하는 문제. 사실 이 문제를 푸는 다른 방법이 생각나지 않아 일단 DFS로 구현해보았는데 당연히 시간 초과가 날 줄 알았음. 하지만, 막상 돌렸을 때는 통과가 됨. 나중에 찾아보니 대부분 비슷하게 푸신 듯. 다만 주의해야 하는 부분은, dfs를 돌아갈 때 마지막에 탐색하지 못하는 던전 케이스에 대해 return할 때는 count를 ..

https://school.programmers.co.kr/learn/courses/30/lessons/42628?language=python3 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 예전에 풀었던 이중우선순위 큐 문제 복습. 전에는 heapq._heapify_max() 라는 함수를 썼었는데 사실 이런 함수 말고 그냥 -1을 곱해주는 형태로도 max_heap은 쉽게 구현할 수 있다. 당연하지 사실 min_heap의 반대가 max_heap일 뿐이니까 level 3이지만 비교적 쉽게 구현할 수 있는 문제 import heapq as hp def sol..

https://www.acmicpc.net/problem/11725 11725번: 트리의 부모 찾기 루트 없는 트리가 주어진다. 이때, 트리의 루트를 1이라고 정했을 때, 각 노드의 부모를 구하는 프로그램을 작성하시오. www.acmicpc.net 기존에 Union Find의 rank 개념을 활용해서 문제를 풀었고 어지간한 반례를 다 풀었었는데 틀렸습니다가 나온다..ㅠㅠ 그래서 여기저기 공부하다 인접 노드를 활용해 BFS를 이용하여 탐색으로 푼 아래 블로그 분의 포스팅을 참고하였고 공부하는 겸 구현해보았다. https://velog.io/@dark6ro/%EB%B0%B1%EC%A4%80-11725%EB%B2%88-%ED%8A%B8%EB%A6%AC%EC%9D%98-%EB%B6%80%EB%AA%A8-%EC%..

아래 유형들은 최소 일자를 count하는 것이기 때문에 BFS를 수행할 때, 방문한 노드를 queue에 넣기 이전에 동일한 날짜에 시작하는 point부터 먼저 queue로 넣어야 한다. 추가로 현재 위치하는 counting이 같은 날짜이므로 이후 누적되는 날짜를 더해주어야하기 때문에 visited에 들어간 값에 +1을 해주며 날짜를 누적하는 방식으로 동작함을 기억하자. 대표 예재, 백준의 토마토 https://www.acmicpc.net/problem/7576 7576번: 토마토 첫 줄에는 상자의 크기를 나타내는 두 정수 M,N이 주어진다. M은 상자의 가로 칸의 수, N은 상자의 세로 칸의 수를 나타낸다. 단, 2 ≤ M,N ≤ 1,000 이다. 둘째 줄부터는 하나의 상자에 저장된 토마토 www.acm..

https://www.acmicpc.net/problem/2583 2583번: 영역 구하기 첫째 줄에 M과 N, 그리고 K가 빈칸을 사이에 두고 차례로 주어진다. M, N, K는 모두 100 이하의 자연수이다. 둘째 줄부터 K개의 줄에는 한 줄에 하나씩 직사각형의 왼쪽 아래 꼭짓점의 x, y좌표값과 오 www.acmicpc.net 전형적인 BFS 유형. 하지만 문제 상 "모눈 종이"의 눈금이라는 것이 x와 y축의 개념이 혼동이 될 수 있는 예제로 주의해야할 거 같다. 코테는 어떤 알고리즘이냐 파악도 중요하지만 못지 않게 국어 능력이 중요하다... 문제의 조건을 잘 파악해야 한다. from collections import deque M, N, K = [int(x) for x in input().split..

기억하자. 가중치가 없는 최단 경로는 무조건 BFS 가중치가 있는 경우 다익스트라 https://www.acmicpc.net/problem/1697 1697번: 숨바꼭질 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 www.acmicpc.net 여느 BFS 문제와 크게 다르지 않았음 from collections import deque N, K = [int(x) for x in input().split()] #M = max(N,K) ## 이걸로 하면 안되고 걍 100000 사용하자 visited = {i:0 for i in ran..