No Limitation

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..

코테에서 자주 나오는지는 모르겠지만 그래도 워낙에 유명한 알고리즘이다보니 공부하면 좋을 듯 일반적으로 최소 경로를 구하는 경우 모든 Edge의 가중치가 같으면 일반적인 BFS로 풀면 되지만 가중치가 다른 경우는 가장 최소 가중치 기준으로 방문을 수행하는 그리디 알고리즘이 필요하기 때문에 다익스트라가 요구된다. 여기서 다익스트라를 구현하는 많은 방법이 있지만 개인적으로 가장 파이썬에서 구현이 간단한 Heap을 사용한 방법을 익혀 코테에 써먹어보자. 예전에 자료구조 수업을 들을 때 얼핏 정리했던 코드를 가져와보았다. 주로 이중 배열을 사용해서 구현을 하던데 나는 dictionary 형태로 배우다보니 그냥 지금도 이 폼을 사용한다. import heapq graph = { 'A' : {'B':8, 'C':1,..

SQL 코테 시 주의해야 하는 유형들 1. WHERE 다중 조건문 수행 시 https://www.hackerrank.com/challenges/what-type-of-triangle/problem Type of Triangle | HackerRank Query a triangle's type based on its side lengths. www.hackerrank.com 위 문제에서 중요한 특징은 "이전 WHERE 조건에서 필터된 경우 다음 WHERE 조건에는 반영되지 않는다"는 점. 예를 들어 아래 코드를 보면 SELECT CASE -- 정삼각형 조건 WHEN A=B AND B=C THEN 'Equilateral' -- 삼각형 여부 판단 -- 정삼각형은 무조건 삼각형이 성립, 하지만 이등변의 경우 삼..

https://school.programmers.co.kr/learn/courses/30/lessons/84512?language=python3 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 본 문제는 아래와 같이 접근을 시도하였다. 사진에서 보이는 것처럼 A AA AAA AAAA AAAAA -- 종점 도착 AAAAE 이렇게 쭉 종점까지 선회하는 방법으로 searching하기 때문에 깊이 우선 탐색 전략을 채택한다. 이렇게 종점에 도착해도 여전히 사전의 순서는 진행되어야 하므로 이를 나타내는 변수 cnt는 누적이 되어야 한다. 따라서 global 변수를 ..

https://school.programmers.co.kr/learn/courses/30/lessons/42842?language=python3 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 완전 탐색 카테고리라고 하지만.. 사실 전에 1+2+3더하기 문제처럼 규칙성을 찾는 문제라고 생각하였다. 우선 본 문제에서 중요한 관점은 3가지 포인트라고 생각하였다. 1. 가로, 세로의 값의 설정에 따라 직사각형 모양이 다를 수 있음 2. Boundary를 감싸고 있는 수의 규칙성을 찾아보기 3. 가로, 세로의 길이를 구하는 규칙성을 찾아보기 먼저 1번에 나온 내용..