시나위

1103번: 게임 줄에 보드의 세로 크기 N과 가로 크기 M이 주어진다. 이 값은 모두 50보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에 보드의 상태가 주어진다. 쓰여 있는 숫자는 1부터 9까지의 자연수 또는 www.acmicpc.net 문제 요약 동전이 보드 위에서 움직일 수 있는 최대횟수 구하기 접근 1. 생각의 흐름 1 - BFS 보드가 이차원이고 모든 방향을 탐색하면서 최대로 움직이는 횟수를 파악해야하므로 그래프 탐색중 BFS를 사용해야할 것 같았다. BFS는 특정 지점까지의 최소 거리를 구할 때 사용하는데 이 경우에서도 충분히 사용할수 있을 거라고 생각했다. (멈추는 지점까지의 최소 거리를 구하면 최대로 움직인 거리를 구하는 거랑 같을 거니까) 간단하게 적어보면 다음과 같다. (0,0)..

2580번: 스도쿠 스도쿠는 18세기 스위스 수학자가 만든 '라틴 사각형'이랑 퍼즐에서 유래한 것으로 현재 많은 인기를 누리고 있다. 이 게임은 아래 그림과 같이 가로, 세로 각각 9개씩 총 81개의 작은 칸으로 이루 www.acmicpc.net 문제 요약 스도쿠 정답을 찾으면된다. 행과 열, 3X3 안에 1~9가 중복없이 들어가야한다. 접근 1. Brute-force 숫자를 넣어야하는 자리수는 최대 81개이고 1부터 9까지 모든 값을 넣어서 확인하려면 981 이 된다. O(232) 는 대충 42초 정도 걸리는데 이 값보다 크므로 이 방법으로 풀수 없다. 물론 0인 위치에서만 확인하면 되지만 찾아야하는 위치가 9개 이상이면 3초가 넘으므로 입력값을 알지 못하면 풀수 없다. 2. Backtracking 백..

프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 문제 요약 손님들이 주문한 단품 메뉴로 코스요리(조합)를 만든다. 코스 요리는 단품 두개 이 상으로 이루어져있다. 코스 요리의 길이(단품 메뉴의 개수)를 보고 그 중에 가장 많이 선택된 조합을 반환한다. 접근 모든 손님들이 주문한 단품 메뉴로 모든 조합을 만들어야한다. 조합을 만들 때 반복문, 라이브러리, 백트래킹으로 구현할수 있다. 1. 조합만들기 - 반복문 반복문을 중첩해서 사용하면 쉽게 조합을 만들수 있다. 예를 들면 ABCDE에서 3개의 원소를 가지는 조합을 만들기 위해선 다음과 같이 짜면 된다. st..

2641번: 다각형그리기 모눈종이에 다각형을 그리려고 한다. 그리는 방법은 모양수열로 표시된다. 모양수열은 1과 4사이의 숫자가 연속되어 나열된 것으로 1은 오른쪽으로, 2는 위쪽으로, 3은 왼쪽으로, 4는 아래쪽으로 www.acmicpc.net 문제 요약 처음 주어지는 모양수열로 만들어진 도형과 같은 도형이 나오는 수열을 찾는 문제이다. 모양수열은 방향을 가리키는 숫자 (1: 우, 2: 상, 3: 좌, 4: 하)로 이루어진 수열이다. 회전이나 뒤집었을때 같은 도형은 다른 것으로 생각한다. 접근 1. 쉬운 도형을 직접 그려서 규칙 확인 크기가 1인 정사각형의 모양수열을 확인했다. 좌측 상위의 점을 시작점으로 잡았을 때 시계방향으로 도는 모양수열은 1-4-3-2가 된다. 같은 시작점이고 반시계방향인 모양수..

1149번: RGB거리 첫째 줄에 집의 수 N(2 ≤ N ≤ 1,000)이 주어진다. 둘째 줄부터 N개의 줄에는 각 집을 빨강, 초록, 파랑으로 칠하는 비용이 1번 집부터 한 줄에 하나씩 주어진다. 집을 칠하는 비용은 1,000보다 작거나 www.acmicpc.net 알고리즘 스터디의 첫 문제이다. 이 문제의 알고리즘은 Dynamic Programming 이다. 이웃하는 집의 색이 같지 않게 하면서 모든 집을 칠해야하고, 이 때의 최소 비용을 구해야한다. 제일 처음 생각했던 건 Greedy 방식이다. 매순간 마다 최소 비용을 선택하되 이웃하는 집의 색이 같지 않게 칠하면 된다. 3 1 100 100 100 100 100 1 100 100 위와 같은 입력에서 입력이 1번 집은 최소 비용이 1인 빨강을 선택..

https://leetcode.com/problems/lowest-common-ancestor-of-a-binary-search-tree/submissions/ Lowest Common Ancestor of a Binary Search Tree - LeetCode Level up your coding skills and quickly land a job. This is the best place to expand your knowledge and get prepared for your next interview. leetcode.com 이진 탐색 트리에서 가장 가까운 공통 조상을 찾는 문제이다. 알고리즘 순서는 다음과 같다. 1. 주어진 root를 시작으로 BFS를 진행한다. 1-1. 이 때 unorde..

https://programmers.co.kr/learn/courses/30/lessons/1835 코딩테스트 연습 - 단체사진 찍기 단체사진 찍기 가을을 맞아 카카오프렌즈는 단체로 소풍을 떠났다. 즐거운 시간을 보내고 마지막에 단체사진을 찍기 위해 카메라 앞에 일렬로 나란히 섰다. 그런데 각자가 원하는 배치가 모두 programmers.co.kr 꽤 오래 걸린 문제이다. 우선 어떻게 풀어야할지 감이 안왔다. 처음 문제를 봤을때 순열을 구하는 공식을 사용해서 만들어야하나 고민했다. 하지만 level 2에서 그런 문제가 나올리가 없다고 생각해서 다른 방법을 생각했다. 물론 공식을 사용해서 풀수만 있으면 훨씬 빠르게 끝낼수 있었겠지만 범위가 있어서 공식은 아니라고 판단헀다. 오랫동안 고민했는데 도저히 떠오..

https://www.acmicpc.net/problem/21608 21608번: 상어 초등학교 상어 초등학교에는 교실이 하나 있고, 교실은 N×N 크기의 격자로 나타낼 수 있다. 학교에 다니는 학생의 수는 N2명이다. 오늘은 모든 학생의 자리를 정하는 날이다. 학생은 1번부터 N2번까지 번호 www.acmicpc.net 구현문제여서 알고리즘 설명은 스킵. #include #include using namespace std; typedef struct Seat { int num; // student number int adj[4]; // u l r d int adj_student; // number of adjacent student } SEAT; SEAT arr[20][20]; int like[401]..

https://www.acmicpc.net/problem/17281 17281번: ⚾ ⚾는 9명으로 이루어진 두 팀이 공격과 수비를 번갈아 하는 게임이다. 하나의 이닝은 공격과 수비로 이루어져 있고, 총 N이닝 동안 게임을 진행해야 한다. 한 이닝에 3아웃이 발생하면 이닝이 종 www.acmicpc.net 브루트포스 문제이고 시뮬레이션 방식으로 풀었다. 알고리즘은 다음과 같다. 1. 입력 vector에 array를 추가하는 방식으로 이닝별 선수들의 행동을 저장했다. 2. 브루트포스 2-1. 1~9까지 순열 구하기(permutation) 2-2. 구한 순열로 시뮬레이션해서 점수 구하기 2-3. 최대 점수 갱신 1부터 9까지 숫자를 가지고 있는 배열(players_order)을 선언하고 algorithm 헤..

SW Expert Academy 5658. [모의 SW 역량테스트] 보물상자 비밀번호 SW Expert Academy SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요! swexpertacademy.com 삼성 기출을 대비한 문제. 문자열을 사용하는 문제이고 쉬운 문제이다. 문자열을 회전시켜가며 k번째 큰 수를 출력하면된다. 문자열을 회전시킬때 조금 쉽게 하기위해 받은 문자열의 맨 처음글자부터 N//4까지의 글자를 복사해서 뒤에 넣어주었고 반복문을 사용해서 특정 길이까지 잘라서 set에 넣어주었다. set은 중복값이 제거되므로 넣어주기만 하면 된다. 모든 문자열을 순회한 이후엔 정렬을 한뒤 찾는 자리의 값을 반환했다. def find_number(string, string_size..