No Limitation

DFS를 연습할 때 중요한 것은 종료 조건 (leaf node)까지 다다랐을 때부터 점차적으로 값을 누적해주는 개념이 중요하다. 그것을 꼭 기억하자. 나 같은 경우는 DFS의 named parameter에서 정의를 해주고 leaf node에서부터 값을 가지고 이를 back tracking했을 때마다 해당된 값을 더해주는 식으로 구현하는 것이 익숙하다. 이는 MAP형태가 아니라 다음과 같은 유형에서도 반복될 수 있다. https://school.programmers.co.kr/learn/courses/30/lessons/43163?language=python3 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들..

적록색약 문제와 같이 비슷한 유형의 문제를 풀어보았다. https://www.acmicpc.net/problem/2667 2667번: 단지번호붙이기 과 같이 정사각형 모양의 지도가 있다. 1은 집이 있는 곳을, 0은 집이 없는 곳을 나타낸다. 철수는 이 지도를 가지고 연결된 집의 모임인 단지를 정의하고, 단지에 번호를 붙이려 한다. 여 www.acmicpc.net 다행이 문제는 빠른 시간 내에 풀었지만, 나는 set 별로 coloring을 해준 다음에 갯수를 count해서 그다지 갯수를 세는 데에 효율적인 코딩은 아니었던 거 같다. 처음 통과 코드 from collections import deque N = int(input()) maps = [ [int(x) for x in input()] for _ ..

상, 하, 좌, 우 등의 방문을 수행했을 때, 모든 반복을 마친 최종 경우의 수가 각각 cnt1, cnt2, cnt3, cnt4라고 할 때 이 때 최대의 경우의 수를 구하는 문제 유형들이 있다. 아래가 대표적인 유형이고 첫 번째 문제는 아래 쪽으로 내려갈 때 좌, 우 중 어느 곳이 더 최대인지 두 번째 문제의 경우 상, 하, 좌, 우 중 어느 곳이 더 최대인지 문제를 푸는 방법들이다. 이 것들을 잘 익혀서 문제에 써먹어보자. 유형이 비슷하니 꼭 반복숙달하기를 https://school.programmers.co.kr/learn/courses/30/lessons/43105?language=python3 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 ..

전에 풀었던 유형이지만 코테를 대비해서 체화하기 위해 문제를 다시 풀어보았다. 2X2 그리드로 주어지는 MAP 형태에서 DFS, DP를 사용하는 경우 보통 "~한 경우의 수"를 구하는 문제에서 주로 출제된다. 즉, count+=1를 종점에 도착했을 때마다 더해주어 이를 누적하는 식의 유형이다. 또한 memoization을 활용하여 방문한 그리드는 memo에 바로 return해주는 DP의 경우를 바로 사용하는 예제 또한 중요하다. 아래 두 문제가 대표 예시이다. 코드의 얼개를 기억하고 바로바로 구현할 수 있도록 체화하자. https://www.acmicpc.net/problem/1520 1520번: 내리막 길 여행을 떠난 세준이는 지도를 하나 구하였다. 이 지도는 아래 그림과 같이 직사각형 모양이며 여러 ..

계속 DFS로 푸는게 익숙해서 BFS가 너무 어렵다.. 익숙해지자! 화이팅! https://www.acmicpc.net/problem/10026 풀이는 아래 분 및 다양한 블로그 포스팅들을 참고 https://www.youtube.com/watch?v=xzOEbKqQQC4&t=314s https://www.youtube.com/watch?v=-daSs-maaVk 10026번: 적록색약 적록색약은 빨간색과 초록색의 차이를 거의 느끼지 못한다. 따라서, 적록색약인 사람이 보는 그림은 아닌 사람이 보는 그림과는 좀 다를 수 있다. 크기가 N×N인 그리드의 각 칸에 R(빨강), G(초록) www.acmicpc.net 이 문제에서 알아야 하는 아이디어 [1] 이 유형은 BFS의 기본 유형으로, 여느 유형처럼 노드..

DFS가 재귀를 죠지는 거라면 BFS는 그래프 및 최단 거리에서 알짜배기로 사용되는 테크닉 https://school.programmers.co.kr/learn/courses/30/lessons/1844/solution_groups?language=python3&type=my 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 이전 포스팅에도 참고했던 것처럼 유형이 비슷하다. 여기는 외우다시피 숙지를 해놓아야한다. https://yscho.tistory.com/68 [Graph, BFS] 벽 부수고 이동하기 - 백준 https://www.acmicpc.net/..

https://school.programmers.co.kr/learn/courses/30/lessons/42627?language=python3 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 오랜 기간 동안 문제를 잘 풀지 못해, 결국 블로그, 영상 등을 참고해 겨우 따라간 문제. 우선 강의는 아래 이 분 것을 참고하였음. https://www.youtube.com/watch?v=qA-wy00bQv4 문제를 보면, 가장 적은 대기 시간이 되도록 업무를 스케줄링 하는것을 의미한다. 나는 이게 바로 heap으로 푸는 건지 긴가민가 했는데, "소요 시간"을 기..

https://www.acmicpc.net/problem/18258 18258번: 큐 2 첫째 줄에 주어지는 명령의 수 N (1 ≤ N ≤ 2,000,000)이 주어진다. 둘째 줄부터 N개의 줄에는 명령이 하나씩 주어진다. 주어지는 정수는 1보다 크거나 같고, 100,000보다 작거나 같다. 문제에 나와있지 www.acmicpc.net import sys N = int(sys.stdin.readline()) from collections import deque queue = deque([]) for _ in range(N) : command = sys.stdin.readline().split() if command[0] == 'push' : queue.append(command[1]) elif comma..

https://www.acmicpc.net/problem/2908 2908번: 상수 상근이의 동생 상수는 수학을 정말 못한다. 상수는 숫자를 읽는데 문제가 있다. 이렇게 수학을 못하는 상수를 위해서 상근이는 수의 크기를 비교하는 문제를 내주었다. 상근이는 세 자리 수 두 www.acmicpc.net A, B = [x for x in input().split()] A = [k for k in A]; B = [k for k in B] A.reverse(); B.reverse() A = ''.join(A); B = ''.join(B) if int(A) > int(B) : print(int(A)) else : print(int(B)) https://www.acmicpc.net/problem/2675 2675번:..

정말 정신 없게, 2년이라는 시간이 폭풍처럼 지나갔다. 2년 동안 많이 성장하기도 했고 많이 깨지기도 했다. 졸업 연구를 현재 논문을 제출하여 리부탈을 기다리는 중이고 졸업 연구를 산업에 적용하는 연구를 현재 진행중이고 2월까지 논문을 제출할 예정이다. 어떻게 지나간 2년인지는 모르겠지만, 어쨌든 시간은 흘렀다. 정말 아무것도 아닌 내가 연구를 마무리할 수 있었던 것은 전적인 주님의 은혜였고 나와 함께하셨기 때문이었다. 다시 한번 하나님께 정말 정말 감사드립니다. 주님 이름이 높임 받으시길 원합니다. 석사 과정은 연구를 제대로 업으로 삼기 전에 살짝 맛보기(?)를 하는 단계인 것 같다. 2년 간에 스스로 논문을 써보면서 연구라는 것이 무엇인지를 배우는 단계랄까. 그래서 박사를 진학하기 전, 내가 학계에 ..