Heecheol's blog

문제 https://www.acmicpc.net/problem/11055 11055번: 가장 큰 증가하는 부분 수열 수열 A가 주어졌을 때, 그 수열의 증가하는 부분 수열 중에서 합이 가장 큰 것을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {1, 100, 2, 50, 60, 3, 5, 6, 7, 8} 인 경우에 합이 가장 큰 증가하는 www.acmicpc.net 풀이 result[k] 는 numbers의 k번째 원소까지 증가하는 부분수열의 합을 나타냄. 즉, numbers[j]가 numbers[i]보다 작다는 것은 result[j]에 numbers[i]를 더할 수 있다는 얘기임. 이렇게 구하며 max값으로 result[i]로 바꿔주면 가장 큰 값으로 result[i]의 값이 정해짐. 마지막..

문제 https://www.acmicpc.net/problem/1759 1759번: 암호 만들기 첫째 줄에 두 정수 L, C가 주어진다. (3 ≤ L ≤ C ≤ 15) 다음 줄에는 C개의 문자들이 공백으로 구분되어 주어진다. 주어지는 문자들은 알파벳 소문자이며, 중복되는 것은 없다. www.acmicpc.net 풀이 간단한 백트래킹 문제였다. 모든 경우를 찾아준 뒤에 암호의 길이와 동일한 배열이 완성되면, 조건을 만족하는지 확인해주었다. 나는 아래처럼 해결했지만 자음을 굳이 선언하지 않고 vowel에 포함되는지 확인하여 자음과 모음을 분리할 수 있을 것이다. 이렇게하면 메모리를 조금이나마 줄일 수 있을 것 같다. import Foundation let input = readLine()!.split(sep..

문제 https://school.programmers.co.kr/learn/courses/30/lessons/92342 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 풀이 이 문제를 풀어보면서 정말 많이 모자라다고 느꼈음. 모든 경우의 수를 구할 때 점수를 얻었을 때와 못얻었을때로 나눠서 생각했어야했는데 처음엔 못했었음. 아무튼 이 문제는 dfs를 이용해서 해결했는데, 라이언이 이길 수 있는 모든 경우의 수를 구한 뒤에 가장 큰 점수차를 갖는 것 중에서 낮은 점수를 맞춘 화살 수가 더 많은 것을 리턴해주었음. 우선 처음에 apeach라는 변수에 라이언이 ..

문제 https://school.programmers.co.kr/learn/courses/30/lessons/118667 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 풀이 swift에는 Queue 자료구조가 없고, 이용하기 위해서는 직접 만들어야한다. 두 개의 배열을 이용해서 구현할 수도 있지만, 나는 큐에서 원소를 제거하지않고 포인터와 append만을 이용하였다. 일단 원소의 합이 더 큰 큐에서 원소를 옮겨야한다는 것은 당연하다. 그래서 합이 더 큰 큐의 앞 원소를 다른 큐에 append해주어야한다. 예를 들어, 첫 번째 큐에서 두 번째 큐로 원소를 ..

문제 https://school.programmers.co.kr/learn/courses/30/lessons/150365 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 풀이 처음에 BFS로 풀었는데 시간초과가 나왔다. 이 문제에서는 사전순으로 가장 빠른 경로를 출력해야한다. 그렇기때문에 BFS로 푼다면 가장 빠른 d를 우선으로 탐색하는 것이 아닌, d r l u 골고루 탐색하게되어 불필요한 연산을 하게된다. 그래서 이 문제는 DFS로 풀어야한다. 기존에 BFS를 이용할때는 queue를 이용하여 removeFirst()로 앞에것부터 빼주면서 돌렸었다. 하지..