No Limitation

코테에서 자주 나오는지는 모르겠지만 그래도 워낙에 유명한 알고리즘이다보니 공부하면 좋을 듯 일반적으로 최소 경로를 구하는 경우 모든 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번에 나온 내용..

많이 나올 거 같은 점화식 유형 https://www.acmicpc.net/problem/9095 9095번: 1, 2, 3 더하기 각 테스트 케이스마다, n을 1, 2, 3의 합으로 나타내는 방법의 수를 출력한다. www.acmicpc.net def DFS(n) : if n == 1 : return 1 if n == 2 : return 2 if n == 3 : return 4 return DFS(n-1)+DFS(n-2)+DFS(n-3) N= int(input()) for _ in range(N) : num = int(input()) print(DFS(num)) 문자열과 수를 이용한 완전 탐색을 사용한 단순한 구현 문제 https://www.acmicpc.net/problem/1065 1065번: 한수 ..

순열, 조합과 같은 유형들에 익숙하지 않아서 공부가 많이 필요할 듯. 아래 포스팅에서 이와 관련된 유형을 정리해주셨는데 참고하면 좋을 듯 https://5myohan.tistory.com/88 [삼성SW테스트 준비] 순열과 조합 연습 문제-1 (백준 15649, 15654, 15655, 15657, 15663, 15664, 15665, 15666) 문제 출처: 알파카고수님(https://m.blog.naver.com/wpghks7/221585604878)의 블로그 [파이썬으로 시작하는 삼성 SW역량테스트] - 4. 순열과 조합 ※실제 시험 시itertools 모듈이 사용 불가능하다는 말이 있습니 5myohan.tistory.com 우선 대표 유형으로 아래 문제를 가져왔고 아래 문제는 "순열"로 푸는 문제..

https://www.acmicpc.net/problem/4963 4963번: 섬의 개수 입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스의 첫째 줄에는 지도의 너비 w와 높이 h가 주어진다. w와 h는 50보다 작거나 같은 양의 정수이다. 둘째 줄부터 h개 줄에는 지도 www.acmicpc.net 계속해서 반복하자. BFS 연습 여긴 특별히 대각선까지 포함한 유형이었음 from collections import deque while True : N, M = [int(x) for x in input().split()] if (N,M) == (0,0): break maps = [ [int(x) for x in input().split()] for _ in range(M)] move_x =..

난 완전 탐색이 왤케 어려운 것인가... 아래 기초 유형은 외우는 식으로도 해도 될거 같아서 가져옴 단순한 구현 연습들도 level 1~2이나 백준의 기초 유형들을 풀어가면서 익숙해져야겠다.. 코테 현장에서는 잘 안될 수 있으므로! 아래 문제는 생각보다 어려웠던 문제였다. 아마 내가 글을 잘 못 이해했을 수도 있다. https://school.programmers.co.kr/learn/courses/30/lessons/86491?language=python3 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 그래서 위 글을 참고했는데 https://codin..

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