배움엔 끝이없다/알고리즘(12)
-
코딩테스트 스터디 - 백준 2186번 : 문자판 (python)
문제 링크 : https://www.acmicpc.net/problem/2186 2186번: 문자판 첫째 줄에 N(1 ≤ N ≤ 100), M(1 ≤ M ≤ 100), K(1 ≤ K ≤ 5)가 주어진다. 다음 N개의 줄에는 M개의 알파벳 대문자가 주어지는데, 이는 N×M 크기의 문자판을 나타낸다. 다음 줄에는 1자 이상 80자 이하의 www.acmicpc.net 요약 N*M크기의 문자판이 있다. 이 문자칸의 어떤 칸에서 한번에 십자방향으로 K칸까지 움직일 수 있다. 특정 단어를 만들 수 있는 경로의 경우의 수를 구하는 문제다. 의식의 흐름 처음에는 DFS를 떠올렸다. 예를들어 단어가 BREAK면, 맵에서 B를 찾아 거기서부터 K칸이내로 REAK를 찾고, R을 찾았으면 거기서부터 K칸 이내로 EAK를 찾고..
2023.01.25 -
코딩테스트 스터디 - 프로그래머스 거스름돈 (python)
문제 링크 : https://school.programmers.co.kr/learn/courses/30/lessons/12907 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 요약 사용 가능한 동전의 종류와 지불해야할 거스름돈의 액수가 주어지면, 동전들을 활용해 액수를 맞출 수 있는 경우의수를 1,000,000,007로 나눈 수를 반환한다. 의식의 흐름 경우의 수 문제는(게다가 숫자가 커질 수 있으니 나머지를 출력하라고하면) DP를 가장 먼저 생각하게된다. table[i] = i원을 만들 수 있는 경우의 수라 하면, table[0]=1이다. 간단하게 생각..
2023.01.20 -
코딩테스트 스터디 - 백준 14891번: 톱니바퀴 (python)
문제 링크 : https://www.acmicpc.net/problem/14891 14891번: 톱니바퀴 총 8개의 톱니를 가지고 있는 톱니바퀴 4개가 아래 그림과 같이 일렬로 놓여져 있다. 또, 톱니는 N극 또는 S극 중 하나를 나타내고 있다. 톱니바퀴에는 번호가 매겨져 있는데, 가장 왼쪽 톱니바퀴 www.acmicpc.net 요약 8개의 이빨은 가진 톱니바퀴 4개가 가로로 연결돼있다. 어떤 톱니바퀴 A를 움직이면, 연결된 B 톱니바퀴는 A와 B가 맞닿아있는 이빨의 극이 달라야 움직인다. 극이 같으면 움직이지 않으며, B와 연결된 다른 톱니도 움직이지 않는다. 톱니바퀴를 움직이는 행동을 K번 한 후 톱니바퀴들의 상태를 알아내면 된다. 의식의 흐름 우선 뭔가 최적값을 찾는 탐색 문제가 아니기 때문에 그냥..
2023.01.12 -
코딩테스트 스터디 - 프로그래머스 테이블 해시 함수(python)
문제 링크 : https://school.programmers.co.kr/learn/courses/30/lessons/147354 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 요약 한 테이블에 대한 해시 함수를 작성한다. 해시 함수는 col, row_begin, row_end를 받으며, 1. col 번째 컬럼을 오름차순으로 (같을 시 0번째 컬럼을 내림차순으로) 정렬하고, 2. row_begin ~ row_end의 각 행의 모든 컬럼에 대해 i번째 컬럼 갑을 i로 나눈 나머지의 합을 구하고, 3. 그 합들을 전부 XOR 한 값을 반환한다. 의식의 흐름 ..
2023.01.11 -
코딩테스트 스터디 - 프로그래머스 양궁대회 (python)
문제 링크 : https://school.programmers.co.kr/learn/courses/30/lessons/92342 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 요약 어피치와 라이언(나)이 양궁게임을 한다. 이 양궁게임에는 과녁이 0~10점까지 있으며, 각 점수에 더 많이 쏜 사람이 해당 점수를 가져간다. 같은 수 만큼 쏘면 어피치가 점수를 가져가며, 둘 다 0개를 쏜 경우 아무도 점수를 얻지 않는다. 이렇게 점수 합산을 해 내가 최대 점수 차이로 이길 수 있는 방법을 반환해야한다. 같은 점수차이가 있다면 가장 낮은 점수 화살이 많은 쪽을 ..
2023.01.09 -
코딩테스트 스터디 - 백준 19236번: 청소년 상어 (python)
문제 링크 : https://www.acmicpc.net/problem/19236 19236번: 청소년 상어 첫째 줄부터 4개의 줄에 각 칸의 들어있는 물고기의 정보가 1번 행부터 순서대로 주어진다. 물고기의 정보는 두 정수 ai, bi로 이루어져 있고, ai는 물고기의 번호, bi는 방향을 의미한다. 방향 bi는 www.acmicpc.net 요약 4*4 판에 1~16으로 번호가 매겨진 물고기들이 있고, 각 물고기는 8방향 중 1가지 방향을 갖는다. 상어는 0,0에서 시작하며 아래를 반복한다. 1. 상어 위치에 있는 물고기를 잡아먹는다. 2. 1번 물고기부터 순서대로 모든 물고기들이 자신의 방향대로 움직인다. 2-1. 상어나 벽에 의해 막혀있을 경우 반시계 방향으로 45도 회전한다. 2-2. 다른 물고기..
2023.01.07